问题1：岛屿个数（dfs）

问题2：有向图最短路径（引导我用动态规划解决）

问题3：问我对NP和P问题的看法

问题4：哥德巴赫猜想、四色猜想

问题5：无序数组第k大的元素，要求给出最低时间复杂度的方法以及推导时间复杂度

题干：给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

样例：grid=[["1","1","1"],["0","1","0"],["1","0","0"],["1","0","1"]]

参考代码如下：

每次找到离源点最近的一个点，以该点为中心，更新源点到其他源点的最短路径，贪心的思想。

参考代码：

解释1：

最简单的解释：

P：算起来很快的问题

NP：算起来不一定快，但对于任何答案我们都可以快速的验证这个答案对不对

NP-hard：比所有的NP问题都难的问题

NP-complete：是NPhard的问题，并且是NP问题

解释2：

通俗的讲，P就是能在多项式时间内解决的问题，NP就是能在多项式时间验证答案正确与否的问题。所以P是否等于NP实质上就是在问，如果对于一个问题我能在多项式时间内验证其答案的正确性，那么我是否能在多项式时间内解决它。再说说NP-hardness和NP-completenes.这里涉及一个概念，不妨称为问题之间的归约。

可以认为各个问题的难度是不同的，表现形式为，如果我可以把问题A中的一个实例转化为问题B中的一个实例，然后通过解决问题B间接解决问题A，那么就认为B比A更难。通过对归约过程做出限制可以得到不同类型的归约。复杂度理论里经常用到的规约叫polynomial-timeKarp'reduction。其要求是转化问题的过程必须是多项式时间内可计算的。到这为止NP-hardness和NP-completeness就很好理解了。

称问题L是NP-hard，如果任意一个NP的问题都可以多项式规约到L。如果一个NP-hard的问题L本身就是NP的，则称L是NP-complete。这个定义可以推广到所有复杂度类。所以compleness的直观解释就是，我能解决这个问题就相当于具备了用相同级别的计算资源解决这个复杂度类里所有问题的能力。

验证“哥德巴赫猜想”，即：任意一个大于2的偶数均可表示成两个素数之和数学领域著名的“哥德巴赫猜想”：

任何一个大于2的偶数总能表示为两个素数之和；将一个偶数用两个素数之和表示的方法，等于同一横线上，蓝线和红线的交点数。数值验证：

1938年，尼尔斯·皮平（NilsPipping）验证了所有小于10^5的偶数。

1964年，M·L·斯坦恩和P·R·斯坦恩验证了小于10^7的偶数。

1989年，A·格兰维尔将验证范围扩大到10^10。

1993年，验证了10^11以内的偶数。

2000年，JörgRichstein验证了10^14内的偶数。

截至2014年，数学家已经验证了10^18以内的偶数，在所有的验证中，没有发现偶数哥德巴赫猜想的反例。

下面用Python进行验证：

思路：对于偶数M，遍历0~M，判断x~[0,M]是否是素数，若是素数则判断M-x是否是素数，若是则找到一个要求的答案：

假设M=100

思路：快排中partition

思想：对于某个索引j，nums[j]经过partition操作：nums[left]到nums[j-1]中的所有元素都不大于nums[j]；nums[j+1]到nums[right]中的所有元素都不小于nums[j]即nums[j]元素的位置是排序好了的，我们判断索引j是否满足条件，若满足则直接返回结果，若不满足我只需要遍历左序列或者右序列，直至满足要求；无需对整个序列进行排序，所以减少了计算量；

参考代码：

复杂度分析：时间复杂度：O(N)，这里N是数组的长度空间复杂度：O(1)，原地排序没有借助额外的辅助空间。