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

Commita76b835

Browse files
committed
update: 4 & 53 & 169 & 215 & 340 & 395
1 parent4919675 commita76b835

File tree

10 files changed

+299
-2
lines changed
  • src
    • kth-largest-element-in-an-array
    • longest-repeating-character-replacement
    • longest-substring-with-at-least-k-repeating-characters
    • longest-substring-with-at-most-k-distinct-characters
    • longest-substring-without-repeating-characters
    • majority-element
    • maximum-subarray
    • median-of-two-sorted-arrays

10 files changed

+299
-2
lines changed

‎README.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@ This is the solutions collection of my LeetCode submissions, most of them are pr
1111
|1|[Two Sum](https://leetcode.com/problems/two-sum/)|[JavaScript](./src/two-sum/res.js)|Easy|
1212
|2|[Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)|[JavaScript](./src/add-two-numbers/res.js)|Medium|
1313
|3|[Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)|[JavaScript](./src/longest-substring-without-repeating-characters/res.js)|Medium|
14+
|4|[Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)|[JavaScript](./src/median-of-two-sorted-arrays/res.js)|Hard|
1415
|5|[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)|[JavaScript](./src/longest-palindromic-substring/res.js)|Medium|
1516
|6|[ZigZag Conversion](https://leetcode.com/problems/zigzag-conversion/)|[JavaScript](./src/zigzag-conversion/res.js)|Medium|
1617
|7|[Reverse Integer](https://leetcode.com/problems/reverse-integer/)|[JavaScript](./src/reverse-integer/res.js)|Easy|
@@ -70,6 +71,7 @@ This is the solutions collection of my LeetCode submissions, most of them are pr
7071
|162|[Find Peak Element](https://leetcode.com/problems/find-peak-element/)|[JavaScript](./src/find-peak-element/res.js)|Medium|
7172
|164|[Maximum Gap](https://leetcode.com/problems/maximum-gap/)|[JavaScript](./src/maximum-gap/res.js)|Hard|
7273
|165|[Compare Version Numbers](https://leetcode.com/problems/compare-version-numbers/)|[JavaScript](./src/compare-version-numbers/res.js)|Medium|
74+
|169|[Majority Element](https://leetcode.com/problems/majority-element/)|[JavaScript](./src/majority-element/res.js)|Easy|
7375
|175|[Combine Two Tables](https://leetcode.com/problems/combine-two-tables/)|[SQL](./src/combine-two-tables/res.txt)|Easy|
7476
|176|[Second Highest Salary](https://leetcode.com/problems/second-highest-salary/)|[SQL](./src/second-highest-salary/res.txt)|Easy|
7577
|177|[Nth Highest Salary](https://leetcode.com/problems/nth-highest-salary/)|[SQL](./src/nth-highest-salary/res.txt)|Medium|
@@ -86,6 +88,7 @@ This is the solutions collection of my LeetCode submissions, most of them are pr
8688
|207|[Course Schedule](https://leetcode.com/problems/course-schedule/)|[JavaScript](./src/course-schedule/res.js)|Medium|
8789
|209|[Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/)|[JavaScript](./src/minimum-size-subarray-sum/res.js)|Medium|
8890
|210|[Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)|[JavaScript](./src/course-schedule-ii/res.js)|Medium|
91+
|215|[Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)|[JavaScript](./src/kth-largest-element-in-an-array/res.js)|Medium|
8992
|217|[Contains Duplicate](https://leetcode.com/problems/contains-duplicate/)|[JavaScript](./src/contains-duplicate/res.js)|Easy|
9093
|219|[Contains Duplicate II](https://leetcode.com/problems/contains-duplicate-ii/)|[JavaScript](./src/contains-duplicate-ii/res.js)|Easy|
9194
|220|[Contains Duplicate III](https://leetcode.com/problems/contains-duplicate-iii/)|[JavaScript](./src/contains-duplicate-iii/res.js)|Medium|
@@ -108,6 +111,7 @@ This is the solutions collection of my LeetCode submissions, most of them are pr
108111
|315|[Count of Smaller Numbers After Self](https://leetcode.com/problems/count-of-smaller-numbers-after-self/) <sup>*</sup>|[JavaScript](./src/count-of-smaller-numbers-after-self/res.js)|Hard|
109112
|327|[Count of Range Sum](https://leetcode.com/problems/count-of-range-sum/)|[JavaScript](./src/count-of-range-sum/res.js)|Hard|
110113
|334|[Increasing Triplet Subsequence](https://leetcode.com/problems/increasing-triplet-subsequence/)|[JavaScript](./src/increasing-triplet-subsequence/res.js)|Medium|
114+
|340|[Longest Substring with At Most K Distinct Characters](https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/)|[JavaScript](./src/longest-substring-with-at-most-k-distinct-characters/res.js)|Hard|
111115
|342|[Power of Four](https://leetcode.com/problems/power-of-four/)|[JavaScript](./src/power-of-four/res.js)|Easy|
112116
|344|[Reverse String](https://leetcode.com/problems/reverse-string/)|[JavaScript](./src/reverse-string/res.js)|Easy|
113117
|349|[Intersection of Two Arrays](https://leetcode.com/problems/intersection-of-two-arrays/)|[JavaScript](./src/intersection-of-two-arrays/res.js)|Easy|
@@ -116,9 +120,11 @@ This is the solutions collection of my LeetCode submissions, most of them are pr
116120
|374|[Guess Number Higher or Lower](https://leetcode.com/problems/guess-number-higher-or-lower/)|[JavaScript](./src/guess-number-higher-or-lower/res.py)|Easy|
117121
|376|[Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/)|[JavaScript](./src/wiggle-subsequence/res.js)|Medium|
118122
|384|[Shuffle an Array](https://leetcode.com/problems/shuffle-an-array/)|[JavaScript](./src/shuffle-an-array/res.js)|Medium|
123+
|395|[Longest Substring with At Least K Repeating Characters](https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/)|[JavaScript](./src/longest-substring-with-at-least-k-repeating-characters/res.js)|Medium|
119124
|404|[Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/)|[JavaScript](./src/sum-of-left-leaves/res.js)|Easy|
120125
|413|[Arithmetic Slices](https://leetcode.com/problems/arithmetic-slices/)|[JavaScript](./src/arithmetic-slices/res.js)|Medium|
121126
|416|[Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)|[JavaScript](./src/partition-equal-subset-sum/res.js)|Medium|
127+
|424|[Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)|[JavaScript](./src/longest-repeating-character-replacement/res.js)|Medium|
122128
|434|[Number of Segments in a String](https://leetcode.com/problems/number-of-segments-in-a-string/)|[JavaScript](./src/number-of-segments-in-a-string/res.js)|Easy|
123129
|486|[Predict the Winner](https://leetcode.com/problems/predict-the-winner/)|[JavaScript](./src/predict-the-winner/res.js)|Medium|
124130
|494|[Target Sum](https://leetcode.com/problems/target-sum/)|[JavaScript](./src/target-sum/res.js)|Medium|
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
/**
2+
*@param {number[]} nums
3+
*@param {number} k
4+
*@return {number}
5+
*/
6+
varfindKthLargest=function(nums,k){
7+
constlen=nums.length;
8+
consttarget=len-k;
9+
letleft=0,right=len-1;
10+
11+
constswap=(a,b)=>{
12+
consttemp=nums[a];
13+
nums[a]=nums[b];
14+
nums[b]=temp;
15+
}
16+
17+
constpartition=(start,end)=>{
18+
constpivot=nums[left];
19+
letlindex=left;
20+
21+
for(leti=left+1;i<=end;i++){
22+
constelement=nums[i];
23+
if(element<pivot){
24+
swap(++lindex,i);
25+
}
26+
}
27+
28+
swap(lindex,left);
29+
returnlindex;
30+
}
31+
32+
while(true){
33+
letindex=partition(left,right);
34+
if(index===target){
35+
returnnums[index];
36+
}elseif(index<target){
37+
left=index+1;
38+
}else{
39+
right=index-1;
40+
}
41+
}
42+
};
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
/**
2+
*@param {string} s
3+
*@param {number} k
4+
*@return {number}
5+
*/
6+
varcharacterReplacement=function(s,k){
7+
constlen=s.length;
8+
letmax=0;
9+
letstrdict={};
10+
letleft=0,right=0;
11+
12+
for(;right<len;right++){
13+
conste=s[right];
14+
15+
if(strdict[e]!==undefined){
16+
strdict[e]+=1;
17+
}else{
18+
strdict[e]=1;
19+
}
20+
21+
letcurMaxStr='';
22+
Object.keys(strdict).map(ele=>{
23+
if(strdict[ele]>(strdict[curMaxStr]||0)){
24+
curMaxStr=ele;
25+
}
26+
});
27+
28+
while(right-left+1-strdict[curMaxStr]>k){
29+
strdict[s[left]]-=1;
30+
left+=1;
31+
32+
Object.keys(strdict).map(ele=>{
33+
if(strdict[ele]>strdict[curMaxStr]){
34+
curMaxStr=ele;
35+
}
36+
});
37+
}
38+
39+
max=Math.max(max,right-left+1);
40+
}
41+
42+
returnmax;
43+
};
Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
/**
2+
* 超时 - 分治方法
3+
*@param {string} s
4+
*@param {number} k
5+
*@return {number}
6+
*/
7+
varlongestSubstring=function(s,k){
8+
constlen=s.length;
9+
if(len<k)return0;
10+
11+
constcount=(start,end)=>{
12+
if(end-start+1<k)return0;
13+
14+
conststrdict={};
15+
letnumOfLessThanK=0;
16+
for(leti=start;i<=end;i++){
17+
conste=s[i];
18+
if(strdict[e]===undefined){
19+
strdict[e]=1;
20+
numOfLessThanK+=1;
21+
}else{
22+
strdict[e]+=1;
23+
if(strdict[e]===k){
24+
numOfLessThanK-=1;
25+
}
26+
};
27+
}
28+
29+
if(!numOfLessThanK)returnend-start+1;
30+
while(end-start+1<k&&strdict[start]<k){
31+
start++;
32+
}
33+
while(end-start+1<k&&strdict[end]<k){
34+
end--;
35+
}
36+
if(end-start+1<k)return0;
37+
38+
for(leti=start;i<=end;i++){
39+
conste=s[i];
40+
if(strdict[e]<k){
41+
letnext=i+1;
42+
while(strdict[next]<k&&next<end)next++;
43+
returnMath.max(count(start,i-1),count(next,end));
44+
}
45+
}
46+
47+
returnend-start+1;
48+
}
49+
50+
returncount(0,len-1);
51+
};
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
constlengthOfLongestSubstringTwoDistinct=(s,k)=>{
2+
constlen=s.length;
3+
letstart=0,max=0,strdict={};
4+
5+
for(leti=0;i<len;i++){
6+
conste=s[i];
7+
8+
if(strdict[e]!==undefined){
9+
strdict[e].push(i);
10+
}else{
11+
strdict[e]=[i];
12+
}
13+
14+
while(Object.keys(strdict).length>k){
15+
letdelElement=strdict[e[start]];
16+
17+
if(delElement.length===1){
18+
deletestrdict[e[start]];
19+
}else{
20+
strdict[e[start]].shift();
21+
}
22+
start+=1;
23+
}
24+
25+
max=Math.max(max,i-start+1);
26+
}
27+
28+
returnmax;
29+
}

‎src/longest-substring-without-repeating-characters/res.js

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -67,4 +67,29 @@ let lengthOfLongestSubstring = function(s) {
6767
}
6868

6969
returnmaxLen;
70-
};
70+
};
71+
72+
/**
73+
* 滑动窗口
74+
*@param {*} s
75+
*/
76+
letlengthOfLongestSubstring_2=function(s){
77+
letstrlen=s.length;
78+
letstart=0;
79+
letstrdict={};
80+
letmax=0;
81+
82+
for(leti=0;i<strlen;i++){
83+
conste=s[i];
84+
85+
if(strdict[e]!==undefined&&strdict[e]>=start){
86+
start=strdict[e]+1;
87+
}else{
88+
constcurLen=i-start+1;
89+
max=Math.max(curLen,max);
90+
}
91+
92+
strdict[e]=i;
93+
}
94+
returnmax;
95+
}

‎src/majority-element/res.js

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/**
2+
* 求众数
3+
*@param {number[]} nums
4+
*@return {number}
5+
*/
6+
varmajorityElement=function(nums){
7+
constlen=nums.length;
8+
if(len===1)returnnums[0];
9+
10+
constgetCount=(m,left,right)=>{
11+
letcount=0;
12+
for(leti=left;i<=right;i++){
13+
if(nums[i]===m)count+=1;
14+
}
15+
16+
returncount;
17+
}
18+
19+
constgetMajority=(left,right)=>{
20+
if(left===right)returnnums[left];
21+
constmid=(left+right)>>1;
22+
23+
constleftMajority=getMajority(left,mid);
24+
constrightMajority=getMajority(mid+1,right);
25+
26+
if(leftMajority===rightMajority)returnleftMajority;
27+
28+
constlmCount=getCount(leftMajority,left,right);
29+
constrmCount=getCount(rightMajority,left,right);
30+
31+
returnlmCount>rmCount ?leftMajority :rightMajority;
32+
}
33+
34+
returngetMajority(0,len-1);
35+
};

‎src/maximum-subarray/res.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,4 +19,4 @@ var maxSubArray = function(nums) {
1919
}
2020

2121
returnans;
22-
};
22+
};

‎src/maximum-subarray/res.py

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
2+
# 论坛解法 - 分治法
3+
# https://leetcode-cn.com/problems/maximum-subarray/solution/bao-li-qiu-jie-by-pandawakaka/
4+
5+
classSolution:
6+
defmaxSubArray(self,nums):
7+
"""
8+
:type nums: List[int]
9+
:rtype: int
10+
"""
11+
n=len(nums)
12+
#递归终止条件
13+
ifn==1:
14+
returnnums[0]
15+
else:
16+
#递归计算左半边最大子序和
17+
max_left=self.maxSubArray(nums[0:len(nums)//2])
18+
#递归计算右半边最大子序和
19+
max_right=self.maxSubArray(nums[len(nums)//2:len(nums)])
20+
21+
#计算中间的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加
22+
max_l=nums[len(nums)//2-1]
23+
tmp=0
24+
foriinrange(len(nums)//2-1,-1,-1):
25+
tmp+=nums[i]
26+
max_l=max(tmp,max_l)
27+
max_r=nums[len(nums)//2]
28+
tmp=0
29+
foriinrange(len(nums)//2,len(nums)):
30+
tmp+=nums[i]
31+
max_r=max(tmp,max_r)
32+
#返回三个中的最大值
33+
returnmax(max_right,max_left,max_l+max_r)
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
/**
2+
*@param {number[]} nums1
3+
*@param {number[]} nums2
4+
*@return {number}
5+
*/
6+
varfindMedianSortedArrays=function(nums1,nums2){
7+
constlen1=nums1.length;
8+
constlen2=nums2.length;
9+
10+
letleft=(len1+len2+1)>>1;
11+
letright=(len1+len2+2)>>1;
12+
13+
constgetMedian=(n1,s1,e1,n2,s2,e2,k)=>{
14+
constl1=e1-s1+1;
15+
constl2=e2-s2+1;
16+
17+
if(l1>l2)returngetMedian(n2,s2,e2,n1,s1,e1,k);
18+
if(l1===0)returnn2[s2+k-1];
19+
20+
if(k==1)returnMath.min(n1[s1],n2[s2]);
21+
22+
leti=s1+Math.min(l1,k>>1)-1;
23+
letj=s2+Math.min(l2,k>>1)-1;
24+
25+
if(n1[i]>n2[j]){
26+
returngetMedian(n1,s1,e1,n2,j+1,e2,k-(j-s2+1));
27+
}else{
28+
returngetMedian(n1,i+1,e1,n2,s2,e2,k-(i-s1+1));
29+
}
30+
}
31+
32+
return(getMedian(nums1,0,len1-1,nums2,0,len2-1,left)+getMedian(nums1,0,len1-1,nums2,0,len2-1,right))/2;
33+
};

0 commit comments

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