祝大家前程似锦。
3. 无重复字符的最长子串
频度：75
使用滑动窗口，这里难考率的是左边界的情况。
- 比如abca，当遍历到第二个a时，左边界更新为map.get(a)+1=1，此时最长有效字段为bca;
- 当abba，当遍历到第二个b时，左边界如果更新为map.get(b)+1=2，下一个遍历到a，a还在map里，那么left就变成map.get(a)+1=1，结果就错了。
所以采用left=Math.max(left , map.get(s.charAt(i))+1)，这样就能去除第二种情况的旧数据了。
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) return 0;
int res = 0, left = 0;
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
left = Math.max(left, map.get(s.charAt(i)) + 1);
}
map.put(s.charAt(i), i);
res = Math.max(res, i - left + 1);
}
return res;
}
15. 三数之和
频度：50
建议多手写几遍背下来，感觉很流畅的方法
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
if (nums.length < 3) return list;
Arrays.sort(nums);
int left, right;
for (int i = 0; i < nums.length - 2; i++) {
//如果最小的都大于0，和就肯定不能为0了
if (nums[i] > 0) break;
//去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
left = i + 1;
right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
list.add(Arrays.asList(nums[i], nums[left++], nums[right--]));
//去重
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
//去重
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum > 0) {
right--;
} else {
left++;
}
}
}
return list;
}
25. K 个一组翻转链表
频度：80
两两交换，顺序递推，还是多写几遍背下来吧
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy, cur = head, next;
int len = 0;
while (cur != null) {
len++;
cur = cur.next;
}
cur = head;
//可以分出len/k组
for (int i = 0; i < len / k; i++) {
//需要k-1次交换
for (int j = 0; j < k - 1; j++) {
//获取下一个结点
next = cur.next;
//当前结点跳过下一个指向下下个
cur.next = next.next;
//下一个结点指向第一个结点
next.next = pre.next;
//更新第一个结点
pre.next=next;
}
//到下一个分组
pre = cur;
cur = cur.next;
}
return dummy.next;
}
103. 二叉树的锯齿形层序遍历
频度：66
经典遍历问题了，最经典的是层次遍历二叉树，不用flag即可。另外一个是二叉树的右视图，每次只把队列最后一个元素的值加入即可。
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> list=new ArrayList<>();
if(root==null){
return list;
}
Deque<TreeNode> queue=new LinkedList<>();
//用标志位来确定是否改反转
boolean flag=true;
queue.add(root);
while (!queue.isEmpty()){
List<Integer> tmp=new ArrayList<>();
//也可以先用len=queue.size;然后让i<len;
for (int i = queue.size(); i > 0; i--) {
TreeNode node=queue.pop();
tmp.add(node.val);
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
if(!flag) Collections.reverse(tmp);
flag=!flag;
list.add(tmp);
}
return list;
}
121. 买卖股票的最佳时机
频度：48
维护一个最大值和最小值即可。因为第一天只能买入，所以初始化min为第一天的值即可（因为给出prices.length>0）
public int maxProfit(int[] prices) {
int min = prices[0], max = 0;
for (int i = 1; i < prices.length; i++) {
min = Math.min(min, prices[i]);
max = Math.max(max, prices[i] - min);
}
return max;
}
146. LRU 缓存机制
频度：79
Java中的LinkedHashMap适合实现LRU，可以设置根据访问时间排序，但是面试的时候肯定还是会要求手写。
class Node {
public int key;
public int val;
public Node pre;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
class DoubleLinkedList {
Node head;
Node tail;
public DoubleLinkedList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.pre = head;
}
public void addFirst(Node node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
public int remove(Node node) {
node.next.pre = node.pre;
node.pre.next = node.next;
return node.val;
}
public int removeLast() {
if (head.next == tail) {
return -1;
}
return remove(tail.pre);
}
}
public class LRUCache {
HashMap<Integer, Node> map;
DoubleLinkedList cache;
int cap;
public LRUCache(int cap) {
this.cap = cap;
map = new HashMap<>();
cache = new DoubleLinkedList();
}
public void put(int key, int val) {
Node newNode = new Node(key, val);
//如果已存在就重新放入
if (map.containsKey(key)) {
cache.remove(map.get(key));
cache.addFirst(newNode);
map.put(key, newNode);
} else {
if (map.size() == cap) {
map.remove(cache.removeLast());
}
cache.addFirst(newNode);
map.put(key, newNode);
}
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
int val = map.get(key).val;
put(key, val);
return val;
}
}
215. 数组中的第K个最大元素
记得覃超大魔王讲过，堆排序很合适。维护一个小顶堆，如果数比他大就与他交换然后重新堆化，Java中有PriorityQueue可以直接实现小顶堆。
public int findKthLargest(int[] nums, int k) {
if (nums.length == 0 || k < 1) {
return Integer.MIN_VALUE;
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < k; i++) {
minHeap.add(nums[i]);
}
for (int i = k; i < nums.length; i++) {
// 若 nums[i] 大于等于堆顶元素，弹出堆顶元素并将 nums[i] 入堆
if (nums[i] > minHeap.peek()) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
}
206. 反转链表
频度：62
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode pre = head, cur = head.next;
head.next = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}