1、二维数组中的查找

  1. 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
  2. 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，
  3. 判断数组中是否含有该整数。
  4. [
  5.   [1,2,8,9],
  6.   [2,4,9,12],
  7.   [4,7,10,13],
  8.   [6,8,11,15]
  9. ]
  10. 给定 target = 7，返回 true。
  11. 给定 target = 3，返回 false。

  • 解法一

    • 每一行记录都是一个一维有序数组，可以用二分查找
      1. public class Solution {
      2. public boolean Find(int target, int [][] array) {
      3.    for(int i=0;i<array.length;i++){
      4.        int low=0;
      5.        int high=array[i].length-1;
      6.        while(low <= high){
      7.            int mid = (low+high)/2;
      8.            if(target > array[i][mid])
      9.                low=mid+1;
      10.            else if(target < array[i][mid])
      11.                high=mid-1;
      12.            else
      13.                return true;
      14.        }
      15.    }
      16.    return false;
      17. }
      18. }

  • 解法二

    • 利用此二维数组的性质，从上到下递增，从左到右递增
    • 那么从左下或者右上作为起点
      • 小于左下就i—，大于左下就j++s
      • 或者 小于右上就j—，大于右上就i++
        1. public class Solution {
        2. public boolean Find(int target, int [][] array) {
        3. int row=array.length-1;
        4. int col=0;
        5. while(row>=0 && col<array[0].length){
        6.     if(array[row][col] == target){
        7.         return true;
        8.     }else if(array[row][col] > target){
        9.         row--;
        10.     }else{
        11.         col++;
        12.     }
        13. }
        14. return false;
        15. }
        16. }

        2、替换空格

        1. 请实现一个函数，将一个字符串中的每个空格替换成“%20”。
        2. 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

  • 方法一

    • 利用Java中String 类的方法 String replace(CharSequence old, CharSequence new) ```java import java.util.*;

public class Solution { /**

  1.  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  2.  *
  3.  * 
  4.  * @param s string字符串 
  5.  * @return string字符串
  6.  */
  7. public String replaceSpace (String s) {
  8.     // write code here
  9.     return s.replace(" ","%20");
  10. }

}

  2. - 方法二
  3.    - 利用StringBuilder不用重新建立字符串，更快速，效率高
  4. ```java
  5. import java.util.*;
  7. public class Solution {
  8.     public String replaceSpace (String s) {
  9.         // write code here
  10.         StringBuilder sb = new StringBuilder();
  11.         for(char c : s.toCharArray()){
  12.             sb.append(c==' '?"%20":c);
  13.         }
  14.         return sb.toString();
  15.     }
  16. }

3、从尾到头打印链表

  1. 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
  • 解法一
    • 建立一个辅助数组arr来将链表值进行反转即可 ```java /**
  • public class ListNode {
  • int val;
  • ListNode next = null; *
  • ListNode(int val) {
  • this.val = val;
  • }
  • } */ import java.util.ArrayList; public class Solution { public ArrayList printListFromTailToHead(ListNode listNode) { int len = 0; ListNode p = listNode; while(p != null){
    1.    len++;
    2.    p = p.next;
    } int arr[] =new int[len]; p = listNode; int t = len-1; while(p != null){
    1.    arr[t] = p.val;
    2.    t--;
    3.    p = p.next;
    } ArrayList list = new ArrayList(len); for(int i=0;i<len;i++){
    1.    list.add(arr[i]);
    } return list; } } ```
  • 解法二
    • 利用递归，先往链表后面走，再add到ArrayList中 ```java /**
  • public class ListNode {
  • int val;
  • ListNode next = null; *
  • ListNode(int val) {
  • this.val = val;
  • }

  • } / import java.util.ArrayList; public class Solution { ArrayList list = new ArrayList(); public ArrayList printListFromTailToHead(ListNode listNode) { if(listNode != null){

    1.    this.printListFromTailToHead(listNode.next);
    2.    list.add(listNode.val);

    } return list; } }

    1. <a name="Lkb5N"></a>
    2. # 4、重建二叉树
    3. ```java
    4. 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
    5. 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
    6. 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
    1. /**
    2. * Definition for binary tree
    3. * public class TreeNode {
    4. *     int val;
    5. *     TreeNode left;
    6. *     TreeNode right;
    7. *     TreeNode(int x) { val = x; }
    8. * }
    9. */
    10. public class Solution {
    11. public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    12.    TreeNode root=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
    13.    return root;
    14. }
    15. //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    16. private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
    18.    if(startPre>endPre||startIn>endIn)
    19.        return null;
    20.    TreeNode root=new TreeNode(pre[startPre]);
    22.    for(int i=startIn;i<=endIn;i++)
    23.        if(in[i]==pre[startPre]){
    24.            root.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
    25.            root.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn);
    26.                  break;
    27.        }
    29.    return root;
    30. }
    31. }

    5、用两个栈实现一个队列

    1. 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型
  • 方法
    • Push操作，当栈1还没满时，则往栈1添加push；当栈1满了时，则将栈1全部数据往栈2移动，再push数据到栈1
    • Pop操作，当栈2不为空，则pop栈2数据；栈2为空，则将栈1全部数据移动到栈2再pop栈2数据 ```java import java.util.Stack;

public class Solution { Stack stack1 = new Stack(); Stack stack2 = new Stack(); int count; public void push(int node) { // 如果栈1满了，就往栈2里移动 if(count == stack1.size()){ while(!stack1.isEmpty()){ int sum = stack1.pop(); stack2.push(sum); } } stack1.push(node); count++; }

  1. public int pop() {
  2.     //如果栈2有，就从栈2取
  3.     if(!stack2.isEmpty()){
  4.         return stack2.pop();
  5.     }
  6.     //否则将栈1所有元素往栈2里面移动，再取数据
  7.     while(!stack1.isEmpty()){
  8.         int sum = stack1.pop();
  9.         stack2.push(sum);
  10.     }
  11.     return stack2.pop();
  12. }

}

  2. - 如果是两个队列，那么如何实现一个栈
  3.    - 入栈直接让元素入队列1
  4.    - 出栈，假如队列1只剩一个元素，就让它出队（出栈）；否则，将队列1的其它元素出队 并 入队到队列2，将队列1的唯一元素出队（出栈），最后队列2的全部元素出对列 并入队列到队列1
  5. <a name="QCx2B"></a>
  6. # 6、旋转数组的最小数字
  7. ```java
  8. 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
  9. 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
  10. NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

  • 解法一

    • 从后面往前面遍历，找到 由小变大 的那个变化，小的值即为所求
      1. import java.util.ArrayList;
      2. public class Solution {
      3. public int minNumberInRotateArray(int [] array) {
      4.    if(array.length == 0){
      5.        return 0;
      6.    }
      7.    int j = array.length-1;
      8.    int i = j-1;
      9.    int sum = array[j];
      10.    while(j>0){
      11.        if(array[i]>array[j]){
      12.            break;
      13.        }
      14.        if(sum > array[j]){
      15.            sum = array[j];
      16.        }
      17.        if(sum > array[i]){
      18.            sum = array[i];
      19.        }
      20.        j--;
      21.        i = j-1;
      22.    }
      23.    return sum;
      24. }
      25. }

  • 解法二

    • 二分查找法
      1. mid = low + (high - low)/2
      2. 需要考虑三种情况：
      3. (1)array[mid] > array[high]:
      4. 出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
      5. low = mid + 1
      6. (2)array[mid] == array[high]:
      7. 出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
      8. 还是右边,这时只好一个一个试 ，
      9. high = high - 1
      10. (3)array[mid] < array[high]:
      11. 出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
      12. 边。因为右边必然都是递增的。
      13. high = mid
      14. 注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
      15. 比如 array = [4,6]
      16. array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
      17. 如果high = mid - 1，就会产生错误， 因此high = mid
      18. 但情形(1)中low = mid + 1就不会错误
      1. public class Solution {
      2. public int minNumberInRotateArray(int [] array) {
      3.    int low = 0 ; int high = array.length - 1;    
      4.    while(low < high){
      5.        int mid = low + (high - low) / 2;         
      6.        if(array[mid] > array[high]){
      7.            low = mid + 1;
      8.        }else if(array[mid] == array[high]){
      9.            high = high - 1;
      10.        }else{
      11.            high = mid;
      12.        }    
      13.    } 
      14.    return array[low];
      15. }
      16. }

      7、波那契数列

      1. 大家都知道斐波那契数列，现在要求输入一个整数n，
      2. 请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。其中n≤39

  • 斐波那契数列第0项为0，第一项为1，后面数的都是等于它前两项之和

  • 方法一

    • 利用递归，占用内存大，耗时长，容易栈溢出
      1. public class Solution {
      2. public int Fibonacci(int n) {
      3.    if(n<=1){
      4.        return n;
      5.    }
      6.    return Fibonacci(n-1)+Fibonacci(n-2);
      7. }
      8. }

  • 方法二

    • 利用辅助数组，长度为n+1（斐波那契数列从0开始，有n+1项），来存每个数据
      1. public class Solution {
      2. public int Fibonacci(int n){
      3.    if(n<=1){
      4.        return n;
      5.    }
      6.    int[] arr = new int[n+1];
      7.    arr[0] = 0;
      8.    arr[1] = 1;
      9.    for(int i = 2;i<n+1;i++){
      10.        arr[i] = arr[i-1] + arr[i-2];
      11.    }
      12.    return arr[n];
      13. }
      14. }

      8、跳台阶

      1. 一只青蛙一次可以跳上1级台阶，也可以跳上2级。
      2. 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

  • 解法一

    • 可以通过找规律的办法：n=1 时，1种；n=2 时，2种；n=3 时，3种；n=4 时，5种；n=5 时，8种……
      • 得出f(n) = f(n-1) + f(n-2)，初始条件：n=1，1种；n=2，2种
    • 也可以这么想： ```java a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);

b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)

c.由a、b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)

d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

e.可以发现最终得出的是一个斐波那契数列：

  1.           | 1, (n=1)

f(n) = | 2, (n=2)

  1.           | f(n-1)+f(n-2) ,(n>2,n为整数)
  1. ```java
  2. public class Solution {
  3.     public int jumpFloor(int target) {
  4.         if(target == 1){
  5.             return 1;
  6.         }
  7.         if(target == 2){
  8.             return 2;
  9.         }
  10.         return jumpFloor(target-1)+jumpFloor(target-2);
  11.     }
  12. }

  • 解法二

    • 利用辅助数组
      1. public class Solution {
      2. public int jumpFloor(int target) {
      3.    if(target == 1){
      4.        return 1;
      5.    }
      6.    if(target == 2){
      7.        return 2;
      8.    }
      9.    int[] temp = new int[target];
      10.    temp[0] = 1;
      11.    temp[1] = 2;
      12.    for(int i=2;i<target;i++){
      13.        temp[i] = temp[i-1] + temp[i-2];
      14.    }
      15.    return temp[target-1];
      16. }
      17. }

      9、变态跳台阶

      1. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级
      2. 求该青蛙跳上一个n级的台阶总共有多少种跳法

  • 解法

    1. 关于本地：前提是n个台阶会有一次n阶的跳法，分析：
    2. f(1) = 1
    3. f(2) = f(2-1)+f(2-2)
    4. f(3) = f(3-1)+f(3-2)+f(3-3)
    5. ...
    6. f(n) = f(n-1)+f(n-2)+...+f(0)
    7. 其中f(n-1) = f(n-2)+f(n-2)+...+f(0)
    8. 那么，f(n) = 2*f(n-1)
    9. 初始条件：f(1) = 1
    1. public class Solution {
    2.   public int jumpFloorII(int target) {
    3.       if(target == 1){
    4.           return 1;
    5.       }
    6.       return 2*jumpFloorII(target - 1);
    7.   }
    8. }

    10、矩形覆盖

    ```java 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形 请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看):

  1. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/358364/1622120829182-50ae59c5-4ad3-44db-a0b5-50d82ea1df3c.png#clientId=u9b753942-2cc7-4&from=paste&height=293&id=udd863cac&margin=%5Bobject%20Object%5D&name=image.png&originHeight=586&originWidth=863&originalType=binary&size=57077&status=done&style=none&taskId=u7bb8e6bb-8990-481c-82ce-ab6c9b1995d&width=431.5)
  3. - 解法
  4.    - 从n的这面方向看，小矩形长宽为1或者2，所以只能补1或者2
  5.    - 即f(n)=f(n-1)+f(n-2)
  6.    - 初始值：n=1，方法个数为1，n=2，方法个数为2
  8. ```java
  9. public class Solution {
  10.     public int rectCover(int target) {
  11.         if(target <=2){
  12.             return target;
  13.         }
  14.         int i=1,j=2,k;
  15.         for(int t=3;t<=target;t++){
  16.             k = i+j;
  17.             i = j;
  18.             j = k;
  19.         }
  20.         return j;
  21.     }
  22. }
  • 注意这种递归的循环表示方式，递归都可以用循环替代，递归代码简单，但是容易栈溢出