总结一道贪心算法题

发表于 | 分类于

关于一道贪心算法题的四个解

原题如下(leetcode_55)

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

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

Determine if you are able to reach the last index.

Example 1:

1
2
3
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

1
2
3
4
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

大致题意

现在给你一个[2,3,1,1,4]的数组，数组的每个数字代表能跳的步数。我们从下标0开始，现在我们知道，我们从下标0可以跳到下标1和2。因为下标0的值是2,接着我们从下标1可以直接跳到下标4，也就是终点。如果上述数组能实现从下标0到终点的操作，返回ture。反之，返回false。

解法一(遍历递归求解)

老规矩，最开始用暴力的遍历求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//solution 1
//c++ 实现
//时间复杂度O(n^2)
//空间复杂度(1)
bool inter(int index,int a,vector<int>& nums){
    bool temp;
    if(index+a >= nums.size()-1){return true;}
    else{
        for(int i = index+1;i<=a+index&&i<nums.size();i++){
            temp = inter(i,nums[i],nums);
            if(temp == true){return temp;}
        }
    }
    return false;
}
class Solution {
public:
    bool canJump(vector<int>& nums) {
        bool refluse = inter(0,nums[0],nums);
        return refluse;
    }
};

对于每一下标，我们遍历他们能跳到的所有下标,如果当前下标加上下标的值大于等于终点，那么返回true,否则返回false。
这个解法在最后一个case点超时了。

让我们看一下这个算法的冗杂之处，当下标1与下标2都能跳到3时,在遍历时会对下标3进行2次判断。但下标3其实在第一次判断完后就已经决定了它是否能返回true，也就是说第二次判断是冗杂的。那么会想到用hash散列对每个节点进行一个记录，保证每个节点只需要访问一次即可。

解法二(hash散列优化解法一)

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
//solution 2
//c++ 实现
//时间复杂度O(n)
//空间复杂度(n)
bool inter(int index,int a,vector<int>& nums,int* ch){
    bool temp;
    if(index+a >= nums.size()-1){return true;}
    else{
        ch[index] = 1;
        for(int i = index+1;i<=a+index&&i<nums.size();i++){
            if(ch[i] == 1){continue;}
            temp = inter(i,nums[i],nums,ch);
            if(temp == true){return temp;}
        }
    }
    return false;
}


class Solution {
public:
    bool canJump(vector<int>& nums) {
        int ch_len = nums.size();
        int ch[ch_len];
        memset(ch,0,sizeof(ch));
        bool refluse = inter(0,nums[0],nums,ch);
        return refluse;
    }
}

我们加了一个数组对每个下标的判断次数做了记录，保证每个下标只会做一次。

这个解法顺利ac。

上半场总结

开头说了有四个解，现在已经出来了两个,按照出题者的说法，前两种解法属于top-down的思路，也就是自顶向下求解。

我认为top-downd的意思就是根据题目给你的意思，按照标准的顺序去求解。这道题目要求我们在下标0的位置开始，看是否能到达终点。那么标准的顺序就是从0开始去向终点方向移动。
这也是基本的解题思路，

但是往往这种递归的题目是可以将递归给消除的。出题者称他们为bottom-up的思路。下面两种解法就是关于这个bottom-up的思路。

解法三(从尾部开始，消除递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//solution 3
//c++ 实现
//时间复杂度O(n)
//空间复杂度(n)
class Solution {
public:
    bool canJump(vector<int>& nums) {
        nums_len = nums.size();
        int ch[nums_len];
        memset(ch,0,sizeof(ch));
        for(int i = 0;i<nums_len;i++){
            if(ch[i]+i >= nums_len-1){ch[i] = 1;}
        }
        for(int i = nums_len-1;i>=0;i++){
            if(ch[i] == 0){
                for(int z = i+1;z<=i+ch[i] && z<nums_len;z++){
                    if(ch[z] == 1){ch[i] = 1;break;}
                }
            }
        }
        if(ch[0] == 1){return true;}
        else{return false;}
    }
};

解法三先将所有可以直接到终点的下标标为1，然后从末尾开始，如果该下标不是1，看看是否能跳至置1的下标处，如果可以，那么这个下标也置1。

最后检查0下标是否置1，如果置1，那么输出true。

解法四(贪心)

在解法三的基础上，我们发现可以将最后的节点移动，如果3节点可以移动到最终节点，那么只要把3节点当作最终节点，前面的节点只要判断是否能够移动到3就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//solution 4
//c++ 实现
//时间复杂度O(n)
//空间复杂度(1)
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int nums_len = nums.size();
        node_number = nums_len - 1;
        for(int i = nums_len-1;i>=0;i++){
            if(i+nums[i] >= node_number){node_number = i;}
        }
        if(node_number == 0){return true;}
        else{return false;}
   }
};

下半场总结

我们可以发现，解法1和2之间，解法3和4之间都有连贯性，4与2都是对前面的解法的一种优化。问题的关键是如何从解法2转化到解法3。

观察解法2与解法3，其实解法3就是对解法2递归的一个逆推。解法2通过递归找到最小的单元，然后确定他们的可行性。解法3反过来，先确定了每个单元的可行性，然后判断是否能达到最初。

大部分的题目都可以用正常的top-down思路求解，但是哪些题目可以采用bottom-up的方法，或者如何找到这类解法。我自己总结一下。

可以单独对一些单元下判断的(比如这一道，我们可以得到一开始就指向终点的合格下标)。

尝试从后面开始判断

找的到特殊的规律(贪心)

前面的解法采用了递归或者hash散列，尝试逆推

暂时就想到这些，后面做到了再总结。