# 面试题一：找出数组中重复的数字

题目描述：

在一个长度为 n 的数组里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为 7 的数组 {2,3,1,0,2,5,3]，那么对应的输出是重复的数字 2 或者 3。

解题思路：

通过参数 duplication 传给函数的调用者，而函数的返回值表示数组中是否有重复的数字。当输入的数组中存在重复的数字时，返回 true; 否则返回 false。
代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是 O (n)。另外，所有的操作步骤都是在输入数组上进行的，不需要额外分配内存，因此空间复杂度为 O (1)。

C++ 实现

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<iostream>
using namespace std;
bool duplicate(int numbers[],int length,int* duplication);

int main()
{
    cout<<"面试题一"<<endl;
    // int n[10];
    // 初始化数组元素          
    // for ( int i = 0; i < 10; i++ )
    // {
    //     n[ i ] = i + 100; // 设置元素 i 为 i + 100
    // }

    int n[] = {2,2,3,4,5,2,3};
    int length = sizeof(n)/sizeof(n[0]);
    int *duplication = new int[length]; 
    bool success = duplicate(n,7,duplication);

    if (success){
        cout<<"找到重复元素："<< *duplication<<endl;
    } else {
        cout<<"没有重复的元素"<<endl;
    }
    //常规操作，释放内存

    delete[] duplication;
    

    return 0;
}

//为了正确地使用duplicate函数，需要按照以下方式传递参数：

// numbers数组：指向一个整数数组的指针，这个数组包含了需要查找重复元素的整数序列。
// length：代表numbers数组中的元素个数。
// duplication：指向一个整型变量的指针，用于存储重复的元素。

bool duplicate(int numbers[],int length,int* duplication)
{
    if (numbers == nullptr||length<=0) // 如果输入数组为空或者长度小于等于0，则返回false
    {
        /* code */
        return false;
    }

    for (int i = 0; i < length; ++i)  // 遍历数组中每个元素
    {
        /* code */
        if (numbers[i] < 0 || numbers[i] > length - 1)  // 如果数组中有元素不在[0, n-1]的范围内，返回false
        {
            /* code */
            return false;
        } 
    }

    for (int i = 0; i < length; i++)  // 再次遍历数组
    {
        /* code */
        while (numbers[i] != i) // 如果当前元素不等于它的下标i
        {
            /* code */
            if (numbers[i] == numbers[numbers[i]]) // 如果当前数字numbers[i]与numbers[numbers[i]]相等，则找到重复的数字
            {
                /* code */
                *duplication = numbers[i]; // 将重复数字记录下来
                return true ;   // 返回true
            }

            //交换numbers[i] 和 numbers[numbers[i]]
            int temp = numbers[i];  // 定义一个临时变量temp
            numbers[i] = numbers[temp]; // 交换numbers[i]和numbers[numbers[i]]
            numbers[temp] = temp;
            
        }
        
    }
    
    return false; // 否则返回false
    
}

java 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int findDuplicate(int[] nums){
    //遍历数组中每个数num[i]
    for (int i = 0; i < nums.length; i++) {
        //如果nums[i]不等于下标i,则将其交换到位置nums[nums[i]]上
        while (nums[i] != i) {
            //如果在交换的过程中发现nums[nums[i]]已经等于nums[i],
            //则说明重复数字，直接返回
            if (nums[nums[i]]  == nums[i]) {
                return nums[i];
            }
            //交换nums[i] 和nums[nums[i]]两个位置上的数字
            swap(nums,i,nums[i]);
        }
    }
    return -1;
}

private static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

# 面试题二：二维数组中的查找

题目描述：

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

解题思路：

可以使用从右上角或左下角开始搜索的方式，每次比较当前位置的值和目标值的大小，并根据大小调整搜索的方向。
这里使用从右上角开始搜索的方式，每次比较当前位置的值和目标值的大小，并根据大小调整搜索的方向。时间复杂度为 O (m+n)，m 和 n 分别是二维数组的行数和列数。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package Temp;

/*
 * @Author: jun
 * @Date:2023/4/23 23:42
 * @概述：
 */
public class TestAlgorithm02 {


    public static void main(String[] args) {
        int[][] nums = {{1,2,3},
                        {4,5,6},
                        {7,8,9}};
        int target = 6;
        TestAlgorithm02 testAlgorithm02 = new TestAlgorithm02();
        boolean search = testAlgorithm02.search(nums, 6);
        System.out.println(search);
    }

    /**
     * 在二维数组中查找目标值
     * @param matrix 二维数组
     * @param target 目标值
     * @return 若二维数组中包含目标值，则返回true，否则返回false
     */
    public boolean search(int[][] matrix, int target) {
        // 判断数组是否为空
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        // 从右上角开始搜索
        int row = 0;
        int col = matrix[0].length - 1;
        System.out.println(matrix[0].length);
        while (row < matrix.length && col >= 0) {
            // 找到目标值
            if (matrix[row][col] == target) {
                return true;
            }
            // 当前值小于目标值，搜索下一行
            else if (matrix[row][col] < target) {
                row++;
            }
            // 当前值大于目标值，搜索前一列
            else {
                col--;
            }
        }
        // 未找到目标值
        return false;
    }
}

# 面试题三：替换空格

题目描述：

请实现一个函数，把字符串中的每个空格替换成 "%20"。例如，输入 “Wearehappy”，则输出 “We%20are%20happy”。

解法：使用时间复杂度为 O (n) 的解法，才够搞定 Offer，换个方向想想，从后往前挪，

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
38
39
40
41
42
43
/*length为字符数组String的总容量*/
void ReplaceBlank(char string[] ,int length)
{
	if(string == nullptr||length<=0)
    return 0;
    
   /*orignalLength为字符串string的实际长度*/
   int orignalLength = 0;
   int numberOfBlank = 0;
   int i = 0;
   while(string[i]!='\0')
   {
   		++originalLength;
      if(string[i] == '')
      		++numberOfBlank;
      ++ i ;
      
   }
   /*newLength 为把空格替换为”%20“之后的长度*/
   int newLength = originLength + numberOfBlank*2;
   if(newLength > length)
   return;
   
   int indexOfOriginal = originalLength;
   int indexOfNew = newLength;
   while(indexOfOringinal >= 0 && indexOfNew >indexOfOriginal)
   {
   		if(string[indexOfOringinal]=='')
            {
                string[indexOfNew -- ]='0';
              string[indexOfNew -- ]='2';             
              string[indexOfNew -- ]='%';

            }
            else
            {
                string[indexOfNew--] = string[indexOfOringinal];
            }
            --indexOfOriginal;
   }
}


# 从头到尾打印链表

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package Algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/*
 * @Author: jun
 * @Date:2023/5/2 16:27
 * @概述：循环打印链表
 */
public class TestAlgorithm04 {
    /**
     * 题目：输入一个链表的头节点，
     * 从尾到头反过来打印出每个节点的值。
     * 链表节点定义如下：
     */

//    public class Node {
//        int val;
//        Node next;
//
//        public Node(int val) {
//            this.val = val;
//            this.next = null;
//        }
//    }
//
//    public class LinkedList {
//        Node head;
//
//        public LinkedList() {
//            this.head = null;
//        }
//
//        public void addNode(int val) {
//            Node newNode = new Node(val);
//
//            if (head == null) {
//                head = newNode;
//            } else {
//                Node curr = head;
//                while (curr.next != null) {
//                    curr = curr.next;
//                }
//                curr.next = newNode;
//            }
//        }
//
//        public void printList() {
//            if (head == null) {
//                System.out.println("List is empty");
//            } else {
//                Node curr = head;
//                while (curr != null) {
//                    System.out.print(curr.val + " ");
//                    curr = curr.next;
//                }
//                System.out.println();
//            }
//        }
//    }

    /**
     * 本题涉及到的知识点为链表和逆序输出。
     * 链表是由一组节点组成的数据结构，每个节点包含两部分内容：
     * 数据和指向下一个节点的指针。逆序输出可以用栈来实现。
     * 因为栈是一种“后进先出”的数据结构，所以可以把链表的节点依次入栈，
     * 然后出栈打印出每个节点的数据，就实现了逆序输出。
     * @param args
     */
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("abb");
        list.add("bcc");
        list.add("cdd");

        for (String i:
             list) {
            System.out.println(i);
        }
        System.out.println("++++++++++++++++++++");
        solution solution = new solution();
        ArrayList<String> list1 = solution.printListFromTailToHead(list);
        for (String d:
                list1) {
            System.out.println(d);
        }


    }

    public static class solution {
        public ArrayList<String> printListFromTailToHead(LinkedList linkedList){
            Stack<String> stack = new Stack<>();
            for (int i = 0; i < linkedList.size(); i++) {
                stack.push(linkedList.get(i).toString());
            }
            ArrayList<String> list = new ArrayList<String>(); // 创建一个ArrayList
            // 把栈中的元素依次出栈，添加到ArrayList中
            while (!stack.isEmpty()) {
                list.add(stack.pop());
            }

            return list;
        }
    }
    
}

# 重建二叉树

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package Algorithm;

/*
 * @Author: jun
 * @Date:2023/5/5 14:42
 * @概述：面试题7 重建二叉树
 */

import java.util.HashMap;


/**
 * 代码首先定义了一个 TreeNode 类，
 * 表示二叉树节点。该类包含一个整型变量值（val）和两个指针左（left）和右（right），
 * 分别指向该节点的左子树和右子树。
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode (int x){
        val = x;
    }
}

public class TestAlgorithm05 {

    private HashMap<Integer, Integer> map;

    /**
     * 实现了一个方法 buildTree，
     * 该方法接受两个整型数组参数：前序遍历结果 preorder 和中序遍历结果 inorder。
     *
     * 算法思路：
     * 1.使用哈希表 Map 存储中序遍历数组中的每个元素和它对应的下标。
     *
     * 2.递归构建二叉树，构建过程如下：
     *
     *  a. 如果前序遍历数组为空，返回 null。
     *
     *  b. 根据前序遍历数组的第一个元素创建根节点 root。
     *
     *  c. 根据哈希表计算出根节点在中序遍历数组中的下标 rootIndex。
     *
     *  d. 根据 rootIndex，计算出左子树的节点个数 leftSize。
     *
     *  e. 递归构建左子树和右子树：
     *
     * · 左子树的前序遍历数组范围是（preLeft+1，preLeft+leftSize），中序遍历数组范围是（inLeft，rootIndex-1）。
     *
     * · 右子树的前序遍历数组范围是（preLeft+leftSize+1，preRight），中序遍历数组范围是（rootIndex+1，inRight）。
     *
     * 3.返回根节点 root。
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder,int[] inorder){
        //初始化哈希表，存储中序遍历结果中每个元素对应的小标
        map = new HashMap<Integer,Integer>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }

        return buildTree(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }

    private TreeNode buildTree(int[] preorder,int[] inorder,int preLeft,int preRight,int inLeft,int inRight){
        //判断边界条件
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }

        //先创建根节点
        TreeNode root = new TreeNode(preorder[preLeft]);
        //获取根节点在中序遍历结果中的下标
        int rootIndex = map.get(preorder[preLeft]);
        //计算出左子树节点的个数
        int leftSize = rootIndex - inLeft;

        //递归构建左子树和右子树
        root.left = buildTree(preorder, inorder, preLeft+1, preLeft+leftSize, inLeft, rootIndex-1);
        root.right = buildTree(preorder, inorder, preLeft+leftSize+1, preRight, rootIndex+1, inRight);

        return root;
    }

    public static void main(String[] args) {
        int[] preorder = {3,9,20,15,7};
        int[] inorder = {9,3,15,20,7};

        TestAlgorithm05 s = new TestAlgorithm05();
        TreeNode root = s.buildTree(preorder, inorder);

        //输出遍历结果，验证是否正确构建二叉树
        printTree(root);
    }

    public static void printTree(TreeNode root) {
        if(root == null) {
            return;
        }

        System.out.print(root.val + " ");
        printTree(root.left);
        printTree(root.right);
    }

}

# 用两个栈实现队列

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package Algorithm;

import java.util.Stack;

/*
 * @Author: jun
 * @Date:2023/5/6 8:13
 * @概述：用两个栈实现队列
 */
public class TestAlgorithm06 {

    /**
     *
     * 题目： 用两个栈实现一个队列。 队列的声明如下，
     * 请实现它的两个函 数appendTail和deleteHead,
     * 分别完成在队列尾部插入节点和在队列头部删除节点的功能。
     * 使用java实现，写明思路与注释。
     *
     * 思路：
     * 首先，我们定义两个栈stack1和stack2。
     * 当我们需要在队列尾部插入一个节点时，我们直接将节点入栈stack1即可。
     * 当我们需要在队列头部删除节点时，我们需要先从stack1栈中把元素弹出来，
     * 压入另一个栈stack2中，然后再从stack2中弹出即可。
     */
    //声明两个栈
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    //声明appendTail方法，在队列尾插入一个节点
    public void appendTail(int value){
        stack1.push(value);
    }

    //声明deleteHead方法，在队列头部删除节点
    public int deleteHead() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.empty()){
            throw new RuntimeException("Queue is empty.");
        }
        return stack2.pop();
    }
    public static void main(String[] args) {
        TestAlgorithm06 queue = new TestAlgorithm06();
        queue.appendTail(1);//1
        System.out.println(queue.deleteHead());//null   删1
        queue.appendTail(2);//2
        System.out.println(queue.deleteHead());//null   删2

        queue.appendTail(3);//3
        queue.appendTail(4);//3 4
        queue.appendTail(5);//3 4 5
        System.out.println(queue.deleteHead());//4 5    删3
        System.out.println(queue.deleteHead());//5      删4
    }

}

# 斐波那契

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
38
39
40
41
42
43
package Algorithm;

/*
 * @Author: jun
 * @Date:2023/5/7 15:16
 * @概述：斐波那契数列
 */
public class TestAlgorithm07 {
    //写一个函数，输入一个n，求斐波那契数列的第n项
    /**
     * 思路：
     * 在循环中，我们定义了三个变量 a、b 和 c。
     * 变量 a 和 b 初始值为 0 和 1，
     * 然后我们递增地遍历循环并计算下一个斐波那契数字 c（即 a 和 b 的总和）。
     * 最终，我们将 c 返回作为斐波那契数列的第 n 项。
     */
    
    public static void main(String[] args) {
        //随便定义一个数
        int a = 3;
        //求取该位置的值
        int fibonacci = fibonacci(a);
        System.out.println("第"+a+"位斐波那契数的值为："+fibonacci);
    }
    public static int fibonacci(int n){
        //首先判断输入的数是否可以求到
        if (n <= 0) {//小于等于零是求不到的
            return 0;
        }
        else if (n == 1)//n为1表示就是斐波那契数列的第一项
            return 1;
        else {
            int a = 0,b = 1, c = 0;
            for (int i = 2; i <= n; i++) {
                //进行迭代求下一个值
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    }
}

# 青蛙跳台阶

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
38
39
40
41
42
43
44
45
package Algorithm;
/*
 * @Author: jun
 * @Date:2023/5/7 15:31
 * @概述：青蛙跳台阶问题
 */
public class TestAlgorithm08 {
    //题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。
    // 求该青蛙跳上一个n级台阶总共有多少种跳法。

    /**
     * 思路：
     *  在这个问题中，每次青蛙跳跃可以选择跳一步或者两步。因此，我们设 f(n) 表示青蛙跳上 n 级台阶的跳法总数，则 f(n)=f(n-1)+f(n-2)。
     *
     * 我们定义 prepre、pre 和 cur 分别为 f(n-2)、f(n-1) 和当前结果 f(n)。通过迭代从初始条件开始，不断更新 prepre、pre 和 cur 值，
     * 直到 n。最后，返回 cur，即为青蛙跳上 n 级台阶的总共跳法数。
     *
     * 需要注意的是，当 n 很大时，此函数可能会因为 int 类型溢出而导致错误结果。如果需要支持更大的 n，可以使用 BigInteger 类型或其他技巧进行计算。
     */

    public static void main(String[] args) {
        //假如有20个台阶
        int n = 20;
        int jumpFloor = jumpFloor(n);
        System.out.println("方法个数为："+jumpFloor);
    }

    public static int jumpFloor(int n) {
        if (n <= 0)
            return 0;
        else if (n == 1)
            return 1;
        else if (n == 2)
            return 2;
        else {
            int pre = 2, prepre = 1, cur = 0;
            for (int i = 3; i <= n; i++) {
                cur = pre + prepre;
                prepre = pre;
                pre = cur;
            }
            return cur;
        }
    }
}

# 旋转数组最小值

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
38
39
40
41
42
43
44
package Algorithm;

/*
 * @Author: jun
 * @Date:2023/5/7 19:40
 * @概述：旋转数组的最小数字
 */
public class TestAlgorithm09 {

    /**
     * 题目：把一个数组最开始的诺干个元素搬到数组的末尾，我们称之为数组的旋转。
     * 输入一个递增排序的数组二点一个旋转，输出旋转数组的最小元素。
     * 例如，数组{3，4，5，1，2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1
     *
     * 思路：
     * 可以使用二分查找，首先我们将数组的元素分为两部分，中间位置记为mid，
     * 前半部分是递增的有序子数组，后半部分也是递增的有序子数组。
     * 同时，旋转之后最小的元素即为后半部分的第一个元素。
     */

    public static void main(String[] args) {
        int[] nums = {3,4,5,1,2};
        int min = findMin(nums);
        System.out.println("最小值为："+min);
    }

    public static int findMin(int[] nums){
        int left = 0,right = nums.length - 1;

        while (left < right) {
            int mid = (left+right)/2;
            if (nums[mid]>nums[right]){
                left = mid + 1;
            }else if (nums[mid] == nums[right]){
                right -- ;
            }else {
                right = mid;
            }
        }

        return nums[left];
    }

}

# 矩阵中的路径

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package Algorithm;

/*
 * @Author: jun
 * @Date:2023/5/7 20:00
 * @概述：矩阵中的路径
 */
public class TestAlgorithm10 {

    /**
     * 题目：
     * 设计一个函数，用来判断在一个矩阵中是否存在一条包含某个字符串所有的路径。
     * 路径可以从矩阵中的任意一格开始，每一步都可以在矩阵中向左，右上，下移动一格
     * 如果一条路径经过了矩阵中的某一格，那么该路径不能再次进入该格子。
     * 例如，在下面的3X4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用下划线标出）
     * 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行
     * 第二个格子之后，路径不能再次进入这个格子
     *
     * 思路：
     * 这是一个典型的深度优先搜索（DFS）问题，可以通过递归方式来实现。具体实现步骤如下：
     *
     * 定义一个函数hasPath(char[][] matrix, String str)，其中matrix表示给定的矩阵，str表示给定的字符串。
     * 遍历矩阵中的每一个格子，找到值等于字符串第一个字符的格子，作为路径起点。
     * 以起点开始，向左、右、上、下四个方向进行搜索，如果搜索到的格子值等于字符串的下一个字符，
     * 则继续深度优先搜索；否则回溯到上一级节点并尝试其他方向。
     * 如果搜索到字符串的最后一个字符，说明存在一条符合条件的路径，返回true；
     * 如果所有路径都搜索完了都没有找到符合条件的路径，返回false。
     */

    public static void main(String[] args) {
        char[][] nums = {{'a','b','t','g'},
                         {'c','f','c','s'},
                         {'j','d','e','h'}};
        boolean result = hasPath(nums, "bfce");
        System.out.println("存在一条路径："+result);
    }

    public static boolean hasPath(char[][] matrix,String str){
        //首先还是一开始需要进行可能的特殊输入判断，比如矩阵为空，矩阵的行为，
        //需要求解的字符的长度为空
        while (matrix == null || matrix.length == 0 || str == null || str.length() == 0) {
            return false;
        }
        //新建一个布尔类型的矩阵，矩阵的大小与需要判断的矩阵大小相同,这个visited是用来记录哪些已经访问过了，哪些没有访问
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == str.charAt(0)){//首先找到需要查找的第一个字符在矩阵中的位置
                    if (dfs(matrix,str,visited,i,j,0)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private static boolean dfs(char[][] matrix,String str,boolean[][] visited,int row,int col,int index){
        if (index == str.length()) {
            //这里的index是索引下标
            return true;
        }
        if (row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || visited[row][col]) {
            //行小于0,行大于矩阵长度，列小于0，列大于等于边界值，或者visited已经记录你走过该方格
            return false;
        }
        if (matrix[row][col] != str.charAt(index)) {
            //遇到的方格与要求的不一样
            return false;
        }
        visited[row][col] = true;//标记为已经访问
        boolean result = dfs(matrix, str, visited, row - 1, col, index + 1)  // 上方格子
                || dfs(matrix, str, visited, row + 1, col, index + 1) // 下方格子
                || dfs(matrix, str, visited, row, col - 1, index + 1) // 左边格子
                || dfs(matrix, str, visited, row, col + 1, index + 1); // 右边格子
        visited[row][col] = false; // 回溯

        return result;
    }
}