leetcode review (3)

easy
1 Two Sum
hashmap

medium
2 Add Two Numbers O(n)
从头到尾遍历,短的计算结束后计算长的,如果进位为零直接加上剩余linkedList

3 Longest Substring Without Repeating Characters O(n)

  1. 用个数组记一下数, two pointer遍历一遍,遇到相同字符算一下最大长度,最后注意一下最后一段全都不一样的情况
  2. 数组记录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

  1. hashMap一一对应存一下 O(n), O(n)
  2. 遍历三遍,第一遍复制所有并传在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)