甲乙小朋友的房子

甲乙小朋友很笨，但甲乙小朋友不会放弃

0%

算法-贪心法

发表于 更新于 分类于

Leetcode题

Jump Game II

给一个数组[2,3,1,1,4]，每个元素代表当前可以跳跃的步数。求问最少跳多少次可以从idx = 0跳到idx = n - 1

dp超时，只能用贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int jump(int[] nums) {
    int end = 0;
    int endGlobal = 0;
    int start = 0;
    int step = 0;
    while (endGlobal < nums.length - 1){
        for(int i = start; i <= end; ++i){
            endGlobal = Math.max(endGlobal, i + nums[i]);
        }
        start = end;
        end = endGlobal;
        ++step;
    }
    return step;
}

Remove K Digits

给一个str代表一个数字。给一个k。求删掉k个字符后，能够变成的最小数字。

方法一，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
29
30
31
32
33
34
35
36
String[][] memo;
String num;
int n;
private String helper(int idx, int k){
    if(idx == -1){
        return "";
    }
    if(memo[idx][k] != null) return memo[idx][k];
    String min = num;
    for(int i = idx; i + 1 >= k; --i){
        String temp = helper(i - 1, k - 1) + num.substring(i + 1, idx + 1);
        if(temp.compareTo(min) < 0){
            min = temp;
        }
    }
    memo[idx][k] = min;
    return min;
}
public String removeKdigits(String num, int k) {
    this.num = num;
    this.n = num.length();
    memo = new String[n][k+1];
    for(int i = 0; i < n; ++i){
        memo[i][0] = num.substring(0, i + 1);
        if(i < k)memo[i][i+1] = ""; // k == i+1时，必须把前k个全部删掉才可以
    }
    String result = helper(n - 1, k);
    if(result.length() == 0) result = "0";
    // 去掉前导零
    int i = 0;
    for(i = 0; i < result.length() - 1; ++i){
        if(result.charAt(i) == '0') continue;
        else break;
    }
    return result.substring(i);
}

方法二，贪心

假设数字abcdef ，从左到右看。如果c > a ，那么明显删掉c比删掉a合适。

那么就要存下来之前遇到的最大值，然后如果之前的比较大，就把之前的删掉。如果当前大，就把当前删掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String removeKdigits(String num, int k) {
        if(k == 0) return num;
        char[] stack = new char[num.length()];
        Arrays.fill(stack, '0');
        int stackTail = -1;
        int digit = num.length() - k;
        for(int i = 0; i < num.length(); ++i){
            while(k > 0 && stackTail >= 0 &&num.charAt(i) < stack[stackTail]) {
                --k; // 如果遇到之前那个值大于后面的值，那就把它删掉
                --stackTail;
            }
            stack[++stackTail] = num.charAt(i);
        }
        // 去掉前导0
        int stackHead = 0;
        while (stackHead < digit && stack[stackHead] == '0') ++stackHead;
        if(stackHead == digit) return "0";
        else return new String(stack, stackHead, digit - stackHead);
    }