剑指offer第二版（leetcode）Java题解（不断更新）

2024-04-07 02:32
文章标签 java leetcode 第二 offer 题解 不断更新

本文主要是介绍剑指offer第二版（leetcode）Java题解（不断更新），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 数组中的重复数字

题目

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

思路

所有的数字都在0到n-1，所以可以将数字看做数组的下标。
通过把每个数字放回它的值作为索引的位置，在放置的时候判断目标位置是否已经有正确对应的值
如果没有，就交换，如果有，说明对应位置存在重复值。

代码

class Solution {public int findRepeatNumber(int[] nums) {for(int i =0;i<nums.length;i++){//如果当前数不是应该在的位置，就放过去，交换对应位置的数回来//如果在应该在的位置，这个就跳过去，看下一个。if(nums[i]!=i){int temp = nums[nums[i]];//移动时如果目标位置已经有了一个应该在的数，说明重复了if(temp == nums[i]){return nums[i];}//没有就交换一下nums[nums[i]]=nums[i];nums[i]=temp;i--;}}return 0;}
}

2 二维数组中的查找

题目

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

思路

代码

class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {int row = matrix.length-1;int col = 0;while(row >=0&&col<matrix[0].length){if(matrix[row][col]==target)return true;if(matrix[row][col]>target){row = row -1;}else{col = col+1;}}return false;}
}

3 替换空格

题目

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

代码

class Solution {public String replaceSpace(String s) {if(s.length()==0)return s;int count =0;//求一下空格的个数确定 array的sizefor(int i= 0;i<s.length();i++)if(s.charAt(i) == ' ')count++;int size = s.length()+count*2;char [] str = new char[size];int j=size-1;//从后往前填写，其实在这道题从前往后也是一样的，从后往前在某些情境下可以实现原地for(int i =s.length()-1;i>=0;i--){if(s.charAt(i)==' '){str[j]='0';str[j-1]='2';str[j-2]='%';j=j-3;}else{str[j]=s.charAt(i);j--;}}return new String(str);}
}

4 从尾到头打印链表

题目

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

代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {//记录长度  创建返回结果 填入即可  当然 链表反转也可以解决public int[] reversePrint(ListNode head) {int len=0;ListNode cur=head;while(cur!=null){len++;cur=cur.next;}int []res=new int[len];for(int i=len-1;i>=0;i--){res[i]=head.val;head=head.next;}return res;}
}

5 重建二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

代码

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {return rebuild(preorder,inorder,0,preorder.length,0,preorder.length);}public TreeNode rebuild(int [] preOrder, int []inOrder,int lp,int rp,int li,int ri){if(lp>=rp||li>=ri)return null;TreeNode node = new TreeNode(preOrder[lp]);int count = 0;for(int i = li;i<ri;i++){if(inOrder[i]==preOrder[lp])break;count++;}node.left = rebuild(preOrder,inOrder,lp+1,lp+1+count,li,li+count);node.right=rebuild(preOrder,inOrder,lp+count+1,rp,li+count+1,ri);return node;}
}

6 用两个栈实现队列

题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

代码

    class CQueue {public Stack<Integer> inStack;public Stack<Integer> outStack;public CQueue() {inStack= new Stack();outStack=new Stack();}public void appendTail(int value) {while(outStack.size()!=0){inStack.push(outStack.pop());}inStack.push(value);}public int deleteHead() {while(inStack.size()!=0){outStack.push(inStack.pop());}if(outStack.size()!=0)return outStack.pop();elsereturn -1;}}/*** Your CQueue object will be instantiated and called as such:* CQueue obj = new CQueue();* obj.appendTail(value);* int param_2 = obj.deleteHead();*/

7 斐波那契数列

题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

代码

class Solution {public int fib(int n) {int first = 0;int second = 1;if(n==0)return 0;if(n==1)return 1;if(n==2)return 1;int third = 0;for(int i =2 ;i<=n;i++){third = (first+second)%1000000007;first = second;second = third;}return third;}
}

8 青蛙跳台阶

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

代码

class Solution {public int numWays(int n) {if(n==0)return 1;if(n==1)return 1;int first = 1,second =1;int third = 2;for(int i=2;i<=n;i++){third = (first+second)%1000000007;first=second;second=third;}return third;}
}

9 旋转数组中的最小数字（有点东西）

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

代码

class Solution {public int minArray(int[] numbers) {int left = 0,right = numbers.length-1;while(left+1<right){int index = left+(right-left)/2;if(numbers[index]>numbers[right]){left = index;}else if(numbers[index]<numbers[right])right =index;elseright--;}if(numbers[left]<numbers[right])return numbers[left];else{return numbers[right];}}
}

10 矩阵中的路径

题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

代码

class Solution {//设定两个全局的标记public boolean success= false;public boolean[][] flag;public boolean exist(char[][] board, String word) {//避免一下错误输入if(board.length<=0||board[0].length<=0)return false;//根据输入初始化标记数组flag = new boolean [board.length][board[0].length];//所有元素作为入口for(int i = 0;i<board.length;i++){for(int j=0;j<board[0].length;j++){move(board,i,j,word,0);}}return success;}public void move(char [][]board,int i,int j,String word, int index){//有一个成功就不继续了if(success == true)return ;//走完word就是成功if(index == word.length()){success = true;return ;}//越界情况处理掉if(i<0||i>=board.length||j<0||j>=board[0].length)return;//如果flag表示没走过这个点且这个点和word当前字符相同，那就往上下左右继续走if(flag[i][j]==false&&board[i][j]==word.charAt(index)){flag[i][j]=true;move(board,i+1,j,word,index+1);move(board,i-1,j,word,index+1);move(board,i,j+1,word,index+1);move(board,i,j-1,word,index+1);//走完说明上下左右没有匹配到，这个点标记恢复标记，退回上一步的节点继续走flag[i][j]=false;}}
}

11 机器人的运动范围

题目

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

代码

class Solution {//要考虑好最重要的就是走过的路能不能走的问题，实际上遍历就是不能往回走的，但是一样可以遍历到所有的路，还是深度优先遍历没有理解好int count = 0;boolean [][]flag;public int movingCount(int m, int n, int k) {//初始化一个标记数组flag = new boolean[m][n];move(m,n,k,0,0);return count;}public void move(int m,int n,int k,int x,int y){//越界不继续if(x<0||x>=m||y<0||y>=n)return ;//走过不走if(flag[x][y]==true){return;}//如果符合要求就走进来，然后上下左右。if(k>=count(x,y)){flag[x][y]=true;count++;move(m,n,k,x+1,y);move(m,n,k,x-1,y);move(m,n,k,x,y-1);move(m,n,k,x,y+1);}}//实际的业务要求独立出来public int count(int x,int y){int sum =0;while(x>0){sum+=x%10;x=x/10;}while(y>0){sum+=y%10;y=y/10;}return sum;}
}

12 剪绳子I

题目

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

代码

class Solution {public int cuttingRope(int n) {//简单数学证明一下切3 切2 的大小比较if(n==2)return 1;if(n==3)return 2;if(n==4)return n;int sum =1;while(n>=5){sum=sum*3;n=n-3;}if(n>0){sum*=n;}return sum;}
}

13 剪绳子 II

题目

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

代码

class Solution {public int cuttingRope(int n) {//简单证明一下切3 切2 的大小比较if(n==2)return 1;if(n==3)return 2;if(n==4)return n;//这里防止溢出long sum =1;while(n>=5){//这里乘三有溢出的情况，所以取余也莫得用sum=sum*3%1000000007;n=n-3;}if(n>0){sum=sum*n%1000000007;}return (int)sum;}
}

14 二进制中1的个数

题目

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

代码

public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {//n是整数，但是负整数也是整数//仗着java有无符号右移，所以这个问题被掩盖了        int count =0;while(n!=0){if((n&1)==1){count++;}n=n>>>1;}return count;}
}
//如果不用无符号右移
public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {//n是整数，但是负整数也是整数//仗着java有无符号右移，所以这个问题被掩盖了int count =0;for(int i=0;i<32;i++){if((n&1)==1){count++;}n=n>>1;}return count;}
}

15 数值的整数次方

题目

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

代码

class Solution {public double myPow(double x, int n) {if(n==0)return 1

这篇关于剑指offer第二版（leetcode）Java题解（不断更新）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/881437。

相关文章

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

闲置电脑也能活出第二春？鲁大师AiNAS让你动动手指就能轻松部署

对于大多数人而言，在这个“数据爆炸”的时代或多或少都遇到过存储告急的情况，这使得“存储焦虑”不再是个别现象，而将会是随着软件的不断臃肿而越来越普遍的情况。从不少手机厂商都开始将存储上限提升至1TB可以见得，我们似乎正处在互联网信息飞速增长的阶段，对于存储的需求也将会不断扩大。对于苹果用户而言，这一问题愈发严峻，毕竟512GB和1TB版本的iPhone可不是人人都消费得起的，因此成熟的外置存储方案开
阅读更多...
JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
Java进阶13讲__第12讲_1/2

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2