题库来源:出现频率五颗星
1. 最高频题，99%命中面试题，字节，快手，shapee，大疆, 华为，蔚来 ！
2. 作为大厂面试管，经常出题，同时从海量题库中精选9题。
-------------------------------------------------------------------------------
Top1: 234. 回文链表 链表+快慢指针
Top2: 2 两数相加 链表+递归
Top3: 102. 二叉树的层序遍历 DFS和BFS的区别
Top4: 78. 子集 回溯和DFS
Top5: 46. 全排列 回溯+哈希表
Top6: 53. 最大子数组和 分治+数组
Top7: 215. 数组中的第K个最大元素 堆+排序
Top8: 20.有效的括号 栈
Top9: 231. 2 的幂. 二分法
-------------------------------------------------------------------------------
总结:
1.最常用的数据结构:链表+哈希表+树
2.最常用的解题方法:排序,双指针,带递归类型的dfs,回溯,bfs
3.常用的数据表单:数组+字符串
------------------------------------------------------------------------------
Top1: 234. 回文链表 链表+快慢指针
...
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
ListNode secondHalfStart = reverseList(firstHalfEnd.next);
// 判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 还原链表并返回结果
firstHalfEnd.next = reverseList(secondHalfStart);
return result;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
Top2: 2 两数相加 链表+递归
```
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int total = l1.val + l2.val;
int next1 = total / 10; // 是否进1
ListNode res = new ListNode(total % 10); // 每次进来创建一个node节点，而且有数据
if (l1.next != null || l2.next != null || next1 != 0) { // 条件,分析出进一的话，还需要进来的
// 移动指针
l1 = l1.next != null ? l1.next : new ListNode(0);
l2 = l2.next != null ? l2.next : new ListNode(0);
l1.val += next1;
res.next = addTwoNumbers(l1, l2);
}
return res;
}
Top3: 102. 二叉树的层序遍历 DFS和BFS的区别
'''
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
// 队列
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);// 添加进去
while (queue.size() > 0) {
List<Integer> innerList = new ArrayList<>();
int size = queue.size(); // 在变化
while (size > 0) {
TreeNode curNode = queue.poll(); // 取出来,在内层取出来
innerList.add(curNode.val);
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
size = size - 1; //会动态变的
} // 退出内层循环。
result.add(new ArrayList<>(innerList));
}
return result;
}
Top4: 78. 子集 回溯和DFS
'''
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def helper(i, tmp):
res.append(tmp)
for j in range(i, n):
helper(j + 1,tmp + [nums[j]] )
helper(0, [])
return res
Top5: 46. 全排列 回溯+哈希表
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
HashMap<Integer, Boolean> visited = new HashMap<>();
for (int num : nums) {
visited.put(num, false); // 初始化默认值
}
backTracking(nums, result, visited, new ArrayList<>());
return result;
}
private void backTracking(int[] nums, List<List<Integer>> result, HashMap<Integer, Boolean> visited, ArrayList<Integer> list) {
if (list.size() == nums.length) { // 一个分支得到的结果
result.add(new ArrayList<>(list));
}
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (!visited.get(num)) {
list.add(num);
visited.put(num, true);
backTracking(nums, result, visited, list);
list.remove(list.size() - 1); // 移除
visited.put(num, false);
}
}
}
Top6: 53. 最大子数组和 分治+数组
class Solution {
public class Status {
public int lSum, rSum, mSum, iSum;
public Status(int lSum, int rSum, int mSum, int iSum) {
this.lSum = lSum;
this.rSum = rSum;
this.mSum = mSum;
this.iSum = iSum;
}
}
public int maxSubArray(int[] nums) {
return getInfo(nums, 0, nums.length - 1).mSum;
}
public Status getInfo(int[] a, int l, int r) {
if (l == r) {
return new Status(a[l], a[l], a[l], a[l]);
}
int m = (l + r) >> 1;
Status lSub = getInfo(a, l, m);
Status rSub = getInfo(a, m + 1, r);
return pushUp(lSub, rSub);
}
public Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = Math.max(l.lSum, l.iSum + r.lSum);
int rSum = Math.max(r.rSum, r.iSum + l.rSum);
int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
return new Status(lSum, rSum, mSum, iSum);
}
}
