Posted Updated LeetCode / Medium2 minutes read (About 266 words)

2274. Maximum Floors Without Special Floors

Question

Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be special floors, used for relaxation only.

You are given two integers bottom and top, which denote that Alice has rented all the floors from bottom to top (inclusive). You are also given the integer array special, where special[i] denotes a special floor that Alice has designated for relaxation.

Return the maximum number of consecutive floors without a special floor.

Solution

可以视为特殊的动态规划。

计算每个特殊房间与上一个特殊房间的层数。（可以将底层的上一个房间视为特殊房间，需要将第一个房间设置为bottom-1）。
当距离大于当前结果时则更新res。

最后需要计算最后一层到上一个特殊房间的距离。（可以将顶楼的上一层视为特殊房间，因此直接计算top - lastRoom的层数即可）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxConsecutive(int bottom, int top, int[] special) {
        int res = 0;
        int lastRoom = bottom-1;
        Arrays.sort(special);
        
        for(int room : special){
            int temp = room - lastRoom - 1;
            res = Math.max(res, temp);
            lastRoom = room;
            
        }
        int temp = top - lastRoom;
        res = Math.max(res, temp);
        
        return res;
    }
}
673. Number of Longest Increasing Subsequence
Posted Updated LeetCode / Medium / 复习4 minutes read (About 538 words)

673. Number of Longest Increasing Subsequence

Question

Given an integer array nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Solution

本题还有贪心算法+前缀和+二分查找的算法。

本题是300. Longest Increasing Subsequence的拓展。
同样采用动态规划，数组dp[i]记录到i为止最长递增数列长度。
可以用一个新的数组cnt[i]记录到i为止可以组成的最长递增数列的数量。

对于每个新位置i，cnt[i]的最小值为i。
遍历i之前的所有位置j。如果nums[j] < nums[i]，则i可以比dp[j]组成更长的递增数列，其长度为dp[j]+1。
如果dp[i] < dp[j]+1。则可以更新dp[i]。同时，cnt[i]可以从cnt[j]继承其计数。
如果dp[i] == dp[j]+1。则之前已经更新过dp[i]。说明有新的组合同样可以组成更长的递增数列。此时将cnt[j]加入当前的cnt[i]。

遍历完成i以内的所有j后，如果dp[i]大于当前的最长递增数列长度，则更新max。
同时更新长度的总数count为cnt[i]。
如果dp[i]等于max，则将cnt[i]加入计数count。
最后返回count。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] cnt = new int[n];
        int max = 0;
        int count = 0;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];    //如果后面的数字大于前面的，且可以组成更长的数列，则继承之前的计数。
                    }
                    else if(dp[j] + 1 == dp[i]){    //如果之前已经更新过dp[i]，则有新的组合长度一直，加和之前的计数。
                        cnt[i] += cnt[j];
                    }
                }
            }
            if(dp[i] > max){    //如果当前的长度大于之前的最大值，则更新。
                max = dp[i];
                count = cnt[i];  //同时将之前计算的计数记录。
            }
            else if(dp[i] == max){  //如果有同样达到最大值的情况，则加和计数。
                count += cnt[i];
            }
        }
        return count;
    }
}
72. Edit Distance
Posted Updated LeetCode / Hard2 minutes read (About 331 words)

72. Edit Distance

Question

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character

Solution

本题和583. Delete Operation for Two Strings大同小异。

动态规划，两个字符串的分别以长宽组成一个矩阵，记录该位置得编辑距离。
将初始的编辑距离dp[i][0]一行和dp[0][j]一列按照对应的位置i和j填写。

双重遍历矩阵的坐标。
当两个字符相等时，编辑距离等于对角线方向的状态的编辑距离（即两个字符都没有取得上一个状态）。
当两个字符不相等时，编辑距离等于左边，上边（少取一个字符的状态）以及对角线方向（两个字符都不取的状态）的编辑距离中得最小值再加上1。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        char[] bin1 = word1.toCharArray();
        char[] bin2 = word2.toCharArray();
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(bin1[i-1] == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j], dp[i][j-1]) + 1);
                }
            }
        }
        return dp[m][n];
    }
}
343. Integer Break
Posted Updated LeetCode / Medium3 minutes read (About 499 words)

343. Integer Break

Question

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Solution

动态规划，用数组dp[]记录最大乘积。
在n < 4之前为特例，由于必须拆分，因此乘积小于自身。但由于之后的数字要用到拆分的特性，因此这三个数字要特殊设置为自身。
在此之后，每个数字可以拆分成两个数的加和，然后乘积等于对应两个数的乘积。
（dp[4]可以不设置计算得出，但是指定值的话可以加快速度。）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 1; j <= (i/2)+1; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}

Solution 2

数学方法，当两数之和大于4时，拆分成两个更小的加和可以得到更大的乘积。
而当等于4时，可以拆分为两个2相乘。
因此，最终有意义的拆分结果只会有2和3。

拆分规则：

  1. 最优： 3 。把数字 n 可能拆为多个因子 3 ，余数可能为 0,1,2 三种情况。
  2. 次优： 2 。若余数为 2 ；则保留，不再拆为 1+1 。
  3. 最差： 1 。若余数为 1 ；则应把一份 3+1 替换为 2 + 22+2，因为 2 * 2 > 3 * 1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        }
        else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        }
        else {
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

Solution 3

同样，我们可以将之前的结论用在动态规划上，j只取2或3，将时间复杂度从O(n^2)降低到O(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int integerBreak(int n) {
        if(n <= 1) return 0;
        if(n == 2) return 1;
        if(n == 3) return 2;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
  
        for(int i = 4; i <= n; i++){
            for(int j = 2; j <= 3; j++){
                int k = i - j;
                dp[i] = Math.max(dp[i], dp[j] * dp[k]);
            }
        }
        return dp[n];
    }
}
322. Coin Change
Posted Updated LeetCode / Medium2 minutes read (About 231 words)

322. Coin Change

Question

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Solution

动态规划，首先将amount长度的数组填满最大值。
双重遍历数组和硬币，不取当前硬币的上一个状态加一（dp[i - coin]+1）就是当前可取的最小值。
注意先取硬币，将amount的起始值设置为硬币面值可以增快速度。（减少了面值大于总额的情况。）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        int dp[] = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int coin : coins){
            for(int i = coin; i <= amount; i++){
                if(dp[i-coin] != Integer.MAX_VALUE)
                dp[i] = Math.min(dp[i],dp[i - coin]+1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 295 words)

583. Delete Operation for Two Strings

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

动态规划，创建数组dp[][]，长宽分别为两个字符串的长度。
在dp中填入子字符串修改成另一个子字符串时需要删除的数量。
如果两个字符相同，则相对于上一个状态不需要增加数量。因此可以直接等于对角线方向上的值。
如果两个字符串不同，则取上方向和左方向中的较小值，然后+1。（由于题目只允许删除操作，不允许修改操作，因此不能从字符串左上角取值。）
最后返回dp中右下角的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        char[] bin1 = word1.toCharArray();
        char[] bin2 = word2.toCharArray();
        
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        
        for(int i = 1; i <= m; i++){
            char k = bin1[i-1];
            for(int j = 1; j <= n; j++){
                if(k == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 275 words)

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.

动态规划，dp的长和宽分别为两个字符串的长度。
遍历dp字符串的长和宽。（注意在第一层遍历时先保存当前选择的字符可以提升速度。）
当两个字符串相同时，则可以从上一个状态+1。
注意状态转移方程的上一个状态应该是从对角线方向+1。
当两个字符串不同时，则继续保存之前的最大长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m+1][n+1];
        char[] bin1 = text1.toCharArray();
        char[] bin2 = text2.toCharArray();

        for(int i = 1; i <= m; i++){
            int k = bin1[i-1];
            for(int j = 1; j <= n ; j++){
                if(k == bin2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }
                else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 285 words)

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

动态规划，创建一个数组dp[]，长度为字符串长度+1，记录是否可以达到。
将dp[0]设置为1，表示可以达到。

从可取长度为1开始，遍历直到可取长度为字符串的长度。
用下一个遍历j将字符串分为两部分。（这里j从i-1下降到0会比从0上升到i-1更快。）
当dp[j]可以到达，且当前的哈希表中有(i-j)组成的字符串时，则dp[i]也可以到达。结束第二层循环。
继续搜索更长的字符串是否可以达到。
最后返回dp中的最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>();
        int n = s.length();
        int[] dp = new int[n+1];
        
        for(String word : wordDict){
            set.add(word);
        }
        dp[0] = 1;
        int temp = 0;
        for(int i = 1; i <= n; i++){
            for(int j = i - 1; j >= 0; j--){
                if(dp[j] == 1 && set.contains(s.substring(j, i))){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[n] == 1; 
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 312 words)

91. Decode Ways

A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped into:

  • “AAJF” with the grouping (1 1 10 6)
  • “KJF” with the grouping (11 10 6)
    Note that the grouping (1 11 06) is invalid because “06” cannot be mapped into ‘F’ since “6” is different from “06”.

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

动态规划。转移方程的考虑比较麻烦。
当当前的字符不为0时，该为可以自己组成有效编码，因此dp[i] = dp[i-1]。
然后考虑上一位可以和当前位组成有效编码的情况，如果上一位和当前位的数字小于26，且上一位不等于0，则可以联合编码。
因此dp需要再加上前一位可以组成的编码数，即dp[i] += dp[i-2]。
当i等于1时，由于会越界因此我们手动给dp[i]++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(s.charAt(0) == '0') return 0;
        int[]dp = new int[n];
        dp[0] = 1;

        for(int i = 1 ; i < n; i++){
            if(s.charAt(i) != '0'){
                dp[i] = dp[i-1];
            }
            if(s.charAt(i-1) != '0' && (s.charAt(i-1) - '0') * 10 + (s.charAt(i) - '0') <= 26 ){
                if(i > 1) dp[i] += dp[i-2];
                else dp[i]++;
            }
        }
        return dp[n-1];
    }
}
300. Longest Increasing Subsequence
Posted Updated LeetCode / Medium / 复习4 minutes read (About 589 words)

300. Longest Increasing Subsequence

Question

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Solution

贪心算法

创建一个数组记录达到升序的长度时升序数列的最小末尾值。
如果想要增加数组的长度（即增加最大的升序数列长度），则新的数字必须要大于该数组最后一位的大小。
因此在这种情况下，该数组必然是单调递增的。

二分搜索

将第一个数字填入数组。
然后遍历数组，当新一项大于数组的最后一个值时，最大长度加一，并将其加入数组的尾部。
当新一项小于数组的最后一个值时，该数字需要与之前的数组组成新的升序数列。
我们可以替换掉之前数组中比该数字大的第一个数字，代表新组成的数组。（最长数组之间的数字无所谓，只记录最小的末尾值即可。）
我们可以用二分搜索查到该数字需要加入的index。然后替换掉数组中的数字。
单次二分搜索的时间复杂度为O($logn$)。总的时间复杂度为O($nlogn$)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLIS(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        int len = 1;
        ans.add(nums[0]);
    
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > ans.get(ans.size()-1)){
                ans.add(nums[i]);
                len++;
            }
            else{
                int index = Collections.binarySearch(ans, nums[i]);
                if(index < 0){
                    ans.set(-(index+1), nums[i]);
                }
            }
        }
        return len;
    }
}

Solution 2

动态规划，创建一个数组dp[]用来记录最大长度，创建max记录最大值。
遍历，先将数组dp[]上的所有位置都填上1。
从0到i-1遍历j。当nums[i] > nums[j]时，更新dp[i]为dp[i]与dp[j]+1中的较大值。
当更新dp[i]时将其和max比较，如果比max大则更新max。
最后返回max值。时间复杂度为O($n_2$)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int max = 1;
        
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = i-1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                    if(max < dp[i]){
                        max = dp[i];
                        break;
                    }
                }
            }
        }
        return max;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 189 words)

413. Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

  • For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
    Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

动态规划，遍历一次记录所有数字的差。
然后遍历并计算连续相同的数字数量temp。
当不相同时，则计算temp长度可以选择的组合数，将其添加到count。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {

        if(nums.length == 1) return 0;
        int[] difference = new int[nums.length-1];
        for(int i = 0; i < nums.length-1; i++){
            difference[i] = nums[i+1] - nums[i];
        }
        
        int count = 0;
        int temp = 1;
        int prev = difference[0];
        for(int j = 1; j < nums.length-1; j++){
            if(difference[j] == prev){
                temp++;
            }
            else{
                count += combinations(temp);
                temp = 1;
            }
            prev = difference[j];
        }
        count += combinations(temp);
        return count;
    }
    
    private int combinations(int n){
        return (n * (n-1)) / 2;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 208 words)

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

动态规划，每一个位置的线路都等于其左侧和上侧的两条线路的加和。
将初始的两个边值设置为1，然后计算直至终点位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int count;
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }
        
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 209 words)

45. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

设置一个当前可以访问的最大范围limit，在遍历中对其进行更新。
和当前可访问位置中的最远距离end，每次访问到达end时，计算步数。

遍历数组，比较limit和当前i能访问的最远距离i+nums[i]，保留较大值。
当i达到end时，更新end为之前记录的可访问最远距离limit。步数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        int count = 0;
        int limit = 0;
        int end = 0;
        
        for(int i = 0; i < nums.length-1; i++){
            limit = Math.max(limit, i + nums[i]);
            if(i == end){
                end = limit;
                count++;
            }
        }
        
        return count;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 440 words)

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

反向查找，动态规划。
到达目标点前必须到达上一个节点，且上一个节点能前进的步数必须大于目标点。
设置目标点goal，反向遍历goal以外的点。
如果该点能前进的步数加上自身的位置i大于目标点，则可以从上一个点到达goal。
更新goal的位置到上一个点。
如果遍历结束后，能返回到起始点0，则可以到达终点。

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length-1;
        for(int i = nums.length-2; i >=0; i--){
            if(nums[i] >= goal - i) goal = i;
        }
        return goal == 0;
    }
}

贪心算法，储存一个到i时可以到达的最远值maxJump。
遍历数组，如果i大于maxJump，则无法到达下一个点，返回false。
在当前点可以到达的最大范围为nums[i]+i，如果大于maxJump则更新该值。
遍历完毕返回true。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > maxJump) return false;
            maxJump = Math.max(maxJump, nums[i] + i);
        }
        return maxJump >= nums.length-1;
    }
}

设置一个数组记录可访问的范围。
当遍历时，如果可以访问，则将当前位置可以进一步访问的位置变为1。
如果访问范围大于等于数组末尾，则返回真。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean canJump(int[] nums) {
        int[] reach = new int[nums.length];
        reach[0] = 1;
        
        for(int i = 0; i < nums.length; i++){
            if(reach[i] == 1){
                if(i == nums.length-1) return true;
                for(int j = 0; j < nums[i]; j++){
                    if(i+j+1 >= nums.length) return true;
                    reach[i+j+1] = 1;
                }
            }
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 291 words)

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

动态规划，和普通的动态规划不同的是这道题是首尾相连的。
因此分两种情况讨论——如果选择了头，就不选择尾。反之亦然。
建立两个动态规划表，分别选择第一个和第二个数字作为第一次抢劫的目标。
前一个最多抢劫到倒数第一个房子，后一个最多抢劫到最后一个房子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        int max = 0;
        int[] dp = new int[nums.length+1];
        int[] dp2 = new int[nums.length+1];
        dp[1] = nums[0];

        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);
        }

        dp2[2] = nums[1];
        
        for(int i = 3; i <= nums.length; i++){
            dp2[i] = Math.max(dp2[i-2] + nums[i-1], dp2[i-1]);
        }
        
        return Math.max(dp[dp.length-2], dp2[dp2.length-1]);
    }
}
Follow

Recents

Archives

Links

×