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

Commitb0505f9

Browse files
author
zongyanqi
committed
add 025 030 031 032 033 034 036 038 067 101
1 parent4965c83 commitb0505f9

10 files changed

+638
-0
lines changed

‎025-Reverse-Nodes-in-k-Group.js

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
/**
2+
* https://leetcode.com/problems/reverse-nodes-in-k-group/description/
3+
* Difficulty:Hard
4+
*
5+
* Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
6+
* k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
7+
* You may not alter the values in the nodes, only nodes itself may be changed.
8+
* Only constant memory is allowed.
9+
* For example,
10+
* Given this linked list: 1->2->3->4->5
11+
* For k = 2, you should return: 2->1->4->3->5
12+
* For k = 3, you should return: 3->2->1->4->5
13+
*
14+
*/
15+
16+
// Definition for singly-linked list.
17+
functionListNode(val){
18+
this.val=val;
19+
this.next=null;
20+
}
21+
22+
/**
23+
*@param {ListNode} head
24+
*@param {number} k
25+
*@return {ListNode}
26+
*/
27+
varreverseKGroup=function(head,k){
28+
// if (k === 1)
29+
// return head;
30+
vart=newListNode(0);
31+
t.next=head;
32+
vars=t;
33+
34+
while(true){
35+
varcnt=0;
36+
varf=t;
37+
while(cnt++<k&&f){
38+
f=f.next;
39+
}
40+
// console.log(p(t), p(f));
41+
42+
if(!f||cnt!==k+1)break;
43+
cnt=0;
44+
vara=t.next;
45+
46+
while(++cnt<k){
47+
varb=a.next;
48+
a.next=b.next;
49+
b.next=t.next;
50+
t.next=b;
51+
// console.log(p(t), p(a), p(b));
52+
}
53+
t=a;
54+
}
55+
56+
returns.next;
57+
};
58+
59+
functionp(n){
60+
vart=n;
61+
vars='';
62+
while(t){
63+
s=s+t.val+'->';
64+
t=t.next;
65+
}
66+
s+='null';
67+
returns;
68+
}
69+
//
70+
console.log(p(reverseKGroup({
71+
val:1,
72+
next:{
73+
val:2,
74+
next:{
75+
val:3,
76+
next:{
77+
val:4
78+
}
79+
}
80+
}
81+
},2)))
82+
83+
console.log(p(reverseKGroup({val:1},2)));
84+
85+
console.log(p(reverseKGroup({
86+
val:1,
87+
next:{
88+
val:2
89+
}
90+
},2)))
91+
92+
console.log(p(reverseKGroup({
93+
val:1,
94+
next:{
95+
val:2,
96+
next:{
97+
val:3,
98+
next:{
99+
val:4,
100+
next:{
101+
val:5,
102+
next:{
103+
val:6,
104+
next:{
105+
val:7
106+
}
107+
}
108+
}
109+
}
110+
}
111+
}
112+
},3)))
113+
//
114+
115+
console.log(p(reverseKGroup({
116+
val:1,
117+
next:{
118+
val:2,
119+
next:{
120+
val:3,
121+
next:{
122+
val:4,
123+
next:null
124+
}
125+
}
126+
}
127+
},2)));
128+
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/**
2+
*
3+
* https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/
4+
* Difficulty:Hard
5+
*
6+
* You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s)
7+
* in s that is a concatenation of each word in words exactly once and without any intervening characters.
8+
* For example, given:
9+
* s: "barfoothefoobarman"
10+
* words: ["foo", "bar"]
11+
* You should return the indices: [0,9].
12+
* (order does not matter).
13+
*
14+
*/
15+
/**
16+
*@param {string} s
17+
*@param {string[]} words
18+
*@return {number[]}
19+
*/
20+
varfindSubstring=function(s,words){
21+
if(!s.length||!words.length)return[];
22+
varans=[];
23+
vartoFind={};
24+
25+
varm=words.length;
26+
varn=words[0].length;
27+
28+
for(vari=0;i<m;i++){
29+
toFind[words[i]]=(toFind[words[i]]||0)+1;
30+
}
31+
32+
for(i=0;i<=s.length-m*n;i++){
33+
varfound={};
34+
35+
for(varj=0;j<m;j++){
36+
vark=i+n*j;
37+
varw=s.substr(k,n);
38+
if(!toFind[w])break;
39+
found[w]=(found[w]||0)+1;
40+
if(found[w]>toFind[w])break;
41+
}
42+
if(j===m)ans.push(i);
43+
}
44+
45+
returnans;
46+
47+
};
48+
49+
console.log(findSubstring('barfoothefoobarman',['foo','bar']));

‎031-Next-Permutation.js

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
/**
2+
* https://leetcode.com/problems/next-permutation/description/
3+
* Difficulty:Medium
4+
*
5+
* Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
6+
* If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
7+
* The replacement must be in-place, do not allocate extra memory.
8+
* Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
9+
* 1,2,3 → 1,3,2
10+
* 3,2,1 → 1,2,3
11+
* 1,1,5 → 1,5,1
12+
*/
13+
/**
14+
*@param {number[]} nums
15+
*@return {void} Do not return anything, modify nums in-place instead.
16+
*/
17+
varnextPermutation=function(nums){
18+
19+
if(nums.length<2)return;
20+
varpeak=nums.length-1;
21+
for(vari=peak-1;nums[i]>=nums[peak];peak=i--);
22+
23+
if(peak!==0){
24+
varswapIndex=findSwap(nums,peak,nums.length-1,peak-1);
25+
if(swapIndex!==-1){
26+
swap(nums,peak-1,swapIndex);
27+
}
28+
}
29+
30+
reverse(nums,peak,nums.length-1);
31+
32+
};
33+
34+
functionfindSwap(nums,s,e,target){
35+
for(vari=e;i>=s;i--){
36+
if(nums[i]>nums[target])returni;
37+
}
38+
return-1;
39+
}
40+
41+
functionswap(nums,s,e){
42+
vart=nums[s];
43+
nums[s]=nums[e];
44+
nums[e]=t;
45+
}
46+
functionreverse(nums,s,e){
47+
// var len = e - s;
48+
for(vari=0;i<Math.ceil((e-s)/2);i++){
49+
50+
swap(nums,s+i,e-i);
51+
}
52+
// return nums;
53+
}
54+
55+
// console.log(reverse([1, 2, 3, 4, 5], 0, 4));
56+
// console.log(reverse([1, 2, 3, 4, 5], 3, 4));
57+
// console.log(reverse([1, 2, 3, 4, 5], 2, 3));
58+
// console.log(reverse([1, 2, 3, 4, 5], 1, 1));
59+
// console.log(reverse([1, 2, 3, 4, 5], 1, 4));
60+
61+
// var nums = [1, 2, 5, 4, 3];
62+
// console.log(nums);
63+
// nextPermutation(nums);
64+
// console.log(nums);
65+
//
66+
console.log('====');
67+
68+
varnums=[2,3,1];
69+
console.log(nums);
70+
nextPermutation(nums);
71+
console.log(nums);
72+
73+
console.log('====');
74+
75+
varnums=[1,1];
76+
console.log(nums);
77+
nextPermutation(nums);
78+
console.log(nums);
79+
80+
console.log('====');
81+
82+
varnums=[3,2,1];
83+
console.log(nums);
84+
nextPermutation(nums);
85+
console.log(nums);
86+
87+

‎032-Longest-Valid-Parentheses.js

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/**
2+
* https://leetcode.com/problems/longest-valid-parentheses/description/
3+
* Difficulty:Hard
4+
*
5+
* Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
6+
* For "(()", the longest valid parentheses substring is "()", which has length = 2.
7+
* Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
8+
*/
9+
10+
/**
11+
* 使用栈解决
12+
*@param {string} s
13+
*@return {number}
14+
*/
15+
varlongestValidParentheses=function(s){
16+
varstack=[];
17+
for(vari=0;i<s.length;i++){
18+
if(s[i]==='(')stack.push(i);
19+
else{
20+
if(stack.length&&s[stack[stack.length-1]]==='(')stack.length--;
21+
elsestack.push(i);
22+
}
23+
}
24+
25+
if(!stack.length)returns.length;
26+
varlongest=0;
27+
varend=s.length;
28+
varstart=0;
29+
while(stack.length){
30+
start=stack[stack.length-1];
31+
stack.length--;
32+
longest=Math.max(longest,end-start-1);
33+
end=start;
34+
}
35+
longest=Math.max(longest,end);
36+
returnlongest;
37+
};
38+
39+
40+
console.log(longestValidParentheses('()'),2);
41+
console.log(longestValidParentheses('())'),2);
42+
console.log(longestValidParentheses('(()'),2);
43+
console.log(longestValidParentheses('))()())((())))'),6);
44+
console.log(longestValidParentheses('()'),2);
45+
console.log(longestValidParentheses('('),0);
46+
console.log(longestValidParentheses(')()()))()()())'),6);
47+
console.log(longestValidParentheses('()(()'),2);
48+
console.log(longestValidParentheses('()(()'),2);
49+
console.log(longestValidParentheses('(()'),2);
50+

‎033-Search-in-Rotated-Sorted-Array.js

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
/**
2+
* https://leetcode.com/problems/search-in-rotated-sorted-array/description/
3+
* Difficulty:Medium
4+
*
5+
* Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
6+
* (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
7+
* You are given a target value to search. If found in the array return its index, otherwise return -1.
8+
* You may assume no duplicate exists in the array.
9+
*/
10+
/**
11+
*@param {number[]} nums
12+
*@param {number} target
13+
*@return {number}
14+
*/
15+
varsearch=function(nums,target){
16+
17+
18+
varlo=0;
19+
varhi=nums.length-1;
20+
while(lo<hi){
21+
varmid=Math.floor((lo+hi)/2);
22+
if(nums[mid]<nums[hi])hi=mid;
23+
elselo=mid+1;
24+
}
25+
vari=lo;
26+
27+
lo=target<nums[0] ?i :0;
28+
hi=target<=nums[nums.length-1] ?nums.length-1 :i;
29+
30+
// console.log(nums, lo, hi);
31+
while(lo<=hi){
32+
mid=Math.floor((lo+hi)/2);
33+
// console.log(lo, mid, hi)
34+
if(nums[mid]<target)lo=mid+1;
35+
elseif(nums[mid]===target)returnmid;
36+
elsehi=mid-1;
37+
}
38+
39+
return-1;
40+
41+
};
42+
43+
console.log(search([],5))
44+
console.log(search([1],0))
45+
console.log(search([4,5,6,7,0,1,2],2))
46+
console.log(search([3,1],1))

0 commit comments

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