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

买卖股票的最佳时机

有点类似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;
    }
}

颜色分类

最直白的方法就是拿Map记录下个数然后写回去。 第二种方法类似冒泡排序，遍历两次，第一轮遍历把0全部放最前面，第二次遍历把1全部放最前面。

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        if( n <= 1) return;
        int ptr = 0;
        // 第一次遍历 把0全排序到最前面来 并得到0的边界是ptr-1
        for(int i = 0; i<n; i++){
            if(nums[i] == 0){
                nums[i] = nums[ptr];
                nums[ptr] = 0;
                ptr++;
            }
        }

        for(int i = ptr; i<n; i++){
            if(nums[i] == 1){
                nums[i] = nums[ptr];
                nums[ptr] = 1;
                ptr++;
            }
        }
        return;
    }
}

下一个排列

思路题，31. 下一个排列 – 力扣（LeetCode），参考力扣题解。 背下来思路吧。

以4、5、2、6、3、1为例，为了拿到大于它的下一个数4、5、3、1、2、6，需要做三步：

首先从后向前查找第一个顺序对 (i,i+1)，满足 a[i]<a[i+1]。这样「较小数」即为 a[i]。此时 [i+1,n) 必然是下降序列（因为是字典序）。
如果找到了顺序对，那么在区间 [i+1,n) 中从后向前查找第一个元素 j 满足 a[i]<a[j]。这样「较大数」即为 a[j]。
交换 a[i] 与 a[j]，最后反转[i+1，n]，即为答案。

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }
        // 找到最后一个满足a[i] < a[i+1]的了
        // 第二步 在i+1和n之间找满足 a[i] < a[x]的
        int j = nums.length - 1;
        // 如果i<0只能是一种情况 即 123456这种情况
        if(i >= 0){
            while(j >=0 && nums[i] >= nums[j]){
                j--;
            }
        // 找到最后一个满足 a[i] < a[x]的了
        // 交换并反转顺序i+1到n
        swap(nums, i, j);
        }
        reverse(nums, i+1);
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int i){
        // 调换i到n之间的顺序
        int l = i;
        int r = nums.length - 1;
        while(l < r){
            swap(nums, l, r);
            l++;
            r--;
        }
    }
}

寻找重复数

纯技巧题，用i->num[i]来映射，如果没有重复数，不会出现环，有重复数会出现环。

以数组 [1,3,4,2,2]为例，其映射关系 n->f(n) 为： 0->1 1->3 2->4 3->2 4->2

产生一个类似链表一样的序列：0->1->3->2->4->2->4->2->……，2->4 是一个循环。

⚠注意：如果从非 0 节点出发，可能无法找到答案，必须从0出发。

// 代码逻辑同 142. 环形链表 II
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0; 
        int fast = 0;
        while (true) {
            slow = nums[slow]; // 等价于 slow = slow.next
            fast = nums[nums[fast]]; // 等价于 fast = fast.next.next
            if (fast == slow) { // 快慢指针移动到同一个节点
                break;
            }
        }

        int head = 0; // 再用一个指针，从起点出发
        while (slow != head) {
            slow = nums[slow];
            head = nums[head];
        }
        return slow; // 入环口即重复元素
    }
}