代码随想录算法训练营第二天｜977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 代码随想录算法训练营第二天｜977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II",
   "id": "123ecedf2b232839"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 977.有序数组的平方 \n",
    "\n",
    "题目建议： 本题关键在于理解双指针思想 \n",
    "\n",
    "题目链接：https://leetcode.com/problems/squares-of-a-sorted-array/  \n",
    "文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html  \n",
    "视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep "
   ],
   "id": "283fa6dcdeae537e"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "__核心__：负数的平方会插到正数平方的队列中，需要比较确定插入位置。  \n",
    "第一想法：找到负数和正数的分界点，然后指针从分界点向两端移动，按从小到大顺序插入。  \n",
    "    问题：实现过于复杂，容易出错；特殊情况过多（全是负数、全是正数、一端结束后的处理）。  \n",
    "暴力解法：直接计算平方，然后排序。 `O(nlogn + n)`  \n",
    "正解思路：从**两端开始**比较，**从大到小**插入到数组的尾部。"
   ],
   "id": "92d6fd4a3942833b"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-05T08:14:16.261123Z",
     "start_time": "2024-07-05T08:14:16.254743Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def sortedSquares(self, nums: List[int]) -> List[int]:\n",
    "        l, r, i = 0, len(nums)-1, len(nums)-1\n",
    "        res = [float('inf')] * len(nums) # 需要提前定义列表，存放结果\n",
    "        while l <= r:\n",
    "            if nums[l] ** 2 < nums[r] ** 2: # 左右边界进行对比，找出最大值\n",
    "                res[i] = nums[r] ** 2\n",
    "                r -= 1 # 右指针往左移动\n",
    "            else:\n",
    "                res[i] = nums[l] ** 2\n",
    "                l += 1 # 左指针往右移动\n",
    "            i -= 1 # 存放结果的指针需要往前平移一位\n",
    "        return res"
   ],
   "id": "6ceaa7b4d13e7459",
   "outputs": [],
   "execution_count": 11
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "\n",
    "## 209.长度最小的子数组\n",
    "\n",
    "题目建议： 本题关键在于理解滑动窗口 \n",
    "\n",
    "题目链接：https://leetcode.com/problems/minimum-size-subarray-sum/  \n",
    "文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html  \n",
    "视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE\n"
   ],
   "id": "f3a7fcba9d00d71"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "注意：Subarray是连续的子数组，所以滑动窗口的核心是连续性。  \n",
    "暴力解法：双重循环，从小到大找出所有的子数组，当子数组的和大于等于目标值时返回。`O(n^2)`\n",
    "#### `O(n)`解法：\n",
    "1. 外循环：移动右指针，添加元素\n",
    "2. 内循环：移动左指针，找到最小的子数组\n",
    "3. 长度：`right - left + 1`：左闭右闭区间"
   ],
   "id": "c4a28ea777e91e2e"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def minSubArrayLen(self, s: int, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        left = 0\n",
    "        right = 0\n",
    "        min_len = float('inf')\n",
    "        cur_sum = 0 #当前的累加值\n",
    "        \n",
    "        while right < l:\n",
    "            cur_sum += nums[right]\n",
    "            \n",
    "            while cur_sum >= s: # 当前累加值大于目标值\n",
    "                min_len = min(min_len, right - left + 1)\n",
    "                cur_sum -= nums[left]\n",
    "                left += 1\n",
    "            \n",
    "            right += 1\n",
    "        \n",
    "        return min_len if min_len != float('inf') else 0"
   ],
   "id": "3198dcd74fab76b5"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "#### 尝试：\n",
    "1. 只移动右指针，找到第一个满足条件的子数组，返回0如果没有找到。\n",
    "2. 子数组的和大于等于目标值时，移动左指针，找到最小的子数组，更新最小值；小于目标值时，移动右指针。  \n",
    "缺点：特殊情况处理复杂，容易出错。  \n",
    "改进处：将左右指针的移动分开判断，因为左指针的移动是有条件的，右指针的移动是无条件的（必须遍历）。"
   ],
   "id": "fc52ab0a297dbdff"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def minSubArrayLen(self, target: int, nums: List[int]) -> int:\n",
    "        total, tail, head,size, diff = 0,0,0,0,0\n",
    "        while total < target and tail < len(nums):\n",
    "            total += nums[tail]\n",
    "            tail += 1\n",
    "            size += 1\n",
    "        if tail == len(nums) and total < target:\n",
    "            return 0\n",
    "        end = False\n",
    "        while end == False or diff != tail - head:\n",
    "            diff = tail - head\n",
    "            if total >= target:\n",
    "                size = min(size, diff)\n",
    "                total -= nums[head]\n",
    "                head += 1\n",
    "            elif total < target:\n",
    "                if tail < len(nums):\n",
    "                    total += nums[tail]\n",
    "                    tail += 1\n",
    "                else:\n",
    "                    end = True\n",
    "        return size"
   ],
   "id": "e836957c523aa6cf"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "提示的`O(nlogn)`解法：待补充",
   "id": "efe79e85f1799949"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 59.螺旋矩阵II\n",
    "\n",
    "题目建议：  本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。 \n",
    "\n",
    "题目链接：https://leetcode.com/problems/spiral-matrix-ii/  \n",
    "文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html  \n",
    "视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/\n"
   ],
   "id": "cb23025ae1f365f5"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "#### 二分法，循环不变量\n",
    "1. 按圈数循环，每次循环填充一圈：圈数为n//2，n为奇数时，最后一个位置单独填充\n",
    "2. 每次循环按右下左上的顺序填充，每个循环填充`n-1-圈数`个位置（每圈一共有'4*(边长-1)'个格子）\n",
    "3. 每圈起始位置沿主对角线移动\n",
    "4. 不随填充位置变化指针 --> 减少赋值次数（本题影响不大？）\n"
   ],
   "id": "7380375670ef4454"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-05T07:41:40.948478Z",
     "start_time": "2024-07-05T07:41:40.938342Z"
    }
   },
   "cell_type": "code",
   "source": [
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        nums = [[0] * n for _ in range(n)]\n",
    "        startx, starty = 0, 0               # 起始点\n",
    "        loop, mid = n // 2, n // 2          # 迭代次数、n为奇数时，矩阵的中心点\n",
    "        count = 1                           # 计数\n",
    "\n",
    "        for offset in range(1, loop + 1) :      # 每循环一层偏移量加1，偏移量从1开始\n",
    "            for i in range(starty, n - offset) :    # 从左至右，左闭右开\n",
    "                nums[startx][i] = count\n",
    "                count += 1\n",
    "            for i in range(startx, n - offset) :    # 从上至下\n",
    "                nums[i][n - offset] = count\n",
    "                count += 1\n",
    "            for i in range(n - offset, starty, -1) : # 从右至左\n",
    "                nums[n - offset][i] = count\n",
    "                count += 1\n",
    "            for i in range(n - offset, startx, -1) : # 从下至上\n",
    "                nums[i][starty] = count\n",
    "                count += 1                \n",
    "            startx += 1         # 更新起始点\n",
    "            starty += 1\n",
    "\n",
    "        if n % 2 != 0 :\t\t\t# n为奇数时，填充中心点\n",
    "            nums[mid][mid] = count \n",
    "        return nums"
   ],
   "id": "812010d4b9557267",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "execution_count": 9
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "#### 自己的尝试：\n",
    "1. 外循环条件：填充值\n",
    "2. 按右下左上的顺序填充至边界或者已经填充过的位置，每次走一圈\n",
    "3. 单独填充最后一个位置（原因：先填充后移动，判断循环条件时没进行填充）"
   ],
   "id": "ffd89a060af3450b"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-05T09:01:57.308191Z",
     "start_time": "2024-07-05T09:01:57.303257Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from typing import List\n",
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        matrix = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        i, j, k = 0,0,1\n",
    "        while k < (n**2):\n",
    "            while j < n - 1 and matrix[i][j+1] == 0:\n",
    "                matrix[i][j] = k\n",
    "                j += 1\n",
    "                k += 1\n",
    "            while i < n - 1 and matrix[i+1][j] == 0:\n",
    "                matrix[i][j] = k\n",
    "                i += 1\n",
    "                k += 1\n",
    "            while j > 0 and matrix[i][j-1] == 0:\n",
    "                matrix[i][j] = k\n",
    "                j -= 1\n",
    "                k += 1\n",
    "            while i > 0 and matrix[i-1][j] == 0:\n",
    "                matrix[i][j] = k\n",
    "                i -= 1\n",
    "                k += 1\n",
    "        matrix[i][j] = k\n",
    "        return matrix"
   ],
   "id": "d75ff16f2333d9a4",
   "outputs": [],
   "execution_count": 8
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "#### AI作答：\n",
    "1. 存储方向指针（0，1，-1）\n",
    "2. 如果下一个位置超出边界（用模避免outOfBounds)或者已经填充过（python直接用非0为True)，改变方向（正交：交换取负）"
   ],
   "id": "b4519138b68ea7f2"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "    def generateMatrix(self, n: int) -> List[List[int]]:\n",
    "        matrix = [[0] * n for _ in range(n)]\n",
    "        i, j, di, dj = 0, 0, 0, 1  # di, dj are directions for i and j\n",
    "        for k in range(1, n * n + 1):\n",
    "            matrix[i][j] = k\n",
    "            # Check if the next cell is out of bounds or already filled\n",
    "            if matrix[(i + di) % n][(j + dj) % n]:\n",
    "                # Change direction: right -> down -> left -> up\n",
    "                di, dj = dj, -di\n",
    "            i += di\n",
    "            j += dj\n",
    "        return matrix"
   ],
   "id": "d0d87c11bc9164f0"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 总结 \n",
    "\n",
    "文章链接：https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html \n"
   ],
   "id": "6d1c214260e0f813"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}