3~13

03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

通过交换使得每一个数字回到与他自己的位置（最多两次），然后判断是否与相应下标的数字相同即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public static void swap(int[]arr,int i,int j)
    {
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public int findRepeatNumber(int[] nums) {
        for(int i=0;i<nums.length;i++){
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]]) {
                    return nums[i];
                }
                swap(nums,i,nums[i]);
            }
        }
        return -1;
    }
}

或者是直接通过Set或者Map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set=new HashSet<>();
        for(int a:nums)
        {
            if(!set.add(a))
                return a;
        }
        return -1;
    }
}

class Solution {
    public int findRepeatNumber(int[] nums) {
        Map<Integer, Boolean> map=new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num))
                return num;
            else map.put(num, true);
        }
        return  -1;
    }
}

04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

每一次都从右上角开始查询，

如果是大于target字的数，那么这个数字所在列的所有数字也一定大于target， 剔除该行

如果是小于target字的数，那么这个数字所在的行所有数字也一定小于target，剔除该列

这样每一步缩小范围，直到查找范围为null或者找到target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        boolean isFound=false;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return isFound;
        }
        int rows =matrix.length;
        int columns=matrix[0].length;
        if(matrix!=null&&rows>0&&columns>0){
            int row=0,column=columns-1;
            while(row<rows&&column>=0)
            {
                if(matrix[row][column]==target)
                {
                    isFound=true;
                    break;
                }else if(matrix[row][column]>target)   // 剔除当前列
                {
                    column--;
                }else{                               //剔除当前行
                    row++;
                }
            }
        }
        return isFound;
    }
}

05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

本题如果使用cpp 来写的话， 核心思想就是 从末尾开始赋值， 可以节省大量的时间（通过这样做就不需要string 因为前面的数组插入数据 而后移 导致消耗时间）

由于java String 的不可变性， 本体java代码直接使用 StringBuffer一个个的append 即可

image-20220717181023757image-20220717181023757

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String replaceSpace(String s) {
        StringBuffer res=new StringBuffer("");
        for (int i = 0; i < s.length(); i++){
            if(s.charAt(i)==' '){
                res.append("%20");
            }else{
                res.append(s.charAt(i));
            }
        }
        return res.toString();
    }
}

或者直接

return s.replaceAll(" ","%20");一行代码搞定。

06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

通过ArrayList 添加 每个节点的val ，然后反向赋值给 int []res ,最后返回res 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head==null) return new int[0];   // 数组为空 。返回 [] 
        ArrayList<Integer> list=new ArrayList<>();
        while(head.next!=null){
            list.add(head.val);
            head=head.next;
        }
        list.add(head.val);
        int len =list.size();
        int []res=new int[len];
        for (int i = len-1; i >=0 ; i--) {
                res[i]=list.get(len-i-1);
        }
        return res;
    }
}

07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

image-20220719143417614image-20220719143417614

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return f(preorder,inorder,null);
    }
    int preindex;
    int inindex;  //记录是否结束的标志
    // 前序遍历 根左右   中序遍历 左根右
    public TreeNode f(int []preorder,int []inorder,TreeNode finish)  
        //中序遍历的 节点的左右两边是他的左右孩子, 如果孩子是他自身，说明这个节点是个叶子结点
    {
        if(preindex==preorder.length||(finish!=null&&inorder[inindex]==finish.val))
            return null ;  // 遍历完了
        //当前子树的根节点
        TreeNode root=new TreeNode(preorder[this.preindex++]);
        //左子树
        root.left=f(preorder,inorder,root);
        this.inindex++;  // 中序遍历对应数组的下标
        //右子树
        root.right=f(preorder,inorder,finish);
        return root;
    }
    /* 先扫描前序序列的 ， 第一个节点的位置就是根节点，然后根据这个去扫描 中序遍历的序列，根节点的左侧是左子树，
右侧是右子树， 然后依次重复这个操作，找出 左子树的根节点，左子树的左子树，左子树的右子树， 继续重复，直到没有左右子树
         */

}

中序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    List<Integer> list=new ArrayList();
    public List<Integer> inorderTraversal(TreeNode root) {
        dfs(root);
        return list;
    }
        public void dfs(TreeNode root){
        if(root==null) return ;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}

09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

Stack 类

  • 栈是Vector的一个子类，它实现了一个标准的后进先出的栈。
  • 堆栈只定义了默认构造函数，用来创建一个空栈。 堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。
序号 方法描述
1 boolean empty() 测试堆栈是否为空。
2 Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
3 Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
4 Object push(Object element) 把项压入堆栈顶部。
5 int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。

使用两个Stack: A ， B。 其中A 用来添加 元素， B用来移除元素

A B 的元素的顺序相反

  • 注意appendTail方法返回的 都是null

    deleteHead返回的是当前删除的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class CQueue {
	public CQueue() {
		A=new Stack<>();
		B=new Stack<>();
	}
	Stack<Integer> A;
	Stack<Integer> B;
	public void appendTail(int value) {
		A.add(value);
	}

	public int deleteHead() {
		if(!B.isEmpty())
		{
			return	B.pop();   // 如果B中有元素，直接让B 的栈顶 出栈
		}
		if(A.isEmpty())
			return -1;    // 代表此时的栈是空栈 ，返回-1 
		while(!A.isEmpty()) // 使A 的元素全部出栈 ，赋值给B ，并且 B的元素顺序与原本A 的顺序相反
		{
			B.add(A.pop());
		}
		 return B.pop();
	}
}

示例 1：

1
2
3
4
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

示例2

1
2
3
4
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

N 较小， 直接循环计算即可

需要注意的是 (a+b)%mod < = > (a%mod+b%mod)%mod

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    static final int mod=1000000007;
    //  0   1  1  2  3   5   8  13
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1||n==2) return 1;
        long f1=0L,f2=1L ,f3=1L;
        for(int i=1;i<n;i++ )
        {
            long temp =f3;
            f3=(f1%mod+f2%mod)%mod;
            f1=f2;
            f2=f3;
        }
        return (int)f3%mod;
    }
}

10- II. 青蛙跳台阶问题

与上一题类似

1、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numWays(int n) { // 1 1 2 3
        return fib(n);
    }      
   static int mod=1000000007;
        public int fib(int n) {
        if(n==2) return 2;
        if(n==1||n==0) return 1;
        long f1=1L,f2=1L ,f3=2L;
        for(int i=1;i<n;i++ )
        {
            long temp =f3;
            f3=(f1%mod+f2%mod)%mod;
            f1=f2;
            f2=f3;
        }
        return (int)f3%mod;
    }
}

2、

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
   static int mod=1000000007;
     
    int []res=new int[101];  // 这里的数字替换为HashMap 也可以
    public int numWays(int n) { // 1 1 2 3
        res[0]=1;
        res[1]=1;
        res[2]=2;
        for(int i=3;i<=100;i++)
        {   
            res[i]=(res[i-1]%mod+res[i-2]%mod)%mod;
            if(i==n) break;
        }
        return res[n];
    }      

}

3、 将上一个的数组替换为了HashMap ，可以节省内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {

    Map<Integer,Integer> res=new HashMap<>();
    static int mod=1000000007;
    public int numWays(int n) { 
        res.put(0,1);
        res.put(1,1);
        res.put(2,2);
        for(int i=3;i<=n;i++)
        {   
            res.put(i,(res.get(i-1)%mod+res.get(i-2)%mod)%mod);
        }
        return res.get(n);
    }      
}

11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

image-20220719174150375image-20220719174150375

遍历数组，由于原来的数组一定是升序排列， 那么如果出现了 相邻的两个数字，后面的数字小于前面的数字，说明后面的这个数字就是原来的数组的第一项

，如果遍历完没有满足条件的情况，说明旋转后的数组与原来的数组一模一样。

  • 题目的数组不会出现 完全从大到小排序的情况
1
2
3
4
5
6
7
8
9
class Solution {
    public int minArray(int[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            if(numbers[i]<numbers[i-1])
                return numbers[i];
        }
         return numbers[0];
    }
}
  • 二分

通过判断中点 与 右端的大小关系找到 原数组第一个元素所在的区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minArray(int[] numbers) {
        int l=0,r=numbers.length-1;
        while(l<r){
           int m=(l+r)/2;
            if(numbers[m]>numbers[r])
                l=m+1;
            else if(numbers[m]<numbers[r])
                r=m;
            else r--;
        }
        return numbers[l];
    }
}

12. 矩阵中的路径

难度中等655

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

注意不能往回走

  • 注意下面的代码, 思路就错了 ,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    boolean res=false;
    int totalLen;
    String word;
    public boolean exist(char[][] board, String word) {
        totalLen=word.length();
        this.word=word;
        dfs(board,new StringBuilder(""),0,0);
        return res;
    }
    public void dfs(char[][]board , StringBuilder s,int i,int j){
        if(i<0||j<0||i>=board.length||j>=board[0].length||board[i][j]=='\0') // 越界
            return ;
        s.append(board[i][j]);
        if(s.length()==totalLen){ //单词长度到了
            if(s.toString().equals(word)) res=true;
            return ;
        }
        if(res) return ;
        char temp=board[i][j];
        board[i][j]='\0';
        // 由于StringBuilder是引用类型, 因此每一个都需要 new 一个新的空间, 否则会影响到原来的空间
        dfs(board,new StringBuilder(s.toString()),i,j-1);
        dfs(board,new StringBuilder(s.toString()),i,j+1);
        dfs(board,new StringBuilder(s.toString()),i+1,j);
        dfs(board,new StringBuilder(s.toString()),i-1,j);
        board[i][j]=temp;
    }
}

  • 由于只进行了一次 dfs, 其实就是只有第一个格子进行操作了, 因此能读取的字符也只有从 第一个格子开始的字符, 所以需要使用两层for循环

  • 递归每一个格子

    1
    2
    3
    4
    5
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs(board,new StringBuilder(""),i,j);
        }
    }

  • 能通过, 但是很慢

i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    boolean res=false;
    int totalLen;
    String word;
    public boolean exist(char[][] board, String word) {
        totalLen=word.length();
        this.word=word;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board,new StringBuilder(""),i,j);
            }
        }
        return res;
    }
    public void dfs(char[][]board , StringBuilder s,int i,int j){
        if(i<0||j<0||i>=board.length||j>=board[0].length||board[i][j]=='\0') // 越界
            return ;
        s.append(board[i][j]);
        if(s.length()==totalLen){ //单词长度到了
            if(s.toString().equals(word)) res=true;
            return ;
        }
        if(res) return ;
        char temp=board[i][j];
        board[i][j]='\0';
        dfs(board,new StringBuilder(s.toString()),i+1,j);
        dfs(board,new StringBuilder(s.toString()),i,j-1);
        dfs(board,new StringBuilder(s.toString()),i,j+1);
        dfs(board,new StringBuilder(s.toString()),i-1,j);
        board[i][j]=temp;
    }
}
  • 深度优先搜索（DFS）+ 剪枝
  • 快得多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][]board,char[]words, int i,int j,int k){
        if(i<0||j<0||i>=board.length||j>=board[0].length||words[k]!=board[i][j]) // 越界 and 字符不相同
            return false ;
        if(k==words.length-1) return true;// 如果能走到这一步, 说明前面的字符全都相同(不相同的都pass了)
        board[i][j] = '\0';// 赋值为null , 表示当前位置的字符已经走过了(就不需要走了) ,(剪枝)
        boolean res= dfs(board,words,i,j-1,k+1)||dfs(board,words,i-1,j,k+1) ||
                dfs(board,words,i,j+1,k+1)||dfs(board,words,i+1,j,k+1);
        board[i][j]=words[k]; // 还原 board[i][j] , (如果能走到这一步, 两者的这个位置的字符一定相同)
        return res;
    }
}

13. 机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

image-20220719194018772

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int movingCount(int m, int n, int k) {
        int res=0;
        boolean visited[][]=new boolean[m][n];
        return dfs(visited,m,n,k,0,0);
    }
    public int dfs(boolean visited[][],int m,int n,int k,int i,int j)
    {
        // 终止 ；走到了边界 或者 数位之和不满足条件了 或者当前的格子已经走过了
        if(i>=m||j>=n||sum(i)+sum(j)>k||visited[i][j]) return 0;

        visited[i][j]=true; // 标记，表示当前格子走了
        //  当前格子 + 往下走+往右走
       return 1+ dfs( visited,m,n,k,i+1,j)+dfs(visited, m, n, k,i, j+1);
    } 
    public static int sum(int n){ // 获取一个数字的 每个位数之和    （由于题目要求的n<=100，因此直接return 即可）
        return n==100?1:n%10+n/10;
    }
}

另一道相似的题目

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

image-20220719202608622

这个题跟上一个不太一样，这个是四周发散的

先遍历， 如果位置的值是1 ， 再开始搜索，可以节省大量时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int max_res=0;
        int m=grid.length, n=grid[0].length; // 这里 n 表示的是 行数 ， m 表示的是列数  ,不太理解为什么不 -1 
        for (int i = 0; i < m; i++) {  // 这里要注意 i 表示的是 第几行 ， j 表示的是第几列 ，
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1)   
                    max_res= Math.max(DFS(grid, m, n, i, j), max_res);
            }
        }
        return max_res;
    }
    public int DFS(int [][]grid,int m,int n,int i,int j){
        if(i<0||j<0||i>= m||j>=n||grid[i][j]==0) return 0;
        if(grid[i][j]==1){
            grid[i][j]=0; // 表示这个位置走过了, 赋值为 0 ,避免重复
        return 1+  // +1 是因为 当前的 位置就是1 是土地
        DFS(grid,m, n, i+1, j)+
        DFS(grid,m, n, i, j+1)+
        DFS(grid,m, n, i, j-1)+
        DFS(grid,m, n, i-1, j);
        }
        return 0;
    }
}