算法
算法

经典算法-动态规划

跳跃游戏

非负整数数组nums，最初位于数组的第一个位置，数组中的每个元素代表在该位置可以跳跃的最大长度，使用最少的跳跃次数到达数组的最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
public int jump(int[] nums) {
    int len = nums.length - 1;
    int steps = 0;
    int maxPosition = 0, end = 0;
    for (int i = 0; i < len; i++) {
        maxPosition = Math.max(maxPosition, i + nums[i]);
        if (i == end) {
            end = maxPosition;
            steps++;
        }
    }
    return steps;
}

零钱兑换

整数数组coins表示不同面额的硬币，整数amount表示总金额，计算并返回可凑成总金额所需最少的硬币个数，若没有任何一种硬币组合能组成总金额返回-1，可认为每种硬币的数量是无限的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    for (int i = 0; i <= amount; i++) {
        dp[i] = amount + 1;
    }
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

最大子数组和

1
2
3
4
5
6
7
8
public int maxSubArray(int[] nums) {
    int max = nums[0], prevMax = 0;
    for (int i = 0; i < nums.length; i++) {
        prevMax = Math.max(nums[i], prevMax + nums[i]);
        max = Math.max(max, prevMax);
    }
    return max;
}

接雨水

暴力破解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int trap(int[] height) {
    int left = 0, right = height.length - 1, res = 0;
    for (int leftIndex = 1, rightIndex = height.length - 2; leftIndex < height.length && rightIndex > -1; leftIndex++, rightIndex--) {
        if (height[left] <= height[leftIndex]) {
            for (int k = left + 1; k < leftIndex; k++) {
                res += height[left] - height[k];
            }
            left = leftIndex;
        }
        if (height[right] < height[rightIndex]) { // 等于的情况只能有一个
            for (int k = right - 1; k > rightIndex; k--) {
                res += height[right] - height[k];
            }
            right = rightIndex;
        }
    }
    return res;
}
动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int trap2(int[] height) {
    int[] leftMax = new int[len];
    leftMax[0] = height[0];
    int[] rightMax = new int[len];
    rightMax[len - 1] = height[len - 1];
    for (int left = 1, right = len - 2; left < len || right > -1; left++, right--) {
        leftMax[left] = Math.max(leftMax[left - 1], height[left]);
        rightMax[right] = Math.max(rightMax[right + 1], height[right]);
    }

    int res = 0;
    for (int i = 0; i < len; i++) {
        res += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return res;
}
双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int trap3(int[] height) {
    int res = 0;
    int leftMax = 0, rightMax = 0;
    int left = 0, right = len - 1;
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (height[left] < height[right]) {
            res += leftMax - height[left];
            left++;
        } else {
            res += rightMax - height[right];
            right--;
        }
    }
    return res;
}

最长连续递增序列

未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度

贪心算法
1
2
3
4
5
6
7
8
9
10
11
public static int findLength(int[] nums) {
    int ans = 0;
    int start = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] <= nums[i - 1]) {
            start = i;
        }
        ans = Math.max(ans, i - start + 1);
    }
    return ans;
}

乘积最大子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProduct(int[] nums) {
    int len = nums.length;
    int[] minF = new int[len];
    int[] maxF = new int[len];
    minF[0] = nums[0];
    maxF[0] = nums[0];
    for (int i = 1; i < len; i++) {
        maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(minF[i - 1] * nums[i], nums[i]));
        minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(maxF[i - 1] * nums[i], nums[i]));
    }
    int max = nums[0];
    for (int i = 0; i < len; i++) {
        max = Math.max(maxF[i], max);
    }
    return max;
}

使用RandN生成RandM

  • 首先通过randN生成randX，且X>=M，且X是N的整数幂，例：通过rand3生成rand11，则先通过rand3生成rand27，然后再生成rand22，最后生成rand11
  • 通过randX生成randY，且Y是M的整数倍，其实是生成一个大于Y的然后过滤到大于Y的值，例：rand3可生成(1，2,3)，rand3-1生成(0,1,2)，(rand3-1)*3生成(0,3,6)，(rand3-1)*3*3可生成(0,9,18)，则(rand3-1)*3*3 + (rand3-1)*3 + rand3-1则可等概览输出0-26
  • 然后通过对randY取模M然后加一即可得到randM
1
// 470. 用 Rand7() 实现 Rand10()