ps做网站要多大,传奇世界游戏官网,wordpress 会员下载,无锡定制网站原题链接#xff1a;力扣热题-HOT100 我把刷题的顺序调整了一下#xff0c;所以可以根据题号进行参考#xff0c;题号和力扣上时对应的#xff0c;那么接下来就开始刷题之旅吧~ 1-8题见LeetCode-hot100题解—Day1 9-16题见LeetCode-hot100题解—Day2 17-24题见LeetCode-hot…原题链接力扣热题-HOT100 我把刷题的顺序调整了一下所以可以根据题号进行参考题号和力扣上时对应的那么接下来就开始刷题之旅吧~ 1-8题见LeetCode-hot100题解—Day1 9-16题见LeetCode-hot100题解—Day2 17-24题见LeetCode-hot100题解—Day3 25-34题见LeetCode-hot100题解—Day4 39-56题见LeetCode-hot100题解—Day5 注需要补充的是如果对于每题的思路不是很理解可以点击链接查看视频讲解是我在B站发现的一个宝藏UP主视频讲解很清晰UP主用的是C可以结合视频参考本文的java代码。 力扣hot100题解 62-71 62.不同路径63.不同路径Ⅱ64.最小路径和66.加一67.二进制求和69.x的平方根70.爬楼梯71.简化路径 62.不同路径
思路 本题采用动态规划来求解最后需要得到的时候到达网格右下角的路径的数量设f(i,j)是到达f[i][j]的路径数量由于每次只能向下或者向右移动所以可以用f(i,j)f(i-1,j)f(i,j-1)来计算路径数量其中f(i-1,j)是指到f[i][j]上一格的数量f(i,j-1)是指到达f[i][j]左边一格的路径数量那么动态方程为f(i,j)f(i-1,j)f(i,j-1)最后返回f(m-1,n-1)的值即为所求详细的视频讲解点击视频讲解-不同路径。 时间复杂度 由于要对整个二维数组进行遍历计算所以时间复杂度为O(mn)需要开辟一个二维数组来存储对应格子的路径数所以空间复杂度也为O(mn)。 代码实现
class Solution {public int uniquePaths(int m, int n) {int[][] f new int[m][n];for(int[] item : f){Arrays.fill(item,1);}for(int i 1; i m; i){for(int j 1;j n;j){f[i][j] f[i - 1][j] f[i][j - 1];}}return f[m-1][n-1];}
}知识点扩展 对数组元素进行初始化设置可以使用以下函数需要注意的是是的Arrays.fill(nums,x)方法只能用于一维数组。该方法用指定的值填充整个数组对于多维数组每个维度需要分别使用fill方法进行填充。
//将nums数组的元素初始化为x
Arrays.fill(nums,x)63.不同路径Ⅱ
思路 本题是62题的加强版思路基本一样都用到了动态规划的方法唯一不同的是本题中多了一个障碍物的限制有障碍物的网格是不能经过的所以我们只要加一个判断条件如果某个网格有障碍物则将这个网格的可到达路径设置为0即可需要注意的是本题不能将记录路径数的二维数组初始化值为1而应该是062题中第一行(i0)和第一列(j0)因为只能向右和向下走才能到达所以将其初始值设置为1在后续的遍历中就可以直接从i1和j1开始遍历数组但是本题中第一行和第一列可能会出现障碍物所以也要统一处理遍历时也需要从0开始同时为了保证第一行和第一列没有障碍物时可能正确的记录其可到达的路径数量需要将其实位置的路径数置为1视频讲解点击视频讲解-不同路径Ⅱ。 时间复杂度 时间复杂度和空间复杂度同62题均为O(mn)。 代码实现
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m obstacleGrid.length;int n obstacleGrid[0].length;int[][] f new int[m][n];for(int i 0; i m; i){for(int j 0; j n; j){//判断是否有障碍物有则直接跳过if(obstacleGrid[i][j] 1) continue;//将f[0][0] 1方便对第一行和第一列的路径数的计算if(i 0 j 0) f[i][j] 1;else{//i0时 路径数等于到达上面格子的路径数f[i][j]if(i 0) f[i][j] f[i - 1][j];//j0时 路径数等于到达左边格子的路径数f[i][j]if(j 0) f[i][j] f[i][j - 1];}}}return f[m - 1][n - 1];}
}64.最小路径和
思路 本题采用动态规划的方法来解决设f(i,j)表示从(0,0)到(i,j)的路径和由于每次只能向右或者向下走所以可以得到以下的两个动态方程
//从上面格子向下走
f[i][j] f[i - 1][j] grid[i][j]
//从左边格子向右走
f[i][j] f[i][j - 1] grid[i][j]要得到最小路径和所以两种走法中取最小值即可所以最终的动态方程为
f[i][j] Math.min(f[i - 1][j],f[i][j - 1]) grid[i][j]注意最后在代码中不要直接使用该动态方程因为要分别处理i和j为0的情况视频讲解点击视频讲解-最小路径和。 时间复杂度 由于要遍历二维数组得到每一格的路径和所以时间复杂度为O(mn)开辟一个二维数组来记录每一格的路径和所以空间复杂度为O(mn)。 代码实现
class Solution {public int minPathSum(int[][] grid) {int m grid.length;int n grid[0].length;int[][] f new int[m][n];//初始化为最大值for(int[] item : f){Arrays.fill(item,Integer.MAX_VALUE);}for(int i 0;i m;i){for(int j 0;j n;j){//(0,0)处的值为网格的值特判处理if(i 0 j 0) f[i][j] grid[i][j];else{//处理j为0即第一列的情况if(i 0) f[i][j] Math.min(f[i][j],f[i - 1][j] grid[i][j]);//处理i为0即第一行的情况if(j 0) f[i][j] Math.min(f[i][j],f[i][j - 1] grid[i][j]);}}}return f[m - 1][n - 1];}
}66.加一
思路 本题需要对数组元素组成的数字进行加一操作重点在于加法操作中对进位的处理可以分为两种情形
当数组最后一个元素小于时最后一个元素直接加一然后直接返回数组即可。当数组最后一个元素大于时需要考虑到进位将数组最后一个元素置为进位然后继续对倒数第二个元素进行加一处理依次类推。这里需要对数组元素全是做特判处理需要在结果数组的开头插入元素1。
视频讲解点击视频讲解加一。 时间复杂度 这个算法的时间复杂度为O(n)其中n是输入数组digits的长度。在大多数情况下算法只需遍历一次数组因此时间复杂度为O(n)。但在最坏情况下需要创建一个新的数组并将所有元素复制到新数组中此时时间复杂度为O(n1)即O(n)。因此可以将算法的时间复杂度简化为O(n)。 代码实现
class Solution {public int[] plusOne(int[] digits) {for(int i digits.length - 1 ;i 0; i--){if(digits[i] 9){digits[i];break;}else{digits[i] 0;if(i 0){int[] newdigits new int[digits.length 1];newdigits[0] 1;for(int j 1; j digits.length 1 ;j){newdigits[j] digits[j - 1];}digits newdigits;}}}return digits;}
}67.二进制求和
思路 本题直接对二进制进行求和使用StringBuilder来构建结果字符串关于StringBuilder的使用下面的知识拓展中做了总结之前系列文章中也有简单介绍LeetCode-hot100题解—Day3中 17.电话号码的字母组合因为要动态的往结果数组里添加元素所以不建议直接使用String并使用carry变量来记录进位。从字符串的末尾开始逐位相加并将结果插入到StringBuilder的开头。代码中将a和b两个字符串中对应位置的元素全部加到carry中最后使用carry得到结果carry更新carry的值。视频讲解点击视频讲解二进制求和其中有详细的模拟演示。 时间复杂度 该方法的时间复杂度为O(max(,))其中和分别是字符串a和b的长度。在最坏情况下需要遍历较长的字符串并执行常数时间操作。所以时间复杂度可以看成O(n)。 代码实现
class Solution {public String addBinary(String a, String b) {StringBuilder ans new StringBuilder();int carry 0;int i a.length() - 1;int j b.length() - 1;while(i 0 || j 0 || carry 0){if(i 0){carry a.charAt(i) - 0;i--;} if(j 0){carry b.charAt(j) - 0;j--;} ans.insert(0,carry % 2);carry / 2;}return ans.toString();}
}知识拓展 以下总结了StringBuilder的一些基本用法需要注意的是StringBuilder是线程不安全的如果需要在多线程环境中使用应该考虑使用StringBuffer类。
//1.创建StringBuilder对象
//创建一个空的StringBuilder对象
StringBuilder s new StringBuilder();
//创建一个包含初始字符串的StringBuilder对象
StringBuilder s new StringBuilder(Hello);
//创建一个初始容量为100的StringBuilder对象
StringBuilder s new StringBuilder(100);//2.添加字符串或字符
//添加字符串
s.append(World)
//添加空字符串
s.append( );
//添加一个字符
s.append(!);//3.插入字符串或字符
//在索引5处插入字符串world
s.insert(5,world);
//在索引0处插入字符!
s.insert(0,!);//4.删除字符或字符串
//删除索引5到10之间的字符包括索引为5的字符不包括索引为10的字符左闭右开
s.delete(5,10);
//删除索引0处的字符
s.deleteCharAt(0);//5.替换字符串或字符
//替换索引5到10之间的字符为nihao
s.replace(5,10,nihao);
//替换索引0处的字符为N
s.replace(0,1,N);//6.获取字符串
//将StringBuilder对象转换为字符串
String str s.toString();69.x的平方根
思考 由于题目不允许使用任何内置指数函数和算符所以采用二分查找来解决该问题。首先定义左右边界计算中点mid的平方值如果该值小于等于x值则说明x的平方根在mid的右侧此时更新左边界l的值为mid因为mid的值也可能是结果如果该值大于x则说明x的平方根在mid的左侧此时更是右边界r的值为mid-1mid的平方值大于x所以mid肯定不是所求的结果最后循环结束返回l和r任意一个即为所求视频讲解点击视频讲解-x的平方根。 时间复杂度 使用二分查找时间复杂度为O(logn)。 代码实现
class Solution {public int mySqrt(int x) {int l 0;int r x;while(l r){int mid l (r - l) / 2 1;if((long)mid * mid x) l mid;else r mid - 1; }return l;}
}70.爬楼梯
思路 本题采用动态规划来解决假设f(i)表示爬到i阶的方法数那么f(1) 1第1阶爬1阶到达有一种方法f(2)2第2阶可以可以从1阶爬到2阶也可以直接爬2阶到2所以有两种方法由于一次可以爬1阶或2阶所以动态方程为f(i)f(i-1)f(i-2)其中f(i-1)表示爬到i-1阶的方法数爬到i需要爬1阶可以到达i阶f(i-2)表示爬到i-2阶的方法数爬到i阶需要爬2阶可以到达i阶两者加起来即为爬到i阶的方法数视频讲解点击视频讲解-爬楼梯。 时间复杂度 时间复杂度为O(n)由于开辟了一个数组来保存爬到每一阶的方法数空间复杂度为O(n)。 代码实现
class Solution {public int climbStairs(int n) {//数组大小设置为n2防止溢出int[] f new int[n 2];f[1] 1;f[2] 2;for(int i 3;i n;i){f[i] f[i - 1] f[i - 2];}return f[n];}
}71.简化路径
思路 根据题意可知当在路径中遇到.时表明当前目录不做处理当在路径中遇到..时表明上级目录需要返回上级目录所以可以将path中的目录全部压入栈中当遇到..时弹出栈顶元素即回到上一级目录,最后在遍历完path后将栈中的元素逆序拼接输出即可如果栈为空直接返回根目录/视频讲解点击视频讲解-简化路径。关于java中Stack的使用在之前系列文章LeetCode-hot100题解—Day3 20.有效的括号中总结过如果需要可以去复习一下。 时间复杂度 时间复杂度是O(n)其中n是路径字符串path的长度只对path进行了一次遍历。 代码实现
class Solution {public String simplifyPath(String path) {StackString stk new Stack();String[] items path.split(/);for(String item : items){if(item.equals(..)){if(!stk.isEmpty()){stk.pop();}}else if(!item.equals(.) !item.equals()){stk.push(item);}}StringBuilder ans new StringBuilder();while(!stk.isEmpty()){ans.insert(0,/stk.pop());}//如果栈为空直接返回根目录/return ans.length() 0 ? / : ans.toString();}
}知识拓展 equals和的使用 使用运算符判断两个对象是否相等时它实际上比较的是两个对象的引用地址而不是它们的值也就是说它检查的是两个对象是否指向相同的内存位置。 而使用equals()方法可以比较两个对象的值是否相等equals() 不能用于判断基本数据类型的变量只能用来判断两个对象是否相等。在Java中equals()方法是Object类的方法所有的类都继承了它。默认情况下equals()方法与运算符的行为相同比较的是两个对象的引用地址。 但是很多类会覆盖equals()方法以便根据对象的内容来判断它们是否相等。例如在字符串类(String)中String 中的 equals 方法是被重写过的equals()方法比较的是字符串的内容也就是对象的值而不是引用地址。 因此如果你想比较两个对象的值是否相等应该使用equals()方法而不是运算符。
