最长有效括号
给一个只包含'('和')'的字符串，找出最长的有效（正确关闭）括号子串的长度。对于
"(()"，最长有效括号子串为"()"，它的长度是 2。另一个例子
")()())"，最长有效括号子串为"()()"，它的长度是 4。C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
int _max = 0, left = -1;
int i = 0;
for(i = 0; i < s.length(); i++){
if(s[i] == '(') st.push(i);
else{
if(st.empty()) left = i; // 前面不匹配
else{
st.pop();
if(st.empty()) _max = max(_max, i - left); // 前面全部匹配 ()()
else _max = max(_max, i - st.top()); // 前面部分匹配 (()
}
}
}
return _max;
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
v = []
max_len = 0
max_i = -1
for i in range(len(s)):
if s[i] == '(':
v.append(i)
else:
if len(v) == 0:
max_i = i
else:
left = v.pop()
if len(v) == 0:
max_len = max(max_len, i - max_i)
else:
max_len = max(max_len, i - v[-1])
return max_len最大子序和 给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。
例如，给定序列
[-2,1,-3,4,-1,2,1,-5,4]， 连续子序列[4,-1,2,1]的和最大，为6。Python:
1
2
3
4
5
6
7
8
9
10
11
12class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = -0x80000000
sum = 0
for i in range(len(nums)):
sum = max(sum+nums[i],nums[i])
result = max(sum,result)
return resultC++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int _max = -0x80000000, _sum = 0;
for(auto num : nums){
_sum += num;
_max = max(_max, _sum);
if(_sum < 0){
_sum = 0;
}
}
return _max;
}
};
爬楼梯 你正在爬楼梯。需要 n 步你才能到达顶部。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方式可以爬到楼顶呢？
注意：给定 n 将是一个正整数。
示例 1：
1
2
3
4
5
6
7
8
9输入： 2
输出： 2
说明： 有两种方法可以爬到顶端。
1. 1 步 + 1 步
2. 2 步
```
**示例 2：**输入： 3 输出： 3 说明： 有三种方法可以爬到顶端。
- 1 步 + 1 步 + 1 步
- 1 步 + 2 步
- 2 步 + 1 步
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
C++:
```c++
class Solution {
public:
int climbStairs(int n) {
if(n <= 1) return 1;
int a=1, b=1, tmp;
for(int i=2; i<= n; i++){
tmp = a;
a = a + b;
b = tmp;
}
return a;
}
};
Pyhton:
1
2
3
4
5
6
7
8
9
10class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
dp = [1,1]+[0] * (n-1)
for i in range(2,n+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[n]
最小路径和
给定一个只含非负整数的 m x n 网格，找到一条从左上角到右下角的可以使数字之和最小的路径。
注意: 每次只能向下或者向右移动一步。
示例 1:
1
2
3[[1,3,1],
[1,5,1],
[4,2,1]]根据上面的数组，返回
7. 因为路径 1→3→1→1→1 总和最小。Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m, n = len(grid), len(grid[0])
dp = [[0 for j in range(n)] for i in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
return dp[m - 1][n - 1]C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.size()<1 || grid[0].size()<1)
return 0;
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int i, j;
dp[0][0] = grid[0][0];
for(i = 1; i < m; ++i){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(j = 1; j < n; ++j){
dp[0][j] = dp[0][j-1] + grid[0][j];
}
for(i = 1; i < m; ++i){
for(j = 1; j < n; ++j){
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
};打家劫舍
你是一个专业的强盗，计划抢劫沿街的房屋。每间房都藏有一定的现金，阻止你抢劫他们的唯一的制约因素就是相邻的房屋有保安系统连接，如果两间相邻的房屋在同一晚上被闯入，它会自动联系警方。
给定一个代表每个房屋的金额的非负整数列表，确定你可以在没有提醒警方的情况下抢劫的最高金额。
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n < 1) return 0;
vector<int> dp(n + 1, 0);
dp[1] = nums[0];
int i = 0;
for (i = 2; i <= n; ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i-1]);
}
return dp[n];
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n=len(nums)
dp=[0]*(n+1)
if n:
dp[1]=nums[0]
for i in range(2,n+1):
dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
return dp[n]打家劫舍II
注意事项: 这是 打家劫舍 的延伸。
在上次盗窃完一条街道之后，窃贼又转到了一个新的地方，这样他就不会引起太多注意。这一次，这个地方的所有房屋都围成一圈。这意味着第一个房子是最后一个是紧挨着的。同时，这些房屋的安全系统与上次那条街道的安全系统保持一致。
给出一份代表每个房屋存放钱数的非负整数列表，确定你可以在不触动警报的情况下盗取的最高金额。
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int robb(vector<int> nums) {
int n = nums.size();
if(n < 1) return 0;
vector<int> dp(n + 1, 0);
dp[1] = nums[0];
int i = 0;
for (i = 2; i <= n; ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i-1]);
}
return dp[n];
}
int rob(vector<int>& nums) {
int n = nums.size();
if(n < 1) return 0;
if(n == 1) return nums[0];
vector<int> numsA(nums.begin() + 1, nums.end());
vector<int> numsB(nums.begin(), nums.end()-1);
return max(robb(numsA), robb(numsB));
}
};Pyhton:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution(object):
def robb(self,nums):
n=len(nums)
dp=[0]*(n+1)
if n:
dp[1]=nums[0]
for i in range(2,n+1):
dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
return dp[n]
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==1:
return nums[0]
return max(self.robb(nums[1:]),self.robb(nums[:-1]))
最长上升子序列给出一个无序的整形数组，找到最长上升子序列的长度。
例如，
给出
[10, 9, 2, 5, 3, 7, 101, 18]， 最长的上升子序列是[2, 3, 7, 101]，因此它的长度是4。因为可能会有超过一种的最长上升子序列的组合，因此你只需要输出对应的长度即可。你的算法的时间复杂度应该在 O(n2) 之内。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
n=len(nums)
dp=[1]*n
pre=[None]*n
for j in range(n):
for i in range(j):
if nums[j]>nums[i] and dp[i]+1>dp[j]:
dp[j]=dp[i]+1
pre[j]=i # 采用pre记录，倒退回去求序列
idx=dp.index(max(dp))
ans=[]
while idx is not None:
ans+=nums[idx], #list add element or use append
idx=pre[idx]
return len(ans)
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
if(n < 1) return 0;
vector<int> dp(n, 1);
int i = 0, j = 0;
for(i = 0; i < n; ++i){
for(j = 0; j < i; ++j){
if(nums[j] < nums[i]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};获得最长子序列是这样做的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
vector<int> getLIS(vector<int>& nums) {
int n = nums.size();
if (n < 1) return {};
vector<int> dp(n, 1), pre(n, -1);
int i = 0, j = 0;
for (i = 0; i < n; ++i) {
for (j = 0; j < i; ++j) {
if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
}
int idx = max_element(dp.begin(), dp.end()) - dp.begin();
vector<int> ans;
while (idx != -1) {
ans.push_back(nums[idx]);
idx = pre[idx];
}
return vector<int>(ans.rbegin(), ans.rend());
}
};
零钱兑换
给定不同面额的硬币(coins)和一个总金额(amount)。写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合方式能组成总金额，返回
-1。示例 1: coins =
[1, 2, 5], amount =11return3(11 = 5 + 5 + 1)示例 2: coins =
[2], amount =3return-1.注意:
你可以认为每种硬币的数量是无限的。
Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [0x7fffffff] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for j in coins:
if j <= i:
dp[i] = min(dp[i], dp[i - j] + 1)
return dp[amount] if dp[amount] <= amount else -1C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount < 1)
return 0;
int n = coins.size();
vector<int> dp(amount + 1, 0x7fffffff);
dp[0] = 0;
for (int i = 1; i <= amount; ++i) {
for (auto coin : coins) {
if (coin <= i && dp[i-coin]!=0x7fffffff) { //注意python不会越界
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == 0x7fffffff ? -1 : dp[amount];
}
};使用最小花费爬楼梯
数组的每个索引做为一个阶梯，第
i个阶梯对应着一个非负数的体力花费值cost[i](索引从0开始)。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
1
2
3输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。示例 2:
1
2
3输入: 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]。
Python:
1
2
3
4
5
6
7
8
9
10
11class Solution:
def minCostClimbingStairs(self, cost):
"""
:type cost: List[int]
:rtype: int
"""
n = len(cost)
dp = [0] * (n + 1)
for i in range(2, n+1):
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[n]
C++:
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n+1, 0);
int i;
for(i = 2; i <= n; i++){
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[n];
}
};
最长回文子序列
给定一个字符串
s，找到其中最长的回文子序列。可以假设s的最大长度为1000。示例 1: 输入:
1
"bbbab"
输出:
1
4
一个可能的最长回文子序列为 “bbbb”。
示例 2: 输入:
1
"cbbd"
输出:
1
2
一个可能的最长回文子序列为 “bb”。
C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.length();
if (n < 1) return 0;
if (n == 1) return 1;
int i, j;
vector<vector<int>> dp(n, vector<int>(n, 0));
for(i = n-1; i >= 0; i--){
dp[i][i] = 1;
for (j = i+1; j < n; j++) {
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
return dp[0][n - 1];
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution(object):
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
dp = [[0 for _ in range(n)] for __ in range(n)]
for i in range(n - 1, -1, -1):
dp[i][i]=1
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
return dp[0][n - 1]
一和零
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个
0和 n 个1。另外，还有一个仅包含0和1字符串的数组。你的任务是使用给定的 m 个
0和 n 个1，找到能拼出存在于数组中的字符串的最大数量。每个0和1至多被使用一次。注意:
- 给定
0和1的数量都不会超过100。 - 给定字符串数组的长度不会超过
600。
示例 1:
1
2
3
4输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。示例 2:
1
2
3
4输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
int i, j;
int c0, c1;
for(auto str: strs){
c0 = count(str.begin(), str.end(), '0');
c1 = str.length() - c0;
for(i = m; i >= c0; i--){
for(j = n; j >= c1; j--){
dp[i][j] = max(dp[i][j], 1 + dp[i-c0][j-c1]);
}
}
}
return dp[m][n];
}
};Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution(object):
def findMaxForm(self, strs, m, n):
"""
:type strs: List[str]
:type m: int
:type n: int
:rtype: int
"""
dp = [[0] * (n + 1) for _ in range(m + 1)]
for s in strs:
c0, c1 = s.count('0'), s.count('1')
for i in range(m, c0 - 1, -1):
for j in range(n, c1 - 1, -1):
dp[i][j] = max(dp[i][j], 1 + dp[i - c0][j - c1])
return dp[m][n]
- 给定
扫一扫，分享到微信