Q5. 最长回文子串 MEDIUM

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

  1. class Solution:
  2.     def longestPalindromeSubseq(self, s: str) -> int:
  3.         '''
  4.             dp[i][j] = s[i:j+1]组成的子串中最长回文子串的长度
  5.             [i (i+1 ... j-1) j]
  6.             [(i i+1 ... j-1) j]
  7.             [i (i+1 ... j-1 j)]
  8.             j>=i 右上角table
  9.                 i,j-1   |   (i,j)
  10.              -----------|---------
  11.                 i+1,j-1 |   i+1,j
  12.         '''
  13.           n = len(s)
  14.         dp = [[0 for _ in range(n)] for _ in range(n)]
  15.         for i in range(n):
  16.             dp[i][i] = 1
  17.         for i in range(n-1,-1,-1):
  18.             for j in range(i+1,n,1):
  19.                 if s[j] == s[i]:
  20.                     dp[i][j] = dp[i+1][j-1] + 2 
  21.                 else:
  22.                     dp[i][j] = max(dp[i+1][j],dp[i][j-1]) + 1
  23.            return dp[0][-1]

1312. 让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

  1. class Solution:
  2.     def minInsertions(self, s: str) -> int:
  3.         n = len(s)
  4.         dp = [[0]*n for _ in range(n)]
  5.         for i in range(n-1,-1,-1):
  6.             for j in range(i+1,n,1):
  7.                 if s[i] == s[j]:
  8.                     dp[i][j] = dp[i+1][j-1]
  9.                 else:
  10.                     dp[i][j] = min(dp[i+1][j],dp[i][j-1]) +1
  11.         return dp[0][-1]

Q53. 最大子序和 EASY

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 通过次数263,576 | 提交次数511,934

  1. class Solution:
  2.     def maxSubArray(self, nums: List[int]) -> int:
  3.         pre,res = 0,nums[0]
  4.         for x in nums:
  5.             pre = max(pre+x,x)
  6.             res = max(pre,res)
  7.         return res
  1. class Solution {
  2. public:
  3.     int maxSubArray(vector<int>& nums) {
  4.         int pre = 0,res=nums[0];
  5.         for(auto x:nums)
  6.         {
  7.             pre = max(pre+x,x);
  8.             res = max(res,pre);
  9.         }
  10.         return res;
  11.     }
  12. };

Q62. 不同路径 MEDIUM

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。

  1. 向右 -> 向右 -> 向下
  2. 向右 -> 向下 -> 向右

  3. 向下 -> 向右 -> 向右

    通过次数113,501 | 提交次数186,972

  1. class Solution {
  2. public:
  3.     int uniquePaths(int m, int n) {
  4.         vector<vector<int>> dp(m,vector<int>(n,1));
  5.         for (int i=1;i<m;i++)
  6.         {
  7.             for ( int j =1;j<n;j++)
  8.             {
  9.                 dp[i][j] = dp[i-1][j]+ dp[i][j-1];
  10.             }
  11.         }
  12.         return dp[m-1][n-1];
  13.     }
  14. };
  1. class Solution:
  2.     def uniquePaths(self, m: int, n: int) -> int:
  3.         dp = [[1 for _ in range(n)] for _ in range(m)]
  4.         for i in range(1,m):
  5.             for j in range(1,n):
  6.                 dp[i][j] = dp[i-1][j] + dp[i][j-1]
  7.         return dp[-1][-1]

Q63. 不同路径 II MEDIUM

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 示例 1: 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：

  1. 向右 -> 向右 -> 向下 -> 向下
  2. 向下 -> 向下 -> 向右 -> 向右

通过次数73,055 | 提交次数209,869

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& grid) {
        int m = grid.size(),n =grid[0].size();
        vector<vector<long int>> dp(m,vector<long int>(n,0));
        for ( int i=0;i<m;i++)
        {
            if (grid[i][0]==1) break;
            dp[i][0] = 1;
        }
        for (int j =0;j<n;j++)
        {
            if (grid[0][j]==1) break;
            dp[0][j] = 1;
        }
        for (int i=1;i<m;i++)
        {
            for ( int j=1;j<n;j++)
            {
                if (grid[i][j]==1) continue;
                dp[i][j] = dp[i-1][j]+ dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

Q64. 最小路径和 MEDIUM

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。 通过次数95,196 | 提交次数144,577。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m= grid.size(),n = grid[0].size();
        vector<vector<int>> res(m,vector<int>(n,0));
        res[0][0] = grid[0][0];
        for(int i =1;i<m;i++){
            res[i][0] = res[i-1][0] + grid[i][0];
        }
        for (int j = 1;j<n;j++)
        {
            res[0][j] = res[0][j-1] + grid[0][j];
        }
        for(int i =1;i<m;i++){
            for (int j = 1;j<n;j++)
            {
                res[i][j] = min(res[i][j - 1], res[i - 1][j]) + grid[i][j]  ;
            }
        }
        return res[m-1][n-1];

    }
};

Q70. 爬楼梯 EASY

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。

  1. 1 阶 + 1 阶
  2. 2 阶

示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

通过次数229,410 | 提交次数460,216

class Solution {
public:
    int climbStairs(int n) {
        if( n<=2){
            return n;
        }
        int r1=2,r2=1;
        int res;
        for (int i =3;i<=n;i++)
        {
            res = r1+r2;
            r2 = r1;
            r1 =res;

        }
        return res;

    }
};

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<=2:
            return n
        pre1,pre2 = 2,1
        res = 3
        for i in range(3,n+1):
            res = pre1 + pre2
            pre2 = pre1
            pre1 = res
        return res

Q97. 交错字符串 HARD

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。 示例 1: 输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” 输出: true 示例 2: 输入: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” 输出: false 通过次数18,393提交次数43,994 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/interleaving-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

定义dp

`dp[i][j]`表示`s1`的前`i`个字符与`s2`的前`j`个字符拼接成`s3`的前`i+j`个字符；

定义边界：

dp需要考虑s1 或者 s2 存在空字符串的情况，所以dp的维度应该是`(len(s1)+1,len(s2)+1)`

`dp[0][0]` = 1 ， 0 + 0 个字符可以拼接成`s3`的前0个字符

定义好`dp[0][0]`后，`i,j`从1开始初始化边界

`dp[i][0]` = 1 if s1[i-1] == s3[i-1] else 0 且当s1[i-1] !=s3[i-1]，i-1后的所有`dp[i][0]`均为0

`dp[0][j]` = 1 if s2[j-1] == s3[j-1] else 0 且当s2[j-1] !=s3[j-1]，i-1后的所有`dp[0][j]`均为0

择优选择：

看成路径选择问题，`(i, j)`可由`(i-1, j)`  或 `(i, j-1)`走一步到达`+1`。

状态转移方程：

`dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])`
aadbbcbcac j: 0 a a b c c e
i: 0 1 1 0 0 0 0 0
b 0 1 1 0 0 0 0
a 0 1 1 0 0 0 0
c 0 0 1 1 1 1 1
c 0 0 0 0 1 0 1

Q118. 杨辉三角 EASY

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。 示例: 输入: 5 输出: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 通过次数85,950 | 提交次数128,951

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res(numRows);
        for (int i =0;i<numRows;i++)
        {
            res[i] = vector<int> (i+1,1);

        }
        for (int i = 2;i <numRows;i++)
        {
            for (int j =1;j<i;j++)
            {
                res[i][j] = res[i-1][j-1] + res[i-1][j];
            }
        }
        return res;
    }
};

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(numRows):
            res.append([1]*(i+1))
        for i in range(2,numRows):  
            for j in range(1,i):
                res[i][j] = res[i-1][j-1] + res[i-1][j]
        return res

139. 单词拆分 MEDIUM

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。 示例 2： 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。 示例 3： 输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false 通过次数67,593 | 提交次数147,236 dp[i]=dp[j] && check(s[j..i−1])

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        # wordDict.sort(key=lambda x: len(x))
        if len(wordDict) == 0:
            return False
        dp = [False]*(n+1)
        dp[0] = True
        # for i in range(len(wordDict[0])-1, n+1):
        for i in range( n+1):
            for j in range(i):

                dp[i] = dp[j] & wordDict.__contains__(s[j:i])
                if dp[i]:
                    break
        return dp[-1]

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        if (wordDict.size()==0)
        {
            return false;
        } 
        auto wordDictSet = unordered_set <string> ();
        for (auto word: wordDict) {
            wordDictSet.insert(word);
        }
        auto dp = vector<bool> (n+1);
        dp[0] = true;
        for (int i =1;i<=n;i++)
        {
            for(int j =0;j<i;j++)
            {
                if (dp[j] && wordDictSet.find(s.substr(j, i-j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

vector<string>::iterator index = find(wordDict.begin(),wordDict.end(),s.substr(j,i-j));
bool flag = false;
if (index!=wordDict.end()){
    flag = true;
}
dp[i] = dp[j] && flag;
if (dp[i])
{
    break;
}

Q300. 最长上升子序列 MEDIUM

给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 说明: 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 你算法的时间复杂度应该为 O(n2) 。 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗? 通过次数111,087 | 提交次数248,782

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n <=1:
            return n
           dp = [1]*(n)
        for i in range(1,n):
            for j in range(i):
                if nums[j]<nums[i] and dp[i] < dp[j]+1:
                    dp[i] = dp[j]+1
        return max(dp)

Q746. 使用最小花费爬楼梯 EASY

数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。 示例 1: 输入: cost = [10, 15, 20] 输出: 15 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。 示例 2: 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出: 6 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。 注意： cost 的长度将会在 [2, 1000]。 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。 通过次数35,966 | 提交次数73,345

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        cost.emplace_back(0);
        int pre1=cost[1];
        int pre2 = cost[0];
        for(int i =3;i<=cost.size();i++)
        {
            int temp = min(pre1,pre2)+cost[i-1];
            pre2 = pre1;
            pre1 = temp;
        }
        return pre1;
    }
};

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        cost.append(0)
        pre1,pre2 = cost[1],cost[0]
        for i in range(3,len(cost)+1):
            pre2,pre1 = pre1,min(pre1,pre2)+cost[i-1]
        return pre1
    最后一个台阶消耗为0
    dp[i] = min(dp[i-1],dp[i-2]) + cost[i-1] dp[i]->i个台阶

Q718. 最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。 示例： 输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释： 长度最长的公共子数组是 [3, 2, 1] 。 提示： 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100 通过次数30,341 | 提交次数57,644

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        m,n = len(A),len(B)
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # res = []
        for i in range(m):
            for j in range(n):
                if A[i] == B[j]:
                    dp[i][j] = dp[i-1][j-1] +1 if i and j else 1
            # res = max(max(dp[i]),res)
        return max(map(max,dp))
        # return max(dp)

Q1277. 统计全为1的正方形子矩阵 MEDIUM

给你一个 m n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。 *示例 1： 输入：matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出：15 解释： 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 = 10 + 4 + 1 = 15. 通过次数8,189 | 提交次数11,707

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res= 0
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i and j and matrix[i][j]:
                    matrix[i][j] += min(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1])
                res += matrix[i][j]
        return res

[招商银行信用卡2019编程题]解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

输入描述:

12可以解码成“AB”，“L”这两种

输出描述:

解码方法的总数

输入例子1:

12

输出例子1:

2

例子说明1:

12可以解码成“AB”，“A，B”这两种

#include<iostream>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
    int numDecodings(string s) {
        /*
        dp[i]表示到第i-1位时解码的方法数
        两种情况：
        1.s[i-1]单独解码，方法数为dp[i-1]
        2.s[i-2:i]拼接成双字符解码，若10<=s[i-2:i]<26，双字符合格，解码的方法数位dp[i-2]，否则为0
        综合两种情况，得到状态转移矩阵：
        dp[i] = dp[i-1] + (dp[i-2] if 双字符合格 else 0)

         216，在判断第二位‘1’时，i-2<0了，状态转移矩阵不能用了，故在前加一位，即dp[0]为1

        */
        if(s.empty()) return 1;
        int n = s.size();
        vector<int> dp(n+1,0);
        dp[0] = 1;
        dp[1] = s[1]!='0'?1:0;
        for(int i =2;i<=n;i++)
        {
            dp[i] += s[i]!='0'?dp[i-1] :0;
            if(s[i-2] =='1'|| (s[i-2] == '2' && s[i-1] - '6'<=0))
            {
                dp[i] +=dp[i-2];
            }
        }
        return dp[n];
    }
};
int main()
{
    string s;
    cin>>s;
    Solution solution;
    int res = solution.numDecodings(s);
    cout<<res<<endl;
    return 0;
}