常見面試算法題
1. 判斷連結清單是否有環
- 快慢指針法
import jianzhiOffer.ListNode; //判斷連結清單是否有環 public class HasCycle { public boolean hasCycle(ListNode head){ /*快慢指針法*/ if (head == null){ return false; } ListNode slowPoint = head; ListNode fastPoint = head.next; while (slowPoint != fastPoint){ if (fastPoint == null || slowPoint==null){ return false; } slowPoint = slowPoint.next; fastPoint = fastPoint.next.next; } return true; } }
2. 合并有序連結清單
import jianzhiOffer.ListNode;
public class MergeTwoList {
public static void main(String[] args) {
ListNode head1 = new ListNode(1);
ListNode node2 = new ListNode(3);
ListNode node3 = new ListNode(4);
ListNode node4 = new ListNode(7);
ListNode head2 = new ListNode(2);
ListNode node22 = new ListNode(5);
ListNode node23 = new ListNode(7);
ListNode node24 = new ListNode(9);
node3.next = node4;
node2.next = node3;
head1.next = node2;
node23.next = node24;
node22.next = node23;
head2.next = node22;
// ListNode newHead = merge(head1, head2);
ListNode newHead = merge(head1,null);
while (newHead != null){
System.out.println(newHead.val);
newHead = newHead.next;
}
}
public static ListNode merge(ListNode head1,ListNode head2){
if (head1==null || head2==null){
return head1==null?head2:head1;
}
ListNode p1 = head1;
ListNode p2 = head2;
ListNode dummyHead = new ListNode();
ListNode preNode = dummyHead;
while (p1 != null && p2 != null){
preNode.next = p1.val<=p2.val ? p1:p2;
preNode = preNode.next;
if (p1.val <= p2.val){
p1 = p1.next;
}else {
p2 = p2.next;
}
}
preNode.next = p1==null?p2:p1;
return dummyHead.next;
}
}
3. 判斷括号序列是否合法
leetcode 20
輔助棧，左括号入棧，碰到右括号則将棧頂元素出棧，看看是不是比對，不比對傳回false，比對則繼續，如果周遊到最後一個括号，棧正好空了，說明整個字元串合法
public class ValidParentheses { /*合法的括号字元串*/ public static void main(String[] args) { String str1 = "()"; String str2 = "(){}[]"; String str3 = ""; String str4 = "{[)]}"; System.out.println(isValidParentheses(str1)); System.out.println(isValidParentheses(str2)); System.out.println(isValidParentheses(str3)); System.out.println(isValidParentheses(str4)); } private static boolean isValidParentheses(String parentheses){ Map<String ,String> assistMap = new HashMap<>(); assistMap.put(")","("); assistMap.put("]","["); assistMap.put("}","{"); Stack<String> assistStack = new Stack<>(); for (int i=0; i<parentheses.length(); i++){ String s = parentheses.substring(i,i+1); if (assistMap.containsKey(s)){ //如果是右括号，判斷棧頂是不是對應的左括号 String top = assistStack.isEmpty()?"#":assistStack.pop(); if (!top.equals(assistMap.get(s))){ return false; } }else { //如果是非右括号，入棧 assistStack.push(s); } } return assistStack.isEmpty(); } }
4. 跳台階
可以從第n-1個台階跳一步到，跳上第n個台階，或者從第n-2個台階跳2步到n，是以調上第n個台階的方法等于跳上第n-1個台階的方法加上跳上第n-2個台階的方法，符合斐波那契數列，是以這個問題等同于求斐波那契的第n項
5. 求數組中的連續子數組的最大累加和 劍指offer42
- 設定一個max，初始化為一個非常小的值，再設定一個tempSum，用于試探累積下一個元素的結果
- tempSum逐個累加數組元素，每加上一個，比較tempSum的值是不是大于max，如果是，更新max；
- 還要比較tempSum是不是變成了負數，如果是，說明這次加到tempSum的元素太小了，子數組裡不能包括它，不然絕對得不到最大累加和，是以把tempSum設為0，從下一個元素開始重新累加。
public class FindGreatestSumOfSubArray { /*找到數組中連續子數組的最大累加和*/ public static void main(String[] args) { System.out.println(findGreatestSumOfSubArray(new int[]{1, -2, 3, 5, -2, 6, -1})); System.out.println(findGreatestSumOfSubArray(new int[]{0,0,0,0,0,3,0,0,0})); } private static int findGreatestSumOfSubArray(int[] nums){ int max = Integer.MIN_VALUE; int tempSum = 0; int length = nums.length; for (int i=0; i<length; i++ ){ tempSum += nums[i]; max = Math.max(tempSum,max); if (tempSum < 0){ tempSum = 0; } } return max; } }
6. 求二叉樹最大深度或最小深度
遞歸，如果不是葉子節點，則傳回節點左右子樹深度最大的那個，最大深度和最小深度可以同一求法，隻不過最小深度是傳回較小的那個深度public class FindMDepth { /*找一棵樹的最大深度，一棵樹的最大深度等于其左子樹和右子樹的最大深度+1 * 同理，一棵樹的最小深度等于其左子樹和右子樹最小深度+1 * 是以，可以遞歸周遊一棵樹的所有節點的左右子樹，傳回比較大或者比較小的深度*/ public static void main(String[] args) { } private static int findMaxDeprth(TreeNode root){ if (root == null){ return 0; } int leftDepth = findMaxDeprth(root.leftChild); int rightDepth = findMaxDeprth(root.rightChild); return Math.max(leftDepth, rightDepth)+1; } private static int findMinDeprth(TreeNode root){ if (root == null){ return 0; } int leftDepth = findMaxDeprth(root.leftChild); int rightDepth = findMaxDeprth(root.rightChild); return Math.min(leftDepth, rightDepth)+1; } }
7. 找到一個數組中的兩個數，他們的和等于target
用HashMap做，但是注意是數組元素為Key,下标為value。周遊數組，先求target-目前元素，然後看看Map裡面有沒有以這個差為key的鍵值對，如果有，傳回，沒有的話，存入<元素，下标>。import java.util.HashMap; import java.util.Map; public class TwoSum { /*在一個數組中找出兩個數，使他們的和等于一個目标值，傳回兩個數在數組中的出現順序，注意不是下标 * 例如： 給出的數組為 {2, 7, 11, 15},目标值為9 輸出 index1=1, index2=2 */ public static void main(String[] args) { } private static int[] twoSum(int[] numbers,int target){ Map<Integer,Integer> numberMap = new HashMap<>(); int[] result = new int[]{0,0}; int length = numbers.length; for (int i=0; i<length; i++){ int anotherNum = target-numbers[i]; if (numberMap.containsKey(anotherNum)){ result[1] = i+1; result[0] = numberMap.get(anotherNum)+1; break; }else { numberMap.put(numbers[i],i); } } return result; } }
8. 二叉樹鏡像
前序周遊二叉樹，交換每一個節點的左右子樹import jianzhiOffer.ListNode; public class MirrorOfBinaryTree { /*求一刻二叉樹的鏡像*/ private static TreeNode mirrorOfBinaryTree(TreeNode root){ if (root == null) return root; //前序周遊，交換每個結點的左右子樹 TreeNode tempNode = root.leftChild; root.leftChild = root.rightChild; root.rightChild = tempNode; mirrorOfBinaryTree(root.leftChild); mirrorOfBinaryTree(root.rightChild); return root; } }
9. 找出數組中隻出現了一次的數
可以用Set實作，如果，把每個數add到set中，如果傳回true，說明set中沒有添加過這個數，如果傳回false，說明這個數已經存在于set中，即這個數重複了，然後從set中remove這個重複的數import java.util.Arrays; import java.util.HashSet; import java.util.Set; public class OnceOcurredNum { public static void main(String[] args) { int[] nums = new int[]{0,1,3,4,3,6,13,4,9,23}; System.out.println(Arrays.toString(getOnceOcurredNum(nums))); } private static int[] getOnceOcurredNum(int[] nums){ Set<Integer> numSet = new HashSet<>(); for (int number : nums) { if (!numSet.add(number)){ numSet.remove(number); }else{ numSet.add(number); } } return numSet.stream().mapToInt(Integer::intValue).toArray(); } }
10. 二叉搜尋樹的第k小的節點
中序周遊二叉樹，得到的結果就是節點的從小到大排序，那麼第k-1個節點就是第k小的節點public class KthNodeOfBinaryTree { int index = 0; private TreeNode findKthNodeOfBinaryTree(TreeNode pRoot, int k){ TreeNode result = null; //周遊左節點 if (pRoot.left != null){ result = findKthNodeOfBinaryTree(pRoot.left,k); } //如果當前節點的左節點為null，則周遊目前節點 index++; if (k==index) { result = pRoot; } // 如果還未找到第k個節點，且右節點不為空,才去周遊右節點 if (result==null && pRoot.right != null){ result = findKthNodeOfBinaryTree(pRoot.right,k); } return result; } private TreeNode KthNode(TreeNode root, int k){ if (root == null || k<=0){ return null; } return findKthNodeOfBinaryTree(root,k); } }
11. 判斷一個連結清單是否為回文結構
先看看怎麼找一個連結清單的中間節點
設定兩個指針，一快一慢，慢的每次走一步，快的每次走兩步，當快指針為null（偶數節點）或者快指針的next為null（奇數節點）時，此時慢指針即指向中間節點。
兩個方法：public ListNode middleNode(ListNode head) { ListNode fast = head; ListNode slow = head; //每次移動之前，都要判斷fast是否為null，或者fast.next是否為null，才能移動 while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } /*退出循環後，快指針有兩種情況 * 1、連結清單偶數個節點，快指針指向null，即尾結點的next,慢指針指向第n/2+1個節點 * 2、連結清單奇數個節點，快指針指向尾結點，不為null，慢指針指向第（n+1）/2個節點*/ return slow; }
- 把所有節點依次壓入棧中，然後挨個出棧，與連結清單節點比較，如果都相等，則是回文結構
- 快慢指針法，結合棧實作，設定快慢指針，找到中間節點，然後把中間節點開始的節點全部入棧，這樣就不用把所有節點全部入棧
/*快慢指針加反轉連結清單實作， AC*/ public boolean isPalindrome2(ListNode head){ //空連結清單或者單節點連結清單，傳回true if (head==null ){ return true; } if (head.next == null){ return true; } //快慢指針 ListNode fastPoint = head; ListNode slowPoint = head; //找中間節點 ListNode midNode = null; while (fastPoint!=null && fastPoint.next!=null){ fastPoint = fastPoint.next.next; slowPoint = slowPoint.next; } midNode = slowPoint; /*退出循環後，快指針有兩種情況 * 1、連結清單偶數個節點，快指針指向null，即尾結點的next * 2、連結清單奇數個節點，快指針指向尾結點，不為null*/ ListNode newHead = null; if(fastPoint == null){ //如果是偶數個節點 newHead = reverseList(midNode); }else { //如果是奇數個節點 newHead = reverseList(midNode.next); } //開始比較 while (newHead != null){ if (newHead.val!=head.val){ return false; }else { newHead = newHead.next; head = head.next; } } return true; } public static ListNode reverseList(ListNode head){ if(head == null || head.next==null){ return head; } ListNode firstNodeOfNewList = null; ListNode nextNode = null; ListNode curNode = head; //目前周遊的節點 while (curNode != null){ // 1、取出目前節點的next nextNode = curNode.next; //2、把目前節點接到新連結清單上 curNode.next = firstNodeOfNewList; //3、讓目前節點成為新連結清單的第一個節點 firstNodeOfNewList = curNode; //4、nextNode成為下一個周遊的節點 curNode = nextNode; } //循環退出後，curNode指向的是原來連結清單尾部的null節點，firstNodeOfNewList指向新結點的頭部，也是原節點的尾部 return firstNodeOfNewList; }
12. 股票買入和賣出能獲得的最大利潤
周遊每一個數組，然後找到之前最低的股價，兩者之差就是在現在這天賣出股票能獲得的最大利潤。有一個問題是怎麼獲得曆史股價的最低值，我們需要設定一個min變量，它存儲着目前的曆史最低股價，還需要儲存一個maxProfit，它儲存着曆史最大利潤，每次循環都判斷是否更新這兩個值。import java.util.Map; public class MaxProfit { /*買賣股票能得到的最大利潤 * 基本思路：每天都算一下，當天的股價減去曆史最低點的股價，得到的利潤是不是最大利潤，是則更新最大利潤*/ public int maxProfit(int[] prices){ //曆史最低股價 int lowestPrice = Integer.MAX_VALUE; int maxProfit = 0; //逐天周遊，計算利潤，當天賣出的最大利潤 for (int price : prices) { //判斷是否要更新曆史最低股價 lowestPrice = Math.min(price,lowestPrice); //判斷是否要更新最大利潤 maxProfit = Math.max(price - lowestPrice, maxProfit); } return maxProfit; } }
13. 設計一個有getMin()功能的棧
利用兩個棧來實作，其中一個棧allDataStack正常存儲元素，另一個棧minStack的棧頂始終是棧中最小元素。
- 入棧：入棧前先判斷待入棧元素是不是小于或等于allDateStack的棧頂元素，是的話需要存入minStack，不是的話，隻入allDataStack
- 出棧：需要注意，如果出棧元素值等于minStack元素的棧頂，那麼需要把minStack的棧頂也彈出去，minStack不能包含allData中不存在的元素
- getMin：隻peek()minData，不pop
14. 合并兩個有序數組，比如A和B，兩個數組合并到A中，A的空間足夠大
從兩個數組的最後一個元素開始比較，A[i]和B[j]中比較大的數放到A數組的尾部，如果i活着j中某一個下标變成了0，就把另一個數組剩下的元素全部放到A中
15. 斐波那契數列
遞歸實作
- 循環實作
16. 反轉數字
leetCode第7題
除10取餘，得到最後一位數字，然後result = result*10+最後一位數，注意溢出
17. 判斷二叉樹有沒有一條從根節點到葉子節點的路徑的和等于一個目标值
遞歸周遊每一條路徑，每周遊一個節點，用目标值sum減去節點值，如果到了葉子節點(leftnull && rightnull)，sum==0，則說明存在這樣的路徑。
18. 判斷對稱二叉樹
分别用前序周遊和對稱前序周遊兩種方法來周遊二叉樹，如果最後得到的序列是對稱的，則是對稱二叉樹，需要注意：就算節點為null，也需要把節點加入到序列中。
19. 找出在數組中出現次數超過數組長度一半的數字 劍指offer 39
- 方法1：随機快排方法，不懂
- 方法2：從頭開始周遊數組，我們需要在每次周遊時修改儲存兩個量，一個是數組中的數字，另一個是次數。如果目前周遊到的數字和現在儲存的數字相同，則把次數加1，如果不同，減1，如果減到次數為0了，就把儲存的數字換成目前周遊到的數字。最後肯定隻有出現次數超過一半的那個數字最終的次數能夠大于0
20. 反轉連結清單
21. 排序算法
1. 冒泡
package sort;
import java.util.Arrays;
/*冒泡排序需要對每一個元素進行冒泡，找到它能達到的最後的位置*/
public class BubbleSort {
public static void main(String[] args) {
int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
bubbleSort(nums);
System.out.println(Arrays.toString(nums));
}
private static void bubbleSort(int[] nums){
if (nums == null || nums.length <= 1){
return;
}
int length = nums.length;
for (int i=0; i<length; i++){
for (int j=0; j< length-i-1; j++){
if (nums[j]>nums[j+1]){
//如果目前數字大于他的下一個數，那麼就交換他倆的位置
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
}
private static void swap(int curNum, int num) {
int temp = curNum;
curNum = num;
num = temp;
}
}
2. 插入
package sort;
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
insertSort(nums);
System.out.println(Arrays.toString(nums));
}
private static void insertSort(int[] nums){
if (nums == null || nums.length <= 1){
return;
}
int length = nums.length;
int temp = 0;
// i從1 到 數組末尾
for (int i=1; i<length; i++){
// j 從i到1
for (int j=i; j>0; j--){
//比較目前數和前一個數，如果比前一個數小，交換位置
if (nums[j] < nums[j-1]){
//交換兩數
temp = nums[j];
nums[j] = nums[j-1];
nums[j-1] = temp;
}
}
}
}
}
3. 歸并
package sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// int[] nums = {3, 44, 38, 5, 47, 15};
mergeSort(nums);
System.out.println(Arrays.toString(nums));
}
private static int[] assistArray = null;
private static void mergeSort(int[] nums){
int leftIndex = 0;
int rightIndex = nums.length-1;
int midIndex = (leftIndex+rightIndex)/2;
assistArray = new int[nums.length]; //輔助數組
mergeSort(nums,leftIndex,rightIndex);
}
private static void mergeSort(int[] nums, int leftIndex, int rightIndex) {
if (leftIndex < rightIndex){
//不斷遞歸，拆分數組，直到數組中隻有一個元素
//1、計算中間坐标
int midIndex = (leftIndex+rightIndex)/2;
//2、繼續拆分左半邊
mergeSort(nums,leftIndex,midIndex);
//3、繼續拆分右半邊
mergeSort(nums,midIndex+1,rightIndex);
//兩邊都拆成了隻有一個元素的數組，就可以開始合并了
merge(nums,leftIndex,midIndex,rightIndex);
}
}
private static void merge(int[] nums, int leftIndex, int midIndex, int rightIndex) {
int p1 = leftIndex;
int p2 = midIndex+1;
int k = leftIndex;
//合并兩個數組
while (p1<=midIndex && p2<=rightIndex){
assistArray[k++] = nums[p1]<nums[p2]?nums[p1++]:nums[p2++];
}
while (p1<=midIndex){
assistArray[k++] = nums[p1++];
}
while (p2<=rightIndex){
assistArray[k++] = nums[p2++];
}
//把排好序的這部分放到原數組中
for (int i=leftIndex; i<=rightIndex; i++){
nums[i] = assistArray[i];
}
}
}
4. 快排
package sort;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// int[] nums = {3, 44, 38, 5, 47, 15};
quickSort(nums);
System.out.println(Arrays.toString(nums));
}
private static void quickSort(int[] nums){
quickSort(nums,0,nums.length-1);
}
private static void quickSort(int[] nums,int low,int high){
if (low >= high){
return;
}
int pLeft=low; //
int pRight=high;
int curNum = nums[low]; //最左邊的數作為基準數
while (pLeft<pRight){
//先移動右邊的指針
while (nums[pRight] >= curNum && pLeft<pRight){
pRight--;
}
//移動左邊的指針
while (nums[pLeft] <= curNum && pLeft<pRight){
pLeft++;
}
if (pLeft < pRight){
//這是左邊指針指向了比基準數大的數，右邊的指針指向了比基準數小的數
//交換兩個數
int temp = nums[pRight];
nums[pRight] = nums[pLeft];
nums[pLeft] = temp;
}
}
//外部的while退出時，說明 pLeft和 pRight相遇
//交換基準數與相遇處的元素
nums[low] = nums[pLeft];
nums[pLeft] = curNum;
//繼續遞歸對左邊數組排序
quickSort(nums,low,pLeft-1);
//遞歸對右邊數組排序
quickSort(nums,pLeft+1,high);
}
}
5. 選擇
package sort;
import java.util.Arrays;
/*快速排序，從第一個元素開始，找數組中最小的元素，放到第一個位置，然後找第二小的放到第二個位置*/
public class SelectSort {
public static void main(String[] args) {
int[] nums = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
selectSort(nums);
System.out.println(Arrays.toString(nums));
}
private static void selectSort(int[] nums){
if (nums == null || nums.length<=1){
return;
}
for (int i=0; i<nums.length; i++){
int minIndex = i;
for (int j=i; j<nums.length; j++){
if (nums[j] < nums[minIndex]){
minIndex = j;
}
}
if (i != minIndex){
//交換nums[i]和num[minIndex]
nums[i] = nums[minIndex]-nums[i];
nums[minIndex] = nums[minIndex]-nums[i];
nums[i] = nums[minIndex] + nums[i];
}
}
}
}
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)