easy
1 Two Sum
hashmap
medium
2 Add Two Numbers O(n)
从头到尾遍历,短的计算结束后计算长的,如果进位为零直接加上剩余linkedList
3 Longest Substring Without Repeating Characters O(n)
- 用个数组记一下数, two pointer遍历一遍,遇到相同字符算一下最大长度,最后注意一下最后一段全都不一样的情况
- 数组记录idx,一个整数prev记录上一个合理的开始位置,遇到不合理的计算一下最大长度,如果使prev后移,更新prev
11 Container With Most Water O(n)
two pointers, 往中间移动,一边算max
5 Longest Palindromic Substring O(n^2)
遍历一遍,每个字符都计算以其为中心的奇数、偶数长度的回文字符串,更新结果,注意空字符串
138 Copy List with Random Pointer
- hashMap一一对应存一下 O(n), O(n)
- 遍历三遍,第一遍复制所有并传在linkedList里,第二遍为新node指定random,第三遍把新node从linkedList里提取出来,注意指针操作 O(n), O(1)
238 Product of Array Except Self O(n)
遍历两遍,第一遍算左边的积,第二遍算右边的积顺便乘左边算结果
17 Letter Combinations of a Phone Number O(n^x)
递归写一下
681 Next Closest Time O(2^4)
dfs得到所有结果判断是否合理,算一下next time
49 Group Anagrams O(26nm)
遍历每个字符串,统计一下每个字符出现的次数生成一个key,hashMap存一下key,返回list(map.values())
33 Search in Rotated Sorted Array O(lgn)
binary search,注意边界值
535 Encode and Decode TinyURL O(1)
id + hashmap
hard
23 Merge k Sorted Lists O(nlogm)
priorityQueue
42 Trapping Rain Water O(n)
two pointers(左:l,右:r)
小的那个往中间移动并累加结果,遇到比它大的就更新数值重修比较left, right
115 Distinct Subsequences O(mn)
dp:
if s[i] == t[j]: dp[i + 1][j + 1] = dp[i][j](新的) + dp[i][j + 1](原来的)
else: dp[i + 1][j + 1] = dp[i][j + 1]
146 LRU Cache O(1)
需要:hashmap保存key与节点,双向链表保存cache中的值
get: if key in map: return val & move node to list head || else: return -1
put: if key in map: update || else: if full: remove tail & add to head || else: add to head
460 LFU Cache O(1)
需要: HashMap1(存储key是否存在),hashmap2(freq及对应节点),hashmap3(freq结尾)
get: 如果key不存在,返回-1,如果存在:freq++,更新,返回对应值
update: freq中删除,++freq列表头增加,更新min_freq
847 Shortest Path Visiting All Nodes O(n*2^k)
0 需要:二维数组存储节点及对应状态是否被访问过; int保存当前状态(哪些节点被访问过);queue保存当前需要继续访问的状态;step表示结果;int表示最终结果
1 初始化, 将所有节点加入队列
2 BFS,取出此步需要判断的节点,判断是否到达最终状态,如果没有将下一步需要判断的节点和状态放入队列
864 Shortest Path to Get All Keys BFS O(mn(2^k))
0 需要:三维数组保存当前状态是否被访问过;int保存当前状态(0-7key,8-15y,16-23x);queue保存当前需要继续访问的状态
1 初始化 (开始状态,!记得修改mark)
2 BFS (状态判断,wall,key,lock决定是否继续,if get all keys return steps)