优化网站用软件好吗,wordpress更改文件夹,建设工程施工合同和承揽合同区别,有没有专业做淘宝网站吗文章目录 前言一、只出现一次的数字二、只出现一次的数字 II三、只出现一次的数字 III四、杨辉三角五、删除有序数组中的重复项六、数组中出现次数超过一半的数字七、电话号码的字母组合总结 前言
今天我们一起来看vector相关的题目~ 一、只出现一次的数字
只出现一次的数字… 文章目录 前言一、只出现一次的数字二、只出现一次的数字 II三、只出现一次的数字 III四、杨辉三角五、删除有序数组中的重复项六、数组中出现次数超过一半的数字七、电话号码的字母组合总结 前言
今天我们一起来看vector相关的题目~ 一、只出现一次的数字
只出现一次的数字
经典的单身狗问题不断异或就好啦~ 可以使用 位运算中的异或操作 来解决这个问题。异或操作有几个重要的性质
任意数与 0 异或的结果是它本身即 a ^ 0 a。任意数与它自己异或的结果是 0即 a ^ a 0。异或满足交换律和结合律即 a ^ b ^ a a ^ a ^ b b。
利用这些性质我们可以将数组中所有的数字进行一次异或运算相同的数字异或后会抵消为 0最终剩下的就是只出现一次的那个数字。 class Solution {
public:int singleNumber(vectorint nums) {int value 0;for(auto e : nums){value ^ e;}return value;}
};二、只出现一次的数字 II
只出现一次的数字 II ones 记录那些位在某一时刻出现了 一次 的状态。 twos 记录那些位在某一时刻出现了 两次 的状态。 ones ^ num对 ones 和当前数字 num 进行异或操作更新 ones 的状态。 如果 ones 中某个位是 0而 num 中该位是 1则该位变为 1表示该位出现了一次。如果 ones 中某个位是 1而 num 中该位也是 1则该位变为 0表示该位出现了两次此时我们需要把该位交给 twos 追踪。 ~twos这是最关键的一步。 这一步的目的是清除 ones 中那些已经出现在 twos 中的位即某个位已经出现了 两次因为这些位不再属于“只出现一次”的范围。~twos 的作用是对 twos 中的位进行按位取反~ 是按位取反操作这样 twos 中原本是 1 的位就变成了 0原本是 0 的位就变成了 1。然后将 ones 与 ~twos 进行按位 与操作确保那些在 twos 中为 1 的位在 ones 中被清除掉。具体说 如果 twos 中某个位是 1表示该位已经出现了两次那么 ~twos 中对应位为 0与 ones 进行按位与时这个位在 ones 中会被清零清除这位。如果 twos 中某个位是 0那么 ~twos 中对应位为 1此时 ones 中该位的状态保持不变。 twos (twos ^ num) ~ones twos ^ num对 twos 和当前数字 num 进行异或操作更新 twos 的状态。 ~ones这一步与 ~twos 类似作用是清除 twos 中那些已经出现在 ones 中的位即只出现一次的位。 ~twos 确保 ones 中只记录那些出现 一次 的位将出现两次的位从 ones 中清除。 ~ones 确保 twos 中只记录那些出现 两次 的位将只出现一次的位从 twos 中清除。 class Solution {
public:int singleNumber(vectorint nums) {int ones 0, twos 0;for(auto e : nums){ones (ones^e) ~twos;twos (twos^e) ~ones;} return ones;}
};三、只出现一次的数字 III
只出现一次的数字 III class Solution {
public:vectorint singleNumber(vectorint nums) {int xorsum 0;for (int num: nums) {xorsum ^ num;}// 防止溢出int lsb (xorsum INT_MIN ? xorsum : xorsum (-xorsum));int type1 0, type2 0;for (int num: nums) {if (num lsb) {type1 ^ num;}else {type2 ^ num;}}return {type1, type2};}
}; 四、杨辉三角
杨辉三角
这段代码是C语言的风格用到了二级指针而且开空间很不方便
这段代码是Cvector的风格vector不用我们手动开辟空间调用接口既可以达到开空间的效果。
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv(numRows);for(int i 0; i numRows; i){vv[i].resize(i 1, 1);}for(int i 0; i numRows; i){for(int j 1; j vv[i].size() - 1; j){vv[i][j] vv[i - 1][j] vv[i - 1][j - 1];}}return vv;}
};五、删除有序数组中的重复项
删除有序数组中的重复项
属于双指针的思想~ 前面有讲解 int removeDuplicates(int* nums, int numsSize) {if(numsSize 1){return 1;}int k 1;int slow 0;int fast 0;for(int i 0; inumsSize; i){if(nums[slow] nums[fast]){fast;}else{nums[k] nums[fast];slow fast;fast;k;}}return k;
}六、数组中出现次数超过一半的数字
数组中出现次数超过一半的数字
这个直接排序中间的数就是出现超过一半的数~
class Solution {
public:int MoreThanHalfNum_Solution(vectorint numbers) {sort(numbers.begin(), numbers.end());int cond numbers[numbers.size() / 2];return cond;}
};七、电话号码的字母组合
电话号码的字母组合 代码讲解
1. 映射部分 (strA 数组): strA 数组用于存储数字到字母的映射关系模拟了手机按键的布局
strA[2] abc 表示数字 2 对应的字母为 “abc”。strA[3] def 表示数字 3 对应 “def”依此类推。
这个映射数组中的索引值对应于按键上的数字数字从 2 到 9 各自映射到一组不同的字母。而数字 0 和 1 对应空字符串因为题目中 1 不映射到任何字母。
2. 递归组合部分 (Combine 函数): 该函数通过递归的方式生成所有可能的字母组合。
level 参数表示当前递归的层级即当前处理的数字索引。combine_str 是当前已组合好的字符串。
递归的步骤如下
如果当前 level 等于 digits 的长度说明已经处理完所有的数字将当前生成的组合字符串 combine_str 添加到 ansA 结果集中。取出当前数字digits[level]对应的字母通过 strA 获取并依次与前面已经组合好的字符串拼接。通过递归调用将处理移动到下一个数字直到组合出所有可能的字母排列。
这个地方其实是一个全排列
这里递归调用展开图是这样的 递归遍历通过层层递进的方式依次处理每个数字对应的字母将当前构造的组合传递到下一层直到所有数字都处理完为止。在每次递归中当前数字的每个字母都与之前的组合拼接递归到最深处时完成一组字母组合并添加到结果中。
class Solution {
public://数字与字母间的映射string strA[10] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};//返回所有组合void Combine(int level, string digits, string combine_str, vectorstring ansA){if(level digits.size()){ansA.push_back(combine_str);return;}int nums digits[level] - 0;string str strA[nums];for(int i 0; i str.size(); i){Combine(level 1, digits, combine_str str[i], ansA);}}vectorstring letterCombinations(string digits) {vectorstring ansA;if(digits.empty())return ansA;Combine(0, digits, , ansA);return ansA;}
};总结
谢谢大家~
