1 二維數(shù)組中的查找

public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array.length == 0) {
            return false;
        }
        int len1 = array.length;//求行
        int len2 = array[0].length;//求列
        for (int j = len2 - 1; j >= 0; j--) {
            for (int i = 0; i <= len1 - 1; i++) {
                if (target < array[i][j]) {
                    break;
                }else if (target > array[i][j]) {
                    continue;
                }else {
                    return true;
                }
            }
        }
        return false;
    }
}

2 替換字符串

public class Solution {
    public String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == ' ') {
                str.replace(i,i+1,"%20");
            }
        }
        return str.toString();
    }
}

3 從尾到頭打印鏈表

import java.util.Stack;//注意添加包
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if (listNode == null) {
            ArrayList<Integer> list = new ArrayList<>();
            return list;
        }
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }
}

4 重建二叉樹

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
         if(pre.length == 0||in.length == 0){
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for(int i = 0; i < in.length; i++){
            if(pre[0] == in[i]){
                node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
            }
        }
        return node;
    }
    
}

5 兩個(gè)棧實(shí)現(xiàn)隊(duì)列

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if (stack2.isEmpty()) {//只有當(dāng)stack2為空時(shí)才一次性將stack1中的數(shù)據(jù)全部壓入
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

6 旋轉(zhuǎn)數(shù)組的最小數(shù)字

//二分查找
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        int low = 0;
        int high = array.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (array[mid] > array[high]) {//注意是拿mid和high比
                low = mid + 1;
            }else if (array[mid] < array[high]) {
                high = mid;
            }else {
                high -= 1;
            }
        }
        return array[low];
    }
}

7 斐波那契數(shù)列

//1,1,2,3,5,8,13,21
public class Solution {
    public int Fibonacci(int n) {
        if (n == 0) {
            return 0;
        }
        int a = 1, b = 1, c = 0;
        if (n == 1 || n == 2) {
            return 1;
        }else {
            for (int i = 3; i <= n; i++) {
                c = a + b;
                a = b;
                b = c;
            }
        }
        return c;
    }
}

8 跳臺(tái)階

//變版斐波那契數(shù)列:1,2,3,5,8,13,21
//當(dāng)前臺(tái)階的跳法總數(shù)=當(dāng)前臺(tái)階后退一階的臺(tái)階的跳法總數(shù)+當(dāng)前臺(tái)階后退二階的臺(tái)階的跳法總數(shù)
//n級(jí)=n-1級(jí)的每個(gè)方法后面添上1浑槽，n-2級(jí)的每個(gè)方法后面填上2

public class Solution {
    public int JumpFloor(int target) {
        if (target <= 0) {
            return 0;
        }
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3; i <= target; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
}

9 變態(tài)跳臺(tái)階

//n = 之前所以方法的和再加1,
//1,2,4,8,16,32
public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 0) {
            return 0;
        }
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        int sum = 3;
        int c = 0;
        for (int i = 3; i <= target; i++) {
            sum = sum + c;
            c = sum + 1;
        }
        return c;
    }
}

10 矩形覆蓋

//變斐波那契:1,2,3,5,8,13,21债热；同跳臺(tái)階
public class Solution {
    public int RectCover(int target) {
        if (target <= 0) {
            return 0;
        }
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        int a = 1;
        int b = 2;
        int c = 0;
        for (int i = 3; i <= target; i++) {
            c = a + b;
            a = b; 
            b = c;
        }
        return c;
    }
}

11 二進(jìn)制中1的個(gè)數(shù)

//一個(gè)數(shù)減去1再和這個(gè)數(shù)做位與運(yùn)算，結(jié)果是將這個(gè)數(shù)  最  右邊的那位1置0.一直操作直到這個(gè)數(shù)為0，這樣有幾個(gè)1就操作幾次
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {//java中必須為boolean表達(dá)式
            count++;
            n = (n - 1) & n;
        }
        return count;
    }
}

12 數(shù)值的整數(shù)次方

import java.util.*;
public class Solution {
    public double Power(double base, int exponent) {
        if (base ==0.0 & exponent < 0) {//如果底數(shù)為0，且指數(shù)為負(fù)數(shù)，需要取倒數(shù)，但0不能做分母。
            return 0.0;
        }
        int abs = Math.abs(exponent);//取絕對(duì)值
        double result = pow(base, abs);//求指數(shù)為絕對(duì)值時(shí)的結(jié)果
        if (exponent < 0) {
            return 1 / result;
        }
        return result;
  }
    public double pow(double base, int abs) {
        if (abs == 0) {//絕對(duì)值為0蝉仇，返回1.0
            return 1.0;
        }
        if (abs == 1) {//絕對(duì)值為1，返回底數(shù)
            return base;
        }
        double re = pow(base,abs >> 1);
        re *= re;
        if ((abs & 1) == 1) {//奇數(shù)要多乘個(gè)base,
            return re *= base;
        }
        return re;
    }
}

13 奇數(shù)位于偶數(shù)前

//快排殖蚕，不能保證相對(duì)位置不變轿衔。
//low奇數(shù)，low向后走直到遇到偶數(shù)睦疫。
//high是偶數(shù)害驹，high向前走直到遇到奇數(shù)。
//如果low在high前蛤育，交換宛官。
public class Solution {
    public void reOrderArray(int [] array) {
        if (array.length == 0) {
            return;
        }        
        int low = 0;
        int high = array.length - 1;
        while (low < high) {
            while ((array[low] & 1) == 1) {//位與比求余效率高
                low += 1;
            }
            while ((array[high] & 1) == 0) {
                high -= 1;
            }
            if (low < high) {
                int temp = array[low];
                array[low] = array[high];
                array[high] = temp;
            }
        }
    }
}

//插入排序葫松，保證相對(duì)位置不變
//第1個(gè)數(shù)先不管，i從第2個(gè)數(shù)開始向后走底洗，先找到第1個(gè)奇數(shù)
//j=i腋么，找到j(luò)前一個(gè)偶數(shù)，j向前走亥揖，一次換
//2党晋，4，6徐块，5，7：i先走到5灾而，j也定位到5胡控，5和6，4旁趟，2依次換
public class Solution {
    public void reOrderArray(int [] array) {
        if (array.length == 0) {
            return;
        }
        for (int i = 1; i < array.length; i++) {
            int target = array[i];
            if ((array[i] & 1) == 1) {//如果為奇數(shù)
                int j = i;
                while (j >= 1 && (array[j - 1] & 1) == 0 ) {
                    array[j] = array[j - 1];
                    j--;
                }
                array[j] = target;
            }
        }
    }
}

14 輸入一個(gè)鏈表昼激，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

/*
1.定義兩個(gè)游標(biāo)p1锡搜，p2橙困，其中p2先走k步，然后p1和p2一起走耕餐，當(dāng)p2走到空時(shí)凡傅，p1為倒數(shù)第k個(gè)結(jié)點(diǎn)
2.需要驗(yàn)證head為空，k<1肠缔，k大于鏈表長(zhǎng)度三種情況
*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null || k < 1) 
            return null;
        ListNode p1 = head;
        ListNode p2 = head;
        for (int i = 0; i < k; i++) {
            if (p2 == null)//當(dāng)k大于鏈表長(zhǎng)度時(shí)會(huì)發(fā)生
                return null;
            p2 = p2.next;
        }
        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;           
    }
}

15 反轉(zhuǎn)鏈表

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newHead = null;
        ListNode pNode = head;
        ListNode pPre = null;
        while (pNode != null) {
            ListNode pNext = pNode.next;//若pNode一開始為空夏跷，這句話寫到外面就是錯(cuò)的
            if (pNext == null) {
                newHead = pNode;
            }
            pNode.next = pPre;
            pPre = pNode;
            pNode = pNext;
        }
        return newHead;
    }
}

16 合并兩個(gè)排序鏈表

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode node = null;
        if (list1.val <= list2.val) {
            node = list1;
            node.next = Merge(list1.next, list2);
        }else {
            node = list2;
            node.next = Merge(list1, list2.next);
        }
        return node;
    }
}

17 樹的子結(jié)構(gòu)

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        boolean flag = false;
        if (root1.val == root2.val) {//如果根值相同才去判斷是否為子結(jié)構(gòu)，以這個(gè)根點(diǎn)開始
            flag = IsSubtree(root1, root2);//判斷是否為子結(jié)構(gòu)的方法
        }
        if (!flag) {//以這個(gè)點(diǎn)開始的明未，不是子結(jié)構(gòu)
            flag = HasSubtree(root1.left, root2);//左子樹結(jié)點(diǎn)和root2比
            if (!flag) {
                flag = HasSubtree(root1.right, root2);//如果左子樹不是槽华，比較右子樹
            }
        }
        return flag;
    }
    public boolean IsSubtree(TreeNode root1, TreeNode root2) {
        if (root2 == null) {//右樹已比完，左樹還有趟妥，情況正確
            return true;
        }
        if (root1 == null && root2 != null) {//左樹已完猫态，右樹還有，錯(cuò)誤
            return false;
        }
        if (root1.val == root2.val) {
            return IsSubtree(root1.left, root2.left) && IsSubtree(root1.right, root2.right);
        }else {
            return false;
        }
    }
}

18 樹的鏡像

public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {//葉結(jié)點(diǎn)
            return;
        }
        TreeNode pTemp = root.left;//交換root的左右子樹
        root.left = root.right;
        root.right = pTemp;
        if (root.left != null) {//還有子結(jié)點(diǎn)
            Mirror(root.left);
        }
        if (root.right != null) {
            Mirror(root.right);
        }
    }
}

19 順時(shí)針打印矩陣

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer> list = new ArrayList<>();
       if (matrix.length == 0) return list;
       int len1 = matrix.length;
       int len2 = matrix[0].length;
       int layers = (Math.min(len1, len2) + 1) / 2;
        
       for (int i = 0; i < layers; i++) {
           for (int m = i; m < len2 - i; m++) {//注意考慮一列
               list.add(matrix[i][m]);
           }
           for (int n = i + 1; n < len1 - i; n++) {//注意考慮一行
               list.add(matrix[n][len2 - 1 - i]);
           }
           for (int p = len2 - 2 - i; (p >= i) && (len1 - 1 - i != i);p--) {//防止只有一行
               list.add(matrix[len1 - 1 - i][p]);
           }
           for (int k = len1 - 2 - i; (k > i) && (len2 - 1 - i != i);k--) {//防止只有一列
               list.add(matrix[k][i]);
           }
       }
       return list;
    }
}