给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。
class Solution {
public:
string multiply(string num1, string num2) {
//参考做法，由个位开始计算相加,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;
}
};
给定一个 没有重复数字的序列，返回其所有可能的全排列。
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表示正在访问的节点序号，n表示已访问节点个数
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();
}
}
};
给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
//动态规划：[i]结尾的最大连续子数组和=max(以[i-1]数字结尾的的连续子数组和+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;
}
};
