leetcode977.有序数组的平方

核心思想：双指针

链接：977. 有序数组的平方 - 力扣（LeetCode）

方法一：暴力解法

1. 思路

最直观最直接的想法是，将数组中的每个数都平方，然后排序。

2.代码实现

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 遍历数组，将每个数组中的元素平方
        for i in range(len(nums)):
            # Python中可以用 nums[i] ** 2 表示平方
            nums[i] = nums[i] * nums[i]
        # 直接可以用Python自带的函数去排序
        nums.sort()
        return nums

3.复杂度分析

每个数都平方的复杂度是O(N)，排序的复杂度的O(NlogN)，所以总体的复杂度是O(N+NlogN) = O(NlogN)。

4. 思考

（1）排序使用了Python的库函数，比较sort（）和sorted（）

• sort是对原有列表进行操作，而sorted返回的是一个新的可迭代对象，不会改变原来的对象；
• sort使用方法为list.sort()， 而sorted的使用方法为sorted(list)

方法二：双指针法

1.思路

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

2. 代码实现

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        # 初始化容纳结果的数组result
        result = [0]*length
        # 初始化指针i和j,分别指向nums数组的两头
        i = 0
        j = length -1
        # 初始化k指针，指向result数组的最后一位
        # 因为i和j比较是选出目前最大的元素
        # 所以k应该从result的最后一位开始更新
        k = length -1
        # 循环条件有=号的原因是，当没有的时候，i=j指向的元素会被遗漏
        while i<=j:
            leftMax = nums[i] ** 2
            rightMax = nums[j] ** 2
            # 这时候说明左边的比右边的指针大，更新数组result之后，i指针向右挪动一位
            if leftMax > rightMax:
                result[k] = leftMax
                i += 1
            else:
                # 这时候说明右边的比左边的指针大，更新数组result之后，j指针向左挪动一位
                result[k] = rightMax
                j -= 1
            # 不论哪种情况，K指针都要向前挪动一位
            k -= 1
        return result

3. 复杂度分析

此时的时间复杂度为O(n)，相对于暴力排序的解法O(n + nlog n)还是提升不少的。

4. 思考

（1）数组其实是有序的，在暴力解法中就没有用到这一个特点。

（2）一开始我想到了把两个指针放在中间的相邻位置，分别是正数和负数的分界处的两边，然后一个向左，一个向右，比较，把最小的元素逐个放进result中去，但是找这个初始化的指针也是一个比较复杂的过程，没想到可以直接初始化到两头，找最大值，然后分别向中间遍历一遍！！

（3）可以直接将结果数组从后往前填结果，不用得到结果了再反转过来。

本题学习时间：95分钟

LeetCode209. 长度最小的子数组

链接：209. 长度最小的子数组 - 力扣（LeetCode）

方法一：暴力解法

1. 思路

这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度是O(n^2)

2层for循环进行遍历：第一层for循环控制区间的起始位置，第二层for循环控制区间的终止位置。

把数组的所有区间情况都遍历出来，然后找到 >= target 的最小区间长度。 在这个区间里面不断搜索，把所有区间情况都枚举出来，然后判断 >= target 的最小长度是多少，最后返回这个最小长度。

具体实现方法是这样：定义一个result，是最终的结果；定义currentSum,为目前的元素之和；定义currentLens,为子数组的长度。第一个循环，是子数组的起点位置，所有位置都需要遍历一遍的。第二个循环是子数组的终点位置，持续从前往后累加，一旦发现currentSum满足targrt数值之后，算出目前数组的长度，然后更新result的值。如果result仍然是之前的赋值，则返回0，否则返回result。

2. 代码实现

# 暴力解法
# time:O(N^2);space:O(1)
# leetcode执行会超出时间限制
class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        currrentSum = 0
        currentLen = 0
        # 结果先初始化为最大值
        result = float("inf")
        # i为区间的起始位置
        for i in range(length):
            currrentSum = 0
            # j 为区间的终点位置，从i开始向后遍历，找到满足要求的最小长度
            for j in range(i,length):
                currrentSum += nums[j]
                # 找到了满足要求的区间，更新result，然后跳出当前循环
                # 因为再往后，虽然也可能会满足要求，但是长度一定比之前长
                if currrentSum >= target:
                    currentLen = j-i+1
                    result = min(result,currentLen)
                    break
        # 这里必须要加上这个判断条件，因为可能全部长度加起来都不满足sum>=target
        # result 仍然是默认值
        if result == float("inf"):
            return 0
        else:
            return result

3. 复杂度分析

起始位置的指针i从数组的第一个开始遍历，一共会遍历N个数组元素；终止位置的 j 在每个 确认的 i 值之下， 往后遍历所有的可能性，所以时间复杂度是O(N^2)；空间上只有常数个变量，因此空间复杂度为O(1)。

4. 思考

（1）关于result的初始值，首先因为result = min(result,currentLen)，所以设置0和-1是不合理的。应该设置为一个尽可能大的值，所以设置为float（“inf”)，最后需要加上if-else逻辑去return。

（2） 暴力解法在LeetCode中会超时。

（3）这题说了是连续最小数组，暴力法穷举了所有组合，所以多了很多不必要的计算。

方法二：滑动窗口

1. 思路

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

用一个for循环来做2个for循环所做的事情。

思考：这个索引下标 j 表示的究竟是滑动窗口里面的终止位置还是起始位置？

可以先假设 j 表示的是起始位置，

若 j 表示的是起始位置，这个for循环一次一次把索引下标向后移动，这个终止位置要把后面所有的元素遍历一遍，才能返回所有以这个起始 i 为起始位置的集合，然后我们再去判断这个集合里面的所有元素:

如果 >= target，去搜集所有 >= target这些集合里面的所有的长度，再取一个最小的。 如果终止位置是一个一个向后移动的话，那么和这个暴力的解法又存在什么区别呢？

此时你会发现：如果这一个for循环里面的这个j表示的是起始位置的话，那终止位置依然要把所有位置都遍历一遍，那么它的思路就和暴力是一样的。

因此这一个for循环里面的j一定指向的是终止位置，而起始位置需要我们用动态移动的策略来移动起始位置，这样才能用一个for循环的思路来解决这道题。

滑动窗口解题的关键：窗口的起始位置如何移动？

终止位置随着for循环一个一个向后移动，那什么时候移动起始位置？

如果我们的终止位置指向这里，这个集合里面的元素之和如果 >= target 的话，说明这是符合条件的一个集合，我们收集它的长度之后，起始位置就可以向后移动了。

从而缩小当前这个集合，看下一个集合是否符合我们的条件。

就是当我们发现集合里面所有的元素和 >= target，我们再去移动起始位置，这样就实现了动态调整起始位置，来去收集不同长度区间里面的和。

sum收集滑动窗口里面的和

我们需要有一个集合，通过这个集合里面的元素之和来和target做比较，

res是最终取的最小的长度。

应该写if(sum >= target) 还是 while(sum >= target)？

如果你写的是if，看看这个样例： 输入：target = 100, nums = [1,1,1,1,1,100]

举个例子：

这里还是以示例来举例，来看一下查找的过程：

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

2. 代码实现

# 双指针解法
# time:O(N)；space:O(1)
class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        currrentSum = 0
        currrentSum = 0
        # i 为滑动窗口的起始位置
        i = 0
        result = float("inf")
        # j是滑动窗口的终止位置，遍历一遍所有终止位置
        for j in range(len(nums)):
            currrentSum += nums[j]
            # 当前满足要求之后，试着将起始位置往后挪，
            # 看看是否可以得到长度更短的且满足要求的区间，因此用while
            while (currrentSum >= target):
                currrentLen = j-i+1
                result = min(result,currrentLen)
                currrentSum -= nums[i]
                i += 1
        # 仍然要记得判断result是否仍然为初始值
        return 0 if result == float("inf") else result

3. 复杂度分析

每个元素在滑动窗后进来操作一次（每次常数个指令），出去操作一次，每个元素都是被被操作两次，所以时间复杂度是 2 × n 也就是O(n)。（不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数）

4. 思考

（1）本质是满足了单调性,即左右指针只会往一个方向走且不会回头。收缩的本质即去掉不再需要的元素。也就是做题我们可以先固定移动右指针，判断条件是否可以收缩左指针算范围。

（2）滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)

本题学习时间：70分钟

Leetcode59. 螺旋矩阵II

链接：59. 螺旋矩阵 II - 力扣（LeetCode）

1. 思路

这道题目可以说在面试中出现频率较高的题目，本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

由外向内一圈一圈这么画下去。

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开又闭的原则，这样这一圈才能按照统一的规则画下来。

那么我按照左闭右开的原则，来画一圈，大家看一下：

2. 代码实现

注意1：原则是左闭右开区间，贯彻到底，包括循环的条件，绘制每条边的循环条件，但是也有遗漏下的，就是N为奇数的时候，最中心的那个元素会被漏下，因此最后循环结束的时候，需要补上那个。

注意2：Python写法 matrix = [[0]n for _i in range(n)] 创造了一个NN的正方形矩阵，全为0，例如N=3的时候，就是[[0,0,0],[0,0,0],[0,0,0]]。

注意3：Python写法for x in range (2,0,-1)；遍历的x 为2,1就这样。

# 纯纯的模拟转圈，但是有很多边界条件容易出错
# 如果给的是N的话，time：O(N^2)；space：O(N^2)

class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """ 
        matrix =  [[0]*n for _ in range(n)] # matrix = [[0]*n]*n
        # 初始化左指针，右指针，上指针，下指针
        left = 0
        right = n-1
        up = 0
        down = n-1
        # number是要随着矩阵的更新而逐渐增加的，初始化为1
        number = 1
        # 循环条件之所以没有等于号是因为本题也贯彻循环不变量思想
        # 区间为左闭右开，如果left=right的话，这个区间没有意义
        while left < right and up<down :
            # 从第一行开始填起，从左到右，左闭右开，最开头的填上，最末尾的不填
            for x in range(left,right):
                matrix[up][x] = number # 要注意在二维数组里面的索引
                number += 1
            # 最右竖列，从上到下，最开头填上，最末尾不填，左闭右开
            for y in range(up,down):
                matrix[y][right] = number
                number += 1
            # 最下面一行，从右到左，最开头填上，最末尾不填
            # 注意这里写range(大的数，小的数，-1)，小的数不会包括，开区间
            for x in range(right,left,-1):
                matrix[down][x] = number
                number += 1
            # 最左边一列，从下到上，最开头填上，最末尾不填
            for y in range(down,up,-1):
                matrix[y][left] = number
                number += 1
            # 换到下一个内圈
            left += 1
            right -= 1
            up += 1
            down -= 1
        # 如果N为奇数的话，那么最后会漏掉最中间的一个数，这里做一个判断，然后补上
        if n%2: matrix[n//2][n//2] = number
        return matrix

3. 复杂度分析

给的参数是N，while循环做的事情就是遍历一遍二维数组，所以时间复杂度为 O(n^2)，该二维数组需要生成，故空间复杂度也是 O(n^2)

4. 思考

（1）使用列表推导式生成数组需注意：

• 生成一维数组：[0] * n 或者 [0 for _ in range(n)]
• 生成二维数组：[[0] * m for _ in range(n)] 或者 [[0 for _ in range(m)] for _ in range(n)]

注意还有一种也可以生成二维数组的方法是 [ [0]*n ]*n ，但是这种方法，会保持二维数组中的每行一维数组一直保持一致，这次开始写的时候一开始就定义错了，导致找了很久的bug。

>>> matrix = [[0]*3]*3
>>> matrix
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> matrix[0][0] = 1
>>> matrix
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]

>>> matrixB = [[0]*3 for _ in range(3)]
>>> matrixB
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> matrixB[0][0] = 1
>>> matrixB
[[1, 0, 0], [0, 0, 0], [0, 0, 0]]
>>>

（2） 要使用range()函数逆序遍历需注意：

注意这里写range(大的数，小的数，-1)，小的数不会包括，开区间

（3） 本题的关键点是要贯彻循环不变量思想，坚持每条边的处理方式一致，不重复处理。

本题学习时间：100分钟