北京城乡建设官方网站网站备案查询app下载

当前位置： 首页 > news >正文

北京城乡建设官方网站,网站备案查询app下载,哪个网站公司做的好,老旧小区改造国家最新政策文章目录前言一、 数组中重复的数字:fire: 解决方法:dog: 代码二、二维数组中的查找:fire:思路:dog:代码三、替换空格:fire:思路:dog: 代码四、从尾到头打印链表:fire:思路:dog:代码:dog: 代码五、重建二叉树:fire:思路:dog: 代码总结前言 剑指offer系列是一本非常著名的面试题… 文章目录前言一、 数组中重复的数字:fire: 解决方法:dog: 代码二、二维数组中的查找:fire:思路:dog:代码三、替换空格:fire:思路:dog: 代码四、从尾到头打印链表:fire:思路:dog:代码:dog: 代码五、重建二叉树:fire:思路:dog: 代码总结前言 剑指offer系列是一本非常著名的面试题目集旨在帮助求职者提升编程能力和应对面试的能力。随着互联网行业的迅速发展和竞争的加剧技术人才的需求量也越来越大而面试已经成为求职过程中至关重要的一环。 剑指offer系列汇集了许多公司常见的面试题目并且针对每个问题都给出了详细的解答和分析对于准备参加面试的求职者来说非常实用。 在本系列文章中我们将一步步地学习这些问题的解决方法掌握如何在面试中优雅地回答这些问题帮助读者更好地备战面试拿到心仪的工作机会❤️。 一、 数组中重复的数字 找出数组中重复的数字 在一个长度为 n 的数组 nums 里的所有数字都在 0n-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 i0;// 当i小于数组的长度时:while(inums.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对象中添加%20else // 如果当前字符不是空格bulider.append(s.charAt(i)); // 向StringBuilder对象中添加原始字符}return bulider.toString(); // 返回由StringBuilder对象构建的新字符串} } 四、从尾到头打印链表 从尾到头打印链表 思路 ️ 方式一 Java算法流程 1️⃣. 递推阶段每次传入head.next,以headnull (即走过链表尾部节点) 为递归终止条件此时直接返回。 2️⃣. 回溯阶段层层回时将当前节点值加入列表即tmp.add(head.val)。 3️⃣. 最终将列表tmp转化为数组 res,并返回即可。 时间复杂度O(N): 遍历链表递归N次。空间复杂度O(N): 系统递归需要使用O(N)的栈空间。 该解决方案计算链表的长度并使用一个数组来存储链表元素。我们首先遍历链表以计算其长度。然后创建一个大小为链表长度的数组并从头到尾遍历链表将每个节点的值存储在数组中。 最后返回结果数组其中包含链表元素的倒序副本。 ❤️请注意这两种方法的时间复杂度均为On其中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作为堆栈LinkedListInteger stack new LinkedListInteger();//遍历链表将每个节点的值添加到堆栈中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 preorderinorder 如果没有它将检索数组的第一个元素该元素应该是二叉树的当前根节点。将使用该值创建一个新值。preorderTreeNode 该变量使用从 .preIndexinorderget()IndexHashMap 2️⃣接下来通过使用更新的参数调用方法递归构造左侧子树。 数组中左子树的起始索引是通过在 上加 1 并从计算中减去来给出的。数组中左侧子树的结束索引位于 。treeBuilderpreorderpreLeftinLeftpreIndexinorderpreIndex - 1 右子树的构造类似但数组中的起始索引是通过添加到 来计算的而数组中的结束索引位于 。preorderpreIndex - inLeft 1preLeftinorderinRigth ❌最后返回表示子树根节点的构造。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 MapInteger,Integer IndexHashMap; // 声明一个 Hashmap 存储中序遍历数组元素及其下标public TreeNode buildTree(int[] preorder, int[] inorder) { // 构建二叉树的方法输入是前序和中序遍历数组IndexHashMap new HashMap(); // 初始化上文声明的 HashMapfor(int i 0 ;iinorder.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(preLeftpreRight || inLeftinRigth) return null;// 取出当前子树的根节点并创建新节点int rootValue preorder[preLeft];TreeNode root new TreeNode(rootValue);// 获取当前根节点在中序遍历数组中的下标int preIndexIndexHashMap.get(rootValue);// 递归构建左子树root.left treeBuilder(preorder,preLeft1,preIndexpreLeft-inLeft,inorder,inLeft,preIndex-1);// 递归构建右子树root.right treeBuilder(preorder,preIndexpreLeft-inLeft1,preRight,inorder,preIndex1,inRigth);// 返回当前根节点return root;} } 总结 提示这里对文章进行总结 以上五道算法题是典型的面试题还有很多各种类型的算法题接下来回继续更新持续更新。