Skip to content

Commit f75c7c0

Browse files
SpongeMaSpongeMa
committed
week01 assignment-1
1 parent 0fd6bbe commit f75c7c0

3 files changed

Lines changed: 247 additions & 1 deletion

File tree

‎Week01/1.twoSum.js‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
/*
2+
* @lc app=leetcode.cn id=1 lang=javascript
3+
*
4+
* [1] 两数之和
5+
*
6+
* https://leetcode-cn.com/problems/two-sum/description/
7+
*
8+
* algorithms
9+
* Easy (48.57%)
10+
* Likes: 8428
11+
* Dislikes: 0
12+
* Total Accepted: 1.1M
13+
* Total Submissions: 2.3M
14+
* Testcase Example: '[2,7,11,15]\n9'
15+
*
16+
* 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
17+
*
18+
* 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
19+
*
20+
*
21+
*
22+
* 示例:
23+
*
24+
* 给定 nums = [2, 7, 11, 15], target = 9
25+
*
26+
* 因为 nums[0] + nums[1] = 2 + 7 = 9
27+
* 所以返回 [0, 1]
28+
*
29+
*
30+
*/
31+
32+
// @lc code=start
33+
/**
34+
* @param {number[]} nums
35+
* @param {number} target
36+
* @return {number[]}
37+
*/
38+
39+
/* @sponge
40+
1.暴力求解,两次遍历
41+
时间复杂度：O(n^2)
42+
空间复杂度：O(1)
43+
*/
44+
var twoSum = function(nums, target) {
45+
for(let i = 0 ;i< nums.length ;i++){
46+
for(let j = i+1 ;j< nums.length ;j++){
47+
if(nums[i]+nums[j]==target)
48+
return [i,j]
49+
}
50+
}
51+
};
52+
53+
/*
54+
2.一遍哈希表
55+
时间复杂度：O(n)
56+
空间复杂度：O(n)
57+
runtime:64ms beats 94.44%
58+
memory usage:34.1MB beats 97.46%
59+
*/
60+
var twoSum = function(nums, target) {
61+
let hash = {};
62+
for(let i = 0;i<nums.length;i++){
63+
let dis = target - nums[i];
64+
if((typeof hash[dis])!=='undefined'){
65+
return [hash[dis],i]
66+
}
67+
hash[nums[i]]=i;
68+
}
69+
};
70+
71+
/*
72+
3.两遍哈希表
73+
runtime:60ms beats 97.79%
74+
memory usage:36.6MB beats 7.628%
75+
时间复杂度：O(n)
76+
空间复杂度：O(n)
77+
*/
78+
var twoSum = function(nums, target) {
79+
if(nums.length === 2) return[0,1];
80+
const len = nums.length;
81+
let hash = {};
82+
//把数组的所有值和对应下标存到哈希表
83+
for(let i = 0;i<len;i++){
84+
hash[nums[i]]=i;
85+
}
86+
//直接找哈希表是否有dis这个值，有则返回对应下标和当前下标
87+
for(let i = 0;i<len;i++){
88+
let dis = target - nums[i];
89+
let found = hash[dis];
90+
if(hash[dis]!==undefined && i!=found){
91+
return [i,found]
92+
}
93+
}
94+
};
95+
// @lc code=end
96+

‎Week01/283-moveZero.js‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
/*
2+
* @lc app=leetcode.cn id=283 lang=javascript
3+
*
4+
* [283] 移动零
5+
*
6+
* https://leetcode-cn.com/problems/move-zeroes/description/
7+
*
8+
* algorithms
9+
* Easy (60.98%)
10+
* Likes: 612
11+
* Dislikes: 0
12+
* Total Accepted: 158.5K
13+
* Total Submissions: 259.3K
14+
* Testcase Example: '[0,1,0,3,12]'
15+
*
16+
* 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
17+
*
18+
* 示例:
19+
*
20+
* 输入: [0,1,0,3,12]
21+
* 输出: [1,3,12,0,0]
22+
*
23+
* 说明:
24+
*
25+
*
26+
* 必须在原数组上操作，不能拷贝额外的数组。
27+
* 尽量减少操作次数。
28+
*
29+
*
30+
*/
31+
32+
// @lc code=start
33+
/**
34+
* @param {number[]} nums
35+
* @return {void} Do not return anything, modify nums in-place instead.
36+
*/
37+
38+
39+
/*
40+
1.倒着循环遍历数组，是零就删除并添加到数组末尾
41+
时间复杂度: O(n)
42+
*/
43+
var moveZeroes = function (nums) {
44+
for (let i = nums.length; i >= 0; i--) {
45+
if (nums[i] === 0) {
46+
nums.splice(i, 1);
47+
nums.push(0);
48+
}
49+
}
50+
};
51+
52+
/*
53+
2.两次遍历，利用双指针，指针j存储当前下标，遍历数组，非0的数就赋值给数组
54+
的当前下标，直到非0的数遍历完，接着将当前下标后的所有位置置0
55+
时间复杂度: O(n)
56+
空间复杂度: O(1)
57+
*/
58+
var moveZeroes = function(nums) {
59+
if(nums == null || nums.length==0) return;
60+
61+
let j=0;
62+
for(let i=0; i< nums.length ; i++){
63+
if(nums[i] != 0 ){
64+
if(i!=j)
65+
nums[j] = nums[i];
66+
j++;
67+
}
68+
}
69+
while(j<nums.length){
70+
nums[j++] = 0;
71+
}
72+
}
73+
74+
/*
75+
3.一次遍历，利用双指针，当遇到非零的数就交换两个数
76+
时间复杂度: O(n)
77+
空间复杂度: O(1)
78+
*/
79+
var moveZeroes = function (nums) {
80+
if (nums.length == 0) return;
81+
82+
let j = 0;
83+
for (let i = 0; i < nums.length; i++) {
84+
if (nums[i] != 0) {
85+
if (i > j) {
86+
nums[j] = nums[i];
87+
nums[i] = 0;
88+
}
89+
j++;
90+
}
91+
}
92+
}
93+
// @lc code=end

‎Week01/NOTE.md‎

Lines changed: 58 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,58 @@
1-
学习笔记
1+
学习笔记
2+
3+
**时间、空间复杂度**
4+
5+
------
6+
7+
主要用**Big O notation**来表示
8+
9+
- O(1): Constant Complexity 常数复杂度
10+
- O(log n): Logarithmic Complexity 对数复杂度
11+
- O(n): Linear Complexity 线性时间复杂度
12+
- O(n^2): N square Complexity 平方
13+
- O(n^3): N cubic Complexity 立方
14+
- O(2^n): Exponential Growth 指数
15+
- O(n!): Factorial 阶乘
16+
17+
18+
19+
### 一维基础数据结构
20+
21+
- 数组array
22+
- 链表linked list
23+
- 跳表skip list
24+
25+
#### **数组array**
26+
27+
| 操作 | 时间复杂度 | 备注 |
28+
| :------ | :--------- | ------------------------------------------------------------ |
29+
| prepend | O(1) | 注：正常情况下应该是O(n)，但是可以进行特殊优化到O(1)。采用的方式是申请稍大一些的内存空，然后再数组最开始预留一部分空间，然后prepend时把第一个下标前移一个位置即可 |
30+
| append | O(1) | |
31+
| loopup | O(1) | |
32+
| insert | O(n) | |
33+
| delete | O(n) | |
34+
35+
#### **链表linked list**
36+
37+
| 操作 | 时间复杂度 | 备注 |
38+
| :------ | :--------- | ---- |
39+
| prepend | O(1) | |
40+
| append | O(1) | |
41+
| loopup | O(n) | |
42+
| insert | O(1) | |
43+
| delete | O(1) | |
44+
45+
#### 跳表skip list
46+
47+
跳表对标的是平衡树（AVL Tree）和二分查找，是一种插入、删除、搜索都是O(log n)的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率高。因此在一些热门的项目里用来代替平衡树，如Redis、LevelDB等。
48+
49+
**注：只能用于元素有序的情况。**
50+
51+
**时间复杂度：**O(log n）
52+
53+
54+
55+
#### **工程中的应用**
56+
57+
- LRU Cache - Linked list
58+
- Redis - Skip List

0 commit comments

Comments
 (0)