題庫來源:出現(xiàn)頻率五顆星
1.?最高頻題，99%命中面試題，字節(jié)，快手，shapee，大疆, 華為，蔚來 ！
2.? 作為大廠面試管，經(jīng)常出題，同時(shí)從海量題庫中精選9題。
-------------------------------------------------------------------------------
Top1:? ?234. 回文鏈表? ? ? ? ? ? ? ? ? ? ? ? ? ? 鏈表+快慢指針
Top2:? ?2?兩數(shù)相加? ? ? ? ? ? ? 鏈表+遞歸
Top3:? ?102. 二叉樹的層序遍歷? ? ? ? ? ? ? DFS和BFS的區(qū)別
Top4:? ?78. 子集? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 回溯和DFS
Top5:? ?46. 全排列? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?回溯+哈希表??
Top6:? ? 53. 最大子數(shù)組和? ? ? ? ? ? ? ? ? ? ? ? 分治+數(shù)組
Top7:? ?215. 數(shù)組中的第K個(gè)最大元素? ? ? 堆+排序
Top8:? ? 20.有效的括號(hào)? ? ? ? ? ? ? ? ? ? ? ? ? ? ?棧?
Top9:? ? 231. 2 的冪.? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?二分法
-------------------------------------------------------------------------------
總結(jié):
1.最常用的數(shù)據(jù)結(jié)構(gòu):鏈表+哈希表+樹
2.最常用的解題方法:排序,雙指針,帶遞歸類型的dfs,回溯,bfs
3.常用的數(shù)據(jù)表單:數(shù)組+字符串
------------------------------------------------------------------------------
Top1:? ?234. 回文鏈表? ? ? ? ? ? ? ? ? ? ? ? ? ? 鏈表+快慢指針
...
class Solution {
? ? public boolean isPalindrome(ListNode head) {
? ? ? ? if (head == null) {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? // 找到前半部分鏈表的尾節(jié)點(diǎn)并反轉(zhuǎn)后半部分鏈表
? ? ? ? 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;
? ? ? ? }? ? ? ?
? ? ? ? // 還原鏈表并返回結(jié)果
? ? ? ? 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?兩數(shù)相加? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? 鏈表+遞歸
```
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
? int total = l1.val + l2.val;
? ? ? ? int next1 = total / 10; // 是否進(jìn)1
? ? ? ? ListNode res = new ListNode(total % 10); // 每次進(jìn)來創(chuàng)建一個(gè)node節(jié)點(diǎn)，而且有數(shù)據(jù)
? ? ? ? if (l1.next != null || l2.next != null || next1 != 0) { // 條件,分析出進(jìn)一的話，還需要進(jìn)來的
? ? ? ? ? ? // 移動(dòng)指針
? ? ? ? ? ? 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的區(qū)別
'''
public List<List<Integer>> levelOrder(TreeNode root) {
? List<List<Integer>> result = new ArrayList<>();
? ? ? ? if (root == null) {
? ? ? ? ? ? return result;
? ? ? ? }
? ? ? ? // 隊(duì)列
? ? ? ? Queue<TreeNode> queue = new LinkedList<>();
? ? ? ? queue.add(root);// 添加進(jìn)去
? ? ? ? while (queue.size() > 0) {
? ? ? ? ? ? List<Integer> innerList = new ArrayList<>();
? ? ? ? ? ? int size = queue.size(); // 在變化
? ? ? ? ? ? while (size > 0) {
? ? ? ? ? ? ? ? TreeNode curNode = queue.poll(); // 取出來,在內(nèi)層取出來
? ? ? ? ? ? ? ? innerList.add(curNode.val);
? ? ? ? ? ? ? ? if (curNode.left != null) {
? ? ? ? ? ? ? ? ? ? queue.add(curNode.left);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (curNode.right != null) {
? ? ? ? ? ? ? ? ? ? queue.add(curNode.right);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? size = size - 1; //會(huì)動(dòng)態(tài)變的
? ? ? ? ? ? } // 退出內(nèi)層循環(huán)。
? ? ? ? ? ? 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); // 初始化默認(rèn)值
? ? ? ? }
? ? ? ? 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) { // 一個(gè)分支得到的結(jié)果
? ? ? ? ? ? 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. 最大子數(shù)組和? ? ? ? ? ? ? ? ? ? ? ? 分治+數(shù)組
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);
? ? }
}
