leetcode-cn | 动态规划

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]

       1
      / \
     2   3

输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

#最开始理解题目出错，以为是以此节点为根的树杈的最大值，看题很马虎了，感觉像是测试驱动的开发，以后还是自己想测试用例吧#

题目的关键点在于如果这个节点作为这条路径上深度最小的节点，那么它可以同时连接左右子节点，如果一个节点不是这条路径上深度最小的节点，那么它只能连接左子节点或右子节点或者不连接子节点。由于只需要返回最大值且使用递归方法，那么可以考虑将此节点的值赋值为只连接左节点或右节点的最小值，将同时连接左节点和子节点的情况与当前的最大值进行比较。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int max=INT_MIN;
        getMax(root,max);
        return max;
    }
    
    int getMax(TreeNode* node,int &max){
        if(node==NULL){
            return 0;
        }
        int left=getMax(node->left,max);
        int right=getMax(node->right,max);
        int temp=(node->val+right)>(node->val+left)?(node->val+right):(node->val+left);
        temp=temp>(node->val)?temp:(node->val);
        max=max>temp?max:temp;
        max=max>(node->val+right+left)?max:(node->val+left+right);
        node->val=temp;
        return node->val;
    }

};

至少有K个重复字符的最长子串

找到给定字符串（由小写字符组成）中的最长子串 T ，要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:

输入:
s = "aaabb", k = 3

输出:
3

最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2:

输入:
s = "ababbc", k = 2

输出:
5

最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

在解题时还是要依次判断每个子串是否满足条件，使用哈希表或者数组存储时，频繁的判断会导致超时（尤其是自己还用了函数调用，就更别说了），在看了其他人的解法，使用一个数来存储结果，初始化为0，每一位代表一个字母，0代表这个字母出现次数大于k，1则反之，最后如果这个数为0，那么则符合条件，否则不符合

class Solution {
public:
    int longestSubstring(string s, int k) {
        int ans=0;
        int n=s.size();
        for(int i=0;i<=n-k;i++){
            int m[26]={0};
            int point=0;   //用二进制的数记录数每一位（每个字母）是否满足条件
            int max_tail=i;
            for(int j=i;j<n;j++){
                int temp=s[j]-'a';
                m[temp]++;
                if(m[temp]<k)
                    point=point|(1<<temp);
                else
                    point=point&(~(1<<temp));
                if(point==0){
                    ans=max(ans,j-i+1);
                    max_tail=j;
                }
            }
            //i=max_tail;
            //不加这句的话也不会超时
        }
        return ans;
    }
    
};

最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是          [1, 2, 3, 4]。它的长度为 4。

题目难度：hard

看到有的解法使用了hashmap，时间换空间

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

这道题目和在路上立广告牌是一致的，考虑每个广告牌是立还是不立。

class Solution {
public:
    int rob(vector<int>& nums) {
        int dp[nums.size()+1];
        if(nums.size()<=0) return 0;
        dp[0]=0;
        dp[1]=nums[0];
        int res=max(dp[0],dp[1]);
        for(int i=1;i<nums.size();i++){
            int index=i+1;
            dp[index]=max(dp[index-1],dp[index-2]+nums[i]);
            res=max(res,dp[index]);
        }
        return res;
    }
};

完全平方数

给定正整数 n，找到若干个完全平方数（比如

1, 4, 9, 16, ...

）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n =          12                
输出: 3 
解释:          12 = 4 + 4 + 4.

示例 2:

输入: n =          13                
输出: 2
解释:          13 = 4 + 9.

转化为完全背包求解。

class Solution {
public:
int numSquares(int n){
	int list[101];
	for(int i=0;i<101;i++){
		list[i]=i*i;  //物品的重量 
	}
	int dp[n+1];
	for(int i=0;i<=n;i++){
		dp[i]=9999999;
	}
	dp[0]=0;
	dp[1]=1;
	for(int i=1;i<=100;i++){
		for(int j=list[i];j<=n;j++){
			dp[j]=min(dp[j],dp[j-list[i]]+1);
		}
	}
	return dp[n];
}
};

最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入:          [10,9,2,5,3,7,101,18]
                输出: 4 
解释: 最长的上升子序列是          [2,3,7,101]，                它的长度是          4                。

说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解法一：动态规划，时间复杂度O(n^2)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0) return 0;
        else if(nums.size()==1) return 1;
        vector<int> dp(nums.size());
        dp[0]=1;
        int res=1;
        for(int i=1;i<nums.size();i++){
            int temp=1;
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    temp=max(temp,dp[j]+1);
                }
            }
            dp[i]=temp;
            res=max(res,dp[i]);
        }
        return res;
    }
};

解法二：贪心算法+二分

维护一个临时数组，用来存储当前的最大上升子序列，遇到一个新的数字的时候，替换临时数组中稍稍比他大的那个数。

之前在这里看到这个解法的有两个疑惑：

一个是将序列用临时数组存储的时候，如果用后面的替换前面的数，不会导致最终的序列长度增加吗？对于这个问题只是有模糊的理解：这里仅仅是替换对应的位置，在替换的时候临时数组中的数并没有改变，而对于之后的数的处理情况不会因为替换而发生变化。

二是既然只是要维护最大上升子序列，那么就替换最后一个字符就好了啊，为什么还要去替换前面的？因为替换最后一个字符的时候不仅要求比最后一个字符大，还要求比倒数第二个字符大。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size()==0) return 0;
        else if(nums.size()==1) return 1;
        vector<int> temp;
        temp.push_back(nums[0]);
        for(int i=1;i<nums.size();i++){
            int len=temp.size()-1;
            if(nums[i]>temp[len]) temp.push_back(nums[i]);
            else if(nums[i]<temp[len]){
                //替换比nums[i]小的最大的数
                int begin=0;
                int end=len;
                while(begin<=end){
                    int mid=begin+(end-begin)/2;
                    if(nums[i]==temp[mid]){
                        begin=end=mid;
                        break;
                    }
                    else if(nums[i]<temp[mid]){
                        end=mid-1;
                    } 
                    else{
                        begin=mid+1;
                    }
                }
                temp[begin]=nums[i];
            }
        }
        return temp.size();
    }
};

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回

-1

。

示例 1:

输入: coins =          [1, 2, 5]                , amount =          11                
输出:          3                 
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins =          [2]                , amount =          3                
输出: -1

说明:

你可以认为每种硬币的数量是无限的。

此问题为完全背包问题。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //多重背包
        vector<int> dp(amount+1);  //dp[i]表示值为i的时候，最少的硬币数量
        for(int i=0;i<dp.size();i++){
            dp[i]=amount+1;
        }
        dp[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]<=amount) return dp[amount];
        else return -1;
        
    }
};

dp[ j ]表示书包容量为 j 时，书包中物品的最大价值为多少

矩阵中的最长递增路径

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为          [1, 2, 6, 9]                。

示例 2:

输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是          [3, 4, 5, 6]                。注意不允许在对角线方向上移动。

初次看到这道题目的第一反应是动态规划（因为也出现在动态规划专题里），但是用动态规划又似乎有些不合适，走到当前点的最长路径长度可以由上下左右分别递推而来，但是遍历是要按照一定的顺序进行更新的，那么在更新一个点的时候，它的孩子们就一定还没有被更新，多遍历几遍，从不同的方向遍历似乎是比只遍历依次要靠谱点，但是还是有点奇怪，代码写好之后果不其然，没有成功。

在看了其他人的代码之后了解到，涉及到了另外一个概念 —— 记忆化搜索

class Solution {
public:
    int n, m;
    vector<vector<int>> f, g;
    int next[4][2]={1,0,-1,0,0,-1,0,1};
    int dp(int x, int y)
    {
        if (f[x][y] != -1) return f[x][y];//记忆话搜索的的核心，搜过就标记，避免重复搜索。
        f[x][y] = 1;//注意这里要初始化为1
        for (int i = 0; i < 4; i ++ )
        {
            int a=x+next[i][0];
            int b=y+next[i][1];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] < g[x][y])
                f[x][y] = max(f[x][y], dp(a, b) + 1);
        }
        return f[x][y];
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        g = matrix;
        n = g.size(), m = g[0].size();
        f = vector<vector<int>>(n, vector<int>(m, -1));
        int res = 1;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                res = max(res, dp(i, j));
        return res;
    }
};

题目解法为将dp数组换为递归函数，使用数组进行标记，如果已经处理过的话，那么就相当于是dp数组，如果这个点没有被处理过，那么将dp函数当做dp数组不断递归获取值。

此时参考另一个博客：https://blog.csdn.net/qq_41289920/article/details/80691537

能用dp的都能用ms
使用动态规划时，要使用的值一定已经确定的，不能再更新的（完成值）
记忆化搜索=搜索的形式+动态规划的思想

leetcode-cn | 动态规划

至少有K个重复字符的最长子串

最长连续序列

打家劫舍

完全平方数

最长上升子序列

零钱兑换

矩阵中的最长递增路径

继续阅读

【leetcode】32.longest-valid-parentheses（最长有效括号）【leetcode】32.longest-valid-parentheses（最长有效括号）

力扣每日一题：65. 有效数字题目：65. 有效数字解题思路

<LeetCode>三道脑筋急转弯编程题

求水洼的问题——深度优先算法

200. 岛屿的个数（深度优先搜索）

dfs深度优先搜索_图的深度优先搜索（DFS）

【算法提高班】贪婪策略

#每日一题力扣第28题采购方案

【python】：布尔运算

对角线遍历LeetCode–对角线遍历

查找算法之二分查找查找算法之二分查找

LeetCode-110-平衡二叉树-C语言

笔试面试题目：滑动窗口(二)

27. Remove Element(列表)题目代码

LeetCode OJ Binary Tree Right Side View

leetcode809