西安建设手机网站,屯留做网站哪里好,wordpress漂亮轮播代码,怎么用网站推广杨辉三角
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台
给定一个非负整数 numRows#xff0c;生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中#xff0c;每个数是它左上方和右上方的数的和。 示例 1:
输入: numRows 5
输出: [[1],[1,1…杨辉三角
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 示例 1:
输入: numRows 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows 1
输出: [[1]] 知识点
这道题涉及的知识点有1. vector创建二维数组。 2. 杨辉三角的表示法。 vector如何创建数组 创建一维数组的方法 vectorint v(5); //创建5个int初始化成默认值0
vectorint v(5,1); //创建5个int初始化成1
vectorint v{1,2,3}; //创建3个int分别是123 创建二维数组的方法 vectorvectorint(5); //创建5行。 若想要定义列的大小用resize()
vectorvectorint(5,vectorint(4)); //创建5行4列初始化成默认值0
vectorvectorint(5,vectorint(4,9)); //创建5行4列初始化成默认值9 这道题的二维数组每行的大小都不一样的 大小我们用resize()去调整。 至于杨辉三角的表示法它的规律是每行的开头和末尾为1其他的数之间的关系 用找规律法可以得出v[i] [j]v[i-1] [j-1] v[i-1] [j] 解答
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint v(numRows); for(int i0;inumRows;i){v[i].resize(i1);v[i][0]v[i][i]1;for(int j1;ji;j){v[i][j]v[i-1][j-1]v[i-1][j];}}return v;}
}; 删除有序数组中的重复项
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过 更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 示例 1
输入nums [1,1,2]
输出2, nums [1,2,_]
解释函数应该返回新的长度 2 并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2
输入nums [0,0,1,1,1,2,2,3,3,4]
输出5, nums [0,1,2,3,4]
解释函数应该返回新的长度 5 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。 思路与实现
这道题我想到了两个思路。
思路一
设两个迭代器fast、slow。它们初始都指向nums的第一个元素。
fast一步一步地持续往前走slow暂时待在原地。每当fast指向的元素和slow指向的不一样就让slow加加把fast的值赋给slow。
class Solution {
public:int removeDuplicates(vectorint nums) {vectorint::iterator fastnums.begin(),slownums.begin();while(fast!nums.end()){if(*fast!*slow){slow;*slow*fast;}fast;}int kslow-nums.begin()1;nums.resize(k);return k;}
}; 思路二
把数组遍历一遍遇到和上一个相同的就删除。
class Solution {
public:int removeDuplicates(vectorint nums) {vectorint::iterator itnums.begin();while(it!nums.end()){if(it1!nums.end()){ //小心越界加个判断if(*it*(it1)){itnums.erase(it);}else{it;}}else{it;}}int knums.size();return k;}
}; 这个思路二挺容易写错的看看我之前的错误写法
class Solution {
public:int removeDuplicates(vectorint nums) {vectorint::iterator itnums.begin();while(it!nums.end()){if(it1!nums.end()){if(*it*(it1)){ //如果it没走这里的if条件那它也没法自增程序就陷入死循环了itnums.erase(it);}}else{it;}}int knums.size();return k;}
};
这样写的问题还是出在erase那边。之前我强调过erase因为会引起迭代器失效所以写法非常讲究。
正确的erase写法 要用if else语句并且要用迭代器去承接erase的返回值。
而这里我只写了if漏写了else。在else里it要加加。 错误记录
这样写为什么报错呢
class Solution {
public:int removeDuplicates(vectorint nums) {int sznums.size();int i0;while(isz){if(i0){if(nums[i]nums[i-1]){vectorint::iterator posnums.begin()i;posnums.erase(pos); //这里要考虑迭代器失效吗}else{i;}}else{i;} }int knums.size();return k;}
}; 原来是因为我循环里的erase操作会导致size()被修改sz的值失效了。 只出现一次的数字Ⅱ
力扣LeetCode官网 - 全球极客挚爱的技术成长平台
给你一个整数数组 nums 除某个元素仅出现 一次 外其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 示例 1
输入nums [2,2,3,2]
输出3
示例 2
输入nums [0,1,0,1,0,1,99]
输出99 思路
这道题乍一看长得像单身狗问题但实际并不能用异或的方法去做两个相同的值异或在一起为0而这里是三个相同的值。 思路一先排序再前后比较 这题其实可以借鉴刚刚那道“删除数组中的重复项”把乱序的数组排序使得大小相同的数字紧挨在一起当一个数和前后都不相同那这个数就只出现了一次。 class Solution {
public:int singleNumber(vectorint nums) {int sznums.size();//首先要考虑特殊情况if(sz1){return nums[0];}sort(nums.begin(),nums.end());for(int i0;isz;i){//先考虑第一个和最后一个这俩位置比较尴尬容易越界访问if(i0nums[i]!nums[i1]){return nums[i];}else if(isz-1nums[i]!nums[i-1]){return nums[i];}else if(nums[i]!nums[i1]nums[i]!nums[i-1]){return nums[i];}}return 0;}
}; 思路二位运算
先撇开那个只出现一次的数字不看我们就叫它A其他数字都是三个三个出现的。
此时将十进制的数字用二进制的视角来看的话32个比特位1出现的次数一定是3的倍数。
而加进来A以后我们将目光投到任意一个比特位上。如果A的这个比特位是0那1的次数依然是3的倍数如果是1那这个次数模3等于1。
也就是说我们可以通过1的次数 倒推出A的 其中一个比特位了设1出现x次x%30那A的这一位就是0x%3 1,这一位就是1。
A一共有32个比特位复刻这个方法可以推出A的每一个比特位A的值自然也就出来了。 class Solution {
public:int singleNumber(vectorint nums) {//一共32个比特位每一位的0、1值我们都要获知int ret0;for(int i0;i32;i){//统计1出现的次数nint n0;for(int num:nums){if((numi)11){n;}}if(n%31){ret|1i; //注意二进制的加法就用|} //刚刚右移了i位现在再左移回来}return ret;}
}; 小结
1.“去重”问题往往可以考虑先排个序。
2.按位或 相当于是二进制中的加法。
