没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全剑指offer1

剑指offer1

leetcode

java

需积分: 0 0 下载量 80 浏览量 2022-08-04 16:45:29 上传评论收藏 2MB PDF 举报

温馨提示

试读

83页

剑指offer1

资源详情

资源评论

资源推荐

剑指offer

WangC总结

注：以下标题直接链接LeetCode中文题目，以下内容是自己刷题对自己解答和主要解答的总结，仅供大

家在找工作时方便复习，使用Java，希望大家都能找到好工作，后面附上我的剑指offer总结题解的

github

面试题03. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知

道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

限制：



方法一：哈希集合

利用set判断是否存在，如果存在则返回这个数

时间复杂度：O(n)，空间复杂度：O(n)

方法二：排序后进行比较

先将数组排序，然后判断相邻元素是否有重复

时间复杂度：O(nlog(n))，空间复杂度：O(1)

方法三：额外数组做索引

用一个数组与原数组值对应，当大于1时则返回

时间复杂度：O(n)，空间复杂度：O(n)

输入：

[2, 3, 1, 0, 2, 5, 3]

输出：2 或 3

2 <= n <= 100000

 public int findRepeatNumber(int[] nums) {

   int[] renum = new int[nums.length];

   for(int n : nums){

     if(++renum[n] > 1) return n;

   }

   return 0;

 }

方法四：原地置换

数组的索引和值不对应，nums[i] = j，第i个值不是i，就和j下标的数互换，遇到重复就返回

时间复杂度：O(n)，空间复杂度：O(1)

面试题04. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺

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

示例:

现有矩阵 matrix 如下：

给定 target = 5 ，返回 true 。

给定 target = 20 ，返回 false 。

限制：

方法：线性查找

根据右上和左下是最大值，从一端开始搜索，如果从左下开始，比target大就row--，比target小就j++，

不走回头路。

时间复杂度：O(n+m)，空间复杂度：O(1)

 public int findRepeatNumber(int[] nums) {

   int tmp;

   for(int i = 0; i < nums.length; i++){

     while(nums[i] != i){

       if(nums[i] == nums[nums[i]]) return nums[i];

       tmp = nums[i];

       nums[i] = nums[tmp];

       nums[tmp] = tmp;

     }

   }

   return -1;

 }

[[ 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]]

0 <= n <= 1000

0 <= m <= 1000

面试题05. 替换空格

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

示例 1：

限制：

方法一：使用自带函数

方法二：使用StringBuilder

时间复杂度O(N)：遍历O(N)

空间复杂度O(N)：O(N)

面试题06. 从尾到头打印链表

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

示例 1：

 public boolean findNumberIn2DArray(int[][] matrix, int target) {

   int i = matrix.length - 1;

   int j = 0;

   while(i >= 0 && j < matrix[0].length){

     if(matrix[i][j] > target) i--;

     else if(matrix[i][j] < target) j++;

     else return true;

   }

   return false;

 }

输入：s = "We are happy."

输出："We%20are%20happy."

0 <= s 的长度 <= 10000

 public String replaceSpace(String s) {

   s=s.replace(" ","%20");

   return s;

 }

 public String replaceSpace(String s) {

   StringBuilder sb = new StringBuilder();

   for(int i = 0; i < s.length(); i++){

     if(s.charAt(i) == ' ') sb.append("%20");

     else sb.append(s.charAt(i));

   }

   return sb.toString();

 }

输入：head = [1,3,2]

输出：[2,3,1]

限制：

方法一：使用stack

时间复杂度：O(n)

空间复杂度：O(n)

方法二：两遍遍历，倒序存储

第一遍遍历获取长度，第二遍从数组最后一个开始存储

时间复杂度：O(n)

空间复杂度：O(1)

面试题07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果

中都不含重复的数字。

样例

0 <= 链表长度 <= 10000

 public int[] reversePrint(ListNode head) {

   Stack<ListNode> stack = new Stack<>();

   int len = 0;

   while(head != null){

     stack.push(head);

     head = head.next;

     len++;

   }

   int[] res = new int[len];

   for(int i = 0; i < len; i++){

     res[i] = stack.pop().val;

   }

   return res;

 }

 public int[] reversePrint(ListNode head) {

   int len = 0;

   ListNode tmp = head;

   while(tmp != null){

     tmp = tmp.next;

     len++;

   }

   int[] res = new int[len];

   for(int i = len - 1; i >= 0; i--){

     res[i] = head.val;

     head = head.next;

   }

   return res;

 }

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

限制：

方法一：递归

时间复杂度：O(n)

空间复杂度：O(n)

递归二（速度加快）

时间复杂度：O(n)

空间复杂度：O(n)

 3

 / \

9 20

 / \

 15  7

0 <= 节点个数 <= 5000

 public TreeNode buildTree(int[] preorder, int[] inorder) {

   Map<Integer, Integer> map = new HashMap<>();

   for(int i = 0; i < inorder.length; i++){

     map.put(inorder[i], i);

   }

   return buildTreeHelper(preorder, 0, preorder.length, inorder, 0,

inorder.length, map);

 }

 private TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end,

int[] inorder, int i_start, int i_end, Map<Integer, Integer> map){

   if(p_start == p_end) return null;

   int root_val = preorder[p_start];

   TreeNode root = new TreeNode(root_val);

   int i_idx = map.get(root_val);

   int left_num = i_idx - i_start;

   root.left = buildTreeHelper(preorder, p_start + 1, p_start + 1 +

left_num, inorder, i_start, i_idx, map);

   root.right = buildTreeHelper(preorder, p_start + 1 + left_num, p_end,

inorder, i_idx + 1, i_end, map);

   return root;

 }

 private int in = 0;

 private int pre = 0;

 public TreeNode buildTree(int[] preorder, int[] inorder) {

   return backtrack(preorder, inorder, Integer.MAX_VALUE);

 }

 private TreeNode backtrack(int[] preorder, int[] inorder, int stop){

   if(pre == preorder.length) return null;

   if(inorder[in] == stop){

     in++;

     return null;

   }

   int val = preorder[pre++];

剩余82页未读，继续阅读

内容反馈

呆呆美要暴富

粉丝: 34
资源: 339

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

剑指offer1

评论0

最新资源

剑指offer1

评论0

example_page_offer1

剑指Offer1

剑指offer视频授课

剑指offer.md

基于spring boot的小区物业管理系统源码+论文+答辩ppt

最新Java JDK 8安装版（Windows 64位）

自主研发的软著申请代码文档整理输出工具

毕业设计-基于JAVA的springboot超市进销存系统(源代码+论文）

Java 面经手册·小傅哥.pdf

JAVA课程设计，学生管理系统，设计SQL server数据库操作

BurpLoaderKeygen.jar.zip

java-11 windows-x64 安装包

Java面试八股文2023最新版

2024最强Java面试八股文

JDK1.8 windows 64位

Spire.Doc for Java 11.4.2 全功能无限制

JavaWeb仿小米在线商城ShoppingMall

ide-eval-resetter-2.3.5.jar,重新定义idea使用时间

java版本使用springboot vue websocket webrtc实现视频通话

jdk-8u401-windows-x64

MySql5.7.43安装包

教务管理系统——数据库课程设计mysql+java

aspose-cad-23.8.jar

Java第十五届蓝桥杯大赛软件JavaB组真题

jdk-11-windows-x64.zip

myeclipse 10.7.1 windows 安装包

图书管理系统(Java实现）[附完整代码]

JDK11安装包文件、附带环境配置教程（全网最详情，值得收藏）

最新资源