【剑指 Offer】(1)

---

前言

剑指offer系列是一本非常著名的面试题目集，旨在帮助求职者提升编程能力和应对面试的能力。随着互联网行业的迅速发展和竞争的加剧，技术人才的需求量也越来越大，而面试已经成为求职过程中至关重要的一环。 剑指offer系列汇集了许多公司常见的面试题目，并且针对每个问题都给出了详细的解答和分析，对于准备参加面试的求职者来说非常实用。

在本系列文章中，我们将一步步地学习这些问题的解决方法，掌握如何在面试中优雅地回答这些问题，帮助读者更好地备战面试，拿到心仪的工作机会❤️。

---

一、 数组中重复的数字

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

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

🔥 解决方法

该方法将整数数组作为输入，并返回找到的第一个重复数字。使用的算法基于将元素交换到其相应的索引位置的想法，直到找到重复的元素。

该算法的工作原理如下：
1️⃣.初始化指向0的指针.
2️⃣.虽然小于数组的长度：

• 🅰️.如果索引处的当前元素已经等于，则递增并继续到下一个元素。
• 🅱️.如果索引处的值给出的索引处的元素等于索引处的值，那么我们找到了一个重复的数字，所以返回这个数字。
• ❌.否则，将索引处的元素与其值给定的索引处的元素交换。

3️⃣.如果未找到重复元素，则返回-1。

总体而言，该算法的时间复杂度为0()，因为它扁历整个数组一次。空间复杂度为O(1)，因为它不使用任何其他数据结构来存储有关数组的信息。

🐶 代码

class Solution {public int findRepeatNumber(int[] nums) {// 将指针i初始化为0int i=0;// 当"i"小于数组的长度时:while(i<nums.length){// 如果当前元素在索引“i”处已经等于“i”，则增加“i”并继续到下一个元素。if(nums[i]==i){i++;continue;} //  如果索引i处的值给出的索引处的元素等于索引i处的值，那么我们找到了一个重复的数字，因此返回该数字。if(nums[nums[i]]==nums[i])return nums[i];// 否则，将下标为“i”的元素与下标为其值的元素交换。.int t =nums[i];nums[i]=nums[t];nums[t]=t;}//  如果没有找到重复的元素，则返回-1。return -1;}
}

总体来说，这段代码实现了在整型数组中查找第一个重复数字的功能。该算法的时间复杂度为O(n)，空间复杂度为O(1)。

二、二维数组中的查找

二维数组中的查找

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

示例:

现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000

🔥思路

这段代码定义了一个名为 Solution 的类，其中包含一个名为 findNumberIn2DArray 的方法。

1️⃣. 该方法接收两个参数：一个二维整数数组 matrix 和一个整数 target。目标是在二维数组中查找是否存在目标整数。

2️⃣该方法使用 while 循环从左下角开始遍历 matrix。

• 如果当前元素大于 target，则将行索引减少；
• 如果当前元素小于 target，则将列索引增加。如果当前元素等于 target，则返回 true。
• 如果 while 循环完成后仍未找到 target，则返回 false。

总体而言，这个算法被称为“在二维矩阵中搜索”问题，可以使用二分搜索或双指针方法进行解决，因为矩阵是有序的。
需要注意的是，此实现假定 matrix 按行和列均按非降序排列。

🐶代码

class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {// 初始化行和列索引，从左下角开始遍历int rows = matrix.length - 1, col = 0;while(rows >= 0 && col < matrix[0].length){// 如果当前元素比目标大，则将行索引减少if(matrix[rows][col] > target) rows--;// 如果当前元素比目标小，则将列索引增加else if(matrix[rows][col] < target) col++;// 如果当前元素等于目标，返回 trueelse return true;}// 循环结束后仍未找到目标，返回 falsereturn false;}   
}

三、替换空格

替换空格

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

输入：s = “We are happy.”
输出：“We%20are%20happy.”

限制：
0 <= s 的长度 <= 10000

🔥思路

这段Java代码定义了一个名为Solution的类，其中包含了一个replaceSpace方法。

• 该方法接收一个字符串s作为输入，并返回将字符串中所有空格替换成"%20"之后得到的修改后 的新字符串。在实现中，该方法使用了一个StringBuilder对象来逐个构建新字符串。
• 它遍历输入字符串中的每个字符，判断当前字符是否为空格。如果是，则向StringBuilder对象中添加"%20"；
• 否则，向StringBuilder对象中添加原始字符。

这段代码似乎是解决一个常见的编程问题，即将字符串中的空格替换为"%20"。在处理URL或其他类型的Web资源时，经常遇到这种问题。

🐶 代码

class Solution {public String replaceSpace(String s) {StringBuilder  bulider = new StringBuilder(); // 创建一个StringBuilder对象用于构建新字符串for(int i = 0 ; i <s.length();i++){ // 遍历输入字符串中的每个字符if(s.charAt(i)==' ') // 如果当前字符是空格bulider.append("%20"); // 向StringBuilder对象中添加"%20"else // 如果当前字符不是空格bulider.append(s.charAt(i)); // 向StringBuilder对象中添加原始字符}return bulider.toString(); // 返回由StringBuilder对象构建的新字符串}
}

四、从尾到头打印链表

从尾到头打印链表

🔥思路

🅰️ 方式一
Java算法流程：

1️⃣. 递推阶段：每次传入head.next,以head=null (即走过链表尾部节点) 为递归终止条件，此时直接返回。
2️⃣. 回溯阶段：层层回时，将当前节点值加入列表，即tmp.add(head.val)。
3️⃣. 最终，将列表tmp转化为数组 res,并返回即可。

• 时间复杂度O(N): 遍历链表，递归N次。
• 空间复杂度O(N): 系统递归需要使用O(N)的栈空间。

该解决方案计算链表的长度，并使用一个数组来存储链表元素。我们首先遍历链表以计算其长度。然后创建一个大小为链表长度的数组，并从头到尾遍历链表，将每个节点的值存储在数组中。
最后，返回结果数组，其中包含链表元素的倒序副本。
❤️请注意，这两种方法的时间复杂度均为O（n），其中n是链表的长度。

🐶代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public int[] reversePrint(ListNode head) { // 计算链表长度ListNode cur = head;int len = 0;while(cur!=null){cur = cur.next;len++;}// 创建结果数组，并将链表元素倒序存入其中int[] res =new int[len];ListNode node = head;int i = len-1;while(node!=null){res[i]=node.val;i--;node = node.next;}// 返回结果数组return res;}
}

🅱️ 方式二
1️⃣. 入栈：遍历链表，将各节点值push入栈。(Python使用append()方法，Java借助
LinkedList的addLast)方法)。
2️⃣ 出栈：将各节点值pop出栈，存储于数组并返回。(Python直接返回stack的倒序列表，
Java新建一个数组，通过popLast() 方法将各元素存入数组，实现倒序输出)。

这是一个用于反转和打印链表内容的 Java 解决方案。它首先创建一个堆栈并遍历链表，将每个节点的值推送到堆栈上。将所有节点添加到堆栈后，它会使用堆栈的大小初始化整数数组，然后将堆栈中的值弹出到整数数组中，从而创建相反的顺序。LinkedList

该类不包含在提供的代码片段中，但它可能是程序中其他位置使用的自定义类。ListNode

🐶 代码

class Solution {public int[] reversePrint(ListNode head) {// 创建一个新的LinkedList作为堆栈LinkedList<Integer> stack = new LinkedList<Integer>();//遍历链表，将每个节点的值添加到堆栈中while(head != null) {stack.addLast(head.val);head = head.next;}// 创建一个与堆栈大小相同的整数数组int[] res = new int[stack.size()];// 将值从堆栈中弹出到整数数组中，反转它们的顺序for(int i = 0; i < res.length; i++)res[i] = stack.removeLast();// 返回反转的整数数组return res;}
}

五、重建二叉树

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：
0 <= 节点个数 <= 5000

🔥思路

这是一个 Java 代码，实现了从二叉树的预序和无序遍历数组构造二叉树的解决方案。这里使用的方法本质上是递归的。

1️⃣该方法采用两个输入数组：表示二叉树的预序遍历，以及表示同一二叉树的无序遍历。该方法初始化一个命名以存储数组中每个元素的索引。buildTree, preorder, inorder ,HashMapIndex ,HashMap ,inorder。

• 在该方法中，检查的第一件事是 or 数组是否为空。
• 如果为 true，则返回 null，因为没有更多要处理的元素。treeBuilder ，preorder，inorder

如果没有，它将检索数组的第一个元素，该元素应该是二叉树的当前根节点。将使用该值创建一个新值。preorder，TreeNode

该变量使用从 .preIndex，inorder，get()，IndexHashMap

2️⃣接下来，通过使用更新的参数调用方法，递归构造左侧子树。
数组中左子树的起始索引是通过在 上加 1 并从计算中减去来给出的。数组中左侧子树的结束索引位于 。treeBuilder，preorder，preLeft，inLeft，preIndex，inorder，preIndex - 1

右子树的构造类似，但数组中的起始索引是通过添加到 来计算的，而数组中的结束索引位于 。preorder，preIndex - inLeft + 1，preLeft，inorder，inRigth

❌最后，返回表示子树根节点的构造。TreeNode

总体而言，该算法的时间复杂度为 O(n），其中 n 是树中的节点数，因为它访问每个节点一次。

🐶 代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/// 定义 Solution 类
class Solution {private  Map<Integer,Integer> IndexHashMap; // 声明一个 Hashmap 存储中序遍历数组元素及其下标public TreeNode buildTree(int[] preorder, int[] inorder) { // 构建二叉树的方法，输入是前序和中序遍历数组IndexHashMap = new HashMap(); // 初始化上文声明的 HashMapfor(int i =0 ;i<inorder.length;i++){ // 遍历中序遍历数组IndexHashMap.put(inorder[i],i); // 将中序遍历数组的元素及其下标存入 HashMap 中}// 调用递归方法构建二叉树并返回根节点return treeBuilder(preorder,0,preorder.length-1,inorder,0,inorder.length-1);}// 递归函数，用于构建一棵子树private TreeNode treeBuilder(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRigth){// 如果传进来的数组为空，则返回 nullif(preLeft>preRight || inLeft>inRigth) return null;// 取出当前子树的根节点，并创建新节点int rootValue = preorder[preLeft];TreeNode root = new TreeNode(rootValue);// 获取当前根节点在中序遍历数组中的下标int preIndex=IndexHashMap.get(rootValue);// 递归构建左子树root.left = treeBuilder(preorder,preLeft+1,preIndex+preLeft-inLeft,inorder,inLeft,preIndex-1);// 递归构建右子树root.right = treeBuilder(preorder,preIndex+preLeft-inLeft+1,preRight,inorder,preIndex+1,inRigth);// 返回当前根节点return root;}
}

---

总结

提示：这里对文章进行总结：
以上五道算法题是典型的面试题，还有很多各种类型的算法题，接下来回继续更新，持续更新🔥🔥🔥。