Leetcode

Set Matrix Zeroes

• 第一种

  • 通过一次遍历记录所有为0的索引(Python中enumerate()输出当前列表的索引)
  • 再遍历一次, 根据记录的索引进行置0

• 第二种

  • 通过一次遍历所有为0的索引, 设置当前索引的行列的第一个数为0, 作为标记, 如a[9][9]为0, 所以设置a[0][9],a[9][0]为0
  • 再遍历一次, 根据标识的索引进行置0

Min Stack

• 数据结构为两个栈, 一个记录最小值的栈, 一个是存放正常压栈数据

• 入栈的时候判断新加入的数是否小于或等于最小值栈里的top

• 出栈时判断出栈数字和最小栈里的是否相等

Evaluate Reverse Polish Notation

• 逆波兰的后半截实现

Linked List Cycle

• 快慢指针

Linked List Cycle II

• 快慢指针再加个初始指针

• 慢指针到链表开始位置时, 快指针总是比他快k步(每次移动快1步, 移动k次), 第一次相遇的时候快慢指针位置距离链表起始位置差k步即在n-k的位置(链表环长度为n)

Majority Element

• 多数投票算法

• 出现超过n/2次, 说明最多只有一个数(题中已假设一定存在这个数)

• 两个变量记录出现次数和当前值, 遍历到相同值就++, 不同就--, 为0就重新赋值, 超过n/2次的数存在的话出现次数一定大于0

Majority Element II

• 类似前一题

• 出现超过n/3次, 说明最多只有两个数(题中不一定存在这些数!)

• 类似前面, 不过注意赋值时两个变量存的数不一样才赋值

Jump Game II

• 贪心算法

• 一边遍历, 一边比较取最大的, 好像懂了....

Reverse Linked List II

• 反转链表

• 把链表看成三部分, 中间的部分反转, 然后和前面后面连起来

• 第一个节点作为pre节点(上一次操作节点), 第二个节点作为当前current节点, 然后可以拿到next节点, 将第二个节点(current)指向第一个节点(pre), 然后第二个节点就变成了pre节点了, next节点就是current节点了, 同理继续向下操作, 最后的时候, 注意头指针是指向反转后的链表的最后一个节点, 把头指针指向当前pre节点(反转前最后一个节点), 链表反转完成

• 注意特殊处理从第一个位置就开始反转的情况

Climbing Stairs

• 斐波那契数列的for循环实现

Minimum Path Sum

• 动态规划问题

• 先求得第一行和第一列到达每个位置的总和, 再计算每个其他a[i][j] + min(a[i-1][j], a[i][j-1]), 递推到最后即为最短路径

Merge Sorted Array

• 本质上两个指针, 倒着找, 这样把时间降为O(n)

Add Digits

• 数根

Invert Binary Tree

• 反转二叉树

• 非递归方式

• 先pop当前节点, 交换当前节点的左右子节点, 如果左右子节点存在, 将左右子节点压入栈利用栈来保存这些还没遍历的节点

Power of Two

• 理同下题
• 可以尝试用位运算优化

Power of Three

• 题中给出的是int类型, 可知长度为4个字节, 即32位, 除去符号位, 还剩31位, 2^30 < 3^19 < 2^31, 所以3^19总是3的幂的倍数

Minimum Depth of Binary Tree

• 二叉树的最小深度

• 非递归

• 类似层次遍历, 每层作为一个数组来进行遍历, 所以每层+1不会多

Verify Preorder Serialization of a Binary Tree

• 根据二叉树的性质来计算

    设节点: 度为0为n0, 度为1为n1, 度为2为n2, 总节点为n, #个数为n#
   
    n = n0 + n1 + n2
    n0 = n2 + 1
    n# = 2 * n0 + n1
    n# = n0 + n2 + n1 + 1
    n# = n + 1
  

• 按照构建二叉树的顺序, 因为开始时是空树, 所以初始化为空节点个数为1, 增加一个非#节点, 相当于减少一个空节点, 同时增加两个空节点, 增加一个#节点就相当于减少一个空节点, 所以最后总是满足结果为0

Reverse Nodes in k-Group

• 把一个链表分成几部分进行反转, 每次记录每部分的尾部, 下一次尾部连接头部

Length of Last Word

• 自己想到个巧妙的方法, tmp既做计数器又做flag

Reverse Linked List

• 反转单链表

Construct Binary Tree from Preorder and Inorder Traversal

• 递归

  • 由于前序遍历的第一个点是树根, 所以根据树根在中序遍历中来区分左/右子树
  • 把左子树看作单独的🌲, 然后按照第一步进行判断

• 非递归

  • 利用栈来来保存遍历前序遍历的数组, 遍历一个就加入栈, 下一个循环的时候和中序遍历的数组比较来判断是否是右子树, 相同的就pop, 因为这些已经构建了, 每次pop循环完后的, 第一次不同的时候
  • 从左向右扫描先序和中序序列，先将先序的结点入栈，以备后面要建立右结点用；然后用栈顶元素和中序扫描所在位置的值进行比较，1.如果相等，就说明后面还有右子树的结点，并设置标志，使其之后走右子树方向; 2.如果不等，就判断标志，是创建左子树还是右子树，创建之后，并让他自身进栈。

Remove Element

• 不用删除函数的话就用双指针一个赋值, 一个遍历

• py的删除函数使用后后面所有的数据会自动前移, [1,2,3]的索引为0,1,2, 删除2就变为[1,3], 索引0,1

Compare Version Numbers

• 根据'.'分成几部分, 然后int比较, 理论上如果版本号超过了int, 感觉就比较难处理了, 不过实际上版本号还是没那么长...

Binary Tree Level Order Traversal

• 自从非递归反转了二叉树, 徒手层次遍历二叉树一次AC😂

Bitwise AND of Numbers Range

• 很考基础的一道题, 对位运算的认识, 学了计算机组成原理, 数电之类的就很容易做了, 就是求[m, n]的化为二进制后相同的前缀, 最多循环判断31次 //todo 可以试试按字符串的方式来比较看看和位运算来谁更快?

Simplify Path

• 感觉这道题应该放到easy去, 一个栈就能解决问题, 一次AC, 终端用多了还是有点好处2333

Sqrt(x)

• 牛顿法求平方根

Permutations

• 全排列, 非递归, 把一个数插入每个间隔

Search Insert Position

• 给排序好的数组按顺序插入一个值, 实际上是类似于二分法查找相同的数, 利用二分法提高效率

Palindrome Linked List

• 判断是否是回文链表

• 利用快慢指针找到中间节点(注意奇偶), 反转后半部分, 然后进行比较

Path Sum

• 有点DP问题和层次遍历结合的感觉, 把上一个节点的值加给它的子节点, 叶子节点存进数组里, 最后判断下就好了, 2次AC, 修改了下先判断是否是叶子节点速度就快多了

Number of Matching Subsequences

• 就这个实现本身O(m*n)来说还有优化空间：比如判断str的长度
• 查了下还有其他更优雅的解决方案，复杂度是O(m+n), 当然不是类似打表这种trick的方式

LRU Cache

• 附上之前写的LRU，画完图来写比较清晰，口述起来真的一言难尽

Delete Columns to Make Sorted II

• 删去最少的列数，让剩下的字符串以英文字典里单词的顺序排列
• 思路是：
  • 针对每一列，如果符合字典序，那么就保存下来，可以记为变量tmp
  • 对于当前列，因为tmp里是按字典序保存的， 所以先比较tmp里前一列，如果不相等，因为符合字典序，那么没必要校验后面的了；如果相等，又因为符合字典序，就必须比较当前列了； 综上所述，这里其实只需要考虑前一列相等并且当前列的前者大于后者这种情况，即仅这种情况需要删除，其余的通过校验后执行第一步操作
  • 对于第一列，我们可以假设一个空字符串作为dummy beginning，就能够不做特殊处理了

Total Hamming Distance

• 第一反应就是两两之间求异或，然后数结果里的1，虽然答案正确但是超时了

• 没办法，位运算太菜了，想不出来优化思路，看了下别人的思路，如下，取4，14，2找规律

  0	1	0	0
  1	1	1	0
  0	0	1	0
  2	2	2	0

• 可以看出来距离实际上是每一列的1到0的距离，假设有m个1，n个0，那么距离就是m*n, m可以数出来，n就是长度减m

• 然后这里就可以通过 1 << x & y 这种根据列的索引左移进行然后相与检查当前位是否为 1

Coin Change 2

• 动态规划问题

• 因为是动态规划问题，所以要拿到状态转移方程

• 拆解问题

  前 i 种硬币组成 j 金额的方案数量 = 前 i-1 种硬币组成 j 金额的方案数量 + 前 i 种硬币组成 j-coins[i] 金额的方案数量
  前 i-1 种硬币组成 j 金额的方案数量 => 不使用coins[i]的方案数量
  前 i 种硬币组成 j-coins[i] 金额的方案数量 => 使用coins[i]的方案数量, 这里因为使用了coins[i], 所以金额是 j-coins[i]
  于是翻译成方程:
  dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]] 附加条件是(j-coins[i] >= 0)
  

• 因为i大于0, 所以在写代码的时候注意多加一行一列即dp[0][j],dp[i][0]

• 因为dp[i][0]的含义是 前 i 种硬币组成 0 金额的方案数量, 所以永远是1, 初始化数组的时候置要为1

• 最后这个算法还有优化空间, 但是没看懂, 是状态压缩到一行

Maximum Length of a Concatenated String with Unique Characters

• 思路是深搜, 把每个符合条件的组合的长度都拿到, 取最大
• 可以这么思考:
  • 首先有一个初始字符串s和字符串列表arr以及初始索引i
  • 那么对于 s+arr[i]有两种可能
    • 存在重复字符->排除arr[i], 从arr[i+1]继续深搜
    • 不存在重复字符
  • 不存在重复字符, 我们可以有两种选择:
    • s = s+arr[i], 然后从arr[i+1]继续深搜
    • 考虑到后面可能存在比arr[i]更长的字符串->排除arr[i], 从arr[i+1]继续深搜
    • 然后取这两者中最大值返回
  • 最终的结束条件是搜索完毕即i == len(arr), 因为i取值范围是i < len(arr), 这个时候s已经是最大长度了, len(s)即是解

Minimum Swaps To Make Sequences Increasing

• dp问题
• 由题意得一个前提, 给的数据都是通过交换能够递增的合法数据, 那么意思就是交换后最终结果是递增的
• 因为A[i]和B[i]只有两种状态:
  • 相互交换; 记为s
  • 没交换; 记为n
• 那么定义:
  • 前i-1个元素的最小交换次数
  • 当A[i-1],B[i-1]相互交换了, 记为s1
  • 当A[i-1],B[i-1]没交换了, 记为n1
  • 同理得 前i个元素的最小交换次数
    • 交换: s2
    • 没交换: n2
• 因为有了一个最终结果总是递增的大前提, 对于A[i-1],B[i-1],A[i],B[i]仅存在以下两种情况
  • A[i-1] < A[i] && B[i-1] < B[i], 这个条件下说明i-1和i要么一起交换, 要么不交换
    • 在A[i]和B[i]发生了相互交换的下, 说明i-1的也发生了交换, 设最小交换次数为s2, s2 = min(s2, s1+1)
    • 在A[i]和B[i]没交换的情况下, n2 = min(n2, n1)
  • A[i-1] < B[i]&& B[i-1] < A[i] , 这个条件说明了要么i-1交换, 要么i交换
    • 在A[i]和B[i]发生了相互交换的下, 说明i-1的没交换, 所以i-1的交换次数记为n1, 可以得到s2 = min(s2, n1+1)
    • 在A[i]和B[i]没交换的情况下, n2 = min(n2, s1)
• 根据以上推论, 最终答案为min(s2, n2)
• ps: dp问题要建立好模型, 将各个变量解耦, 才好解, 稍微有那么一点感觉了

Knight Dialer

• dp问题, 按照国际象棋的骑士的走法, n步在拨号键盘上能走出多少种走法
• 首先观察一下, 能找到规律, 比如, 0只能走到4和6, 1 只能走到6,8等等
• 可以列出状态方程, 设i为当前所在数字, j为步数, 则有走法: dp[i][j]
• 因为根据规律可以知道, 比如我当前是在0的位置, 所以我上一步必然在4或者6, 此时有dp[0][j] = dp[4][j-1] + dp[6][j-1]
• 总结出来dp[i][j] = sum(dp[i'][j-1] for i' in i所能到达的位置)
• ps: 虽然我dp问题状态方程列出来基本没问题了, 但是实现上还需要加把劲, 第一次写出来的虽然结果对了, 但是超时了...

Valid Boomerang

• esay, 一次AC, 没啥可以讲的, 证明三点共线完事, 这里用的是平行线法

Two Sum II - Input array is sorted

• esay, 三次ac, 首尾双指针, 总和大于目标移动尾指针, 小于移动首指针

Delete Node in a BST

• 二叉搜索树删除节点
• 道理我都懂, 为什么写出来各种bug
• 用递归写, 被删除节点度为0,1,2分情况处理

Integer Replacement

• 给出一个正整数, 偶数除以2, 奇数可以加1或者减1, 问最终得到1到底要几步
• 明显是一道需要观察规律的位运算的题目
• 可以看出规律, 偶数是削减数字最快的方法, 所以尽量凑偶数
  • 是偶数直接右移一位
  • 奇数分情况处理, 奇数必定以1结尾, 所以有两种情况
    • 01
    • 11
  • 因为我们要尽量凑成偶数, 所以0越多越好
    • 01 减1, 可以增加1个0
    • 11, 加1, 至少能凑出1个0
• 处理特殊情况, 可以根据规律看出来, 3很特殊, 虽然为11, 但是只能减1, 所以这里单独处理

Peak Index in a Mountain Array

• easy, 两次ac
• 用二分查找的方法来写, 为了图简练写成了个递归二分查找, 还有切片操作, 性能略低, 没必要没必要

Minimum Genetic Mutation

• BFS
• BFS选取状态用队列的形式，先进先出;DFS用递归的形式，用到了栈结构，先进后出
• 反正都是穷举, 考虑如何剪枝?
• 看思路还有双向BFS? 看了下因为BFS越遍历队列就越长, 大概是[1,2,4,8,16]这种感觉, 双向BFS会优化成[1,2,4,2,1]这种

Word Ladder

• 为什么刷这道题呢, 为了巩固下BFS
• 思路和上面一致, 然后用了双向BFS来解决, 没啥难度, 不过耗时太丑陋了, 毕竟26个岔路, 这块思路不对
• 开始的时候自信写完, 结果超时了, 原因是忘了把wordList进行set操作, 在里面List查找的时候是O(n), set了之后是hash过后的, 时间复杂度是O(1)

House Robber II

• dp问题
• 首先可以看出来分两种情况讨论: 偷第一间, 不偷最后一间; 偷最后一间, 不偷第一间. 也就是nums[1:]和nums[:-1]讨论
• 然后我们假设对于前i个房子, 我们偷了dp[i]的金额
• 接着因为由题意得到, 如果我们偷了i号房子, 那么i-1就不能偷, 反之就能偷i-1
• 那么这两种情况就有两个方程
  • 偷了i房子, dp[i-2]+nums[i]
  • 不偷i房子, dp[i-1]
• 所以最多能偷 dp[i] = max(dp[i-2]+nums[i], dp[i-1])
• 对于前0个房屋, 能偷到的金额为0, 所以dp[0] = 0
• 最后就求两种nums的最大值

Unique Number of Occurrences

• 过于easy, 是个人都知道怎么做

Sort Characters By Frequency

• 写的是middle, 但是实际只有easy, 没啥值得讲的

Remove Nth Node From End of List

• 一次删除链表里的倒数第n个节点
• 双指针, 两个指针相距n, 即可求出, 不过实际上可以相距n+1, 实现会更优雅

Maximum Sum of Two Non-Overlapping Subarrays

• 给定一个数组, 求其中两个非重叠连续子数组的最大和
• dp问题
• 因为两个子数组长度分别为L和M, 分两种情况讨论
  • L在前M在后
  • M在前L在后
• 首先对于给定的数组A进行一些预处理: A[i] += A[i-1], 这样预处理的意义在于求i,j之间的和的时候A[j]-A[i]可以直接取到
• 然后对于两种情况, 我们只需要搞清楚一种, 另一种也就清楚了
• 对于L在M前面这种情况
  • 设dp[i]为前i个数的和的最大值
  • 因为使用了前i个数, 又因为L在M前面, 因此最后M位必定为M, 所以对于有LMax[i] = max(LMax[i-1], A[i-M]-A[i-M-L])
  • dp[i] = LMax[i]+A[i]-A[i-M]
• 同理可得M在L前面的最大值, 最后取两种情况的最大值

Pairs of Songs With Total Durations Divisible by 60

• 是一道有点意思的esay
• 找出n对持续时间可被60整除的歌曲, 可以重复使用, 但要满足{time[i], time[j]} (i<j)
• 对每个数字求模, 余数作为数组索引, 然后计数, 看每个余数有多少首歌, 即arr[time%60] += 1
• 然后把余数为1和59的组合起来, 看有多少种组合, 也就是arr[1]*arr[59]
• 此外注意边界, 单独计算arr[0], arr[30], 组合数量为n*(n-1)/2
• 最后求和就可以了

Valid Parenthesis String

• 基本思路还是算式里对括号的处理方式, 压栈出栈, 合法的算式当)出栈的时候必定有对应(, 不过因为我们不用真正计算, 所以对于它们计数即可, 也就是说当
• 又因为有*, 会稍微多判断下, 因为它既要当(又要当)
• 也就是说当(和*为0, )不为0, )大于0的时候非法, 或者在( > *的情况下非法
• 不过对于)*和*(这种case是非法的, 所以还需要逆序再遍历一遍

Binary Tree Preorder Traversal

• 二叉树的前序遍历, 非递归
• 中左右遍历, 非递归需要用栈来模拟递归
• 因为是栈, 所以当前节点直接把值放进结果里, 入栈的时候得先把当前节点的右节点入栈, 再入当前节点的左节点, 这样下一个循环先弹出来的就是左节点了

Binary Tree Postorder Traversal

• 二叉树的后续遍历, 非递归
• 左右中遍历
• 取巧的方式, 只要我们是按中右左的方式遍历, 最后结果只要反转一下就是答案, 中右左怎么遍历呢, 前序遍历先入右节点再入左节点即可, 和前序遍历代码就两行不同

Binary Tree Inorder Traversal

• 二叉树的中序遍历, 非递归
• 左中右遍历, 这个就得另外写了
• 思路是首先我们找到最左边的左节点, 中途遇到的节点先压入栈里, 然后弹出一个, 结果里记录它的值, 然处理它的右节点, 这里又从最开始的逻辑走了

Construct Binary Tree from Preorder and Postorder Traversal

• 根据前序和后序遍历构造二叉树
• 因为前序是中左右, 后序是左右中遍历, 所以pre[0]和post[-1]是根
• 现在刨去根节点, 判断左子树和右子树, 这个时候pre[1]是第一个子树的根节点, 找到pre[1]在post里的位置index, 就可以隔出来两棵子树
• pre[1:index+1+1]是新的左子树, pre[index+1+1:]是新的右子树
• 相对应的post[:index+1]是新的左子树, post[index+1:]是新的右子树
• 递归解决问题

Remove Duplicates from Sorted List

• 移除排序链表里的重复节点, esay

Uncommon Words from Two Sentences

• 统计两个字符串里只出现了一次的单词, easy

Minimum Add to Make Parentheses Valid

• 栈的思路, 计数来判断, 没难度

Shortest Path with Alternating Colors

• 无权有向图最短路径, 但是有附加条件: 边有两种颜色, 必须在路径中交替出现
• BFS
• 注意点: 需要处理环的情况, 即要标记访问过的边
• 好像是第一次写图相关的, 学+写花了两个小时

Toeplitz Matrix

• 看对角线的数字是不是相等
• 其实就是看matrix[i][j] != matrix[i-1][j-1]
• 注意边界matrix[i][0] matrix[0][j]这一行一列不做判断

K Closest Points to Origin

• 最接近原点的 K 个点
• 偷懒直接用sortd对points排序, 然后返回前K个
• 正统思路该用堆的

Permutation in String

• 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列
• 用滑动窗口
• 首先生成s1CountMap和s2CountMap
• 然后遍历s2CountMap, 加减每个字母出现的次数, 并且和s1CountMap比较

Reorganize String

• 重构字符串, 每个字符串相邻的字母不和自己一样
• 用个数组存每个字母的数量, 然后取最大, 取不含自己的最大拼一个就可以了

Convert Sorted List to Binary Search Tree

• 用分治法将升序链表构建成平衡二叉搜索树
• 因为是二叉搜索树中序遍历是升序, 所以分治, 将中间节点看做根节点, 然后递归组装起来

Max Consecutive Ones III

• 一个包含0,1的列表, 能够转换k个0为1, 问1连续最长个数是多少
• 滑动窗口, 用两个指针, start, end; end每后移一位的时候, start根据情况是否变化, end-start为当前长度
  • 当k > 0的时候:
    • end++
    • 当end == 0时k--
  • 当k == 0的时候
    • 如果 end == 1, 继续end++
    • 当end == 0, start++
  • longest = max(longest, end-start)

Combination Sum IV

• 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数

• 思路类似前面做过的Coin Change 2

• 状态转移方程 dp[i] = sum{dp[i - num] for num in nums if i >= num}, dp[0]=1

Remove K Digits

• 移除这个数中的 k 位数字，使得剩下的数字最小
• 虽然没想出来思路, 但是这道题还是很有趣
• 先说, 其实是有规律的, 假如有a1a2a3a4...每个aN代表一位数, 这样一个数, 如果数字aN小于其左邻居a(N-1)，则我们应该删除左邻居
• 对于特例假如单调递增, 或者说在删除n个数以后, k-n > 0, 并且单调递增的情况下, 只需要把最后k-n删除即可, result[:-k] (k>0)
• 对于结果, 去掉前导0, 如果已经是空字符串返回0
• 剪枝 if len(num) <= k: return '0'

Top K Frequent Elements

• 找出数组里前k个高频元素
• 思路很简单, hashmap存每个元素出现频次, 然后构建大顶堆, 取前k个
• 学习到了新姿势, py的collection.Counter可以直接统计频次, heapq.nlargest直接返回大顶堆的前k个