感觉贪心算法本质上也都是技巧和思路，需要脑子，和技巧栏目放一起。

买卖股票的最佳时机

有点类似DP。迭代每天的价格，更新当前遇到的最小价格和当前能得到的最大利润，最大利润就是p = Math.max(p, 今天价格-历史最小价格) 因为本题只能买一次，所以最大的利润肯定是出现在 过去 最小买入的时候。

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE;
        int profit = 0;
        for (int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

跳跃游戏

也是思路题，直接看注释即可。

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for(int i = 0; i < nums.length; i++){
            // 如果当前能到的最大值 都到不了i了 直接return false
            if(reach < i) return false;
            // 能到达的最大值 要么是先前能到达的 要么就是当前下标+能跳的最远的
            reach = Math.max(reach, i+nums[i]);
        }
        return true;
    }
}

跳跃游戏2

class Solution {
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}

划分字母区间

读懂题意，要求划分最多片字母区间出来，即需要保证片尽可能小，且每一片的字母不重复。

显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] Last = new int[26];
        // 对于每个字母 找出最远的下标 即拿到最小的片段
        for(int i = 0; i < s.length(); i++){
            Last[s.charAt(i) - 'a'] = i;
        }
        // 每个片段用start和end区分开
        int start = 0;
        int end = 0;
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < s.length(); i++){
            // 更新每个片段的end 如果i=end了 说明这个片段到头了
            end = Math.max(end, Last[s.charAt(i) - 'a']);
            if(end == i){
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
}

只出现一次的数字

位运算

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int num: nums){
            res ^= num;
        }
        return res;
    }
}

补充Java的其他位运算方法。

public class BitOperations {
    public static void main(String[] args) {
        int a = 5;  // 二进制: 0101
        int b = 3;  // 二进制: 0011
        // 按位与 &
        System.out.println("a & b = " + (a & b));  // 0101 & 0011 = 0001 -> 1
        // 按位或 |
        System.out.println("a | b = " + (a | b));  // 0101 | 0011 = 0111 -> 7
        // 按位异或 ^
        System.out.println("a ^ b = " + (a ^ b));  // 0101 ^ 0011 = 0110 -> 6
        // 按位取反 ~
        System.out.println("~a = " + (~a));  // ~0101 = 1010 (补码) -> -6
        // 左移 <<
        System.out.println("a << 1 = " + (a << 1));  // 0101 << 1 = 1010 -> 10
        // 右移 >>
        System.out.println("a >> 1 = " + (a >> 1));  // 0101 >> 1 = 0010 -> 2
        // 无符号右移 >>>
        int c = -8;  // 1111...1000
        System.out.println("c >>> 1 = " + (c >>> 1));  // 0111...1100
    }
}

多数元素

技巧题，摩尔投票法。

class Solution {
    public int majorityElement(int[] nums) {
        // 摩尔投票法 当前的值和上一个值一样就+1 不一样就-1 为0就重新开始 最后结果肯定是众数
        int piv = 0;
        int vote = 0;
        for(int i: nums){
            if(vote == 0) piv = i;
            if(piv == i){
                vote++;
            }else{
                vote--;
            }
        }
        return piv;
    }
}