1.只出现1次的数字
给你一个 非空 整数数组 nums
,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
方法:异或
class Solution {
public:int singleNumber(vector<int>& nums) {int val=0;for(auto e:nums){val^=e;}return val;}
};
2.杨辉三角
给定一个非负整数 numRows
,生成「杨辉三角」的前 numRows
行。
如果是C语言
int** generate(int numRows, int* returnSize, int** returnColumnSizes)
行数 每一行的数据个数
int** pp=(int*)malloc(sizeof(int*)*10;
for(int i=0;i<10;++i)
{pp[i]=(int*)malloc(sizeof(int)*(i+1);
}
pp[i][j] 两个指针的解引用
C++实现:
vector<vector<int>> generate(int numRows)
要想访问第i个第j列
vector<vector<int>> vv;vv[i][j] 是两个方括号的调用
vv[i]返回值是vector<int>对象 在加[]就是第j个位置的数据
解答:
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> vv;vv.resize(numRows);//用resize因为要初始化一下for (size_t i = 0; i < vv.size(); i++) {vv[i].resize(i+1,0);//每一行开i+1个空间vv[i][0]=vv[i][vv[i].size()-1]=1;//这一行头和为为1}for(size_t i=0;i<vv.size();i++){for (size_t j=0;j<vv[i].size();j++){if(vv[i][j]==0){vv[i][j]=vv[i-1][j]+vv[i-1][j-1];} }}return vv;}
};
3.电话号码的字母组合
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
是一个全排列和深度优先遍历,本质就是一个多叉树的遍历
class Solution {const char* numStrArr[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:void Combine(const string& digits,int i,vector<string>& ret,string combineStr)//const &拷贝代价大{if(i==digits.size()){ret.push_back(combineStr);return;}int num=digits[i]-'0';string str=numStrArr[num];for(auto ch:str) //依次取str里面字符{Combine(digits,i+1,ret,combineStr+ch);}}vector<string> letterCombinations(const string& digits) {vector<string> v;if(digits.empty())return v;string str;//组合出来的字符串Combine(digits,0,v,str);return v;}
};
digits就是数字串“258”