在线教学网站开发,南昌网站设计企业,企业网络安全,常德尚一网#x1f49d;#x1f49d;#x1f49d;欢迎来到我的博客#xff0c;很高兴能够在这里和您见面#xff01;希望您在这里可以感受到一份轻松愉快的氛围#xff0c;不仅可以获得有趣的内容和知识#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小… 欢迎来到我的博客很高兴能够在这里和您见面希望您在这里可以感受到一份轻松愉快的氛围不仅可以获得有趣的内容和知识也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。 ✨✨ 欢迎订阅本专栏 ✨✨ 前言
本栏目将记录博主暑假从0开始刷力扣的算法题每一条题目我都会把知识点抽丝剥茧地进行分析以便大家更好的理解和学习话不多说肝 序号标题力扣序号1杨辉三角I1182杨辉三角II1193移动零2834区域和检索 -数组不可变3035第三大的数414 1.杨辉三角I 题目:
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 解题思路:
杨辉三角的性质: 每个位置上的数等于它上方两个数之和。
代码go
func generate(numRows int) [][]int {ans : make([][]int, numRows)for i : range ans {ans[i] make([]int, i1)ans[i][0] 1ans[i][i] 1for j : 1; j i; j {ans[i][j] ans[i-1][j] ans[i-1][j-1]}}return ans
} 下面是代码的具体解析 行初始化 ans[i] make([]int, i1) 创建一个长度为 i1 的数组用于存储第 i 行的元素。 边界处理 ans[i][0] 1第一个元素始终为1因为每行的开头和结尾都是1。ans[i][i] 1最后一个元素也为1因为杨辉三角每一行的首尾都是1。 中间元素计算 对于每一行的中间元素即 1 到 i-1 之间的元素通过上一行对应位置的元素相加得到。具体计算公式为 ans[i][j] ans[i-1][j-1] ans[i-1][j]。这里利用了杨辉三角的性质每个位置上的数等于它上方两个数之和。 返回结果 返回完成填充的二维数组 ans其中包含了从第0行到第 numRows-1 行的所有元素。 j 从 1 开始因为杨辉三角每一行的首尾元素都是 1不需要重新计算。 2.杨辉三角II
题目: 给定一个非负索引 rowIndex返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 方式一递推
解题思路:
杨辉三角的性质: 每个位置上的数等于它上方两个数之和。
此题和上面那道杨辉三角解法类似区别就是此题rowIndex是索引所以需要1 代码(go):
func getRow(rowIndex int) []int {C : make([][]int, rowIndex1)for i : range C {C[i] make([]int, i1)C[i][0], C[i][i] 1, 1for j : 1; j i; j {C[i][j] C[i-1][j-1] C[i-1][j]}}return C[rowIndex]
}
方式二:
利用滚动数组进行优化 解题思路:
注意到对第 i1 行的计算仅用到了第 i 行的数据因此可以使用滚动数组的思想优化空间复杂度。
优化后的代码只需要计算两行的杨辉三角即可可以节省内存空间 代码go
func getRow(rowIndex int) []int {var pre, cur []intfor i : 0; i rowIndex; i {cur make([]int, i1)cur[0], cur[i] 1, 1for j : 1; j i; j {cur[j] pre[j-1] pre[j]}pre cur}return pre
} 代码解析: pre前一行的数组。cur当前行的数组随着每一行的生成而更新。cur[j] pre[j-1] pre[j]根据杨辉三角的性质当前行的第 j 列的值等于上一行的第 j-1 列和第 j 列的和。pre cur将当前行 cur 赋给 pre作为下一行的基础。 方式三:
只用一个数组,进一步优化 解题思路:
我们使用一维数组然后从右向左遍历每个位置。
每个位置的元素res[j] 其左边的元素 res[j−1]。 row[j] row[j-1] 第0行只有1 第1行刚刚开始是1根据公式得出 11 第2行刚刚开始是11,根据公式111 --- 121 第3行刚刚开始是121根据公式121---1211---1231---1331 以此类推 为啥不从左向右遍历呢因为如果从左向右遍历那么左边的元素已经更新为第 i 行的元素了而右边的元素需要的是第 i−1 行的元素。故从左向右遍历会破坏元素的状态。 代码go
func getRow(rowIndex int) []int {row : make([]int, rowIndex1)row[0] 1for i : 1; i rowIndex; i {for j : i; j 0; j-- {row[j] row[j-1]}}return row
} 3.移动零 题目:
给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。
请注意 必须在不复制数组的情况下原地对数组进行操作。 示例 :
输入: nums [0,1,0,3,12]
输出: [1,3,12,0,0] 解题思路: 此题运用到双指针的思路设置两个指针a依次向右遍历b记录非零元素的位置当a遇到0则跳过继续向右遍历遇到非0的元素则交换ab的值并且b向右前进一步。 即遍历的时候每遇到一个 非0 元素就将其往数组左边挪第一次遍历完后b指针的下标就指向了最后一个 非0 元素下标。 第二次遍历的时候起始位置就从 b开始到结束将剩下的这段区域内的元素全部置为 0。 这个思路类似于快速排序可以去小破站看一下视频
快速排序 (图片出自王尼玛)
代码(java)
class Solution {public void moveZeroes(int[] nums) {if(numsnull) {return;}//第一次遍历的时候j指针记录非0的个数只要是非0的统统都赋给nums[j]int j 0;for(int i0;inums.length;i) {if(nums[i]!0) {nums[j] nums[i];}}//非0元素统计完了剩下的都是0了//所以第二次遍历把末尾的元素都赋为0即可for(int ij;inums.length;i) {nums[i] 0;}}
} 这道题花费了我两小时的时间因为我先了解了快速排序的原理然后再学习了双指针的思想最后卡到的最简单自增自减运算符上... 注意:
for循环的设计就是先执行循环体内的代码然后再递增计数器
所以其实在 for(int i0;inums.length;i) 这段语句中 无论是i还是i都是可以运行的。
然后在 nums[j] nums[i]这段语句中其实j是先执行然后再修改值的。以第二次循环为例当i 1的时候遇到非0的元素所有i 和 j 要交换元素 所以就是 num[0] num[1] 然后j 变成1 4.区域和检索 -数组不可变
题目: 给定一个整数数组 nums处理以下类型的多个查询: 计算索引 left 和 right 包含 left 和 right之间的 nums 元素的 和 其中 left right 实现 NumArray 类 NumArray(int[] nums) 使用数组 nums 初始化对象int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 包含 left 和 right 两点也就是 nums[left] nums[left 1] ... nums[right] ) 示例
输入
[NumArray, sumRange, sumRange, sumRange]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出
[null, 1, -1, -3]
解题思路:
这里用到前缀和思想可以理解为高中学的数列 我们可以画一个sum[0]到sum[6]的数列以【2,5】为例此处的2,5是索引值
所以就是sum[6]-sum[2]
示例中的数组有6个元素假如要计算索引2到5之间的总和包含2到5,我们可以先计算索引为数组开始到5的总和减去数组开始到索引为2不能包含索引2 代码java
class NumArray {int[] sums;public NumArray(int[] nums) {int n nums.length;sums new int[n 1];for (int i 0; i n; i) {sums[i 1] sums[i] nums[i];}}public int sumRange(int i, int j) {return sums[j 1] - sums[i];}
} 5.第三大的数
题目:
给你一个非空数组返回此数组中 第三大的数 。如果不存在则返回数组中最大的数。 示例 1
输入[3, 2, 1]
输出1
解释第三大的数是 1 。
示例 2
输入[1, 2]
输出2
解释第三大的数不存在, 所以返回最大的数 2 。示例 3
输入[2, 2, 3, 1]
输出1
解释注意要求返回第三大的数是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数它们都排第二。在所有不同数字中排第三大的数为 1 。 方式一:
Set 去重 排序
解题思路:
先使用 Set 对重复元素进行去重然后对去重后的元素进行排序并返回第三大的元素。 代码Java
class Solution {public int thirdMax(int[] nums) {SetInteger set new HashSet();for (int x : nums) set.add(x);ListInteger list new ArrayList(set);Collections.sort(list);return list.size() 3 ? list.get(list.size() - 1) : list.get(list.size() - 3); }
} HashSet 基于 HashMap 来实现的是一个不允许有重复元素的集合。 // 创建 HashMap 对象 SitesHashMapInteger, String Sites new HashMapInteger, String();
ArrayList 类是一个可以动态修改的数组与普通数组的区别就是它是没有固定大小的限制我们可以添加或删除元素。
使用一个增强型for循环遍历数组nums将每个元素添加到set中。
for (int x : nums) set.add(x); 假如数组为【1,2,3】那么执行 return list.size() 3 ? list.get(list.size() - 1) : list.get(list.size() - 3);
这里的 list.size() - 3 实际上是 3 - 3 0而 list.get(0) 会返回列表中的第一个元素即 1。 方式二
有限变量 遍历 解题思路:大家可以参考一下宫水三叶的解析 经典的找数组次大值的做法是使用两个变量 a 和 b 分别存储遍历过程中的最大值和次大值。 假设当前遍历到的元素为 x当满足如下条件时考虑更新 a 或者 b: 当 xa 时说明最大值被更新同时原来的最大值沦为次大值。即有 ba;ax; 在条件 1 不满足且有xb 时此时可以根据是否有「严格次大值」的要求而决定是否要增加 xa 的条件 不要求为「严格次大值」直接使用 x 来更新 b即有 bx 当要求为「严格次大值」 此时需要满足 xa 的条件才能更新 b。 回到本题同理我们可以使用 a、b 和 c 三个变量来代指「最大值」、「严格次大值」和「严格第三大值」。 从前往后遍历 nums假设当前元素为 x对是否更新三者进行分情况讨论判断优先级从上往下 1. xa说明最大值被更新将原本的「最大值」和「次大值」往后顺延为「次大值」和「第三大值」并用 x 更新 a 2. xa 且 xb说明次大值被更新将原本的「次大值」往后顺延为「第三大值」并用 x 更新 b 3. xb 且 xc说明第三大值被更新使用 x 更新 c。 起始时我们希望使用一个足够小的数来初始化 a、b 和 c因此需要使用 long 来进行代替。 返回时通过判断第三大值是否为初始化时的负无穷来得知是否存在第三大值。 代码Java
class Solution {long INF (long)-1e18;public int thirdMax(int[] nums) {long a INF, b INF, c INF;for (int x : nums) {if (x a) {c b; b a; a x;} else if (x a x b) {c b; b x;} else if (x b x c) {c x;}}return c ! INF ? (int)c : (int)a;}
} ❤️❤️❤️小郑是普通学生水平如有纰漏欢迎各位大佬评论批评指正 如果觉得这篇文对你有帮助的话也请给个点赞、收藏下吧非常感谢!
