Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf518057

Browse files
author
zongyanqi
committed
add 010, 019, 162, 167, 202, 347, 561, 647, 654, 718
1 parent272cb1c commitf518057

10 files changed

+415
-35
lines changed

‎010-Regular-Expression-Matching.js

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
/**
2+
* https://leetcode.com/problems/regular-expression-matching/description/
3+
* Difficulty:Hard
4+
*
5+
* implement regular expression matching with support for '.' and '*'.
6+
*
7+
* '.' Matches any single character.
8+
* '*' Matches zero or more of the preceding element.
9+
* The matching should cover the entire input string (not partial).
10+
*
11+
* The function prototype should be:
12+
* bool isMatch(const char *s, const char *p)
13+
*
14+
* Some examples:
15+
* isMatch("aa","a") → false
16+
* isMatch("aa","aa") → true
17+
* isMatch("aaa","aa") → false
18+
* isMatch("aa", "a*") → true
19+
* isMatch("aa", ".*") → true
20+
* isMatch("ab", ".*") → true
21+
* isMatch("aab", "c*a*b") → true
22+
*/
23+
24+
/**
25+
*@param {string} s
26+
*@param {string} p
27+
*@return {boolean}
28+
*/
29+
varisMatch=function(s,p){
30+
31+
vardp=[];
32+
varm=s.length;
33+
varn=p.length;
34+
35+
for(vari=0;i<=m;i++){
36+
dp.push(newArray(n+1).fill(false));
37+
}
38+
dp[0][0]=true;
39+
40+
for(vari=0;i<=m;i++){
41+
for(varj=1;j<=n;j++){
42+
if(p[j-1]==='*'){
43+
dp[i][j]=dp[i][j-2]||(i>0&&(s[i-1]===p[j-2]||p[j-2]==='.')&&dp[i-1][j]);
44+
}else{
45+
dp[i][j]=i>0&&dp[i-1][j-1]&&
46+
(s[i-1]===p[j-1]||p[j-1]==='.');
47+
}
48+
}
49+
}
50+
51+
// console.log(dp);
52+
returndp[m][n];
53+
};
54+
55+
console.log(isMatch("aab","c*a*b"));
56+
console.log(isMatch("aasdfasdfasdfasdfas","aasdf.*asdf.*asdf.*asdf.*s"));
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
/**
2+
* https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
3+
* Difficulty:Medium
4+
*
5+
* Given a linked list, remove the nth node from the end of list and return its head.
6+
*
7+
* For example,
8+
* Given linked list: 1->2->3->4->5, and n = 2.
9+
* After removing the second node from the end, the linked list becomes 1->2->3->5.
10+
*
11+
* Note:
12+
* Given n will always be valid.
13+
* Try to do this in one pass.
14+
*
15+
*/
16+
17+
18+
// Definition for singly-linked list.
19+
functionListNode(val){
20+
this.val=val;
21+
this.next=null;
22+
}
23+
24+
/**
25+
*@param {ListNode} head
26+
*@param {number} n
27+
*@return {ListNode}
28+
*/
29+
varremoveNthFromEnd=function(head,n){
30+
if(!head)returnhead;
31+
varlen=0;
32+
vartail=head;
33+
while(tail){
34+
tail=tail.next;
35+
len++;
36+
}
37+
if(len===n){
38+
returnhead.next;
39+
}
40+
41+
len=len-n-1;
42+
tail=head;
43+
while(len){
44+
tail=tail.next;
45+
len--;
46+
}
47+
tail.next=tail.next.next;
48+
returnhead;
49+
};
50+
51+
vara=newListNode(1);
52+
varb=newListNode(2);
53+
varc=newListNode(3);
54+
vard=newListNode(4);
55+
// var e = new ListNode(5);
56+
a.next=b;
57+
b.next=c;
58+
c.next=d;
59+
// d.next = e;
60+
61+
console.log(removeNthFromEnd(a,2));

‎162-Find-Peak-Element.js

Lines changed: 11 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -10,35 +10,22 @@
1010
*/
1111

1212
/**
13+
*
1314
*@param {number[]} nums
1415
*@return {number}
1516
*/
1617
varfindPeakElement=function(nums){
17-
if(nums.length===1)return0;
18-
nums.unshift(nums[0]-1);
19-
nums.push(nums[nums.length-1]-1);
20-
vari=1;
21-
varj=nums.length-2;
22-
while(i<j){
23-
varhalf=Math.floor((i+j)/2);
24-
// console.log(i, j, half, nums[half]);
25-
if(isPeak(nums,half))returnhalf-1;
26-
if(i===half)returnj-1;
27-
28-
if(nums[half-1]>nums[half])j=half;
29-
elsei=half;
18+
for(vari=1;i<nums.length;i++){
19+
if(nums[i-1]>nums[i])returni-1;
3020
}
31-
return0;
21+
returnnums.length-1;
3222
};
3323

34-
functionisPeak(nums,i){
35-
vara=nums[i-1];
36-
varb=nums[i];
37-
varc=nums[i+1];
38-
returnb>a&&b>c;
39-
}
24+
// ================================================
4025

4126
/**
27+
* 二分查找
28+
*
4229
*@param {number[]} nums
4330
*@return {number}
4431
*/
@@ -53,6 +40,9 @@ var findPeakElement = function (nums) {
5340
}
5441
returnl;
5542
};
43+
44+
// ================================================
45+
5646
console.log(findPeakElement([3,2,1]),0);
57-
console.log(findPeakElement([1,2,3]),2);
47+
console.log(findPeakElement([1,2,3,1]),2);
5848
console.log(findPeakElement([1,3,2]),1);

‎167-Two-Sum-II-Input-array-is-sorted.js

Lines changed: 29 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -2,9 +2,14 @@
22
* https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
33
* Difficulty:Easy
44
*
5-
* Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
6-
* The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
5+
* Given an array of integers that is already sorted in ascending order,
6+
* find two numbers such that they add up to a specific target number.
7+
* The function twoSum should return indices of the two numbers such that they add up to the target,
8+
* where index1 must be less than index2.
9+
*
10+
* Please note that your returned answers (both index1 and index2) are not zero-based.
711
* You may assume that each input would have exactly one solution and you may not use the same element twice.
12+
*
813
* Input: numbers=[2, 7, 11, 15], target=9
914
* Output: index1=1, index2=2
1015
*
@@ -19,9 +24,29 @@ var twoSum = function (numbers, target) {
1924

2025
for(vari=0;i<numbers.length-1;i++){
2126
for(varj=i+1;j<numbers.length;j++){
22-
if(numbers[i]+numbers[j]==target)return[i+1,j+1];
27+
if(numbers[i]+numbers[j]===target)return[i+1,j+1];
2328
}
2429
}
2530
};
2631

27-
console.log(twoSum([2,7,11,15],9))
32+
// ==========================================
33+
34+
/**
35+
* 双指针
36+
*@param {number[]} nums
37+
*@param {number} target
38+
*@return {number[]}
39+
*/
40+
vartwoSum=function(nums,target){
41+
42+
varlo=0;
43+
varhi=nums.length-1;
44+
45+
while(nums[lo]+nums[hi]!==target){
46+
if(nums[lo]+nums[hi]>target)hi--;
47+
elselo++;
48+
}
49+
return[lo+1,hi+1];
50+
};
51+
52+
console.log(twoSum([2,7,11,15],9));

‎202-Happy-Number.js

Lines changed: 15 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -22,20 +22,25 @@
2222
*/
2323
varisHappy=function(n){
2424

25-
varnum=n;
26-
varresults=[];
25+
varresults=[n];
26+
2727
while(true){
28-
vardigits=(''+num).split('');
29-
varnewN=squareSumOfDigits(digits);
30-
if(newN===1)returntrue;
31-
if(results.indexOf(newN)>-1)returnfalse;
32-
results.push(newN);
33-
num=newN;
28+
n=squareSumOfDigits(n);
29+
// console.log(n);
30+
if(n===1)returntrue;
31+
if(results.indexOf(n)>-1)returnfalse;
32+
results.push(n);
3433
}
3534
};
3635

37-
functionsquareSumOfDigits(digits){
38-
returndigits.reduce((sum,d)=>sum+=d*d,0);
36+
functionsquareSumOfDigits(n){
37+
varsum=0,tmp;
38+
while(n){
39+
tmp=n%10;
40+
sum+=tmp*tmp;
41+
n=Math.floor(n/10);
42+
}
43+
returnsum;
3944
}
4045

4146
console.log(isHappy(1));

‎347-Top-K-Frequent-Elements.js

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/**
2+
* https://leetcode.com/problems/top-k-frequent-elements/description/
3+
* Difficulty:Medium
4+
*
5+
* Given a non-empty array of integers, return the k most frequent elements.
6+
*
7+
* For example,
8+
* Given [1,1,1,2,2,3] and k = 2, return [1,2].
9+
*
10+
* Note:
11+
* You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
12+
* Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
13+
*
14+
*/
15+
16+
/**
17+
*@param {number[]} nums
18+
*@param {number} k
19+
*@return {number[]}
20+
*/
21+
vartopKFrequent=function(nums,k){
22+
varmap={};
23+
for(vari=0;i<nums.length;i++){
24+
map[nums[i]]=map[nums[i]] ?map[nums[i]]+1 :1;
25+
}
26+
27+
varkeys=Object.keys(map);
28+
keys.sort((a,b)=>{
29+
if(map[a]>map[b])return-1;
30+
if(map[a]<map[b])return1;
31+
return0;
32+
});
33+
// console.log(map, keys);
34+
returnkeys.slice(0,k).map(a=>parseInt(a));
35+
};
36+
37+
console.log(topKFrequent([1,1,1,2,2,3,4],2));

‎561-Array-Partition-I.js

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/**
2+
* https://leetcode.com/problems/array-partition-i/description/
3+
* Difficulty:Easy
4+
*
5+
* Given an array of 2n integers, your task is to group these integers into n pairs of integer,
6+
* say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
7+
*
8+
* Example 1:
9+
* Input: [1,4,3,2]
10+
* Output: 4
11+
* Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
12+
*
13+
* Note:
14+
* n is a positive integer, which is in the range of [1, 10000].
15+
* All the integers in the array will be in the range of [-10000, 10000].
16+
*/
17+
18+
/**
19+
*@param {number[]} nums
20+
*@return {number}
21+
*/
22+
vararrayPairSum=function(nums){
23+
nums.sort((a,b)=>{
24+
if(a<b)return-1;
25+
if(a>b)return1;
26+
return0;
27+
});
28+
29+
// console.log(nums);
30+
varsum=0;
31+
for(vari=0;i<nums.length/2;i++){
32+
sum+=nums[2*i];
33+
}
34+
35+
returnsum;
36+
};
37+
38+
console.log(arrayPairSum([1,4,3,2]));

‎647-Palindromic-Substrings.js

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/**
2+
* https://leetcode.com/problems/palindromic-substrings/description/
3+
* Difficulty:Medium
4+
*
5+
*
6+
* Given a string, your task is to count how many palindromic substrings in this string.
7+
*
8+
* The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
9+
*
10+
* Example 1:
11+
* Input: "abc"
12+
* Output: 3
13+
* Explanation: Three palindromic strings: "a", "b", "c".
14+
*
15+
* Example 2:
16+
* Input: "aaa"
17+
* Output: 6
18+
* Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
19+
*
20+
* Note:
21+
* The input string length won't exceed 1000.
22+
*/
23+
24+
/**
25+
*@param {string} s
26+
*@return {number}
27+
*/
28+
varcountSubstrings=function(s){
29+
30+
vardp=[];
31+
varn=s.length;
32+
for(vari=0;i<n;i++){
33+
dp.push(newArray(n).fill(false));
34+
// dp[i][i] = 1;
35+
}
36+
varcnt=0;
37+
for(vari=n-1;i>=0;i--){
38+
for(varj=i;j<n;j++){
39+
if(i===j)dp[i][j]=true;
40+
else{
41+
dp[i][j]=s[i]===s[j] ?(i+1>=j-1||dp[i+1][j-1]) :0;
42+
}
43+
if(dp[i][j])cnt++;
44+
}
45+
}
46+
// console.log(dp);
47+
48+
returncnt;
49+
50+
};
51+
52+
// console.log(countSubstrings('abc'));
53+
console.log(countSubstrings('aaaaa'));

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp