刷题笔记

2022-09-11 阅读数:0次

leetcode

二分

找满足条件下标

题目35. Search Insert Position
- 题意：在一个不重复的数组里，如果有数字a，返回下标，没有返回插入位置
- 思路1：二分查找，左闭右开区间
  - 时间复杂度：logn
  - 空间复杂度：1
- 错误思路：
  - 思路1，左闭右开时，判断条件不要写等于。没有时，返回的是left端点。

矩阵搜索

题目74. Search a 2D Matrix
- 题意：矩阵每行从左到右升序，并且每行首位比商议后末位要大，求target是否在矩阵里。
- 思路1：遍历行再遍历列。找到比target小的最大行，然后依次遍历该行。
  - 时间复杂度：n+m
  - 空间复杂度：1
- 思路2【最优】：二分查找。先按行找大于target的行号，行号-1就是所求行，此时注意判断是否为-1，即没有满足的行。然后按列找大于target的列号。两次都是闭区间查找[0,n-1], 判断条件是i<=j，每次i=mid+1, j=mid-1，最后i需要-1。
  - 可以先用upper_bound，再用binary_search
  - 时间复杂度：logn+logm=log(nm)
  - 空间复杂度：1

二叉树

知识

X序遍历指遍历根节点顺序

二叉树+dfs

题目98. Validate Binary Search Tree
- 题意：给一颗二叉树，左子树需要比当前节点小，右子树需要比当前节点大，判断是否满足条件
- 思路1：从下到上回溯，每个节点的条件是左子树最大值lmx<当前节点<右子树最小值rmi，但是返回时，整个子树最小值为lmi，最大值为rmx，所以需要存储每个子树最小值和最大值
  - 时间复杂度：n
  - 空间复杂度：n
- 思路2：从下到上回溯，用指针存最大最小值，这样可以为nullptr，讨论方便点
- 思路3：从上到下，得到每个区间最小最大值，每个区间满足当前节点大于最小值，小于最大值
- 错误思路：
  - 只找左子树最大值和右子树最小值
  - search里search_max找左子树，search_min找右子树
题目124. Binary Tree Maximum Path Sum
- 题意：求树的最大的路径和
  - 思路1【最优】：后序遍历。一个外置变量记录最大路径，最大路径=max(当前节点，当前节点+左子树，当前节点+右子树，当前节点+左子树+右子树)。而子树=maxx(当前节点，当前节点+左子树，当前节点+右子树),不能算“当前节点+左子树+右子树”的情况。
    - 时间复杂度：n
    - 空间复杂度：n
  - 错误思路：
    - 计算当前节点时，算了“当前节点+左子树+右子树”的情况。
题目297. Serialize and Deserialize Binary Tree
- 题意：将二叉树进行序列化成字符串和反序列化
- 思路1【最优】：先序遍历序列化+list或者queue辅助建树。通过先序遍历转成字符串，再从左到右顺序遍历字符串建树。注意子树是null时，字符串需要输出null。使用list或者queue建树，用vector会超时。
  - 时间复杂度：n，其中n是树的节点数
  - 空间复杂度：n，其中n是树的节点数
- 错误思路：
  - 思路1中，子树没有输出null
  - 思路1中，错误以为是idx+1,idx+2表示左右子树，这是层次遍历，先序遍历得到的字符串是从左到右
  - 思路1中，建树时按照’,'截断时，没有加入最后一个节点
  - 思路1中,使用vector导致超时
题目226. Invert Binary Tree【水题】
- 题意：翻转二叉树
- 思路1：dfs，每个节点交换左右子树
  - 时间复杂度：n
  - 空间复杂度：n
题目543. Diameter of Binary Tree【水题】
- 题意：求二叉树的直径
- 思路1：dfs，返回左右子树最大高度max(l, r) + 1;，用一个数字维护直径max(ans, l+r)
  - 时间复杂度：n
  - 空间复杂度：n
题目114. Flatten Binary Tree to Linked List
- 题意：将二叉树按照先序遍历展开为单链表
- 思路1：一边dfs一边展开。dfs遍历完左子树和右子树时，得到leftb, lefte, rightb, right分别指向左子树起点、展开好的左子树链表末尾、右子树起点、展开好的左子树链表末尾。如果leftb不为空，则该节点的左子树设为空，右子树为leftb，lefte->right=rightb。此时，如果右子树不为空，则返回righte, 否则如果左子树不为空，则返回lefte，否则返回root。
  - 时间复杂度：n
  - 空间复杂度：n
- 思路2：先先序遍历存储节点，再连起来。
  - 时间复杂度：n
  - 空间复杂度：n
- 思路3：迭代版，先先序遍历存储节点，再连起来。用stack存储节点，每次左孩子入栈，左边为空时，栈顶出栈it, 然后遍历右孩子，继续循环。
  - 时间复杂度：n
  - 空间复杂度：n
- 错误思路：

链表

双向链表

题目146. LRU Cache
- 题意：一个缓存器，n大小，有get(key)和put(key, val)操作，缓存器缓存最新的key和对应value, get和put也会影响时间，需要在o1时间完成get和put操作
- 思路1：双向链表可以在o1时间移动已缓存key，表尾表示最新操作，用map记录每个key的指针，需要讨论的情况
  - get：目标key前后都有节点，目标key在表头，需要移动到表尾; 目标key在表尾无影响; 只有一个节点无影响
  - put: 新key, 第一个节点; 新key, 当前链表长度小于n, 直接放在表尾; 新key, 当前链表长度大于等于n, 弹出表头，新节点直接放在表尾，同时去掉map，注意长度为1的情况; 旧key, 直接调用get, 更新val就好
  - 注意的坑：指针移动顺序，前后节点对应关系，前后指针是否为空，不要断链，首尾指针位置, 单节点，空节点
  - 时间复杂度：1 【还是会超时】
  - 空间复杂度：n
- 思路2：用list实现双向链表
- 错误思路：
  用queue维护，无法再o1时间移动已在队列的key

链表合并

题目23. Merge k Sorted Lists
- 题意：给k个升序排序的链表，求合起来升序排序的链表
- 思路1：一个个选。用一个指标数组存每个链表位置，一个头指针和尾指针保存合起来结果，每次取k个链表最小值更新到尾指针
  - 时间复杂度： $kn$ ,n是全部节点总和
  - 空间复杂度：k
- 思路2：一个个选。一个头指针和尾指针保存合起来结果，每次取k个链表最小值更新到尾指针，同时更新最小值的链表往后移，不会断链因为有head
  - 时间复杂度： $kn$ ,n是全部节点总和
  - 空间复杂度：1
- 思路3：一条条合并
  - 时间复杂度： $kn$ ,n是全部节点总和
  - 空间复杂度：1
- 思路4：优先队列
  - 时间复杂度： $nlogk$ ,n是全部节点总和
  - 空间复杂度：k
- 思路5：归并，merge函数拆分k组，merge2lists函数合并两个链表【难想】
  - 时间复杂度： $nlogk$ ,n是全部节点总和
  - 空间复杂度：1，但是需要 $logk$ 栈空间
- 思路6【最优】：归并+非递归，merge2lists函数合并两个链表, 用循环优化拆分不需要递归【难想】
  - 时间复杂度： $nlogk$ ,n是全部节点总和
  - 空间复杂度：1

链表交换位置

题目24. Swap Nodes in Pairs
- 题意：交换链表每两个相邻的节点
- 思路1：指针。一个指针A指向当前节点，一个指针B指向下一个节点，交换位置后，指针A移动2个节点位置，指针B需要连接此时指针A的下一个位置
  - 注意节点大于2返回的是head->next
  - 上一个交换位置需要和下一个交换位置建立连接，否则断链
  - 时间复杂度：n
  - 空间复杂度：1
- 错误思路：
  - 没有交换节点，只换数值
  - 思路1中，两个交换位置没有连接，造成断链

图

知识

bfs时间复杂度是o(n+e)

图+dfs

题目130. Surrounded Regions
- 题意：给定一个200x200图，如果’O’完全被’X’包围，则把’O’变成’X’
- 思路1：
  vis表示一个点属于哪个连通图。只进入’O’点，枚举四个方向，该方向越界就标记false，如果该方向是’O’点且没有遍历过就继续dfs，最后判断该点有问题，返回false。跑完一个连通图后，如果当前连通图为true，则把’O’变成’X’
  - 时间复杂度：nxm
  - 空间复杂度：nxm
- 思路2：
  从边界找到’O’的连通图，这些连通图不需要修改
- 错误思路：
  vis表示一个点是否有问题。只进入’O’点，枚举四个方向，该方向越界就返回false，如果该方向是’O’点且已知有问题就返回false，如果该方向是’O’点且没有遍历过就继续dfs，最后判断该点有问题，返回false。
  这种没有遍历完连通图就剪枝做结论返回，容易前一个分支一开始可行，但后面分支发现不可行，没办法更新。
题目212. Word Search II
- 题意：给一张图和一组单词，求出在图的单词，单词间可重叠
- 思路1【超时】：dfs。枚举单词，再枚举起始位置，每次做dfs, dfs之前vis=1, dfs之后vis=0，这样失败路径的节点可以再访问。
  - 时间复杂度：不会算
  - 空间复杂度：不会算
- 思路2【可以】：dfs+剪枝路径长度+删除已匹配单词。举起起始位置，每次做dfs, dfs之前vis=1, dfs之后vis=0。dfs时路径长度不超过单词最长值。用unordered_set存储字典单词，如果路径在set里，更新结果。同时需要删除set中的单词，否则会重复。
  - 时间复杂度：不会算
  - 空间复杂度：不会算
- 思路3【可以】：dfs+剪枝前缀+删除已匹配单词。枚举起始位置，每次做dfs, dfs之前vis=1, dfs之后vis=0。【也可以不用vis,直接原来地图设置成#】一个unordered_map a记录单词列表的全部前缀，如果遍历不在前缀里return，一个unordered_map b记录是否找到单词，找到则删掉单词在a的前缀。
  - 时间复杂度：不会算
  - 空间复杂度：不会算
- 思路4【最优】：dfs+剪枝前缀+字典树+删除已匹配单词。枚举起始位置，每次做dfs, dfs之前vis=1, dfs之后vis=0。【也可以不用vis,直接原来地图设置成#】。字典树记录单词列表，如果遍历不在则return，同时字典树记录要找的单词，找到且后面没有child，则在字典树删掉该字母。
  - 时间复杂度： $m \times n \times 3^{l-1}$ ，需要遍历 $m \times n$ 个单元格，每个单元格在最坏情况下仍需要遍历 $4 \times 3^{l-1}$ 条路径
  - 空间复杂度： $k \times l$ ，其中 k是单词个数，l是最长单词的长度。最坏情况下，需要 $k \times l$ 存储前缀树
- 错误思路：
  - 枚举单词，再枚举起始位置，每次做bfs, vis存储访问状态，这样会导致失败路径的节点无法再访问
  - 思路2，用set存储dfs时遍历到的前缀，这样预处理结果，set插入会超时。没有删掉set中单词，导致重复。
  - 思路3，没有使用unordered_map，find时间复杂度是n，导致超时。
  - 思路3，剪枝前缀，但没有删掉已经找到单词的前缀，超时。
  - 思路4，删掉已找到单词时，要判断是否有child再删

图+最短路

题目127. Word Ladder
- 题意：给开始字符串s1、结尾字符串sk、字符串字典d，求s1->s2->sk的最短路径，si和si+1只能修改一个字符，其中s2到sk必须在字典里.n<=5000，c<=10。
- 思路1【超时】：广度优先搜索+预处理图关系。用二维数组mp[n][n]记录字典中si和sj是否存在路径,同时判断s1和sk是否在字典中，sk不在return 0。用queue广度优先搜素，先放入s1（如果s1不在字典则放入s2)。用vis[n]记录是否遍历过, pair记录路径长度。每次取队首，用mp判断是否有路径，加入队尾。
  - 时间复杂度： $n^2c$
  - 空间复杂度： $n^2$
- 思路2【超时】：广度优先搜索+不预处理图关系。判断s1和sk是否在字典中，sk不在return 0。用queue广度优先搜素，先放入s1。用vis[n]记录是否遍历过, pair记录路径长度。每次取队首，遍历字典选有路径的单词，加入队尾。
  - 时间复杂度： $n^2c$
  - 空间复杂度： $n$
- 思路3：广度优先搜索+不预处理图关系+枚举字符变化。判断s1和sk是否在字典中，sk不在return 0。map记录字典字符串和字典下标关系。用queue广度优先搜素，先放入s1。用vis[n]记录是否遍历过, pair记录路径长度。每次取队首的单词，按26个字母逐个替换字符，判断新单词是否在字典中，是就加入队尾。
  - 时间复杂度： $n*c*26$
  - 空间复杂度： $n*c$
- 思路4：广度优先搜索+枚举字符变化+合并map和vis和pair。判断s1和sk是否在字典中，sk不在return 0。map记录字典字符串和s1步数，初始为0。用queue广度优先搜素，先放入s1，map[s1]=1。每次取队首的单词，按26个字母逐个替换字符，判断新单词是否在字典中，是就加入队尾， map[sj]=map[si]+1。
  - 时间复杂度： $n*c*26$
  - 空间复杂度： $n*c$
- 思路5：广度优先搜索+虚拟节点。map建立节点字符串和id映射。对s1和字典中的字符串，枚举每个字符，扩充虚拟节点，然后建图vector<vector
  >。判断sk是否在映射中，sk不在return 0。vis记录步数，初始为-1。用queue广度优先搜素，先放入s1，vis[s1]=1。每次遍历虚拟节点，再遍历实节点，实节点加入队尾， vis[sj]=vis[si]+1。结果是vis[si]。
  - 时间复杂度： $n*c*c$ ，n*c个节点，判断是否相同需要c
  - 空间复杂度： $n*c*c$ , n*c个节点，字符串c大小
- 思路6【次优】：广度优先搜索+虚拟节点+queue放虚拟节点。map建立节点字符串和id映射。对s1和字典中的字符串，枚举每个字符，扩充虚拟节点，然后建图vector<vector
  >。判断sk是否在映射中，sk不在return 0。vis记录步数，初始为-1。用queue广度优先搜素，先放入s1，vis[s1]=1。每次遍历边，节点加入队尾， vis[sj]=vis[si]+1。结果是(vis[si]+1)/2。
  - 时间复杂度： $n*c*c$ ，n*c个节点，判断是否相同需要c
  - 空间复杂度： $n*c*c$ , n*c个节点，字符串c大小
- 思路7【最优】：双向广度优先搜索+虚拟节点+queue放虚拟节点。map建立节点字符串和id映射。对s1和字典中的字符串，枚举每个字符，扩充虚拟节点，然后建图vector<vector
  >。判断sk是否在映射中，sk不在return 0。
  - vis记录步数，初始为-1。用queue q从s1广度优先搜素，先放入s1，vis[s1]=1。
  - vis_记录步数，初始为-1。用queue q_从sk广度优先搜素，先放入sk，vis_[sk]=1。
  - 每次循环，前面遍历一层，加入队尾；后面遍历一层，加入队尾；如果前后都遍历过，返回(vis[si]+vis_[si])/2
  - 时间复杂度： $n*c*c$ ，n*c个节点，判断是否相同需要c
  - 空间复杂度： $n*c*c$ , n*c个节点，字符串c大小
- 错误思路：
  - 忽略s1不在字典情况

动态规划

最大最小dp+滚动数组

题目152. Maximum Product Subarray
- 题意：求一个数组的最大乘积区间，含负数和0
- 思路1：遍历数组，用滚动数组方式pn, fn记录前一个位置最大正数和最大负数，用p,f,z表示上一个位置是否有正数、负数、0结果。
  - 当前值为正数时，前一个有正数结果pn = pn * arr[i]; 前一个无正数结果pn = arr[i]; 前一个有负数结果，fn = fn * arr[i]。更新p,f值
  - 当前值为负数时，前一个有正数结果fn = pn * arr[i]; 前一个无正数结果fn = arr[i]; 前一个有负数结果，pn = fn * arr[i]。注意负数情况，需要分开存前一个和当前情况，避免覆盖。更新p,f值
  - 当前值为0时，p,f为false,z为true。
  - 最后取三者最大值。
  - 时间复杂度：n
  - 空间复杂度：常数
- 思路2：本质上用滚动数组方式保存正负数可以直接保存最大和最小值
  - 更新最大值：mx = max(mxarr[i], max(miarr[i], arr[i]))
  - 更新最小值：mi = min(mxarr[i], min(miarr[i], arr[i]))
  - 时间复杂度：n
  - 空间复杂度：常数
- 错误思路：
  - dp[i]表示含i的前面区间最大乘积，dp[i] = max(dp[i-1]*num[i], num[i]), 负数不能保证最大
题目64. Minimum Path Sum【水题】
- 题意：求矩阵起点到终点最短路径和
- 思路1：动态规划，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。注意边界00，i0，0j情况。注意矩阵为空情况。
  - 时间复杂度：n*m
  - 空间复杂度：n*m

贪心

区间问题

题目218. The Skyline Problem
- 题意：给出多个矩形建筑左端点、右端点和高（已经按照左端点从小到大排序），求天际线
- 思路1【最优，不是我想的】：扫描线+优先队列。建筑的左右端点排序，依次遍历。
  - 用优先队列，存储含当前位置建筑的最高的右端点。
  - 对于当前位置，右端点比它小或等于就出队列。等于是说明是建筑右边，不符合天际线定义。
  - 取队列的顶，如果高度和上一个天际线高度一致，说明冗余需要舍弃。否则加入结果。
  - 如果队列没有内容，说明是一堆建筑的右边，此时高度为0，也要判断和上一个天际线高度是否一致，一致说明冗余需要舍弃。否则加入结果。
  - 时间复杂度：nlogn，每个建筑最多需要出入队列一次，单次logn
  - 空间复杂度：n
- 错误思路：
  - 思路1，高度为0的时候没有判断是否冗余。建筑佑边缘没有pop。

最少步数

题目45. Jump Game II
- 题意：从当前位置i可以向前至多跳num[i]，求到位置n-1的最少步数
- 思路1：从后往前找可以到达终点的最远起点，相当于从前往后找可以到达终点的最近起点。然后更新终点，继续找起点
  - 时间复杂度：n*n
  - 空间复杂度：1
- 思路2【最优】：从前往后枚举0到n-2位置，求当前步数最远距离。维护可以达到最远的位置maxPos，end维护上一步最远距离。当i==end，即超过当前步数，更新end=maxPos。
  - 时间复杂度：n
  - 空间复杂度：1
- 错误思路：
  - dp做法，dp[i+j] = min(dp[i+j], dp[i]+1);
    - 时间复杂度：n*m
    - 空间复杂度：n
  - 思路2，从前往后枚举时，不应该算n-1位置。

字符串

字符串匹配

题目10. Regular Expression Matching【和题目44类似】
- 题意：求字符串s和模式串p（.表示匹配任意字符，*表示p前面字符的可以使用0-n次），是否匹配成功
- 思路1【最优】：动态规划。dp[i][j]表示s前 $s_{0...(i-1)}$ $s_{0 . . . (i - 1)}$ 字符和p前 $p_{0...(i-j)}$ $p_{0 . . . (i - j)}$ 字符是否匹配
  - 需要设dp[0][0] = true
  - 注意：i=0时，s是空串，但是p为a*和.*也可以匹配
    - dp[i][j] = dp[i][j-2], p[j-1] == *
  - 当p[j-1]不是’*'时
    - s[i-1]和p[j-1]相等时，或者p[j-1]是.时, dp[i][j]=dp[i-1][j-1]
    - 否则为false
  - 当p[j-1]是’*'时【难想】
    - p[j-2]==s[i-1]时，或者p[j-2]是.时
      - *取0次，dp[i][j]=dp[i][j-2]
      - *取N>0次，dp[i][j]=dp[i-1][j]
    - 否则，*取0次，dp[i][j]=dp[i][j-2]
  - 时间复杂度：nm
  - 空间复杂度：nm
- 错误思路：
  - 没用考虑s为空串情况
  - dp[i][j]没用预留边界情况位置，导致后面讨论情况太多
  - .情况相当于增加一种等于情况，不需要分开讨论
题目44. Wildcard Matching【和题目10类似】
- 题意：求字符串s和模式串p（？表示匹配任意字符，*表示匹配任意字符串，含空串），是否匹配成功
- 思路1：动态规划。dp[i][j]表示s前 $s_{0...(i-1)}$ $s_{0 . . . (i - 1)}$ 字符和p前 $p_{0...(i-j)}$ $p_{0 . . . (i - j)}$ 字符是否匹配
  - 需要设dp[0][0] = true
  - 注意：i=0时，s是空串，但是p为*可以匹配
    - dp[i][j] = dp[i][j-1], p[j-1] == *
  - 当p[j-1]不是’*'时
    - s[i-1]和p[j-1]相等时，或者p[j-1]是？时, dp[i][j]=dp[i-1][j-1]
    - 否则为false
  - 当p[j-1]是’*'时
    - *取空串，dp[i][j]=dp[i][j-1]
    - *匹配，dp[i][j]=dp[i-1][j]
  - 时间复杂度：nm
  - 空间复杂度：1
- 思路2【最优】：贪心。遍历s, jstar指向p连续的最后一个，istar指向s需要用的地方，非必要不用*，用*需回退【难想】
  - 当s[i]p[j]或p[j]’?'时
    - i++,j++
  - 当p[j]==’*'时，更新jstar=j，istar=i，j=jstar+1
  - 当不能匹配时
    - 如果之前有’*’，则退回使用，更新istar+=1，i=istar, j=jstar+1
    - 否则return false
  - 如果遍历完s，p还多余且不为*，则return false
  - 时间复杂度：nm
  - 空间复杂度：nm
- 错误思路：
  - 思路1
    - 没用考虑s为空串情况
    - dp[i][j]没用预留边界情况位置，导致后面讨论情况太多
    - ？情况相当于增加一种等于情况，不需要分开讨论
    - p[j-1]=*，直接dp[i][j]=true或者没考虑匹配空串情况
  - 思路2
    - 一定要遍历s，不可以使用 i < sn && j < pn
题目76. Minimum Window Substring
- 题意：求字符串s包含字符串t字母的最小字串，如果没有返回空串
- 思路1：map+滑动窗口。使用字典mp记录字符串s和t出现字母次数，用字典cnt记录当前窗口字母次数，用total表示满足cnt>=mp字母个数。i指向窗口开始，j指向窗口末尾。i和j先指向s中第一个t字母出现位置。移动j:
  - 如果不是t字母跳过
  - 是t字母,cnt+=1
    - 如果该字母cnt==mp则total+=1
    - 如果cnt>mp且i和j指向字母相同，i右移，此时不是t字母和cnt>mp多出来的都可以不要
  - 如果total达到t非重复字母个数，说明该窗口满足，更新结果
  - 时间复杂度：2s，s为字符串s长度
  - 空间复杂度：n,n为字符集合
- 思路2【最优】：在思路1基础上，处理s中非t元素
- 错误思路：
  - 思路1中只用一个map处理

字符串拆分

题目140. Word Break II
- 题意：给一个字符串S和一组单词，求s拆成单词的所有情况
- 思路1：dfs。用map存储单词。从位置st开始枚举当前拆分位置，如果可以拆分，则继续dfs后面的字符串。当前位置为n时，得到一种拆分情况。
  - 时间复杂度： $n^n$ ,n是字符串长度
  - 空间复杂度：
- 思路2【最优】：记忆化dfs。用set存储单词，map[i]存储 $S_{i...n-1}$ $S_{i . . . n - 1}$ 的拆分情况。从位置st开始枚举当前拆分位置i，如果可以拆分，则继续dfs后面的字符串 $S_{i+1...n-1}$ $S_{i + 1 . . . n - 1}$ 。
  - 如果map[i+1]已经搜索过，则直接返回。
  - 如果当前位置为n时，map[n]={""}。
  - 如果map[i+1]有解，则map[st]的情况 += $S_{st...i}$ + map[i+1]的情况
  - 时间复杂度： $n*2^n$ ,写入 $n*2^n$ 的空间至少也需要 $n*2^n$ 的时间。
  - 空间复杂度： $n*2^n$ ,n是字符串长度,S的分隔方法由 $2^n$ 种，每种需要n存储空间。
- 错误思路：
  - 思路2的时候，忘记生成一种空情况，map[st]={}。

排序

改造排序函数+字符串比较

题目179. Largest Number
- 题意：给一串数字，求拼起来最大值
- 思路1：数字首字符不同时越大越早拼装，相同时需要考虑拼接后情况：3 > 31, 32 > 3, 35 > 3 > 304 ，因为两两拼接比较具有传递性，只需要两两拼接对比即可。
  - 时间复杂度：nlognlogm
  - 空间复杂度：logn
- 错误思路：
  - 容易忽略数字为0，拼起来为00的情况
  - 不需要按照1-9划分

排序+思维题

题目324. Wiggle Sort II
- 题意：给一组数字，要求排列成a0 < a1 > a2 < a3 …形式
- 思路1：当数组相同元素个数不超过floor((n+1)/2)时存在满足的排列。先按照从小到大排序，分奇偶从左往右计算
  - 偶数必然：a0+x > a0 < a1+x > a1 < ai+x > ai，只要倒转即可
  - 奇数必然：a0 < a1+x > a1 < a2+x > a2 < ai+x > ai
  - 其中，ai=(n-1)/2，ai+x=n-1
  - 时间复杂度：nlogn
  - 空间复杂度：n
- 思路2：在思路1基础上，可以统一奇数和偶数，从右往左计算
  - 偶数和偶数必然：（a0+x >） a0 < a1+x > a1 < a2+x > a2 < ai+x > ai
  - 其中，ai=(n-1)/2，ai+x=n-1
  - 时间复杂度：nlogn
  - 空间复杂度：n
- 错误思路：
  - 统计比当前数字大的有多少数字，按稀缺排序，情况太复杂

搜索

题目39. Combination Sum
- 题意：给一组因子，求用这些因子组合成target情况，可重复
- 思路1：dfs，dfs(int target, int tmp, vector
  & candidates, int idx, vector
  combine, vector<vector
  > &ans)，idx表示枚举到这个位置
  
  时间复杂度：O(S)，其中S为所有可行解的长度之和
  
  空间复杂度：O(target)，除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归target层。【不能理解】
- 错误思路：
  - python版本没有使用copy.deepcopy，导致pop的时候结果清空

单调栈

单调栈+求面积

题目84. Largest Rectangle in Histogram
- 题意：求柱状图最大矩形面积
- 思路1：左右两边分别遍历，al, ar数组分别存储当前节点j可以扩展的区间端点[al[j],ar[j]]，用单调栈维护端点。
  - 从左往右遍历时，如果stack为空，则al[j]=0；如果栈顶的高度>=j的高度，pop；如果栈顶比j的高度小，则al[j]=st.top()+1。
  - 从右往左遍历时，如果stack为空，则ar[j]=n-1；如果栈顶的高度>=j的高度，pop；如果栈顶比j的高度小，则ar[j]=st.top()-1。
  - 最后结果为heigths[j]*(ar[j]-al[j]+1)最大值。
  - 时间复杂度： $n$
  - 空间复杂度： $n$
- 思路2【最优】：遍历一遍同时更新al和ar。al, ar数组分别存储当前节点j可以扩展的区间端点[al[j],ar[j]]，用单调栈维护端点。
  - 从左往右遍历时，如果stack为空，则al[j]=0；如果栈顶的高度>=j的高度，更新ar[st.top()]=i-1，pop；如果栈顶比j的高度小，则al[j]=st.top()+1。
  - 如果此时st不为空，则ar[st.top()] = n-1, pop。
  - 最后结果为heigths[j]*(ar[j]-al[j]+1)最大值。
  - 时间复杂度： $n$
  - 空间复杂度： $n$
- 思路3：左右两边扩
  - 时间复杂度： $n^2$
  - 空间复杂度：1

模拟

模拟除法

题目166. Fraction to Recurring Decimal
- 题意：给两个数做除法，输出结果，循环节用括号括起来
- 思路1：长除法。
  - 先判断负号
  - 判断是否有整除, 结果是否为0
  - 用map判断余数是否相同，来判断是否循环
  - 时间复杂度：n
  - 空间复杂度：n
- 错误思路：
  - 忘记0，0.2情况

思维题

题目41. First Missing Positive
- 题意：求一个数组里缺少的第一个正数，要求on时间，o1空间
- 思路1：先把数组里的负数和0设置为N+1,然后把arr[i]=1-N时的arr[arr[i]-1]设为负数，注意绝对值，结果就是第一个不是负数的i+1
  - 时间复杂度：n
  - 空间复杂度：1
- 错误思路：
  - map+扫一遍需要n空间
题目31. Next Permutation
- 题意：求当前排列的下一个排列，下一个排列是指其整数的下一个字典序更大的排列
- 思路1：两遍扫描。后面都是递减，从后往前找第一个num[idx-1]小于等于num[idx]的位置
  - 如果这个位置是0，说明下一个排列是初始位置，前后往中间交换位置
  - 如果这个位置不是0，则在idx以及后面找比num[idx-1]大的最小值，并和num[idx-1]交换，再将idx以及后面的数从小到大排序。因为是降序，前后往中间交换位置即可。
  - 时间复杂度：n
  - 空间复杂度：1
- 错误思路：
  - 思路1，在idx以及后面找比num[idx-1]大的最小值时，错误地从前往后找。其实idx以及后面都是从大到小排序，直接从后往前找第一个大于num[idx-1]的值即可，不能等于。
  - 思路1，将idx以及后面的数从小到大排序时，使用排序，忽略了本身是降序。
  - 思路1，num[idx-1]小于等于num[idx], 少了等于

模板

题目
- 题意：
- 思路1：xx
  - 时间复杂度：
  - 空间复杂度：
- 错误思路：
  - xx