【直通BAT】剑指Offer-经典试题整理(1)

深藏阁楼爱情的钟 2022-02-15 12:49 208阅读 0赞

3.1 找出数组中重复的数  
来源：AcWing

题目描述  
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例

给定 nums = \[2, 3, 5, 4, 3, 2, 6, 7\]。

返回 2 或 3。  
解法  
解法一  
排序后，顺序扫描，判断是否有重复，时间复杂度为 O(n²)。

解法二  
利用哈希表，遍历数组，如果哈希表中没有该元素，则存入哈希表中，否则返回重复的元素。时间复杂度为 O(n)，空间复杂度为 O(n)。

解法三  
长度为 n，元素的数值范围也为 n，如果没有重复元素，那么数组每个下标对应的值与下标相等。

从头到尾遍历数组，当扫描到下标 i 的数字 nums\[i\]：

如果等于 i，继续向下扫描；

如果不等于 i，拿它与第 nums\[i\] 个数进行比较，如果相等，说明有重复值，返回 nums\[i\]。如果不相等，就把第 i个数 和第 nums\[i\] 个数交换。重复这个比较交换的过程。

此算法时间复杂度为 O(n)，因为每个元素最多只要两次交换，就能确定位置（比如把 2 跟 5 交换，此时 2 在正确的位置，而 5 需要再交换一次就能跑到正确的位置）。空间复杂度为 O(1)。

class Solution { 
        
        /** * 查找数组中的重复元素 * * @param nums 数组 * @return 其中一个重复的元素 */
        public int duplicateInArray(int[] nums) { 
            if (nums == null || nums.length < 2) { 
                return -1;
            }
    
            int n = nums.length;
            for (int e : nums) { 
                if (e < 0 || e > n - 1) { 
                    return -1;
                }
            }
            for (int i = 0; i < n; ++i) { 
                while (nums[i] != i) { 
                    int val = nums[nums[i]];
                    if (nums[i] == val) { 
                        return val;
                    }
                    swap(nums, i, nums[i]);
                }
            }
            return -1;
        }
    
        private void swap(int[] nums, int i, int j) { 
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }

3.2 不修改数组找出重复的数字  
来源：AcWing

题目描述  
给定一个长度为 n+1 的数组 nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

给定 nums = \[2, 3, 5, 4, 3, 2, 6, 7\]。

返回 2 或 3。  
思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

解法  
解法一  
创建长度为 n+1 的辅助数组，把原数组的元素复制到辅助数组中。如果原数组被复制的数是 m，则放到辅助数组第 m 个位置。这样很容易找出重复元素。空间复杂度为 O(n)。

解法二  
数组元素的取值范围是 \[1, n\]，对该范围对半划分，分成 \[1, middle\], \[middle+1, n\]。计算数组中有多少个(count)元素落在 \[1, middle\] 区间内，如果 count 大于 middle-1+1，那么说明这个范围内有重复元素，否则在另一个范围内。继续对这个范围对半划分，继续统计区间内元素数量。

时间复杂度 O(n \* log n)，空间复杂度 O(1)。

注意，此方法无法找出所有重复的元素。

class Solution { 
    
        /** * 不修改数组查找重复的元素，没有则返回0 * * @param nums 数组 * @return 重复的元素 */
        public int duplicateInArray(int[] nums) { 
            if (nums == null || nums.length < 2) { 
                return 0;
            }
            int start = 1, end = nums.length - 1;
            while (start <= end) { 
                int mid = start + ((end - start) >> 1);
                int cnt = getCountRange(nums, start, mid);
                if (start == end) { 
                    if (cnt > 1) { 
                        // 找到重复的数字
                        return start;
                    }
                    break;
                }
                if (cnt > mid - start + 1) { 
                    end = mid;
                } else { 
                    start = mid + 1;
                }
            }
            return 0;
        }
    
        /** * 计算整个数组中有多少个数的取值在[from, to] 之间 * * @param nums 数组 * @param from 左边界 * @param to 右边界 * @return 数量 */
        private int getCountRange(int[] nums, int from, int to) { 
            int cnt = 0;
            for (int e : nums) { 
                if (e >= from && e <= to) { 
                    ++cnt;
                }
            }
            return cnt;
        }
    }

4 二维数组中的查找  
来源：AcWing

题目描述  
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

输入数组：

\[  
\[1,2,8,9\]，  
\[2,4,9,12\]，  
\[4,7,10,13\]，  
\[6,8,11,15\]  
\]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。  
解法  
从二维数组的右上方开始查找：

若元素值等于 target，返回 true；

若元素值大于 target，砍掉这一列，即 --j；

若元素值小于 target，砍掉这一行，即 ++i。

也可以从二维数组的左下方开始查找，以下代码使用左下方作为查找的起点。

注意，不能选择左上方或者右下方的数字，因为这样无法缩小查找的范围。

class Solution { 
    
        /** * 二维数组中的查找 * * @param array 二维数组 * @param target 要查找的值 * @return 是否找到该值 */
        public boolean searchArray(int[][] array, int target) { 
            if (array == null || array.length < 1) { 
                return false;
            }
            int m = array.length, n = array[0].length;
            int i = 0, j = n - 1;
            while (i < m && j >= 0) { 
                if (array[i][j] == target) { 
                    return true;
                }
                if (array[i][j] < target) { 
                    ++i;
                } else { 
                    --j;
                }
            }
            return false;
        }
    }

5 替换空格  
来源：AcWing

题目描述  
请实现一个函数，把字符串中的每个空格替换成 “%20”。

你可以假定输入字符串的长度最大是 1000。 注意输出字符串的长度可能大于 1000。

样例

输入：“We are happy.”

输出：“We%20are%20happy.”  
解法  
解法一  
利用正则匹配替换。

class Solution { 
    
        /** * 将字符串中的所有空格替换为%20 * * @param str 字符串 * @return 替换后的字符串 */
        public String replaceSpaces(StringBuffer str) { 
            return str == null ? null : str.toString().replaceAll(" ", "%20");
        }
    }

解法二  
先遍历原字符串，遇到空格，则在原字符串末尾 append 任意两个字符，如两个空格。

用指针 i 指向原字符串末尾，j 指向现字符串末尾，i, j 从后往前遍历，当 i 遇到空格，j 位置依次要赋值为 ‘0’,‘2’,’%’，若不是空格，直接赋值为 i 指向的字符。

思路扩展：

在合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。

class Solution { 
    
        /** * 将字符串中的所有空格替换为%20 * * @param str 字符串 * @return 替换后的字符串 */
        public String replaceSpaces(StringBuffer str) { 
            if (str == null) { 
                return null;
            }
            
            int len = str.length();
            for (int i = 0; i < len; ++i) { 
                if (str.charAt(i) == ' ') { 
                    str.append(" ");
                }
            }
    
            int i = len - 1, j = str.length() - 1;
            for (; i >= 0; --i) { 
                char ch = str.charAt(i);
                if (ch == ' ') { 
                    str.setCharAt(j--, '0');
                    str.setCharAt(j--, '2');
                    str.setCharAt(j--, '%');
                } else { 
                    str.setCharAt(j--, ch);
                }
            }
            return str.toString();
        }
    }

6 从尾到头打印链表  
来源：AcWing

题目描述  
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

样例

输入：\[2, 3, 5\]  
返回：\[5, 3, 2\]  
解法  
遍历链表，每个链表结点值 push 进栈，最后将栈中元素依次 pop 到数组中。

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
    
        /** * 从尾到头打印链表 * * @param head 链表头结点 * @return 结果数组 */
        public int[] printListReversingly(ListNode head) { 
            if (head == null) { 
                return null;
            }
            Stack<Integer> stack = new Stack<>();
            ListNode cur = head;
            int cnt = 0;
            while (cur != null) { 
                stack.push(cur.val);
                cur = cur.next;
                ++cnt;
            }
    
            int[] res = new int[cnt];
            int i = 0;
            while (!stack.isEmpty()) { 
                res[i++] = stack.pop();
            }
            return res;
        }
    }

7 重建二叉树  
来源：AcWing

题目描述  
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

样例

给定：  
前序遍历是：\[3, 9, 20, 15, 7\]  
中序遍历是：\[9, 3, 15, 20, 7\]

返回：\[3, 9, 20, null, null, 15, 7, null, null, null, null\]  
返回的二叉树如下所示：  
3  
/  
9 20  
/  
15 7  
解法  
在二叉树的前序遍历序列中，第一个数字总是根结点的值。在中序遍历序列中，根结点的值在序列的中间，左子树的结点位于根结点左侧，而右子树的结点位于根结点值的右侧。

遍历中序序列，找到根结点，递归构建左子树与右子树。

注意添加特殊情况的 if 判断。

/** * Definition for a binary tree node. * class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
    
        /** * 重建二叉树 * * @param preorder 前序遍历序列 * @param inorder 中序遍历序列 * @return 二叉树根结点 */
        public TreeNode buildTree(int[] preorder, int[] inorder) { 
            if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) { 
                return null;
            }
    
            return build(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
        }
    
        private TreeNode build(int[] preorder, int[] inorder, int s1, int e1, int s2, int e2) { 
            int rootVal = preorder[s1];
            TreeNode root = new TreeNode(rootVal);
            if (s1 == e1) { 
                return root;
            }
    
            int i = s2, cnt = 0;
            for (; i <= e2; ++i) { 
                if (inorder[i] == rootVal) { 
                    break;
                }
                ++cnt;
            }
    
            root.left = cnt > 0 ? build(preorder, inorder, s1 + 1, s1 + cnt, s2, i - 1) : null;
            root.right = i < e2 ? build(preorder, inorder, s1 + cnt + 1, e1, i + 1, e2) : null;
            return root;
        }
    }

8 二叉树的下一个节点  
来源：AcWing

题目描述  
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

如果给定的节点是中序遍历序列的最后一个，则返回空节点;

二叉树一定不为空，且给定的节点一定不是空节点。

样例

假定二叉树是：\[2, 1, 3, null, null, null, null\]， 给出的是值等于 2 的节点。

则应返回值等于 3 的节点。

解释：该二叉树的结构如下，2 的后继节点是 3。  
2  
/  
1 3  
解法  
对于结点 p：

如果它有右子树，则右子树的最左结点就是它的下一个结点；

如果它没有右子树，判断它与父结点 p.father 的位置情况：

如果它是父结点的左孩子，那么父结点 p.father 就是它的下一个结点；

如果它是父结点的右孩子，一直向上寻找，直到找到某个结点，它是它父结点的左孩子，那么该父结点就是 p 的下一个结点。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode father; * TreeNode(int x) { val = x; } * } */
    class Solution { 
    
        /** * 获取二叉树中序遍历结点的下一个结点 * * @param p 某结点 * @return p的下一个结点 */
        public TreeNode inorderSuccessor(TreeNode p) { 
            if (p == null) { 
                return null;
            }
    
            TreeNode cur = p.right;
    
            // 右子树不为空
            if (cur != null) { 
                while (cur.left != null) { 
                    cur = cur.left;
                }
                return cur;
            }
    
            // 右子树为空
            TreeNode father = p.father;
            while (father != null && father.left != p) { 
                p = father;
                father = p.father;
            }
            return father;
        }
    }

9.1 用两个栈实现队列  
来源：AcWing

题目描述  
请用栈实现一个队列，支持如下四种操作：

push(x) – 将元素x插到队尾。

pop(x) – 将队首的元素弹出，并返回该元素。

peek() – 返回队首元素。

empty() – 返回队列是否为空。

注意：

你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；

如果你选择的编程语言没有栈的标准库，你可以使用 list 或者 deque 等模拟栈的操作；

输入数据保证合法，例如，在队列为空时，不会进行 pop 或者 peek 等操作；

样例

MyQueue queue = new MyQueue();
    
    queue.push(1);
    queue.push(2);
    queue.peek();  // returns 1
    queue.pop();   // returns 1
    queue.empty(); // returns false

解法  
push 操作，每次都存入 s1； pop 操作，每次从 s2 取：

s2 栈不为空时，不能将 s1 元素倒入；

s2 栈为空时，需要一次将 s1 元素全部倒入。

class MyQueue { 
    
        private Stack<Integer> s1;
        private Stack<Integer> s2;
    
        /** Initialize your data structure here. */
        public MyQueue() { 
            s1 = new Stack<>();
            s2 = new Stack<>();
        }
    
        /** Push element x to the back of queue. */
        public void push(int x) { 
            s1.push(x);
        }
    
        /** Removes the element from in front of queue and returns that element. */
        public int pop() { 
            int t = peek();
            s2.pop();
            return t;
        }
    
        /** Get the front element. */
        public int peek() { 
            if (s2.isEmpty()) { 
                while (!s1.isEmpty()) { 
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }
    
        /** Returns whether the queue is empty. */
        public boolean empty() { 
            return s1.isEmpty() && s2.isEmpty();
        }
    }
    
    /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */

9.2 用两个队列实现栈  
来源：LeetCode

题目描述  
使用队列实现栈的下列操作：

push(x) – 元素 x 入栈

pop() – 移除栈顶元素

top() – 获取栈顶元素

empty() – 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解法  
出栈时，先将队列的元素依次移入另一个队列中，直到队列剩下一个元素。将该元素出队即可。

进栈时，将元素压入不为空的那一个队列即可。如果两队列都为空，随便压入其中一个队列。

class MyStack { 
    
        private Queue<Integer> q1;
        private Queue<Integer> q2;
    
        /** Initialize your data structure here. */
        public MyStack() { 
            q1 = new LinkedList<>();
            q2 = new LinkedList<>();
        }
    
        /** Push element x onto stack. */
        public void push(int x) { 
            if (empty() || q2.isEmpty()) { 
                q1.offer(x);
            } else { 
                q2.offer(x);
            }
        }
    
        /** Removes the element on top of the stack and returns that element. */
        public int pop() { 
            if (q1.isEmpty()) { 
                while (q2.size() > 1) { 
                    q1.offer(q2.poll());
                }
                return q2.poll();
            }
    
            while (q1.size() > 1) { 
                q2.offer(q1.poll());
            }
            return q1.poll();
        }
    
        /** Get the top element. */
        public int top() { 
            int val = pop();
            push(val);
            return  val;
        }
    
        /** Returns whether the stack is empty. */
        public boolean empty() { 
            return q1.isEmpty() && q2.isEmpty();
        }
    }
    
    /** * Your MyStack object will be instantiated and called as such: * MyStack obj = new MyStack(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.top(); * boolean param_4 = obj.empty(); */

10.1 斐波那契数列  
来源：AcWing

题目描述  
输入一个整数 n ，求斐波那契数列的第 n 项。

假定从 0 开始，第 0 项为 0。(n<=39)

样例

输入整数 n=5

返回 5  
解法  
解法一  
采用递归方式，简洁明了，但效率很低，存在大量的重复计算。

f(10)
                   /        
                f(9)         f(8)
              /            /    
           f(8)     f(7)  f(7)   f(6)
          /        /  
       f(7)  f(6)  f(6) f(5)

class Solution { 
    
        /** * 求斐波那契数列的第n项，n从0开始 * * @param n 第n项 * @return 第n项的值 */
        public int Fibonacci(int n) { 
            if (n < 2) { 
                return n;
            }
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }

解法二  
从下往上计算，递推，时间复杂度 O(n)。可以用数组存储，空间复杂度 O(n)；也可以用变量存储，空间复杂度 O(1)。

class Solution { 
    
        /** * 求斐波那契数列的第n项，n从0开始 * * @param n 第n项 * @return 第n项的值 */
        public int Fibonacci(int n) { 
            if (n < 2) { 
                return n;
            }
    
            int a = 1, b = 1;
            for (int i = 2; i < n; ++i) { 
                b = a + b;
                a = b - a;
            }
            return b;
        }
    }
    10.2 跳台阶
    来源：NowCoder
    
    题目描述
    一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
    
    解法
    跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去。所以
    
    f(n) = f(n-1) + f(n-2)
    class Solution { 
    
        /** * 青蛙跳台阶 * * @param target 跳上的那一级台阶 * @return 多少种跳法 */
        public int JumpFloor(int target) { 
            if (target < 3) { 
                return target;
            }
            int a = 1, b = 2;
            for (int i = 3; i <= target; ++i) { 
                b = a + b;
                a = b - a;
            }
            return b;
        }
    }

10.3 变态跳台阶  
来源：NowCoder

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

解法  
解法一：数学推导  
跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去…那么

f(n-1) = f(n-2) + f(n-3) + … + f(0)  
跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去…那么

f(n) = f(n-1) + f(n-2) + … + f(0)  
综上可得

f(n) - f(n-1) = f(n-1)  
即

f(n) = 2\*f(n-1)  
所以 f(n) 是一个等比数列

class Solution \{

/**
     * 青蛙跳台阶II
     *
     * @param target 跳上的那一级台阶
     * @return 多少种跳法
     */
    public int JumpFloorII(int target) {
        return (int) Math.pow(2, target - 1);
    }

\}  
注意，这一解法已同步贡献给开源仓库 CS-Notes。

解法二：动态规划  
每当计算 res\[i\]，把前面所有结果累加起来。

class Solution { 
    
        /** * 青蛙跳台阶II * * @param target 跳上的那一级台阶 * @return 多少种跳法 */
        public int JumpFloorII(int target) { 
            if (target < 3) { 
                return target;
            }
            int[] res = new int[target + 1];
            Arrays.fill(res, 1);
            for (int i = 2; i <= target; ++i) { 
                for (int j = 1; j < i; ++j) { 
                    res[i] += res[j];
                }
            }
            return res[target];
        }
    }

10.4 矩形覆盖  
来源：NowCoder

题目描述  
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2\*n的大矩形，总共有多少种方法？

解法  
覆盖 2\*n 的矩形：

可以先覆盖 2*n-1 的矩形，再覆盖一个 2*1 的矩形；

也可以先覆盖 2\*(n-2) 的矩形，再覆盖两个 1\*2 的矩形。

解法一：利用数组存放结果

class Solution { 
    
        /** * 矩形覆盖 * * @param target 2*target大小的矩形 * @return 多少种覆盖方法 */
        public int RectCover(int target) { 
            if (target < 3) { 
                return target;
            }
            int[] res = new int[target + 1];
            res[1] = 1;
            res[2] = 2;
            for (int i = 3; i <= target; ++i) { 
                res[i] = res[i - 1] + res[i - 2];
            }
            return res[target];
        }
    }

解法二：直接用变量存储结果

class Solution { 
    
        /** * 矩形覆盖 * * @param target 2*target大小的矩形 * @return 多少种覆盖方法 */
        public int RectCover(int target) { 
            if (target < 3) { 
                return target;
            }
            int a = 1, b = 2;
            for (int i = 3; i <= target; ++i) { 
                b = a + b;
                a = b - a;
            }
            return b;
        }
    }

11 旋转数组的最小数字  
来源：AcWing

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

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组 \{3,4,5,1,2\} 为 \{1,2,3,4,5\} 的一个旋转，该数组的最小值为 1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为 0，请返回 -1。

样例

输入：nums=\[2,2,2,0,1\]

输出：0  
解法  
解法一  
直接遍历数组找最小值，时间复杂度 O(n)，不推荐。

class Solution { 
    
        /** * 获取旋转数组的最小元素 * * @param nums 旋转数组 * @return 数组中的最小值 */
        public int findMin(int[] nums) { 
            if (nums == null || nums.length == 0) { 
                return -1;
            }
            int min = nums[0];
            int n = nums.length;
            if (min < nums[n - 1]) { 
                return min;
            }
            for (int i = 1; i < n; ++i) { 
                min = Math.min(min, nums[i]);
            }
            return min;
        }
    }

解法二  
利用指针 start,end 指向数组的首尾，如果 nums\[start\] < nums\[end\]，说明数组是递增数组，直接返回 nums\[start\]。否则进行如下讨论。

计算中间指针 mid：

如果此时 nums\[start\], nums\[end\], nums\[mid\] 两两相等，此时无法采用二分方式，只能通过遍历区间 \[start,end) 获取最小值；

如果此时 start,end 相邻，说明此时 end 指向的元素是最小值，返回 nums\[end\]；

如果此时 nums\[mid\] >= nums\[start\]，说明 mid 位于左边的递增数组中，最小值在右边，因此，把 start 指向 mid，此时保持了 start 指向左边递增子数组；

如果此时 nums\[mid\] <= nums\[end\]，说明 mid 位于右边的递增数组中，最小值在左边，因此，把 end 指向 mid，此时保持了 end 指向右边递增子数组。

/** * @author bingo * @since 2018/12/17 */
    
    class Solution { 
    
        /** * 获取旋转数组的最小元素 * * @param nums 旋转数组 * @return 数组中的最小值 */
        public int findMin(int[] nums) { 
            if (nums == null || nums.length == 0) { 
                return -1;
            }
            int start = 0, end = nums.length - 1;
    
            if (nums[start] < nums[end]) { 
                // 说明这是一个单调递增数组
                return nums[start];
            }
            while (end - start > 1) { 
                int mid = start + ((end - start) >> 1);
                if (nums[start] == nums[end] && nums[mid] == nums[start]) { 
                    // 三个数都相等，只能在[start, end)区间遍历，找出最小值
                    return findMin(nums, start, end);
                }
                if (nums[mid] >= nums[start]) { 
                    start = mid;
                } else { 
                    end = mid;
                }
            }
            return nums[end];
        }
    
        private int findMin(int[] nums, int start, int end) { 
            int min = Integer.MAX_VALUE;
            for (int i = start; i < end; ++i) { 
                min = Math.min(min, nums[i]);
            }
            return min;
        }
    }

12 矩阵中的路径  
来源：AcWing

题目描述  
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

输入的路径不为空；

所有出现的字符均为大写英文字母。

样例

matrix=  
\[  
\[‘A’,‘B’,‘C’,‘E’\],  
\[‘S’,‘F’,‘C’,‘S’\],  
\[‘A’,‘D’,‘E’,‘E’\]  
\]

str=“BCCE” , return “true”

str=“ASAE” , return “false”  
解法  
回溯法。首先，任选一个格子作为路径起点。假设格子对应的字符为 ch，并且对应路径上的第 i 个字符。若相等，到相邻格子寻找路径上的第 i+1 个字符。重复这一过程。

class Solution { 
    
        /** * 判断矩阵中是否包含某条路径 * * @param matrix 矩阵 * @param str 路径 * @return 是否包含某条路径 */
        public boolean hasPath(char[][] matrix, String str) { 
            if (matrix ==  null || matrix.length == 0 || str == null) { 
                return false;
            }
    
            int m = matrix.length, n = matrix[0].length;
    
            boolean[][] visited = new boolean[m][n];
            int pathLength = 0;
            for (int i = 0; i < m; ++i) { 
                for (int j = 0; j < n; ++j) { 
                    if (hasPath(matrix, str, i, j, visited, pathLength)) { 
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean hasPath(char[][] matrix, String str, int i, int j, boolean[][] visited, int pathLength) { 
            if (pathLength == str.length()) { 
                return true;
            }
            boolean hasPath = false;
            if (i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length
                    && !visited[i][j] && matrix[i][j] == str.charAt(pathLength)) { 
                ++pathLength;
                visited[i][j] = true;
                hasPath = hasPath(matrix, str, i + 1, j, visited, pathLength)
                        || hasPath(matrix, str, i - 1, j, visited, pathLength)
                        || hasPath(matrix, str, i, j + 1, visited, pathLength)
                        || hasPath(matrix, str, i, j - 1, visited, pathLength);
                if (!hasPath) { 
                    --pathLength;
                    visited[i][j] = false;
                }
            }
            return hasPath;
        }
    }

--------------------

扫描下方二维码，**及时**获取更多**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术，和**海量资料分享**：  
公众号\*\*`菜鸟名企梦`**后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；  
公众号**`菜鸟名企梦`**后台发送“资料”:即可领取**5T精品学习资料\*\*、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**  
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240]

**推荐阅读**

[**☞知网靠免费使用论文，一年收费10亿多**][10]

[1240]: /images/20220215/489c702a18af4d0fa1aa48a202559060.png
[10]: http://mp.weixin.qq.com/s?__biz=MzI3ODg2OTY1OQ==&mid=2247485193&idx=1&sn=8a87b62d3728a2136698cb39b2c5707f&chksm=eb5124fddc26adeb3786d13e68b5f74f82ef09fe9e7046c47c8c776ebbaced8b493fc139cbb7&scene=21#wechat_redirect