Skip to content

Commit fd4a74a

Browse files
stonehankstonehank
committed
update
1 parent ab9e139 commit fd4a74a

File tree

30 files changed

+692
-359
lines changed

30 files changed

+692
-359
lines changed

‎1-100/33.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -65,7 +65,7 @@
6565
* @return {number}
6666
*/
6767
var search = function(nums, target) {
68-
68+
if(nums.length===0)return -1
6969
let rotateIdx=findPivot(nums)
7070
7171
if(target>=nums[0] && target<=nums[rotateIdx-1]){

‎1-100/74.md

Lines changed: 17 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -93,20 +93,25 @@ var searchMatrix = function(matrix, target) {
9393
* @return {boolean}
9494
*/
9595
var searchMatrix = function(matrix, target) {
96-
let searchRow=null
97-
for(let i=0;i<matrix.length;i++){
98-
let v=matrix[i][matrix[i].length-1]
99-
if(target<=v){
100-
searchRow=i
101-
break
102-
}
103-
}
104-
if(searchRow==null)return false
105-
for(let i=0;i<matrix[searchRow].length;i++){
106-
if(matrix[searchRow][i]===target)return true
96+
if(matrix.length===0)return false
97+
let m=matrix.length,n=matrix[0].length
98+
let lo=0,hi=m*n-1
99+
while(lo<=hi){
100+
let mid=Math.floor((lo+hi)/2)
101+
let [x,y]=to2(mid)
102+
let midV=matrix[x][y]
103+
if(midV===target)return true
104+
else if(midV<target)lo=mid+1
105+
else hi=mid-1
107106
}
108-
109107
return false
108+
109+
function to2(x){
110+
return [Math.floor(x/n),x%n]
111+
}
112+
function to1([x,y]){
113+
return x*m+y
114+
}
110115
};
111116
```
112117

‎1-100/76.md

Lines changed: 22 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -55,47 +55,33 @@
5555
遍历完毕后，返回区间`[start,end]`，如果不存在，则返回`''`。
5656

5757
```
58+
/**
59+
* @param {string} s
60+
* @param {string} t
61+
* @return {string}
62+
*/
5863
var minWindow = function(s, t) {
59-
let hash={},targetLen=0
60-
for(let i=0;i<t.length;i++){
61-
if(!hash[t[i]]){
62-
hash[t[i]]=1
63-
targetLen++
64-
}
65-
else hash[t[i]]++
64+
let count=Array(128).fill(0)
65+
let tLen=t.length
66+
for(let w of t){
67+
let code=w.charCodeAt(0)
68+
count[code]++
6669
}
67-
let left=null,complete=0,minLen=Infinity,begin=0,end=0
68-
for(let i=0;i<s.length+1;i++){
69-
if(complete===targetLen){
70-
let check=true
71-
while(check){
72-
check=false
73-
if(hash[s[left]]<0){
74-
check=true
75-
hash[s[left++]]++
76-
}
77-
if(left<s.length && hash[s[left]]==null){
78-
check=true
79-
left++
80-
}
81-
}
82-
if(i-left<minLen){
83-
begin=left
84-
end=i
85-
minLen=i-left
70+
// console.log(count)
71+
let preID=0,start=0,end=Infinity,curLen=0
72+
for(let i=0;i<s.length;i++){
73+
if(count[s.charCodeAt(i)]-->0){
74+
tLen--
75+
}
76+
while(tLen===0){
77+
if(i-preID<end-start){
78+
end=i+1
79+
start=preID
8680
}
87-
hash[s[left++]]++
88-
complete--
81+
if(count[s.charCodeAt(preID++)]++==0) tLen++
8982
}
90-
if(i===s.length)break
91-
let letter=s[i]
92-
if(hash[letter]!=null){
93-
if(left==null)left=i
94-
hash[letter]--
95-
if(hash[letter]===0)complete++
96-
}else continue
9783
}
98-
return left!=null ? s.substring(begin,end): ""
84+
return end===Infinity?'':s.substring(start,end)
9985
};
10086
```
10187

‎1-100/78.md

Lines changed: 11 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -45,20 +45,18 @@
4545
* @return {number[][]}
4646
*/
4747
var subsets = function(nums) {
48-
let result=[]
49-
let temp=[]
50-
backtrack(result,0,temp,nums)
51-
return result
52-
53-
function backtrack(result,start,temp,nums){
54-
// if(start>=nums.length)return
55-
result.push(temp.slice())
56-
for(let i=start;i<nums.length;i++){
57-
temp.push(nums[i])
58-
backtrack(result,i+1,temp,nums)
59-
temp.pop()
60-
}
48+
let result=[]
49+
backtrack(0,[])
50+
return result
51+
52+
function backtrack(start,temp){
53+
result.push(temp.slice())
54+
for(let i=start;i<nums.length;i++){
55+
temp.push(nums[i])
56+
backtrack(i+1,temp)
57+
temp.pop()
6158
}
59+
}
6260
};
6361
```
6462

‎1-100/79.md

Lines changed: 18 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -51,37 +51,28 @@ board =
5151
* @return {boolean}
5252
*/
5353
var exist = function(board, word) {
54-
if(word==="")return true
55-
if(board.length===0)return false
56-
let found=false
57-
function getAdj(board,x,y){
58-
let adj=[]
59-
if(x>0)adj.push([x-1,y])
60-
if(y>0)adj.push([x,y-1])
61-
if(x<board.length-1)adj.push([x+1,y])
62-
if(y<board[0].length-1)adj.push([x,y+1])
63-
return adj
64-
}
65-
function dfs(board,x,y,word,idx){
66-
if(board[x][y]!==word[idx])return
67-
if(idx===word.length-1)return found=true
68-
let adjs=getAdj(board,x,y)
69-
for(let [row,col] of adjs){
70-
board[x][y]="."
71-
dfs(board,row,col,word,idx+1)
72-
if(found)return
73-
board[x][y]=word[idx]
54+
let m=board.length,n=board[0].length
55+
let moves=[[-1,0],[1,0],[0,1],[0,-1]]
56+
let uniq=0
57+
function dfs([x,y],id){
58+
if(id===word.length)return true
59+
if(x<0 || y<0 || x>=m || y>=n)return
60+
if(board[x][y]!==word[id])return
61+
if(board[x][y]==='*')return
62+
let tmp=board[x][y]
63+
board[x][y]='*'
64+
for(let [dx,dy] of moves){
65+
if(dfs([x+dx,y+dy],id+1))return true
7466
}
67+
board[x][y]=tmp
7568
}
76-
let firstL=word[0]
77-
for(let i=0;i<board.length;i++){
78-
for(let j=0;j<board[i].length;j++){
79-
if(board[i][j]!==firstL)continue
80-
dfs(board,i,j,word,0)
81-
if(found)return found
69+
let start=word[0]
70+
for(let i=0;i<m;i++){
71+
for(let j=0;j<n;j++){
72+
if(dfs([i,j],0))return true
8273
}
8374
}
84-
return found
75+
return false
8576
};
8677
```
8778

‎1-100/80.md

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -83,13 +83,13 @@ for (int i = 0; i < len; i++) {
8383
* @return {number}
8484
*/
8585
var removeDuplicates = function(nums) {
86-
let k=0
87-
for(let i=0;i<nums.length;i++){
88-
if(i<2 || nums[i]>nums[k-2]){
89-
nums[k++]=nums[i]
90-
}
86+
let k=0
87+
for(let i=0;i<nums.length;i++){
88+
if(i<2 || nums[i]>nums[k-2]){
89+
nums[k++]=nums[i]
9190
}
92-
return k
91+
}
92+
return k
9393
};
9494
```
9595

‎1-100/81.md

Lines changed: 14 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -74,26 +74,29 @@ while(nums[rotateIdx]>=nums[rotateIdx-1]){
7474
*/
7575
var search = function(nums, target) {
7676
if(nums.length===0)return false
77-
function findPivot(arr){
78-
let lo=0,hi=arr.length-1
79-
while(lo<hi){
80-
let mid=Math.floor((lo+hi)/2)
81-
if(arr[mid]>=arr[0]) lo=mid+1
82-
else hi=mid
83-
}
84-
return lo
85-
}
8677
let rotateIdx=findPivot(nums)
87-
// console.log(rotateIdx)
78+
79+
/* 额外增加，消除重复值*/
8880
while(nums[rotateIdx]>=nums[rotateIdx-1]){
8981
rotateIdx=rotateIdx-1
9082
}
91-
if(nums[rotateIdx]>nums[rotateIdx-1])rotateIdx=nums.length
83+
9284
if(target>=nums[0] && target<=nums[rotateIdx-1]){
9385
return bs(nums,0,rotateIdx-1)
9486
}else{
9587
return bs(nums,rotateIdx,nums.length-1)
9688
}
89+
90+
function findPivot(arr){
91+
let lo=0,hi=arr.length-1
92+
while(lo<hi){
93+
let mid=Math.floor((lo+hi)/2)
94+
if(arr[mid]>=arr[0]) lo=mid+1
95+
else hi=mid
96+
}
97+
return lo
98+
}
99+
97100
function bs(nums,lo,hi){
98101
while(lo<=hi){
99102
let mid=Math.floor((lo+hi)/2)

‎1-100/84.md

Lines changed: 8 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -81,28 +81,15 @@
8181
* @return {number}
8282
*/
8383
var largestRectangleArea = function(heights) {
84-
let stack=[],maxArea=0,i=0,area=0
85-
for(;i<heights.length;i++){
86-
let h=heights[i]
87-
if(stack.length===0)stack.push(i)
88-
else{
89-
let last=stack[stack.length-1]
90-
if(h<heights[last]){
91-
stack.pop()
92-
if(stack.length===0)area=i*heights[last]
93-
else area=(i-stack[stack.length-1]-1)*heights[last]
94-
i--
95-
}else{
96-
stack.push(i)
97-
}
84+
let stack=[-1],maxArea=0
85+
for(let i=0;i<=heights.length;i++){
86+
while(stack.length>1 && (i===heights.length || heights[i]<heights[stack[stack.length-1]])){
87+
let lastId=stack.pop(),
88+
lastH=heights[lastId],
89+
width=i-stack[stack.length-1]-1
90+
maxArea=Math.max(maxArea,width*lastH)
9891
}
99-
maxArea=Math.max(maxArea,area)
100-
}
101-
while(stack.length!==0){
102-
let last=stack.pop()
103-
if(stack.length===0)area=i*heights[last]
104-
else area=(i-stack[stack.length-1]-1)*heights[last]
105-
maxArea=Math.max(maxArea,area)
92+
stack.push(i)
10693
}
10794
return maxArea
10895
};

‎1-100/85.md

Lines changed: 9 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -56,28 +56,17 @@
5656
* @return {number}
5757
*/
5858
var maximalRectangle = function(matrix) {
59-
function getMaxArea(arr){
60-
// console.log(arr)
61-
let stack=[],tail=0,maxArea=0,area=0
62-
for(;tail<arr.length;){
63-
let cur=arr[tail]
64-
if(stack.length===0 || cur>=arr[stack[stack.length-1]]){
65-
stack.push(tail++)
66-
}else{
67-
let pre=stack.pop()
68-
if(stack.length===0) area=arr[pre]*tail
69-
else area=arr[pre]*(tail-stack[stack.length-1]-1)
70-
maxArea=Math.max(area,maxArea)
59+
function getMaxArea(heights){
60+
let stack=[-1],maxArea=0
61+
for(let i=0;i<=heights.length;i++){
62+
while(stack.length>1 && (i===heights.length || heights[i]<heights[stack[stack.length-1]])){
63+
let lastId=stack.pop(),
64+
lastH=heights[lastId],
65+
width=i-stack[stack.length-1]-1
66+
maxArea=Math.max(maxArea,width*lastH)
7167
}
68+
stack.push(i)
7269
}
73-
// console.log(maxArea,stack)
74-
while(stack.length!==0){
75-
let pre=stack.pop()
76-
if(stack.length===0) area=arr[pre]*tail
77-
else area=arr[pre]*(tail-stack[stack.length-1]-1)
78-
maxArea=Math.max(area,maxArea)
79-
}
80-
// console.log(maxArea)
8170
return maxArea
8271
}
8372

‎1-100/88.md

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -52,9 +52,8 @@ nums2 = [2,5,6], n = 3
5252
* @return {void} Do not return anything, modify nums1 in-place instead.
5353
*/
5454
var merge = function(nums1, m, nums2, n) {
55-
56-
for (let i = m - 1; i > -1; i--) {
57-
nums1[i + n] = nums1[i];
55+
for(let i=m-1;i>=0;i--){
56+
nums1[i+n]=nums1[i]
5857
}
5958
let i=n,j=0,id=0
6059
while(i<m+n || j<n){

0 commit comments

Comments
 (0)