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

Commit1b5dc5f

Browse files
author
luzhipeng
committed
feat: 部分文件增加内容
1 parent8bdef01 commit1b5dc5f

18 files changed

+829
-12
lines changed

‎152.maximum-product-subarray.js

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
/*
2+
*@lc app=leetcode id=152 lang=javascript
3+
*
4+
* [152] Maximum Product Subarray
5+
*
6+
* https://leetcode.com/problems/maximum-product-subarray/description/
7+
*
8+
* algorithms
9+
* Medium (28.61%)
10+
* Total Accepted: 202.8K
11+
* Total Submissions: 700K
12+
* Testcase Example: '[2,3,-2,4]'
13+
*
14+
* Given an integer array nums, find the contiguous subarray within an array
15+
* (containing at least one number) which has the largest product.
16+
*
17+
* Example 1:
18+
*
19+
*
20+
* Input: [2,3,-2,4]
21+
* Output: 6
22+
* Explanation: [2,3] has the largest product 6.
23+
*
24+
*
25+
* Example 2:
26+
*
27+
*
28+
* Input: [-2,0,-1]
29+
* Output: 0
30+
* Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
31+
*
32+
*/
33+
/**
34+
*@param {number[]} nums
35+
*@return {number}
36+
*/
37+
varmaxProduct=function(nums){
38+
// let max = nums[0];
39+
// let temp = null;
40+
// for(let i = 0; i < nums.length; i++) {
41+
// temp = nums[i];
42+
// max = Math.max(temp, max);
43+
// for(let j = i + 1; j < nums.length; j++) {
44+
// temp *= nums[j];
45+
// max = Math.max(temp, max);
46+
// }
47+
// }
48+
49+
// return max;
50+
letmax=nums[0];
51+
letmin=nums[0];
52+
letres=nums[0];
53+
54+
for(leti=1;i<nums.length;i++){
55+
lettmp=min;
56+
min=Math.min(nums[i],Math.min(max*nums[i],min*nums[i]));// 取最小
57+
max=Math.max(nums[i],Math.max(max*nums[i],tmp*nums[i]));/// 取最大
58+
res=Math.max(res,max);
59+
}
60+
returnres;
61+
};

‎189.rotate-array.js

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
/*
2+
*@lc app=leetcode id=189 lang=javascript
3+
*
4+
* [189] Rotate Array
5+
*
6+
* https://leetcode.com/problems/rotate-array/description/
7+
*
8+
* algorithms
9+
* Easy (29.07%)
10+
* Total Accepted: 287.3K
11+
* Total Submissions: 966.9K
12+
* Testcase Example: '[1,2,3,4,5,6,7]\n3'
13+
*
14+
* Given an array, rotate the array to the right by k steps, where k is
15+
* non-negative.
16+
*
17+
* Example 1:
18+
*
19+
*
20+
* Input: [1,2,3,4,5,6,7] and k = 3
21+
* Output: [5,6,7,1,2,3,4]
22+
* Explanation:
23+
* rotate 1 steps to the right: [7,1,2,3,4,5,6]
24+
* rotate 2 steps to the right: [6,7,1,2,3,4,5]
25+
* rotate 3 steps to the right: [5,6,7,1,2,3,4]
26+
*
27+
*
28+
* Example 2:
29+
*
30+
*
31+
* Input: [-1,-100,3,99] and k = 2
32+
* Output: [3,99,-1,-100]
33+
* Explanation:
34+
* rotate 1 steps to the right: [99,-1,-100,3]
35+
* rotate 2 steps to the right: [3,99,-1,-100]
36+
*
37+
*
38+
* Note:
39+
*
40+
*
41+
* Try to come up as many solutions as you can, there are at least 3 different
42+
* ways to solve this problem.
43+
* Could you do it in-place with O(1) extra space?
44+
*
45+
*/
46+
/**
47+
*@param {number[]} nums
48+
*@param {number} k
49+
*@return {void} Do not return anything, modify nums in-place instead.
50+
*/
51+
varrotate=function(nums,k){
52+
// 就像扩容一样操作
53+
k=k%nums.length;
54+
constn=nums.length;
55+
56+
for(leti=nums.length-1;i>=0;i--){
57+
nums[i+k]=nums[i];
58+
}
59+
60+
for(leti=0;i<k;i++){
61+
nums[i]=nums[n+i];
62+
}
63+
nums.length=n;
64+
};

‎217.contains-duplicate.js

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
/*
2+
*@lc app=leetcode id=217 lang=javascript
3+
*
4+
* [217] Contains Duplicate
5+
*
6+
* https://leetcode.com/problems/contains-duplicate/description/
7+
*
8+
* algorithms
9+
* Easy (50.92%)
10+
* Total Accepted: 324K
11+
* Total Submissions: 628.5K
12+
* Testcase Example: '[1,2,3,1]'
13+
*
14+
* Given an array of integers, find if the array contains any duplicates.
15+
*
16+
* Your function should return true if any value appears at least twice in the
17+
* array, and it should return false if every element is distinct.
18+
*
19+
* Example 1:
20+
*
21+
*
22+
* Input: [1,2,3,1]
23+
* Output: true
24+
*
25+
* Example 2:
26+
*
27+
*
28+
* Input: [1,2,3,4]
29+
* Output: false
30+
*
31+
* Example 3:
32+
*
33+
*
34+
* Input: [1,1,1,3,3,4,3,2,4,2]
35+
* Output: true
36+
*
37+
*/
38+
/**
39+
*@param {number[]} nums
40+
*@return {boolean}
41+
*/
42+
varcontainsDuplicate=function(nums){
43+
// 1. 暴力两层循环两两比较， 时间复杂度O(n^2) 空间复杂度O(1)
44+
45+
// 2. 先排序，之后比较前后元素是否一致即可，一层循环即可，如果排序使用的比较排序的话时间复杂度O(nlogn) 空间复杂度O(1)
46+
47+
// 3. 用hashmap ，时间复杂度O(n) 空间复杂度O(n)
48+
constvisited={};
49+
for(leti=0;i<nums.length;i++){
50+
if(visited[nums[i]])returntrue;
51+
visited[nums[i]]=true;
52+
}
53+
returnfalse;
54+
};
55+

‎23.merge-k-sorted-lists.js

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
/*
2+
*@lc app=leetcode id=23 lang=javascript
3+
*
4+
* [23] Merge k Sorted Lists
5+
*
6+
* https://leetcode.com/problems/merge-k-sorted-lists/description/
7+
*
8+
* algorithms
9+
* Hard (33.14%)
10+
* Total Accepted: 373.7K
11+
* Total Submissions: 1.1M
12+
* Testcase Example: '[[1,4,5],[1,3,4],[2,6]]'
13+
*
14+
* Merge k sorted linked lists and return it as one sorted list. Analyze and
15+
* describe its complexity.
16+
*
17+
* Example:
18+
*
19+
*
20+
* Input:
21+
* [
22+
* 1->4->5,
23+
* 1->3->4,
24+
* 2->6
25+
* ]
26+
* Output: 1->1->2->3->4->4->5->6
27+
*
28+
*
29+
*/
30+
functionmergeTwoLists(l1,l2){
31+
constdummyHead={};
32+
letcurrent=dummyHead;
33+
// 1 -> 3 -> 5
34+
// 2 -> 4 -> 6
35+
while(l1!==null&&l2!==null){
36+
if(l1.val<l2.val){
37+
current.next=l1;// 把小的添加到结果链表
38+
current=current.next;// 移动结果链表的指针
39+
l1=l1.next;// 移动小的那个链表的指针
40+
}else{
41+
current.next=l2;
42+
current=current.next;
43+
l2=l2.next;
44+
}
45+
}
46+
47+
if(l1===null){
48+
current.next=l2;
49+
}else{
50+
current.next=l1;
51+
}
52+
returndummyHead.next;
53+
}
54+
/**
55+
* Definition for singly-linked list.
56+
* function ListNode(val) {
57+
* this.val = val;
58+
* this.next = null;
59+
* }
60+
*/
61+
/**
62+
*@param {ListNode[]} lists
63+
*@return {ListNode}
64+
*/
65+
varmergeKLists=function(lists){
66+
// 图参考： https://zhuanlan.zhihu.com/p/61796021
67+
if(lists.length===0)returnnull;
68+
if(lists.length===1)returnlists[0];
69+
if(lists.length===2){
70+
returnmergeTwoLists(lists[0],lists[1]);
71+
}
72+
73+
constmid=lists.length>>1;
74+
constl1=[];
75+
for(leti=0;i<mid;i++){
76+
l1[i]=lists[i];
77+
}
78+
79+
constl2=[];
80+
for(leti=mid,j=0;i<lists.length;i++,j++){
81+
l2[j]=lists[i];
82+
}
83+
84+
returnmergeTwoLists(mergeKLists(l1),mergeKLists(l2));
85+
};
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/*
2+
*@lc app=leetcode id=236 lang=javascript
3+
*
4+
* [236] Lowest Common Ancestor of a Binary Tree
5+
*
6+
* https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
7+
*
8+
* algorithms
9+
* Medium (35.63%)
10+
* Total Accepted: 267.3K
11+
* Total Submissions: 729.2K
12+
* Testcase Example: '[3,5,1,6,2,0,8,null,null,7,4]\n5\n1'
13+
*
14+
* Given a binary tree, find the lowest common ancestor (LCA) of two given
15+
* nodes in the tree.
16+
*
17+
* According to the definition of LCA on Wikipedia: “The lowest common ancestor
18+
* is defined between two nodes p and q as the lowest node in T that has both p
19+
* and q as descendants (where we allow a node to be a descendant of itself).”
20+
*
21+
* Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]
22+
*
23+
*
24+
*
25+
* Example 1:
26+
*
27+
*
28+
* Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
29+
* Output: 3
30+
* Explanation: The LCA of nodes 5 and 1 is 3.
31+
*
32+
*
33+
* Example 2:
34+
*
35+
*
36+
* Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
37+
* Output: 5
38+
* Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant
39+
* of itself according to the LCA definition.
40+
*
41+
*
42+
*
43+
*
44+
* Note:
45+
*
46+
*
47+
* All of the nodes' values will be unique.
48+
* p and q are different and both values will exist in the binary tree.
49+
*
50+
*
51+
*/
52+
/**
53+
* Definition for a binary tree node.
54+
* function TreeNode(val) {
55+
* this.val = val;
56+
* this.left = this.right = null;
57+
* }
58+
*/
59+
/**
60+
*@param {TreeNode} root
61+
*@param {TreeNode} p
62+
*@param {TreeNode} q
63+
*@return {TreeNode}
64+
*/
65+
varlowestCommonAncestor=function(root,p,q){
66+
if(!root||root===p||root===q)returnroot;
67+
constleft=lowestCommonAncestor(root.left,p,q);
68+
constright=lowestCommonAncestor(root.right,p,q);
69+
if(!left)returnright;// 左子树找不到，返回右子树
70+
if(!right)returnleft;// 右子树找不到，返回左子树
71+
returnroot;// 左右子树分别有一个，则返回root
72+
};

‎238.product-of-array-except-self.js

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
/*
2+
*@lc app=leetcode id=238 lang=javascript
3+
*
4+
* [238] Product of Array Except Self
5+
*
6+
* https://leetcode.com/problems/product-of-array-except-self/description/
7+
*
8+
* algorithms
9+
* Medium (53.97%)
10+
* Total Accepted: 246.5K
11+
* Total Submissions: 451.4K
12+
* Testcase Example: '[1,2,3,4]'
13+
*
14+
* Given an array nums of n integers where n > 1,  return an array output such
15+
* that output[i] is equal to the product of all the elements of nums except
16+
* nums[i].
17+
*
18+
* Example:
19+
*
20+
*
21+
* Input: [1,2,3,4]
22+
* Output: [24,12,8,6]
23+
*
24+
*
25+
* Note: Please solve it without division and in O(n).
26+
*
27+
* Follow up:
28+
* Could you solve it with constant space complexity? (The output array does
29+
* not count as extra space for the purpose of space complexity analysis.)
30+
*
31+
*/
32+
/**
33+
*@param {number[]} nums
34+
*@return {number[]}
35+
*/
36+
varproductExceptSelf=function(nums){
37+
constret=[];
38+
39+
for(leti=0,temp=1;i<nums.length;i++){
40+
ret[i]=temp;
41+
temp*=nums[i];
42+
}
43+
// 此时ret[i]存放的是前i个元素相乘的结果(不包含第i个)
44+
45+
// 如果没有上面的循环的话，
46+
// ret经过下面的循环会变成ret[i]存放的是后i个元素相乘的结果(不包含第i个)
47+
48+
// 我们的目标是ret[i]存放的所有数字相乘的结果(不包含第i个)
49+
50+
// 因此我们只需要对于上述的循环产生的ret[i]基础上运算即可
51+
for(leti=nums.length-1,temp=1;i>=0;i--){
52+
ret[i]*=temp;
53+
temp*=nums[i];
54+
}
55+
returnret;
56+
};

0 commit comments

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