108. 将有序数组转换为二叉搜索树
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return f(nums,0,nums.size()-1);
}
TreeNode* f(vector<int>& vec,int l,int r)
{
if(l>r) return nullptr;
int mid=(l+r)/2;
TreeNode* root=new TreeNode(vec[mid]);
root->left= f(vec,l,mid-1);
root->right= f(vec,mid+1,r);
return root;
}
};
111. 二叉树的最小深度
dfs:
class Solution {
public:
int ans=0;
int minDepth(TreeNode* root) {
if(root==nullptr) return 0;
int left=minDepth(root->left); //计算左子树深度
int right=minDepth(root->right); //计算右子树深度
if(left!=0&&right!=0) return min(left,right)+1; //如果都存在则不是叶子结点,深度为最小值+1
return left+right+1; //否则为存在的那个节点深度+1
}
};
bfs:
class Solution {
public:
int ans=0;
queue<pair<TreeNode*,int>> q;
int minDepth(TreeNode* root) {
if(root==nullptr) return 0;
return bfs(root);
}
int bfs(TreeNode*root)
{
q.push({root,1});
while(!q.empty())
{
auto t=q.front();
q.pop();
if(t.first->left!=nullptr)
{
q.push({t.first->left,t.second+1});
}
if(t.first->right!=nullptr)
{
q.push({t.first->right,t.second+1});
}
if(t.first->left==nullptr&&t.first->right==nullptr)
{
return t.second;
}
}
return -1;
}
};
37. 解数独
class Solution {
public:
bool row[10][10],col[10][10],rec[4][4][10];
int n=0;
bool f;
bool dfs(int x,int y,vector<vector<char>>& board) //返回值为bool类型,如果遍历完,则直接返回true,无需回溯
{
if(x==9&&y==0) //遍历完全部格子
{
return true;
}
if(board[x][y]!='.')
{
if(y==8) return dfs(x+1,0,board);
else return dfs(x,y+1,board);
}
for(int i=1;i<=9;i++)
{
if(row[x][i]||col[y][i]||rec[x/3][y/3][i]) continue;
row[x][i]=col[y][i]=rec[x/3][y/3][i]=true;
board[x][y]=i+'0';
if(y==8) f=dfs(x+1,0,board);
else f=dfs(x,y+1,board);
if(f) return true;
row[x][i]=col[y][i]=rec[x/3][y/3][i]=false;
board[x][y]='.';
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(board[i][j]!='.')
{
char c=board[i][j];
row[i][c-'0']=true;
col[j][c-'0']=true;
rec[i/3][j/3][c-'0']=true;
}
}
}
dfs(0,0,board);
}
};
165. 比较版本号
class Solution {
public:
int compareVersion(string version1, string version2) {
int i=0,j=0;
while(i<version1.size()||j<version2.size())
{
long long x=0,y=0;
for(;i<version1.size();i++)
{
if(version1[i]=='.') break;
x=x*10+version1[i]-'0';
}
i++;
for(;j<version2.size();j++)
{
if(version2[j]=='.') break;
y=y*10+version2[j]-'0';
}
j++;
if(x<y) return -1;
else if(x>y) return 1;
}
return 0;
}
};
470. 用 Rand7() 实现 Rand10()
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution {
public:
int rand10() {
int ans;
while(1)
{
int x=rand7();
int y=rand7();
ans=x+(y-1)*7;
if(ans>40) continue;
break;
}
return ans%10+1;
}
};
322. 零钱兑换
完全背包问题
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,0x3f3f3f3f);
dp[0]=0; //表示凑出0元钱的最小硬币个数是0
for(int i=0;i<coins.size();i++) //枚举物品
{
for(int j=coins[i];j<=amount;j++) //枚举体积
{
dp[j]=min(dp[j],dp[j-coins[i]]+1);
}
}
if(dp[amount]==0x3f3f3f3f) return -1;
return dp[amount];
}
};
518. 零钱兑换 II
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1);
dp[0]=1; //表示凑出0元钱的方案数为1(什么也不放)
for(int i=0;i<coins.size();i++)
{
for(int j=coins[i];j<=amount;j++)
{
dp[j]+=dp[j-coins[i]];
}
}
return dp[amount];
}
};
718. 最长重复子数组
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1));
int ans=0;
for(int i=1;i<=nums1.size();i++)
{
for(int j=1;j<=nums2.size();j++)
{
if(nums1[i-1]==nums2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
ans=max(ans,dp[i][j]);
}
}
}
return ans;
}
};
128. 最长连续序列
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> st; //去重+排序
if(nums.size()==0) return 0;
for(auto &i:nums) st.insert(i);
int maxl=1;
int l=1;
int pre=*st.begin();
for(auto ite=++st.begin();ite!=st.end();ite++)
{
if(*ite==pre+1) l++;
else
{
l=1;
}
maxl=max(maxl,l);
pre=*ite;
}
return maxl;
}
};
72. 编辑距离
class Solution {
public:
int minDistance(string word1, string word2) {
int dp[1000][1000];
for(int i=0;i<=word1.size();i++)
{
dp[i][0]=i; //用前i个字符串修改成空串,需要删除i次
}
for(int j=0;j<=word2.size();j++)
{
dp[0][j]=j; //用空串修改成前j个字符串,需要添加j次
}
for(int i=1;i<=word1.size();i++)
{
for(int j=1;j<=word2.size();j++)
{
dp[i][j]=dp[i-1][j-1];
if(word1[i-1]!=word2[j-1])
{
dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));//dp[i-1][j]+1 对应删除操作
//dp[i][j-1]+1对应添加操作
//dp[i-1][j-1]+1对应修改操作
}
}
}
return dp[word1.size()][word2.size()];
}
};
Q.E.D.