做流程图表的网站,营销网站建设技术,国外好的做电视包装的网站,如何设计网站logo118. 杨辉三角 思路#xff1a;
杨辉三角有以下性质使我们要用到的#xff1a; ● 每行数字左右对称#xff0c;由 1 开始逐渐变大再变小#xff0c;并最终回到 1。 ● 第 n 行#xff08;从 0 开始编号#xff09;的数字有 n1 项#xff0c;前 n 行共有 2n(n1)个数。…118. 杨辉三角 思路
杨辉三角有以下性质使我们要用到的 ● 每行数字左右对称由 1 开始逐渐变大再变小并最终回到 1。 ● 第 n 行从 0 开始编号的数字有 n1 项前 n 行共有 2n(n1)个数。 ● 每个数字等于上一行的左右两个数字之和可用此性质写出整个杨辉三角。即第 n 行的第 i 个数等于第 n−1 行的第 i−1 个数和第 i 个数之和。 代码
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorint vv(numRows);// 二维数组for(int i 0;i numRows;i){vv[i].resize(i1,1);// 按行数缩减每一行个数并全部赋值为1}for(int a 2;a numRows ;a){for(int b 1;b a ;b){ // 每个数是左上方和右上方之和vv[a][b] vv[a-1][b] vv[a-1][b-1]; }}return vv;}
};
260. 只出现一次的数字 III 思路
1、相同数异或结果是0 假设数组 nums 中只出现一次的元素分别是 x1和 x2。如果把 nums 中的所有元素全部异或起来得到结果 x那么一定有x x1 ^ x2 。这是因为 nums 中出现两次的元素都会因为异或运算的性质 a ^ b ^ b a 抵消掉那么最终的结果就只剩下 x1和 x2的异或和。 2、区分两个单值数字到两个数组 在异或操作中只有当两个数字在某一位置上的二进制值不同结果的该位置才会是1。因此异或结果中为1的位表示了所有数字在该位上的差异。找到最后一个1的位可以帮助我们区分数组中只出现一次的数字。通过最后一个1的位我们可以将数组中的数字分成两组一组在该位上为1另一组在该位上为0。这两组数字在该位上的差异表明至少有一个只出现一次的数字在该位上与其他数字不同。 3、找出异或值最后一个二进制为1的位置 a (-a) 可以获得a最低的非0位但需要注意整形溢出可以用unsigned int 类型接收。 ▶ 例如 ● a的二进制原码是 0000 1010这里最低非0位是从右往左第2位。 ● -a在二进制中的表示是补码形式即先按位取反再加1取反得 1111 0101(反码)加1得 1111 0110(补码)。 ● 原码(0000 1010) 与 补码(1111 0110) 做与运算()得 0000 0010即原码 0000 1010的LSB最低有效位 ▶ 我们发现 ● 原码最低非0位右边所有的0经由取反后全部变为1反码1会导致这些1逐位发生进位并变为0最终进位记到最低非0位 ● 原最低非0位是1取反后是0进位到这一位0变成1不再向左进位 ● 原最低非0位左边的每一位经由取反后 和 原码 进行与运算必为0 4、处理这两个数组 对于提供的整数数组的其他数相同的数在所找到的mask位置的二进制数肯定是相同的所以会被分到同一个数组。分别对两个数组进行异或操作就能得到最终两个单值。 代码
class Solution {
public:vectorint singleNumber(vectorint nums) {//取反操作就会在无符号整数的范围内进行,//对-2,147,483,648 这个最小值取反时会超出了int类型能表示的范围unsigned int xornum 0;// 全部异或相同的数会被异或成0for (int n : nums) {xornum ^ n;}// mask掩码找出异或值最后一个二进制为1的数字 (重要位置)int mask xornum (-xornum);// 使用 vector 来存储结果vectorint res(2, 0); // 如果要用数组存储最后返回值要写改成vector //int res[2] {0, 0};...//return vectorint {res[0],res[1]};for (int n : nums) {if ((n mask) 0) {// 重要位置的数字是0放在数组中全部异或会剩下一个单值res[0] ^ n;} else {// 重要位置的数字是1放在数组中全部异或会剩下另一个单值res[1] ^ n;}}return res;}
};
137. 只出现一次的数字 II 思路 考虑数字的二进制形式对于出现三次的数字各二进制位出现的次数都是3的倍数。因此统计所有数字的各二进制位中1的出现次数并对3求余结果为出现一次的数字。 方法遍历统计 ● 使用与运算可获取二进制数字n的最右一位n1: n1 ni ● 配合右移操作可获取n的所有为的值n n 1 ● 建立一个32位的数组counts通过以上方法可记录所有数字的各二进制位的 1 的出现次数 int[] counts new int[32];
for(int i 0; i nums.length; i) {for(int j 0; j 32; j) {counts[j] nums[i] 1; // 更新第 j 位nums[i] 1; // 第 j 位 -- 第 j 1 位}
} ● 将counts各元素对3求余成三出现的数字在%3操作后没有余数则结果为“只出现一次的数字”的二进制位。 for(int i 0; i 32; i) {counts[i] % 3; // 得到 只出现一次的数字 的第 (31 - i) 位
} ● 利用左移操作和或运算可将counts数组中个二进制位的值恢复到数字res上。 for(int i 0; i counts.length; i) {res 1; // 左移 1 位res | counts[31 - i]; // 恢复第 i 位的值到 res
}
代码
class Solution {
public:int singleNumber(vectorint nums) {vectorint counts(32,0);for(int n : nums){for(int j 0;j 32 ; j){//n的最低位是0那么n1的结果是0//n的最低位是1那么n1的结果是1counts[j] n 1;//统计该位二进制数是1的个数// 是一个无符号右移操作符与有符号右移操作符 不同的是//无符号右移不考虑符号位无论 num 是正数还是负数左边空出的位都填充 0。n 1;//从右向左依次取二进制数}}//成三出现的数字在%3操作后没有余数只留下那个只出现一次的数字的二进制表示for(int i 0;i 32;i){counts[i] % 3;}int res 0;for(int i 0;i 32;i){//左移最右边空出的位会被填充为0无符号数或保持符号位的值有符号数res 1;res | counts[31 - i];//或运算比较的位中至少有一个为1则结果位为1// 这里是31 - i要注意二进制数存储的先后}return res;}
};26. 删除有序数组中的重复项 左右指针即可 代码
class Solution {
public:int removeDuplicates(vectorint nums) {if(nums.size() 0)return 0;int left 1,right 1;while(right nums.size()){if(nums[right] ! nums[right-1]){nums[left] nums[right];}right;}return left;}
};
JZ39 数组中出现次数超过一半的数字
数组中出现次数超过一半的数字_牛客题霸_牛客网 思路 用计数排序的思想numbers数组的值与counts数组下标相同时对counts[ ]进行计数最后将存储的计数与原数组长度的一半进行对比。 注意这里创建新数组要开辟动态的根据所给数组的最大值进行创建。 代码
#include algorithm
class Solution {
public:int MoreThanHalfNum_Solution(vectorint numbers) {if (numbers.empty()) return 0;//动态数组int maxnum 0;for(int m : numbers){// 找到数组中的最大值maxnum max(maxnum,m);}//初始化数组vectorint counts(maxnum 1,0);for(int i :numbers){// 计数counts[i];}for(int j 0; j counts.size();j){if(counts[j] numbers.size()/2){return j;}}return 0;}
};
17. 电话号码的字母组合666 思路 对于示例1我们利用树的形式表示出来但实现这个过程要用到递归的思想。 维护一个字符串表示已有的字母排列该字符串初始为空。每次取电话号码的一位数字从字符串数组中获得该数字对应的所有可能的字母并将其中的一个字母插入到已有的字母排列后面。即一个一个取第一个号码对应的字母并与另一个号码对应字母一个一个结合然后继续处理电话号码的后一位数字直到处理完电话号码中的所有数字。 代码
class Solution {string Number[10] {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; //深度优先遍历,递归实现,像树一样往深找void dfs(int i,int len, string digits,string path,vectorstring ans){if(i len){//直到找到所有组合ans.push_back(path);//两两组合后尾插到动态数组return;}for(auto e : Number[digits[i] - 0])//根据下标找到对应数字的字符串{path[i] e;dfs(i1,len,digits,path,ans);//注意这里是1不是用来维护一个字符串}}
public:vectorstring letterCombinations(string digits) {int len digits.length();if(len 0)return {};vectorstring ans;string path(len,0);dfs(0,len,digits,path,ans);return ans;}
}; 这一篇写了好久~ (ಥ﹏ಥ) (ಥ﹏ಥ) (ಥ﹏ಥ)
