leetcode-300-301-312

leetcode 300题301题302题

leetcode300题题目(最长上升子序列):

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

示例:

输入:[10,9,2,5,3,7,101,18]

输出:4

解释:最长的上升子序列是 [2,3,7,101],它的长度是 4。

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var lengthOfLIS = function(nums) {
var dp = [];
for(var h=0;h<nums.length;h++){
dp[h] = 1;
}
var result = 0;
for(var i=0;i<nums.length;i++){
for(var j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
result = Math.max(dp[i],result);
}
return result;
};

leetcode301题题目(删除无效的括号):

删除最小数量的无效括号,使得输入的字符串有效,返回所有可能的结果。

说明: 输入可能包含了除 () 以外的字符。

示例:

输入:”()())()”

输出:[“()()()”, “(())()”]

输入:”(a)())()”

输出:[“(a)()()”, “(a())()”]

输入:”)(“

输出:[“”]

解答(深度优先遍历):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
var removeInvalidParentheses = function(s) {
var result = [];
return removeInvalidParentheses1(s);
function removeInvalidParentheses1(s){
var left = 0;
var right = 0;
for(var h=0;h<s.length;h++){//判断其中应该消掉的左右括号数目
var char = s[h];
if(char=='('){
left++;
}
if(char==')'){
if(left>0){
left--;
}else{
right++;
}
}
}
dfs(s,0,left,right);
return result;
}
function dfs(s,start,left,right){//深度优先遍历进行括号消除
if(left==0&&right==0){
if(check(s)){
result.push(s);
}
return;
}
for(var i=start;i<s.length;i++){
if(i-1>=start&&s[i]==s[i-1]){
continue;
}
if(left>0&&s[i]=='('){
dfs(s.substr(0,i)+s.substr(i+1,s.length-i-1),i,left-1,right);
}
if(right>0&&s[i]==')'){
dfs(s.substr(0,i)+s.substr(i+1,s.length-i-1),i,left,right-1);
}
}

}
function check(s){//检查是否满足正常括号对
var count = 0;
for(var h=0;h<s.length;h++){
var char = s[h];
if(char=='('){
count++;
}
if(char==')'){
count--;
if(count<0){
return false;
}
}
}
return count==0;
}
};

leetcode312题题目(戳气球):

有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。

现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] nums[i] nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

  • 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。

  • 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

示例

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var maxCoins = function(nums) {
nums.unshift(1);
nums.push(1);
var length = nums.length;
var dp = [];
for(var i=0;i<length;i++){
dp[i] = [];
for(var j=0;j<length;j++){
dp[i][j] = 0;
}
}
for(var len=2;len<=length;len++){
for(var i=0;i<=length-len;i++){
var j = i+len-1;
for(var k=i+1;k<j;k++){
dp[i][j] = Math.max(dp[i][j],nums[i]*nums[k]*nums[j]+dp[i][k]+dp[k][j]);
}
}
}
return dp[0][length-1];
};
分享到