leetcode习题总结

Remove Comments

• 目标：对给定的一个c++代码字符串数组，删除其中注释内容

• 思路：没有简单思路，分类目处理

  1. 对每一个字符串先检测其中是否含有符号”//”,”/* */”

  2. 对”//”删除该字符后面内容，前面的放到vector中

  3. 对”/*“则记一个全局标志位，如果这个标志位存在，则跳过任何字符

  4. 对”*/”则去除全局标志

Simplify Path

• 目标：给一个绝对路径字符串，将其简化

• 思路：先处理特殊情况，再按”/”分割处理即可

  1. 先处理3种特殊情况”//”，对这种符号只需简单替换即可

  2. 再按”/”分割字符串，一个一个处理即可

Container With Most Water

• 目标：从给定数组抽出2根柱子，计算它们和X轴组成的最大面积

• 思路：面积由长宽两个维度决定，从最长的宽度开始，然后牺牲宽度换长度

  1. 首先计算首尾两根柱子和X轴组成的面积

  2. 更换最短的柱子向中间寻找更长的柱子，即牺牲宽度换长度

• 差思路：暴力破解0(n2)

hash table：

Longest Substring Without Repeating Characters

• 目标：对给定的字符串，找到最长无重复子字符串

• 思路：滑动窗口+Hashtable

  1. 使用left,right双指针遍历字符串；right指针主动检测下一个字符，left指针由right检测到重复元素时，被动更新；hashtable中保存不同字符最后一次出现的位置

  2. 当right指针主动向右扩展，首先判断新元素有没有在hashtable中，如果是，则将left更新为hashtable中保存的值；否则，检测目前目前[left,right]字符串是否最长

• 失败思路：

  1. 双重for循环，对以字符串中每个字符为起点，计算它的最长无重复字符串；即可找到最大者。算法复杂度为O(n2)，无法AC

design twitter(https://leetcode.com/problems/design-twitter/)

• 目标：设计一个简单的twitter系统；关键在user，posts，followers

• 思路：2个map；map<int(userid), set<int(followerid)» followmap, map<int(userid),vector<pair<int(time),int(postid)»posts;输出某个用户的posts的时候，收集该用户所有posts以及该用户的followers的所有posts，再按时间排序输出即可

贪婪算法

Delete Columns to Make Sorted II

• 目标：对给定字符串数组，找一组序列；使得字符串数组中每个字符串以序列为下标删除字符后，为升序

• 思路：按下标贪婪，分别计算按每一下标为首的升序排列需要删除的列数即可

回溯算法

Additive Number

• 目标：判断给定数字字符串是否为”加法数”

• 思路：使用数组装载加法数，对下标进行回溯

  1. 递归参数：已经满足加法数的数组、寻找下一个加法数起始下标、是否已经找到、字符串

  2. 在递归函数中，对数字进行贪婪即可；满足out.size() >= 2 && curNum != out[n - 1] + out[n - 2]，即可再找下一个数

letter combinations of a phone number(https://leetcode.com/problems/letter-combinations-of-a-phone-number/)

• 目标：给一个电话盘及一串0-9数字；找出对应数字的字母的全排列

• 思路：对所有数字进行for循环；要注意的是每个字母都要新增一个字符串数组

动态规划

Maximum Product Subarray

• 目标：给定一个数组，找出其中乘积最大子数组

• 思路：用两个DP数组，max[i]：子树组[0,i]范围内并且一定包含nums[i]数字的最大子树组乘积；min[i]：子树组[0,i]范围内并且一定包含nums[i]数字的最小子树组乘积

  1. max[0]=min[0]=nums[0]

  2. 递推：max[i] = max{max[i-1]nums[i], min[i-1]nums[i], nums[i]},min[i] = min{max[i-1]nums[i], min[i-1]nums[i], nums[i]}

  3. 结果就是max数组中最大值

• 失败思路：有点类似Longest Substring Without Repeating Characters，第一眼看着就是要滑动窗口

  1. 两个for循环，分别寻找以各个点为起始点的子数组最大乘积，复杂度：O(n2)

Longest Palindromic Substring

• 目标：给定字符串，找出其中最长的回文子字符串

• 思路：建立递推关系, dp[i][j]表示字符串区间[i,j]是否为回文串

  1. dp[i,j] = 1 if i == j

  2. dp[i,j] == (s[i] == s[j]) if j = i + 1

  3. dp[i,j] == (s[i] == s[j] && dp[i + 1][j - 1]) if j > i + 1

• 失败思路：对以每个字符为中心，向两边扩展找到最长回文子字符串，复杂度：O(n2)

Unique Paths

• 目标：给定一个方格图，计算从左上角到右下角的不同路径数量

• 思路：建立递推关系，dp[i][j]表示从左上角走到第i行，j列的不同路径数量

  1. dp[i,j] = dp[i-1][j] + dp[i][j-1]

• 失败思路：按照最短路径的方法，真实去走每一条路径，然后统计相加，超时

coin change

• 目标：类似背包问题，但是这个问题是要确定N个coin能否组合出M块钱

• 思路：DP，dp[i]表示钱数为i时的最小硬币数

  1. 递推：两个for循环，外层对钱数i循环，内层对硬币种类循环；dp[i] = max{dp[i], dp[i-coin[j]]+1}

  2. 由于是两层for循环，在dp[i-coin[j]]中，已经是考虑包含coin[j]后的最小硬币数，因此不用像完全背包问题，还需要考虑coin[j]的数量

0/1背包问题

• 目标：有n件物品和容量为m的背包，给出n件物品的重量w[i]及价值v[i]，求解放入背包的物品重量不超过容量m的最大价值

• 思路1：DP，nums[i][j]表示前i种物品能组成不超过j重量的最大价值

  1. 递推公式：nums[i][j] = max{nums[i-1][j-w[i]]+v[i], nums[i-1][j]}

  2. nums[i-1][j-w[i]]+v[i]：表示在加入i物品不会超重的前提下，加入i物品后的最大价值

• 思路2：DP：f[j]表示重量j情况下最大价值

  1. 递推公式：随着遍历所有物品，f[j] = max{f[j], f[j-w[i]]+v[i]}

完全背包问题

• 目标：类似0/1背包，但是所有物品可以无限选用

• 思路：DP，nums[i][j]表示前i种物品能组成不超过j重量的最大价值

  1. 递推公式：nums[i][j] = max{nums[i-1][j-kw[i]]+kv[i], 0<=k && k*w[i]<=j}

  2. 复杂度：f[j] = max{f[j], f[j-kw[i]]+kv[i], 0<=k && k*w[i]<=j}

多重背包问题

• 目标：类似完全背包问题，但是所有物品有一定数量限制num[i]

• 思路：类似完全背包，k值限制即可

can i win(https://leetcode.com/problems/can-i-win/)

• 目标：给定一个maxchoosableinteger(最大可选择数)，一个desiredtotal(目标数)，2个player轮流从1-maxchoosableinteger中选数；是否有可能player1选一个数后，所有选出来的数字相加>=desiredtotal

• 思路：dp, 遍历所有可能的足迹；由于最大可选数为20，因此可以用一个整形来表示足迹，每一bite都是是否已经使用到该数字；再用一个map记录已经走过的足迹，加快搜索速度

  1. 搜索为深度搜索，一旦找到某路径找到一个true的组合，则整条路径的足迹都为true

  2. 搜索过程中，dp的返回值需要取反，因为只有player1先达到desiredtotal才为赢

递归

Valid Tic-Tac-Toe State

• 目标：给定一个3*3棋盘，分析棋盘是否是正确的；X先走，一旦横、竖、斜3连子，则游戏结束

• 思路：比较直观的思路就是两个for循环遍历棋盘，对于几种不可能的情况逐一检查即可

  1. 用一个变量turns来标识下棋顺序；读到X时，turn++；读到O时，turn–；最后turn必为0/1，否则异常

  2. 用xwin、owin分别标识按棋盘看X、O是否赢了；当然X赢时，turn必为1，否则也异常

字符串处理

zigzag conversion

• 目标：将给定字符串按列z字形重新排列，然后按行读字符后重新组合成一个字符串

• 思路：获得每一行的字符串后组合成新字符串

  1. 申请目标行数的空字符串空间

  2. 遍历输入字符串，分别往每行字符串末尾加；

  3. 碰到第0、n-1行则调转方向

• 失败思路：寻找规律，找在不同行数下，多少个字符组成一个周期；再找周期内每个元素的下标和它最后输入哪一行的数学关系；

4sum(https://leetcode.com/problems/4sum/)

• 目标：从给定的字符串数组中找出4个数，使4个数的和=target，输出所有这样的组合

• 思路：可以用两个for循环，在最里层的再用两个指标遍历，一共4个指标，相当于n^3

• 老思路：使用dfs

Group Anagrams(https://leetcode.com/problems/group-anagrams/)

• 目标：对给定的一组字符串进行分组，组成字母一样，顺序不一样属于一组；分行输出所有组的字符串

• 思路：for循环遍历所有字符串，对字符串转化为字母下标出现的次数；用一个unorder_map<string, vector>来装所有字符串；

• 差思路：对每个字符串进行sort后对比是否一样，可以用字母下标出现次数优化

DFS

max area of island(https://leetcode.com/problems/max-area-of-island/)

• 目标：给定一个方形图，其中不是0就是1；找出其中4个方向联结的最多1的数量

• 思路：dfs，用两个for循环遍历图中所有点；只要是1就进行dfs，从上下左右4个方向寻找临近点；已经找过的地方将1置0

Linked list

reorder list(https://leetcode.com/problems/reorder-list/)

• 目标：给定一个整形链表，对链表进行重排L0→Ln→L1→Ln-1→L2→Ln-2→…

• 思路：利用链表性质，一个快指针，一个慢指针遍历链表；快的是慢的2倍，可以快速定位到中间元素

  1. 将所有节点入栈，统计元素个数

  2. 将每次出栈的节点隔一个插入到正确的位置

• 差思路：

  1. 使用快慢指针来找到链表中点，并形成两个独立链表

  2. 将第二个链表翻转（用一个reversed指针指向已经翻转过部分的头节点；再用一个last指针时刻指向下一个要翻转的节点）

  3. 将第二个链表的元素间隔的插入第一个链表中

Swap Nodes in Pairs

• 目标：对给定链表，交换两个相邻节点，再返回

• 思路：引入哨兵机制

  1. 共3个指针，2个指向要交换的两个节点，一个为哨兵（需要自行malloc）

  2. 每次交换要注意前、后链接；由于是单向链表，所以前向指针需要由哨兵维护

array

Next Permutation(https://leetcode.com/problems/next-permutation/)

• 目标：对给定的数组，输出其下一个排序数组

• 思路：根据数组前后元素大小关系，重组数组

  1. 从数组最后往前遍历，找到第一个降序的相邻数字a1

  2. 再从a1往后，找到一个比a1大的最小数字b1

  3. 互换a1,b1，再将a1后的数组按升序重排得到最后结果

  4. 如果整个数组是降序的，则直接对数组按升序重排即可

binary search

Search in Rotated Sorted Array

• 目标：从给定的数组中找出指定数字的位置；数组是递增但是被截断后拼接

• 思路：二分搜索