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.