文章目錄

• 常用的排序算法
• • 1.冒泡排序
  • 2.選擇排序
  • 3.插入排序
  • 4.快排排序
  • 5.歸并排序
  • 6.堆排序
  • Java 的sort基于什么實現
  • 排序算法原理，何為穩定不穩定，快排是否穩定
• 查找
• • 二分查找
• 復盤筆試題
• • 3.尋找重復的子樹
• 樹的遍歷方式
• • 樹的遍歷方式（先序、中序、后序）
  • • 先序
    • 中序
    • 后序
  • 如何用數組模擬二叉樹的遍歷過程？
  • 求二叉樹的深度兩種方法
• 棧、隊列
• • 232. 用棧實現隊列
  • 225. 用隊列實現棧
• 字符串
• • 序列化與反序列化
  • 統計字母出現次數從大到小排序
  • 字符串中的最長不重復子串
• 動態規劃
• • 跳臺階
  • 最長公共子序列
• 鏈表
• • 反轉鏈表
  • leetcode 445. 兩數相加 II
  • 尋找字符串最長回文串
  • 力扣14. 最長公共前綴
  • 1701 平均等待時間

先說思路，然后寫代碼

常用的排序算法

1.冒泡排序

1.設置循環次數。
2.設置開始比較的位數，和結束的位數。
3.兩兩比較，將最小的放到前面去。
重復2、3步，直到循環次數完畢。

int temp;//定義一個臨時變量 for(int i=0;i<arr.length-1;i++){//冒泡趟數for(int j=0;j<arr.length-i-1;j++){//從第一個比到n-1-iif(arr[j+1]<arr[j]){//若前面比后面大，則交換temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}} }

2.選擇排序

1.首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
2.再從剩余未排序元素中繼續尋找最小元素，然后放到已排序序列的末尾。
3.重復第二步，直到所有元素均排序完畢。

/* 選擇排序 */ void SelectionSort(int arr[], int length) {int index, temp;for (int i = 0; i < length; i++){index = i;//未排序序列中最小元素for (int j = i + 1; j < length; j++){if (arr[j] < arr[index])index = j;}if (index != i){temp = arr[i];arr[i] = arr[index];arr[index] = temp;}} }

3.插入排序

將數組R劃分成兩個子區間R[1．．i-1]（已排好序的有序區）和R[i．．n]（當前未排序的部分，可稱無序區）。插入排序的基本操作是將當前無序區的第1個記錄R[i]插人到有序區R[1．．i-1]中適當的位置上，使R[1．．i]變為新的有序區

public voidInsertSort () {int i,j,temp;for(i=1;i<array.length;i++) {// R[i．．n]（當前未排序的部分，可稱無序區）temp=array[i];for(j=i-1;j>=0;j--) {// R[1．．i-1]（已排好序的有序區）if(temp>array[j]) {break;}else {array[j+1]=array[j];//往后挪，騰位置}}array[j+1]=temp;//插入數據} }

4.快排排序

先從右往左找到一個小于基準數的數，再從左往右找到一個大于基準數的數，交換他們.重復，當ij相遇時把此時這個數和基準數交換，再分別處理左右兩邊的數字.
== 先從右往左找,再從左往右找==

public static void quickSort(int[] arr,int low,int high){int i,j,temp,t;if(low>high) return;i=low;j=high;temp = arr[low];//temp就是基準位while (i<j) {while (temp<=arr[j]&&i<j) {j--;}//先看右邊，依次往左遞減 while (temp>=arr[i]&&i<j) {i++;}//再看左邊，依次往右遞增if (i<j) {//如果滿足條件則交換t = arr[j];arr[j] = arr[i];arr[i] = t;}}arr[low] = arr[i];//最后將基準為與i和j相等位置的數字交換arr[i] = temp;quickSort(arr, low, j-1);//遞歸調用左半數組quickSort(arr, j+1, high);//遞歸調用右半數組 }

5.歸并排序

假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2個長度為2(或者是1)的有序子序列，再兩兩歸并。如此重復，直到得到一個長度為n的有序序列為止。

private static void sort(int[] array, int left, int right) {if (left == right) {return;}int mid = left + ((right - left)/2);sort(array, left, mid); // 對左側子序列進行遞歸排序sort(array, mid + 1, right); // 對右側子序列進行遞歸排序merge(array, left, mid, right); // 合并 }private static void merge(int[] array, int left, int mid, int right) {int[] temp = new int[right - left + 1];int i = 0;int p1 = left;int p2 = mid + 1;// 比較左右兩部分的元素，哪個小，把那個元素填入temp中while (p1 <= mid && p2 <= right) {temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];}// 上面的循環退出后，把剩余元素依次填入temp（以下兩個while只有一個會執行）while (p1 <= mid) {temp[i++] = array[p1++];}while (p2 <= right) {temp[i++] = array[p2++];}// 把最終的排序的結果復制給原數組for (i = 0; i < temp.length; i++) {array[left + i] = temp[i];} }

6.堆排序

可以將堆看做是一個完全二叉樹。并且，每個結點的值都大于等于其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小于等于其左右孩子結點的值，稱為小頂堆。

堆排序(Heap Sort)是利用堆進行排序的方法。其基本思想為：將待排序列構造成一個大頂堆(或小頂堆)，整個序列的最大值(或最小值)就是堆頂的根結點，將根節點的值和堆數組的末尾元素交換，此時末尾元素就是最大值(或最小值)，然后將剩余的n-1個序列重新構造成一個堆，這樣就會得到n個元素中的次大值(或次小值)，如此反復執行，最終得到一個有序序列。

圖解

a.將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;
b.將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;
c.重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序。

作者：尼小摩
鏈接：https://www.jianshu.com/p/a161b991fa82
來源：簡書
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

public class HeapSort {public static void main(String []args){int []arr = {7,6,7,11,5,12,3,0,1};System.out.println("排序前："+Arrays.toString(arr));sort(arr);System.out.println("排序前："+Arrays.toString(arr));}public static void sort(int []arr){//1.構建大頂堆for(int i=arr.length/2-1;i>=0;i--){//從第一個非葉子結點從下至上，從右至左調整結構adjustHeap(arr,i,arr.length);}//2.調整堆結構+交換堆頂元素與末尾元素for(int j=arr.length-1;j>0;j--){swap(arr,0,j);//將堆頂元素與末尾元素進行交換adjustHeap(arr,0,j);//重新對堆進行調整}}//調整大頂堆（僅是調整過程，建立在大頂堆已構建的基礎上）public static void adjustHeap(int []arr,int i,int length){int temp = arr[i];//先取出當前元素ifor(int k=i*2+1;k<length;k=k*2+1){//從i結點的左子結點開始，也就是2i+1處開始if(k+1<length && arr[k]<arr[k+1]){//如果左子結點小于右子結點，k指向右子結點k++;}if(arr[k] >temp){//如果子節點大于父節點，將子節點值賦給父節點（不用進行交換）arr[i] = arr[k];i = k;}else{break;}}arr[i] = temp;//將temp值放到最終的位置}public static void swap(int []arr,int a ,int b){int temp=arr[a];arr[a] = arr[b];arr[b] = temp;} }

Java 的sort基于什么實現

（快排），全都是快排嗎（不知道）

排序算法原理，何為穩定不穩定，快排是否穩定

查找

二分查找

時間復雜度（logn）

復盤筆試題

筆試題的思路（說說上次筆試第二題為啥沒全對？？（答：估摸著邊界沒處理好）

3.尋找重復的子樹

題目：
給定一棵二叉樹 root，返回所有重復的子樹。
對于同一類的重復子樹，你只需要返回其中任意一棵的根結點即可。
如果兩棵樹具有相同的結構和相同的結點值，則它們是重復的

思路
序列化二叉樹。

1/ \2 3/ \4 5

序列化結果為 1,2,#,#,3,4,#,#,5,#,#。每棵不同子樹的序列化結果都是唯一的。

算法
使用深度優先搜索，其中遞歸函數返回當前子樹的序列化結果。把每個節點開始的子樹序列化結果保存在 mapmap 中，然后判斷是否存在重復的子樹。

class Solution {Map<String, Integer> count;List<TreeNode> ans;public List<TreeNode> findDuplicateSubtrees(TreeNode root) {count = new HashMap();ans = new ArrayList();collect(root);return ans;}public String collect(TreeNode node) {if (node == null) return "#";String serial = node.val + "," + collect(node.left) + "," + collect(node.right);count.put(serial, count.getOrDefault(serial, 0) + 1);if (count.get(serial) == 2)ans.add(node);return serial;} }

樹的遍歷方式

樹的遍歷方式（先序、中序、后序）

先序

遞歸

// 前序遍歷·遞歸·LC144_二叉樹的前序遍歷 class Solution {ArrayList<Integer> preOrderReverse(TreeNode root) {ArrayList<Integer> result = new ArrayList<Integer>();preOrder(root, result);return result;}void preOrder(TreeNode root, ArrayList<Integer> result) {if (root == null) {return;}result.add(root.val); // 注意這一句preOrder(root.left, result);preOrder(root.right, result);} }

非遞歸

// 前序遍歷順序：中-左-右，入棧順序：中-右-左 class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.right != null){stack.push(node.right);}if (node.left != null){stack.push(node.left);}}return result;} }

中序

遞歸

// 中序遍歷·遞歸·LC94_二叉樹的中序遍歷 class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val); // 注意這一句inorder(root.right, list);} }

非遞歸

class Solution {public List<Integer> inorderTraversal(TreeNode root) {Stack<TreeNode> stack=new Stack<>();List<Integer> list=new ArrayList<>();TreeNode cur=root;while (cur!=null || !stack.isEmpty()){while(cur!=null){stack.push(cur);cur=cur.left;}cur=stack.pop();list.add(cur.val);cur=cur.right; }return list;} }

后序

遞歸

// 后序遍歷·遞歸·LC145_二叉樹的后序遍歷 class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root, res);return res;}void postorder(TreeNode root, List<Integer> list) {if (root == null) {return;}postorder(root.left, list);postorder(root.right, list);list.add(root.val); // 注意這一句} }

非遞歸

// 后序遍歷順序 左-右-中 入棧順序：中-左-右 出棧順序：中-右-左， 最后翻轉結果 class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null){return result;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();result.add(node.val);if (node.left != null){stack.push(node.left);}if (node.right != null){stack.push(node.right);}}Collections.reverse(result);return result;} }

如何用數組模擬二叉樹的遍歷過程？

順序二叉樹的滿足條件：
1.一般指完全二叉樹
2.第n個元素的左子樹為2n+1；
3.第n個元素的右子樹為2n+2；
4.第n個子樹的父節點為（n-1）/2;
注意：n為數組下標所以是從0開始

public class ArrBinaryTreeDemo {public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7};ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);//arrBinaryTree.preOrder(0);//arrBinaryTree.infixOrder(0);arrBinaryTree.postOrder(0);} }class ArrBinaryTree {private int[] arr;public ArrBinaryTree(int[] arr) {this.arr = arr;}//前序遍歷數組public void preOrder(int index) {if (arr == null && arr.length == 0) {System.out.println("數組為空");return;}System.out.println(arr[index]);if ((index * 2 + 1) < arr.length) {preOrder(index * 2 + 1);}if ((index * 2 + 2) < arr.length) {preOrder(index * 2 + 2);}}//中序遍歷public void infixOrder(int index) {if (arr == null && arr.length == 0) {System.out.println("數組為空");return;}//先遍歷左子樹 （index*2+1）if ((index * 2 + 1) < arr.length) {infixOrder(index * 2 + 1);}if (index < arr.length) {System.out.print(arr[index] + "\t");}if ((index * 2 + 2) < arr.length) {infixOrder(index * 2 + 2);}}//后序遍歷public void postOrder(int index) {if (arr == null && arr.length == 0) {System.out.println("數組為空");return;}if ((index * 2 + 1) < arr.length) {postOrder(index * 2 + 1);}if ((index * 2 + 2) < arr.length) {postOrder(index * 2 + 2);}`在這里插入代碼片`if (index < arr.length) {System.out.println(arr[index]+"\t");}}}

求二叉樹的深度兩種方法

方法一：深度優先搜索
左子樹和右子樹的最大深度分別為 l 和 r，則二叉樹的最大深度即為 max(l,r)+1

而左子樹和右子樹的最大深度又可以以同樣的方式進行計算。因此用「深度優先搜索」方法計算二叉樹的最大深度。
在計算當前二叉樹的最大深度時，先遞歸計算出其左子樹和右子樹的最大深度，然后在 O(1)時間內計算出當前二叉樹的最大深度。遞歸在訪問到空節點時退出。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;} else {int leftHeight = maxDepth(root.left);int rightHeight = maxDepth(root.right);return Math.max(leftHeight, rightHeight) + 1;}} }

方法二：廣度優先搜索
廣度優先搜索的隊列里存放的是「當前層的所有節點」。每次拓展下一層的時候，每次只從隊列里拿出一個節點，需要將隊列里的所有節點都拿出來進行拓展，這樣能保證每次拓展完的時候隊列里存放的是當前層的所有節點，即一層一層地進行拓展，最后用一個變量ans 來維護拓展的次數，該二叉樹的最大深度即為ans。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int ans = 0;while (!queue.isEmpty()) {int size = queue.size();while (size > 0) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}size--;}ans++;}return ans;} }

棧、隊列

232. 用棧實現隊列

參考網址

入隊（push）
一個隊列是 FIFO 的，但一個棧是 LIFO 的。這就意味著最新壓入的元素必須得放在棧底。為了實現這個目的，我們首先需要把 s1 中所有的元素移到 s2 中，接著把新元素壓入 s2。最后把 s2 中所有的元素彈出，再把彈出的元素壓入 s1。

出隊（pop）
直接從 s1 彈出就可以了，因為 s1 的棧頂元素就是隊列的隊首元素。同時我們把彈出之后 s1 的棧頂元素賦值給代表隊首元素的 front 變量。

判斷空（empty）
s1 存儲了隊列所有的元素，所以只需要檢查 s1 的是否為空就可以了。

取隊首元素（peek）
在我們的算法中，用了 front 變量來存儲隊首元素，在每次 入隊 操作或者 出隊 操作之后這個變量都會隨之更新。

private int front; public void push(int x) {if (s1.empty())front = x;while (!s1.isEmpty())s2.push(s1.pop());s2.push(x);while (!s2.isEmpty())s1.push(s2.pop()); }public void pop() {s1.pop();if (!s1.empty())front = s1.peek(); }public boolean empty() {return s1.isEmpty(); }public int peek() {return front; }

入隊（push）
新元素總是壓入 s1 的棧頂，同時我們會把 s1 中壓入的第一個元素賦值給作為隊首元素的 front 變量。

出隊（pop）
根據棧 LIFO 的特性，s1 中第一個壓入的元素在棧底。為了彈出 s1 的棧底元素，我們得把 s1 中所有的元素全部彈出，再把它們壓入到另一個棧 s2 中，這個操作會讓元素的入棧順序反轉過來。通過這樣的方式，s1 中棧底元素就變成了 s2 的棧頂元素，這樣就可以直接從 s2 將它彈出了。一旦 s2 變空了，我們只需把 s1 中的元素再一次轉移到 s2 就可以了。

判斷空（empty）
s1 和 s2 都存有隊列的元素，所以只需要檢查 s1 和 s2 是否都為空就可以了。

取隊首元素（peek)
我們定義了 front 變量來保存隊首元素，每次 入隊 操作我們都會隨之更新這個變量。當 s2 為空，front 變量就是隊首元素，當 s2 非空，s2 的棧頂元素就是隊首元素。

private Stack<Integer> s1 = new Stack<>(); private Stack<Integer> s2 = new Stack<>();public void push(int x) {if (s1.empty())front = x;s1.push(x); }public void pop() {if (s2.isEmpty()) {while (!s1.isEmpty())s2.push(s1.pop());}s2.pop(); }public boolean empty() {return s1.isEmpty() && s2.isEmpty(); }public int peek() {if (!s2.isEmpty()) {return s2.peek();}return front; }

225. 用隊列實現棧

為了滿足棧的特性，即最后入棧的元素最先出棧，在使用隊列實現棧時，應滿足隊列前端的元素是最后入棧的元素。可以使用兩個隊列實現棧的操作，其中queue1用于存儲棧內的元素，queue2作為入棧操作的輔助隊列。
入棧操作
首先將元素入隊到queue2，然后將queue1的全部元素依次出隊并入隊到queue2,此時queue 2的前端的元素即為新入棧的元素，再將queue1和queue2互換，則 queue1的元素即為棧內的元素，queue1 的前端和后端分別對應棧頂和棧底。

出棧操作
由于每次入棧操作都確保 queue1?的前端元素為棧頂元素，因此出棧操作和獲得棧頂元素操作都可以簡單實現。出棧操作只需要移除queue1的前端元素并返回即可，

獲得棧頂元素操作
只需要獲得queue1的前端元素并返回即可（不移除元素）。

判斷棧是否為空
由于queue1用于存儲棧內的元素，判斷棧是否為空時，只需要判斷 queue1是否為空即可。

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();} }

字符串

序列化與反序列化

題目：
序列化是將一個數據結構或者對象轉換為連續的比特位的操作，進而可以將轉換后的數據存儲在一個文件或者內存中，同時也可以通過網絡傳輸到另一個計算機環境，采取相反方式重構得到原數據。
請設計一個算法來實現二叉樹的序列化與反序列化。這里不限定你的序列 / 反序列化算法執行邏輯，你只需要保證一個二叉樹可以被序列化為一個字符串并且將這個字符串反序列化為原始的樹結構。

思路： 先序遍歷的遞歸思想
1.序列化：先序遍歷結果（StringBuilder節約空間）
2.反序列化：將String類型轉化為二叉樹，

public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {StringBuilder res=ser_help(root,new StringBuilder());return res; }public StringBuilder res(TreeNode root,StringBuilder str){if(root==null){str.append("null,");return str;}//先序遍歷str.append(root.val);str.append(",");str=ser_help(root.left,str);str=ser_help(right.left,str);return str;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {String[] str_word = data.split(",");List<String> list_word = new LinkedList<String>(Arrays.asList(str_word));return deser_help(list_word);}public TreeNode deser_help(List<String> li){if(li.get(0).equals("null")){li.remove(0);return null;}TreeNode res = new TreeNode(Integer.valueOf(li.get(0)));li.remove(0);res.left = deser_help(li);res.right = deser_help(li);return res;} }

?????

統計字母出現次數從大到小排序

給出一個只包含字母的字符串,
不包含空格,統計字符串中各個子字母(區分大小寫)出現的次數,
并按照字母出現次數從大到小的順序輸出各個字母及其出現次數
如果次數相同,按照自然順序排序,且小寫字母在大寫字母之前

public class pr_73 {public static void main(String[] args){Scanner in=new Scanner(System.in);String str=in.nextLine();HashMap<Character,Integer> map=new HashMap<>();for(int i=0;i<str.length();i++){char c=str.charAt(i);if(map.containsKey(c)) map.put(c, map.get(c)+1);else map.put(c,1);}ArrayList<Map.Entry<Character,Integer>> list=new ArrayList<>();list.addAll(map.entrySet());Collections.sort(list, new Comparator<Map.Entry<Character, Integer>>() {@Overridepublic int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {if(o1.getValue()==o2.getValue())return o1.getKey()-o2.getKey();else return o2.getValue()-o1.getValue();}});StringBuilder sb=new StringBuilder();for(int i=0;i<list.size();i++){sb.append(list.get(i).getKey()).append(":").append(list.get(i).getValue()).append(";");}String res= sb.toString();System.out.print(res.substring(0,res.length()-1));} }

字符串中的最長不重復子串

「滑動窗口」

我們使用兩個指針表示字符串中的某個子串（或窗口）的左右邊界，其中左指針代表枚舉子串的起始位置，而右指針即為rk；

將左指針向右移動一格，表示開始枚舉下一個字符作為起始位置，然后不斷地向右移動右指針，但需要保證這兩個指針對應的子串中沒有重復的字符。在移動結束后，這個子串就對應著 以左指針開始的，不包含重復字符的最長子串。記錄下這個子串的長度；

在枚舉結束后，我們找到的最長的子串的長度即為答案。

class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合，記錄每個字符是否出現過Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指針，初始值為 -1，相當于我們在字符串的左邊界的左側，還沒有開始移動int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指針向右移動一格，移除一個字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不斷地移動右指針occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 個字符是一個極長的無重復字符子串ans = Math.max(ans, rk - i + 1);}return ans;} }

動態規劃

跳臺階

public class pr_5_1 {public static void main(String[] args){Scanner in=new Scanner(System.in);while (in.hasNext()){int n= in.nextInt();int res=find(n);System.out.print(res);}}public static int find(int n){//動態規劃int count=0;if(n==1||n==2) return 1;if(n==3) return 2;if(n>3) count=find(n-1)+find(n-3);return count;} } public class pr_5 {public static void main(String[] args){Scanner in=new Scanner(System.in);while (in.hasNext()){int n= in.nextInt();find(0,n);System.out.print(count);}}public static int count=0;public static void find(int cur,int n){//遞歸if(cur==n){count++;return ;}if(cur>n) return ;find(cur+1,n);find(cur+3,n);} }

最長公共子序列

(1) i == 0 || j == 0 LCS(i, j) = 0
(2) Xi ==Yj LCS(i, j) = LCS(i - 1,j- 1) + 1
(3) Xi !=Yj LCS(i, j) = max(LCS(i – 1, j) , LCS(i, j – 1))

public static int findLCS(String A, int n, String B, int m) {int[][] dp = new int[n + 1][m + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (A.charAt(i - 1) == B.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j] , dp[i][j - 1]);}}}return dp[n][m]; }

鏈表

反轉鏈表

題目：
給定單鏈表的頭節點 head ，請反轉鏈表，并返回反轉后的鏈表的頭節點。

方法一：迭代

class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;} }

方法二：遞歸
遞歸版本稍微復雜一些，其關鍵在于反向工作。假設鏈表的其余部分已經被反轉，現在應該如何反轉它前面的部分？

class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;} }

leetcode 445. 兩數相加 II

題目：
給你兩個 非空 鏈表來代表兩個非負整數。數字最高位位于鏈表開始位置。它們的每個節點只存儲一位數字。將這兩數相加會返回一個新的鏈表。
你可以假設除了數字 0 之外，這兩個數字都不會以零開頭。

思路與算法 : 棧
鏈表中數位的順序與做加法的順序是相反的，為了逆序處理所有數位，使用棧：把所有數字壓入棧中，再依次取出相加。計算過程中需要注意進位的情況。

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Deque<Integer> stack1 = new ArrayDeque<Integer>();Deque<Integer> stack2 = new ArrayDeque<Integer>();while (l1 != null) {stack1.push(l1.val);l1 = l1.next;}while (l2 != null) {stack2.push(l2.val);l2 = l2.next;}int carry = 0;ListNode ans = null;while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {int a = stack1.isEmpty() ? 0 : stack1.pop();int b = stack2.isEmpty() ? 0 : stack2.pop();int cur = a + b + carry;carry = cur / 10;cur %= 10;ListNode curnode = new ListNode(cur);curnode.next = ans;ans = curnode;}return ans;} }

尋找字符串最長回文串

思路:

動態規劃的邊界條件：

public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// dp[i][j] 表示 s[i..j] 是否是回文串boolean[][] dp = new boolean[len][len];// 初始化：所有長度為 1 的子串都是回文串for (int i = 0; i < len; i++) {dp[i][i] = true;}char[] charArray = s.toCharArray();// 遞推開始// 先枚舉子串長度for (int L = 2; L <= len; L++) {// 枚舉左邊界，左邊界的上限設置可以寬松一些for (int i = 0; i < len; i++) {// 由 L 和 i 可以確定右邊界，即 j - i + 1 = L 得int j = L + i - 1;// 如果右邊界越界，就可以退出當前循環if (j >= len) {break;}if (charArray[i] != charArray[j]) {dp[i][j] = false;} else {if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此時記錄回文長度和起始位置if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);} }

力扣14. 最長公共前綴

編寫一個函數來查找字符串數組中的最長公共前綴。
如果不存在公共前綴，返回空字符串 “”。

思路：

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];int count = strs.length;for (int i = 1; i < count; i++) {prefix = longestCommonPrefix(prefix, strs[i]);if (prefix.length() == 0) {break;}}return prefix;}public String longestCommonPrefix(String str1, String str2) {int length = Math.min(str1.length(), str2.length());int index = 0;while (index < length && str1.charAt(index) == str2.charAt(index)) {index++;}return str1.substring(0, index);} }

1701 平均等待時間

題目：
有一個餐廳，只有一位廚師。你有一個顧客數組 customers ，其中 customers[i] = [arrivali, timei] ：
arrivali 是第 i 位顧客到達的時間，到達時間按 非遞減 順序排列。
timei 是給第 i 位顧客做菜需要的時間。
當一位顧客到達時，他將他的訂單給廚師，廚師一旦空閑的時候就開始做這位顧客的菜。每位顧客會一直等待到廚師完成他的訂單。廚師同時只能做一個人的訂單。廚師會嚴格按照 訂單給他的順序 做菜。
請你返回所有顧客需要等待的 平均 時間。與標準答案誤差在 10-5 范圍以內，都視為正確結果。

示例 1：

輸入：customers = [[1,2],[2,5],[4,3]] 輸出：5.00000 解釋： 1) 第一位顧客在時刻 1 到達，廚師拿到他的訂單并在時刻 1 立馬開始做菜，并在時刻 3 完成，第一位顧客等待時間為 3 - 1 = 2 。 2) 第二位顧客在時刻 2 到達，廚師在時刻 3 開始為他做菜，并在時刻 8 完成，第二位顧客等待時間為 8 - 2 = 6 。 3) 第三位顧客在時刻 4 到達，廚師在時刻 8 開始為他做菜，并在時刻 11 完成，第三位顧客等待時間為 11 - 4 = 7 。 平均等待時間為 (2 + 6 + 7) / 3 = 5 。 class Solution {public double averageWaitingTime(int[][] customers) {long endTime = 0;long sum = 0;for (int[] customer : customers) {if (endTime <= customer[0]) {endTime = customer[0];}endTime += customer[1];sum += (endTime - customer[0]);}return sum * 1.0 / customers.length;} }

總結

以上是生活随笔為你收集整理的【华为面试手撕代码】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。