給定兩個(gè)以字符串形式表示的非負(fù)整數(shù)num1和num2，返回num1和num2的乘積，它們的乘積也表示為字符串形式。
class?Solution?{
public:
????string?multiply(string?num1,?string?num2)?{
????????//參考做法，由個(gè)位開(kāi)始計(jì)算相加,O(n2)
????????int?m=num1.length(),n=num2.length();
????????vector<int>res(m+n,0);
????????for(int?i=m-1;i>=0;i--)
????????{
????????????for(int?j=n-1;j>=0;j--)
????????????{
????????????????int?temp=res[i+j+1]+(int)(num1[i]-'0')*(num2[j]-'0');
????????????????res[i+j+1]=temp%10;
????????????????res[i+j]+=temp/10;
????????????}
????????}
????????string?s="";
????????int?st=0;
????????while(st<m+n&&res[st]==0)
????????{
????????????st++;
????????}
????????for(int?i=st;i<m+n;i++)
????????{
????????????s+=(res[i]+'0');
????????}
????????return?(s.length()==0)?"0":s;
????}
};
給定一個(gè) 沒(méi)有重復(fù)數(shù)字的序列，返回其所有可能的全排列。
class?Solution?{
public:
????vector<vector<int>>res;
????vector<int>path;
????vector<vector<int>>?permute(vector<int>&?nums)?{
????????vector<bool>used_i(nums.size(),false);
????????int?num=0;
????????dfs(nums,0,num,used_i);
????????return?res;
????}
????void?dfs(vector<int>&nums,int?s,int&?n,vector<bool>&used)
????{//s表示正在訪問(wèn)的節(jié)點(diǎn)序號(hào)，n表示已訪問(wèn)節(jié)點(diǎn)個(gè)數(shù)
????????if(n==nums.size()){
????????????res.push_back(path);
????????????return;
????????}
????????for(int?i=0;i<nums.size();i++)
????????{
????????????if(used[i])continue;
????????????used[i]=true;
????????????n++;
????????????path.push_back(nums[i]);
????????????dfs(nums,i+1,n,used);
????????????used[i]=false;
????????????n--;
????????????path.pop_back();
????????}
????}
};
給定一個(gè)整數(shù)數(shù)組nums，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
class?Solution?{
public:
????int?maxSubArray(vector<int>&?nums)?{
????????//動(dòng)態(tài)規(guī)劃：[i]結(jié)尾的最大連續(xù)子數(shù)組和=max(以[i-1]數(shù)字結(jié)尾的的連續(xù)子數(shù)組和+nums[i],nums[i])
????????int??sum=0,Maxsum=nums[0],n=nums.size();
????????for(int?i=0;i<n;i++)
????????{
???????????sum=(nums[i]>=nums[i]+sum)?nums[i]:nums[i]+sum;
???????????Maxsum=(Maxsum>=sum)?Maxsum:sum;???
????????}
????????return?Maxsum;
????}
};
