算法 | leetcode



两数之和

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

使用JS编写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 基本两个 for 循环
var twoSum = function(nums, target) {
for (i = 0; i < nums.length; i++) {
for (j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
}

// 内层循环查找差值很浪费时间 利用数组就可以减少查询时间
// 创建一个空数组 temp 用于存储
// 使用一层循环,每遍历到 nums 数组的一个元素就计算该元素与 target 之间的差值 dif
// 如果说 temp 中不存在第 dif 个元素,
// 那么就以当前遍历的 nums 数组中第 i 个元素为索引, 当前递增的 i 为元素, 存储进 temp 数组中
// 那么也必定存在一个 dif, 与之前的 num[i] 相同
// 而此时以 dif 作为索引在 temp 数组中当然可以查到
// 因此输出之前的 i, 与现在的 i, 即 [temp[dif], i]
var twoSum = function(nums, target) {
let temp = []
for (let i = 0; i < nums.length; i++) {
let dif = target-nums[i]
if (temp[dif] !== undefined) {
return [temp[dif], i]
}
temp[nums[i]] = i; // num[0] = 2, dif = 7, temp[2] = 0;
} // num[1] = 7, dif = 2, temp[2] !== undefined
};

删除链表的倒数第n个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 
var removeNthFromEnd = function(head, n) {
let k = head, m = head;
// 需要考虑到长度只有1,此时k已经被赋值为null,if就不能判断k.next了
while(--n) {
k = k.next;
}
if(!k.next) return head.next;
k = k.next;
while(k.next) {
k = k.next;
m = m.next;
}
m.next = m.next.next;
return head;
};


var removeNthFromEnd = function(head, n) {
let m = head, k = head;
while (k.next) {
if (!n) {
m = m.next;
}
n = n ? n - 1 : n;
k = k.next;
}
if (n) {
head = head.next;
} else {
if (m.next)
m.next = m.next.next;
else
m.next = null;
}
return head;
};