1. 题目

  1. https://leetcode-cn.com/problems/lemonade-change/description/
  2. https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/
  3. https://leetcode-cn.com/problems/assign-cookies/description/
  4. https://leetcode-cn.com/problems/walking-robot-simulation/description/
  5. https://leetcode-cn.com/problems/jump-game/
  6. https://leetcode-cn.com/problems/jump-game-ii/

2. 题解

2.1 柠檬水找零#860（简单）

https://leetcode-cn.com/problems/lemonade-change/description/

class Solution {
    public boolean lemonadeChange(int[] bills) {
        // 法一：贪心。时间复杂度O(n),空间复杂度O(1).
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                five--;
                ten++;
            } else {
                if (ten > 0) {
                    ten--;
                    five--;
                } else {
                    five = five - 3;
                }
            }
            if (five < 0) {
                return false;
            }
        }
        return true;
    }
}

2.2 买卖股票的最佳时机Ⅱ#122（中等）

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/description/

class Solution {
    public int maxProfit(int[] prices) {
        // 法一：贪心算法.时间复杂度O(n),空间复杂度O(1)
        int length = prices.length;
        if (length < 2) {
            return 0;
        }
        int ans = 0;
        for (int i = 1; i < length; i++) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

2.3 分发饼干#455（简单）

https://leetcode-cn.com/problems/assign-cookies/description/

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //法一：贪心。时间复杂度O(mlogm + nlogn)排序所需,空间复杂度O(logm + logn)，排序所需
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length;
        int numOfCookies = s.length;
        int count = 0;
        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
            while (j < numOfCookies && g[i] > s[j]) {
                // 找到满足当前小孩能吃的饼干
                j++;
            }
            if (j < numOfCookies) {
                // 找到这样的一块饼干之后就+1.
                count++;
            }
        }
        return count;
    }
}

2.4 模拟行走机器人#874（中等）

https://leetcode-cn.com/problems/walking-robot-simulation/description/

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        //法一：模拟？贪心算法？时间复杂度O(n + k),空间复杂度O(k)
        int[] direx = {0, 1, 0, -1};
        int[] direy = {1, 0, -1, 0};
        int currentX = 0, currentY = 0;
        int currentDire = 0;
        int commandLength = commands.length;
        int ans = 0;
        Set<Pair<Integer, Integer>> obstacleSet = new HashSet<>();
        for (int i = 0 ; i < obstacles.length; i++) {
            obstacleSet.add(new Pair<>(obstacles[i][0], obstacles[i][1]));
        }
        for (int i = 0; i < commandLength; i++) {
            if (commands[i] == -1) {
                currentDire = (currentDire + 1) % 4;
            } else if (commands[i] == -2) {
                currentDire = (currentDire + 3) % 4;
            } else {
                for (int j = 0; j < commands[i]; j++) {
                    int nx = currentX + direx[currentDire];
                    int ny = currentY + direy[currentDire];
                    if (!obstacleSet.contains(new Pair<>(nx, ny))) {
                        currentX = nx;
                        currentY = ny;
                        ans = Math.max(ans, currentX * currentX + currentY * currentY);
                    } else {
                        break;
                    }
                }
            }
        }
        return ans;
    }
}

2.5 跳跃游戏#55（中等）

https://leetcode-cn.com/problems/jump-game/

class Solution {
    public boolean canJump(int[] nums) {
        //法一：贪心算法。时间复杂度O(n),空间复杂度O(1)
        int max = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > max) {
                return false;
            }
            max = Math.max(max, i + nums[i]);
        }
        return true;
    }
}

2.6 跳跃游戏Ⅱ#45（中等）

https://leetcode-cn.com/problems/jump-game-ii/

class Solution {
    public int jump(int[] nums) {
        //法一：贪心算法。时间复杂度O(n),空间复杂度O(1)
        int length = nums.length;
        int cnt = 0;
        int max = 0;
        int end = 0;
        for (int i = 0; i < length - 1; i++) {
            max = Math.max(i + nums[i], max);
            if (i == end) {
                end = max;
                cnt++;
            }
        }
        return cnt;
    }
}