小编Ume*_*ela的帖子

我正在从LeetCode.com解决一个问题:

给定一个非负整数数组,您最初定位在数组的第一个索引处.数组中的每个元素表示该位置的最大跳转长度.确定您是否能够到达最后一个索引.例如:A = [2,3,1,1,4],返回true.A = [3,2,1,0,4],返回false.

投票最多的解决方案之一(这里)说以下是使用贪婪的方法:

bool canJump(int A[], int n) {
    int last=n-1,i,j;
    for(i=n-2;i>=0;i--){
        if(i+A[i]>=last)last=i;
    }
    return last<=0;
}

我有两个问题:

1. 使用贪婪算法背后的直觉是什么？
2. 上述解决方案如何成为贪心算法？

我认为动态编程可以解决这个问题.我理解DP可以解决的问题可以通过贪婪的方法来解决,但是这个特殊的方法背后的直觉是什么使得通过贪婪的方法解决更有意义？

这个问题在某种程度上凸显了这种差异.我理解这可能会更多,但如果可能的话,有人可以在这个背景下回答这个问题吗？我非常感谢.

谢谢.

编辑:我认为我混淆的原因之一是输入[3,3,1,0,4].根据贪婪的范式,i=0我们何时不会跳过大小3(A[0])来贪婪地达到输出？但这样做实际上是不正确的.

什么是获得矩阵中元素列表的Pythonic方法(x,y)？

例如,给定一个矩阵,如:

[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]

还有一点,比如说(1,3)(代表元素9)我怎样才能让对角线中的元素以9Pythonic方式通过？基本上,[3,9,15]和[5,9,13,17,21]两者.

对不起,我只是学习Python,因此问题.谢谢!

我想知道以下代码片段的时间复杂度是O(n^2):

class Solution {
public:

    int numSquares(int n) {
        if(n<=0)
            return 0;

        vector<int> dp(n+1, INT_MAX);
        dp[0]=0;
        for(int i=1; i<=n; i++) {
            for(int j=1; j*j<=i; j++) {
                //+1 because you are adding the current `j`
                dp[i]=min(dp[i], dp[i-j*j]+1);
            }
        }

        return dp[n];
    }
};

我不确定,因为在内循环中,我们正在检查小于的完美正方形i,与i(和我认为那么少,可以假设它们不变)相比,这将是非常少的.在这种情况下,复杂性将是公正的O(n).那么,我可以说复杂性是O(n)或是O(n^2)吗？

注意:代码片段是来自LeetCode.com的问题的解决方案,显然有一系列面试问题.