268. Missing Number
Posted Updated LeetCode / Easya minute read (About 220 words)

268. Missing Number

Question

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Solution 1

采用数学方法，从0到n的和减去从nums中的每个元素的和，得到的即是缺失的数字。
循环所有下标，每次在结果上加上下标的值，并减去下标对应的元素。最后需要再加上nums内元素数量+1的值。

Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        int sum = nums.length;
        for(int i = 0; i < nums.length; i++){
            sum -= nums[i];
            sum += i;
        }
        
        return sum;
    }
}

Solution 2

遍历，采用一个数组found[]记录是否访问过。
再次遍历，如果存在未访问过的位置，则返回下标。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        int[] found = new int[nums.length+1];
        for(int i = 0; i < nums.length; i++){
            found[nums[i]] = 1;
        }
        
        for(int i = 0; i <= nums.length; i++){
            if(found[i] == 0) res = i;
        }
        return res;
    }
}
1342. Number of Steps to Reduce a Number to Zero
Posted Updated LeetCode / Easya few seconds read (About 97 words)

1342. Number of Steps to Reduce a Number to Zero

Question

Given an integer num, return the number of steps to reduce it to zero.

In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it.

Solution

循环，当num不等于零时，如果为奇数则减一，如果为偶数则除以2。
每次循环记录次数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numberOfSteps(int num) {
        int count =0;
        while(num != 0){
            count++;
            if((num & 1) == 0){
                num/=2;
            }
            else{
                num--;
            }
        }
        return count;
    }
}
354. Russian Doll Envelopes
Posted Updated LeetCode / Hard / 复习7 minutes read (About 979 words)

354. Russian Doll Envelopes

Question

You are given a 2D array of integers envelopes where envelopes[i] = [w<sub>i</sub>, h<sub>i</sub>] represents the width and the height of an envelope.

One envelope can fit into another if and only if both the width and height of one envelope are greater than the other envelope’s width and height.

Return the maximum number of envelopes you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

Solution 1

最长递增子数列

这道题是LIS问题（Longest Increasing Subsequence） 的升级版。
后一个数组中的两个元素应该同时严格大于前一个数组中的两个元素。
因此我们需要维护一个宽度和高度同时严格单调递增的数列。

排序

我们可以对数组以宽度进行比较排序。当二者的宽度相等时，以高度的倒序排序。
（采用倒序排序是为了下面处理时排除不严格大于上一个数组的情况。）

递增数列

我们可以维护一个递增动态数组arr，记录高度组成的单调递增数列。（LIS）
首先将数组中的第一个元素的高度加入动态数组。
然后遍历数组envelopes[]：

  • 如果当前数组的高度height大于单调递增数列的最大值：
    • 则当前的数组的宽度和高度均严格大于数组中最后一个高度对应的数组。
    • 数组是优先以宽度的顺序排列，相等时以高度的倒序排列。由于相同宽度时高度大的在前，因此当当前高度大于之前的最大高度，则宽度也一定大于之前的最大宽度。
  • 如果小于或者等于单调递增数列的最大值：
    • 单调数列中高度的增长越平缓，我们在后面找到更多严格大于height的可能性就越大，因此可以用贪心思想，更新单调数列中的第一个大于当前高度的值。
    • 由于单调递增数列是有序的，因此可以采用二分搜索来寻找第一个大于当前高度的值的下标，并将其更新为当前的height。

排序的时间复杂度为O(nlogn)，遍历数组的时间复杂度为O(n)，二分搜索的时间复杂度为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
class Solution {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (a,b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        List<Integer> arr = new ArrayList<>();
        arr.add(envelopes[0][1]);
        for(int i = 1; i < envelopes.length; i++){
            int height = envelopes[i][1];
            if(height > arr.get(arr.size()-1)){
                arr.add(height);
            }
            else{
                int index = Collections.binarySearch(arr, height);
                if(index < 0) index = -index-1;
                arr.set(index, height);
            }
        }
        return arr.size();
    }
}

Solution 2

注意这个方法在LeetCode中会超时，仅仅是记录一下思路，也可以采用动态规划的方法。
记忆化搜索剪枝。
记忆化搜索每个envelope。

memorazation()方法，返回当前的envelope中可以包含的最大数量。
当数组memo[i]不等于0时，返回memo[i]。
否则初始化最大值max为1。
遍历数组中的所有元素，如果宽度于长度都大于envelopes[i]，则向下递归搜索该元素。
比较并更新max和递归结果的返回值+1。
最后将当前位置memo[i]设置为包含的最大数量max。

遍历所有元素时间复杂度O(n)。
记忆化搜索元素的子项时间复杂度O(n)。
时间复杂度为O(n2)。

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
class Solution {
    int[][] dolls;
    int[] memo;
    
    public int maxEnvelopes(int[][] envelopes) {
        dolls = envelopes;
        memo = new int[dolls.length];
        int res = 0;
        for(int i = 0; i < dolls.length; i++){
            if(memo[i] != 0) continue;
            memorazation(i);
            res = Math.max(res, memo[i]);
        }
        return res;
    }
    
    private int memorazation(int i){
        if(memo[i] != 0){
            return memo[i];
        }
        int max = 1;
        for(int k = 0; k < dolls.length; k++){
            if(dolls[k][0] < dolls[i][0] && dolls[k][1] < dolls[i][1]){
                max = Math.max(max, memorazation(k) + 1);
            }
        }
        return memo[i] = max;
    }
}
32. Longest Valid Parentheses
Posted Updated LeetCode / Hard / 复习4 minutes read (About 611 words)

32. Longest Valid Parentheses

Question

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Solution

如果有右括号先出现于左括号，则其永远无法配对。
而如果是左括号先出现，则其有可能可以和之后的右括号进行配对。

因此我们可以将左括号的位置入栈，等待配对。
并记录上一个不能配对的右括号的位置。以此来确定当前位置的有效括号长度。

首先将上一个不能组队的右括号lastRightParenthese初始化为-1。
初始化一个最大有效长度best。

然后遍历字符串：

  • 当遇到左括号时：
    • 将当前下标i压入栈。（记录等待配对的左括号）
  • 遇到右括号时：
    • 如果栈为空，则更新上一个不能组队的右括号的位置为当前下标i。（此时出现的右括号一定无法配对）
    • 如果栈不为空，则挤出上一个左括号的下标，与右括号配对。
      • 挤出上一个左括号后，如果栈为空。则将当前的有效括号总长度为i - lastRightParenthese。（当前的右括号和上一个不能配对的右括号的差）
      • 否则当前的有效括号总长度为i - stack.peek()。（当前的右括号和上一个不配对的左括号的差。）

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 longestValidParentheses(String s) {
        Deque<Integer> stack = new LinkedList<>();
        int best = 0;
        int lastRightParenthese = -1;   //上一个不能配对的右括号位置，初始化为-1
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){ //如果当前位置是左括号，则将下标入栈
                stack.push(i);
            }
            else{   //如果当前位置是右括号...
                if(stack.isEmpty()){    //如果没有可以配对的左括号，则更新不能配对的右括号的位置
                    lastRightParenthese = i;
                }
                else{
                    stack.pop();    //如果有可以配对的右括号，则从栈中挤出
                    if(stack.isEmpty()){    //挤出后如果没有剩余的左括号了，则当前有效括号长度为当前位置减去上一个无法配对的右括号的位置
                        best = Math.max(best, i - lastRightParenthese);
                    }
                    else{   //如果挤出后栈内仍有剩余的左括号存在，则当前有效括号长度为当前位置减去栈顶的左括号的位置
                        best = Math.max(best, i - stack.peek());
                    }
                }
            }
        }
        return best;
    }
}
474. Ones and Zeroes
Posted Updated LeetCode / Medium / 复习7 minutes read (About 1000 words)

474. Ones and Zeroes

Question

You are given an array of binary strings strs and two integers m and n.

Return the size of the largest subset of strs such that there are at most m 0‘s and n 1‘s in the subset.

A set x is a subset of a set y if all elements of x are also elements of y.

Solution 1

0-1背包问题的升级版。经典的背包问题只有一种容量，而这个问题实际等于有两种容量。

经典背包问题需要用二维数组动态规划，分别为物品和容量。
而这道题需要用三维数组动态规划，分别为字符串，0的容量和1的容量。

我们采用一个三维数组dp[i][j][k]保存可取最多物品的数量。
对于每个物品i，我们都可以取（数量+1）或不取（保持上一个物品的状态）。
j和k相当于分别记录了取“0”的总数和“1”的总数

遍历三个维度，并计算字符串中0和1的个数。

  • 如果当总容量大于当前物品中zeros和ones的数量，则可以取当前的物品。

    • 如果取当前的物品，则dp[]数组的总数等于上一个物品的状态加一，即dp[i-1][j-zeros][k-ones]。
    • 也可以不取当前的物品，则dp[]数组的总数直接保持上一个物品的状态。

  • 如果当前背包总容量小于zeros和ones的数量，则不能取当前物品。

    • 数组dp[]保持上一个物品的状态。

时间复杂度：O(lmn + L)，L是数组中所有字符串长度之和。
空间复杂度：O(lmn)。

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 findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length+1][m+1][n+1];
        
        for(int i = 1; i <= strs.length; i++){
            int zeros = 0, ones = 0;
            for(char c : strs[i-1].toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    if(j - zeros >= 0 && k - ones >=0) dp[i][j][k] = Math.max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
                    else dp[i][j][k] = dp[i-1][j][k];
                }
            }
        }
        return dp[strs.length][m][n];
    }
}

Solution 2

由于dp[i][][]的上一个状态只涉及到dp[i-1][][]，因此我们可以采用滚动数组，去掉数组的一个维度，压缩空间。
此时需要从m到zeros，从n到ones倒序遍历，保证dp[i][][]转移过来的是dp[i-1][][]的元素。

此时的空间复杂度降低为O(mn)。

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 findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        
        for(String s : strs){   //记录每个位置对应的0和1数量
            int zeros = 0, ones = 0;
            for(char c : s.toCharArray()){
                if(c == '0') zeros++;
                else ones++;
            }
            
            for(int i = m; i >= zeros; i--){
                for(int j = n; j >= ones; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i-zeros][j-ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

Solution 3

递归+记忆化搜索，保存并返回每个位置的最大长度。
如果位置越界则返回0。
如果memo[i][zero][one]不为0，则返回memo[i][zero][one]。

如果当前字符串的“0”和“1”的个数大于剩余的“0”和“1”的个数，则可以取当前字符串，递归下一个位置并加一。
也可以不取当前的字符串，递归下一个位置。当前位置memo[i][zero][one]等于两者中的最大值。

否则无法取当前字符串，直接递归下一个位置。当前位置等于0。

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
34
35
class Solution {
    String[] s;
    int[] zeros, ones;
    int[][][] memo;
    public int findMaxForm(String[] strs, int m, int n) {
        s = strs;
        zeros = new int[strs.length];
        ones = new int[strs.length];
        memo = new int[strs.length][m+1][n+1];
        
        for(int i = 0; i < strs.length; i++){   //记录每个位置对应的0和1数量
            for(int j = 0; j < strs[i].length(); j++){
                if(s[i].charAt(j) == '0') zeros[i]++;
                else ones[i]++;
            }
        }
        return dfs(0, m, n);
    }
    
    private int dfs(int i, int zero, int one){
        if(i >= s.length){
            return 0;
        }
        if(memo[i][zero][one] != 0) return memo[i][zero][one];
        
        int maxPossibleSubset = 0;
        
        if(zero-zeros[i] >= 0 && one-ones[i] >= 0){
            maxPossibleSubset = 1 + dfs(i+1, zero-zeros[i], one-ones[i]);
        }
        memo[i][zero][one] = Math.max(maxPossibleSubset, dfs(i+1, zero, one));
        return memo[i][zero][one];
        
    }
}
Follow

Recents

Archives

Links

×