算法与数据结构

摘要: 整理常见算法与数据结构面试题

  1. 输入两个链表,分别代表两个数字的倒序排列如下:
    342+465 = 807;

    Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
    Output: 7 -> 0 -> 8

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
38
/**
* ListNode类用来生成具体的节点
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
var l = new ListNode(0);
var head = l;
var sum = 0;
var front = 0;
// sum === 1 是用来满足特殊情况
while (l1 !== null || l2 !== null || sum === 1) {
if (l1) {
sum += l1.val;
l1 = l1.next;
}
if (l2) {
sum += l2.val;
l2 = l2.next;
}
if (sum >= 10) {
front = 1;
sum -= 10;
}
head.next = new ListNode(sum);
head = head.next;
sum = front;
front = 0;
}
return l.next;
};
  1. 给定数组和固定的数,返回数组中元素和为该数的下标

比如: nums = [2, 7, 11, 15], target = 9,
因为 nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
// 时间复杂度较高,mark修改
for (var i = 0; i < nums.length; i++) {
for (var j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
  1. Hamming距离,示例如下:

    Input: x = 1, y = 4
    Output: 2
    Explanation:
    1 (0 0 0 1)
    4 (0 1 0 0)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @param {number} x
* @param {number} y
* @return {number}
*/
var hammingDistance = function(x, y) {
// 位运算之美
if (x < 0 || y < 0) {
return false;
}
var xor = x ^ y;
var dis = 0;
while (xor) {
// 此处的判断是点睛之笔 1,0的转换很巧妙吧2333
if ((xor >> 1) << 1 !== xor) {
dis += 1;
}
xor = xor >> 1;
}
return dis;
};
  1. 给定偶数数目的数组,分组为(a1, b1), (a2, b2), …, (an, bn) 然后求所有 min(ai, bi) 和的最大值

    Input: [1,4,3,2]
    Output: 4

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number[]} nums
* @return {number}
*/
var arrayPairSum = function(nums) {
// 首先进行排序,所谓和的最大值自然就容易计算了
var arr = nums.sort(function(a, b){return a - b;});
var sum = 0;
for (var i = 0; i < nums.length/2; i++) {
sum += arr[2*i];
}
return sum;
};
  1. 给定一个正整数,求它的补位,比如:

    Input: 5
    Output: 2
    Explanation: 例如5的二进制是101(不包括0位), 它的补位为010,所以你需要输出2.

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number} num
* @return {number}
*/
var findComplement = function(num) {
// 使用进制的转换容易的多
var bin = num.toString(2).split('');
console.log(bin)
for (var i = 0; i < bin.length; i++) {
bin[i] = bin[i] === '0' ? '1' : '0';
}
return parseInt(bin.join(''), 2);
};
  1. 给定字符串,求最长元素不重复的子字符串

    Given “abcabcbb”, the answer is “abc”, which the length is 3.

    Given “bbbbb”, the answer is “b”, with the length of 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
var arr = s.split('');
var temp = [];
var len = 0;
// 时间复杂度待优化
while (arr.length >= 1) {
for (var i = 0; i < arr.length; i++) {
if (temp.indexOf(arr[i]) === -1) {
temp.push(arr[i]);
} else {
break;
}
}
arr.shift();
len = temp.length > len ? temp.length : len;
temp = [];
}
return len;
};
  1. 给定一个数字数组,该数组只包含一个只出现一次的元素,输出这个只出现一次的数字

    Input: [1,1,2,3,3,4,4,8,8]
    Output: 2

1
2
3
4
5
6
7
8
9
10
/**
* @param {number[]} nums
* @return {number}
*/
var singleNonDuplicate = function(nums) {
// 经典位运算问题,之前看过一篇位运算之美的博客,正好有讲到,JavaScript的函数式编程太美
return nums.reduce(function(sum, value) {
return sum ^ value;
})
};
  1. 给定数字数组,找到所有满足a+b+c=0的元素返回;
1
2
3
4
5
6
输入:[-1, 0, 1, 2, -1, -4],
输出:
[
[-1, 0, 1],
[-1, -1, 2]
]
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
/**
* @param {number[]} nums
* @return {number[][]}
*/
// 此题借鉴了别人的答案
var threeSum = function(nums) {
var arr = [];
nums = nums.sort(function(a, b) { return a - b; });
if (nums.length < 3 || nums[0] > 0) {
return arr;
}
for (var i = 0; i < nums.length; i++) {
if (nums[i] === nums[i-1]) {
continue;
}
var start = i + 1, end = nums.length - 1;
while (start < end) {
var sum = nums[i] + nums[start] + nums[end];
if (sum === 0) {
arr.push([nums[i], nums[start], nums[end]]);
start += 1;
end -= 1;
// 借鉴的核心在这两句代码,排除重复的数组
while (start < end && nums[start] === nums[start-1]) { start += 1}
while (start < end && nums[end] === nums[end+1]) { end -= 1}
} else if (sum < 0) {
start += 1;
} else {
end -= 1;
}
}
}
return arr;
};
  1. 翻转数字

Example1: x = 123, return 321

Example2: x = -123, return -321

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number} x
* @return {number}
*/
var reverse = function(x) {
// 纯粹API运用
var result = parseInt(x.toString().split('').reverse().join(''));
return x > 0
? result > Math.pow(2, 31)
? 0
: result
: result > Math.pow(2, 31)
? 0
: -result;
};
  1. 输入两个链表,分别代表两个数字的倒序排列如下:
    7243 + 564 = 7807;

    Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
    Output: 7 -> 8 -> 0 -> 7

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
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
// 解决思路: 链表和栈的转换
var addTwoNumbers = function(l1, l2) {
var s1 = [], s2 = [], s = [];
var l = new ListNode(0);
var head = l;
var sum = 0, front = 0;
// 利用数组将链表l1,l2转化为栈s1,s2来解决,结果输出到栈s,再出栈输入链表l
while (l1 !== null) {
s1.unshift(l1.val);
l1 = l1.next;
}
while (l2 !== null) {
s2.unshift(l2.val);
l2 = l2.next;
}
while (s1.length > 0 || s2.length > 0 || sum > 0) {
console.log(s1, s2);
if (s1.length > 0) {
sum += s1.shift();
}
if (s2.length > 0) {
sum += s2.shift();
}
if (sum >= 10) {
sum -= 10;
front = 1;
}
s.unshift(sum);
sum = front;
front = 0;
}
while (s.length > 0) {
head.next = new ListNode(s.shift());
head = head.next;
}
return l.next;
};
  1. 回文数字的判断

比如:121是回文数

1
2
3
4
5
6
7
/**
* @param {number} x
* @return {boolean}
*/
var isPalindrome = function(x) {
return x === parseInt(x.toString().split('').reverse().join('')) ? true : false;
};
  1. 树转字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} t
* @return {string}
*/
var tree2str = function(t) {
if (!t) return '';
// 借鉴了网友的写法
var left = tree2str(t.left);
var right = tree2str(t.right);
return t.val + (left || right ? '(' + left + ")" : '') + (right ? '(' + right + ')' : '');
};
  1. 翻转二叉树

来自网友的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
// 借鉴了网友答案
function invertTree(root) {
if (root) {
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
}
return root;
}
  1. 相同二叉树判断

感觉用了太多判断…出口太多…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if (p && q && p.val === q.val) {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
// 此处略复杂,但是是满足所有case的写法
if ((p && q && p.val !== q.val) || (!p && q) || (p && !q)) {
return false;
}
if (!p && !q) {
return true;
}
};
  1. 根据前序遍历和中序遍历推导二叉树

核心是这个递归思路

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} inorder
* @param {number[]} postorder
* @return {TreeNode}
*/
var buildTree = function(inorder, postorder) {
if (inorder.length === 1) {
return new TreeNode(inorder[0]);
}
if (inorder.length === 0) {
return null;
}
var value = postorder[postorder.length - 1];
var root = new TreeNode(value);
var index = inorder.indexOf(value);
root.left = buildTree(inorder.slice(0, index), postorder.slice(0, index));
root.right = buildTree(inorder.slice(index + 1, inorder.length), postorder.slice(index, postorder.length-1));
return root;
};
  1. 已知前序排列和中序排列推导二叉树

只是对前面的结果更改参数和具体截断的位置罢了…

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
if (inorder.length === 1) {
return new TreeNode(inorder[0]);
}
if (inorder.length === 0) {
return null;
}
var value = preorder[0];
var root = new TreeNode(value);
var index = inorder.indexOf(value);
root.left = buildTree(preorder.slice(1, index + 1), inorder.slice(0, index));
root.right = buildTree(preorder.slice(index + 1, preorder.length), inorder.slice(index + 1, inorder.length));
return root;
};
  1. 判断一个链表是否是回文的

遍历链表,储存在栈中,通过对栈的数据进行判断
遍历链表,通过数组和字符串的转换,调用reverse方法对比

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
var arr = [];
while (head) {
arr.push(head.val);
head = head.next;
}
for (var i = 0, j = arr.length - 1; i <= j;) {
if (arr[i] !== arr[j]) {
return false;
} else {
j -= 1;
i += 1
}
}
return true;
};
  1. 反转链表

借助栈来解决很简单

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
38
39
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
// 2. 借助栈
var reverseList = function(head) {
var stack = [],
newList = new ListNode(0),
temp = newList;
while (head) {
stack.push(head.val);
head = head.next;
}
while (stack.length > 0) {
temp.next = new ListNode(stack.pop());
temp = temp.next;
}
return newList.next;
};
// 2. 直接反转
var reverseList = function(head) {
var newList = new ListNode(0);
var temp = newList;
var replce;
while (head) {
replace = temp.next;
temp.next = new ListNode(head.val);
temp.next.next = replace;
head = head.next;
}
return newList.next;
};
  1. 从链表中移除制定元素

改变下指针的指向即可

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
// 链表为空返回Null
if (head === null) return null;
var temp = head;
while (temp.next !== null) {
if (temp.next.val === val) {
temp.next = temp.next.next;
continue;
}
temp = temp.next;
}
// 对单元素链表进行特殊处理
return head.val === val ? head.next : head;
};
  1. 反转字符串(2)

指定位置反转,比如:Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

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
38
39
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} m
* @param {number} n
* @return {ListNode}
*/
// 借用了栈,似乎没法通过直接改变指针来做
var reverseBetween = function(head, m, n) {
if (m > n) {
return head;
}
var stack = [], temp = [];
while (head) {
stack.push(head.val);
head = head.next;
}
console.log(stack);
if (m !== n) {
temp = stack.splice(m - 1, n - m + 1).reverse();
}
for (var i = 0; i < temp.length; i++) {
stack.splice(m - 1 + i, 0, temp[i]);
}
console.log(temp);
var newList = new ListNode(0);
var replace = newList;
while (stack.length > 0) {
replace.next = new ListNode(stack.shift());
replace = replace.next;
}
return newList.next;
};
  1. 链表去重(已排序)

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
// 借用了栈,转化为了数组去重,但感觉如果使用递归时间复杂度会更低
var deleteDuplicates = function(head) {
var stack = [];
while (head) {
stack.push(head.val);
head = head.next;
}
console.log(stack)
stack = Array.from(new Set(stack));
console.log(stack)
var newList = new ListNode(0);
var temp = newList;
while (stack.length > 0) {
temp.next = new ListNode(stack.shift());
temp = temp.next;
}
return newList.next;
};
  1. 从结尾算起删除链表第n个元素

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
// 依然借用栈解决...
var removeNthFromEnd = function(head, n) {
var stack = [];
while (head) {
stack.push(head.val);
head = head.next;
}
console.log(stack);
stack.splice(-n, 1);
console.log(stack);
var result = new ListNode(0);
var temp = result;
while (stack.length > 0) {
temp.next = new ListNode(stack.shift());
temp = temp.next;
}
return result.next;
};
  1. 去除数组重复元素

Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

1
2
3
4
5
6
7
8
9
10
11
12
/**
* @param {number[]} nums
* @return {number}
*/
// 借鉴了网友Java实现的答案,主要没弄懂它的返回值具体要求,有点迷。
var removeDuplicates = function(nums) {
if (nums.length === 0) return 0;
var j = 0;
for (var i = 0; i < nums.length; i++)
if (nums[i] !== nums[j]) nums[++j] = nums[i];
return ++j;
};
  1. 反转句子中的每个单词

Input: “Let’s take LeetCode contest”
Output: “s’teL ekat edoCteeL tsetnoc”

1
2
3
4
5
6
7
8
9
10
11
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
var arr = s.split(' ' );
for (var i = 0; i < arr.length; i++) {
arr[i] = arr[i].split('').reverse().join('');
}
return arr.join(' ');
};
  1. 分配糖果问题,输入一个数字数组(长度固定位偶数),每一个数字代表一种糖果,将这些糖果分配给两个孩子,求孩子能得到的最大的糖果种类数。

    Input: candies = [1,1,2,2,3,3]
    Output: 3
    Explanation:
    这有不同的糖果(1, 2 and 3), 然后每个孩子三个不同的糖果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} candies
* @return {number}
*/
// 刚开始想的是在排序之后的基础上对半分,发现一些case无法满足,然后想奇偶分。一些case还是没法满足
// 后来醒悟,实际上这是个简单的数组去重的题目
var distributeCandies = function(candies) {
if (candies > 10000 || candies < 2 || candies.length % 2 !== 0) {
return false;
}
var temp = Array.from(new Set(candies));
console.log(temp);
return temp.length <= candies.length / 2
? temp.length
: candies.length / 2
};
  1. 反转字符串

Given s = “hello”, return “olleh”.

Reverse String

1
2
3
4
5
6
7
8
/**
* @param {string} s
* @return {string}
*/
// 这算是偷懒的写法么...再次充当API搬运工的角色
var reverseString = function(s) {
return s.split('').reverse().join('');
};
  1. 给定两个数组num1和num2,已知num1是num2的子集,求num1的元素在num2数组中位置之后的第一个比该元素大的集合(如果没有则返回-1)。

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Next Greater Element I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number[]} findNums
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElement = function(findNums, nums) {
var result = [];
for (var i = 0; i < findNums.length; i++) {
var temp = nums.indexOf(findNums[i]);
var j = temp + 1;
while (j < nums.length) {
if (nums[temp] < nums[j]) {
result.push(nums[j]);
break;
} else {
j += 1;
}
}
if (j === nums.length) {
result.push(-1);
}
}
return result;
};
  1. 寻找数组中最大连续1的数目:给定二进制数组(元素只包括0,1)

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
The maximum number of consecutive 1s is 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} nums
* @return {number}
*/
// 没仔细看题目,刚开始以为是找最长连续数字,白白浪费了时间...
var findMaxConsecutiveOnes = function(nums) {
var temp = 0,
len = 0;
for (var i = 0; i < nums.length; i++) {
if (nums[i]) {
temp += 1;
len = len > temp ? len : temp;
} else {
temp = 0;
}
}
return len;
};
  1. 查找单数:给定数组,元素内部只有一个数字出现一次,其它都是出现两次,找出这个只出现一次的数字

和7题重复了

Single Number

1
2
3
4
5
6
7
8
9
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
return nums.reduce(function(a,b) {
return a ^ b;
})
};
  1. 最长单独序列:给定两个字符串,判断两个有没有父子集关系

Input: “aba”, “cdc”
Output: 3
Explanation: The longest uncommon subsequence is “aba” (or “cdc”),
because “aba” is a subsequence of “aba”,
but not a subsequence of any other strings in the group of two strings.

Longest Uncommon Subsequence I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {string} a
* @param {string} b
* @return {number}
*/
// 主要是一些逻辑判断
var findLUSlength = function(a, b) {
var len = -1;
if (a.indexOf(b) === -1 && b.indexOf(a) === -1) {
len = a.length >= b.length ? a.length : b.length;
} else if (a.indexOf(b) !== -1 && b.indexOf(a) === -1) {
len = a.length;
} else if (b.indexOf(a) !== -1 && a.indexOf(b) === -1) {
len = b.length;
} else {
len = -1;
}
return len;
};
  1. 侦查字符串:

    如下情况返回true:
    所有字母大写 ex:”USA”.
    所有字母小写 ex:”leetcode”.
    第一个字母大写,其余小写 ex:”Google”.

Detect Capital

1
2
3
4
5
6
7
8
9
10
/**
* @param {string} word
* @return {boolean}
*/
// 使用正则很简单就解决,遇到一个问题:正则表达式对象字面量没法使用变量
var detectCapitalUse = function(word) {
var len = word.length;
var par = new RegExp(`[A-Z]{${len}}|[a-z]{${len}}|[A-Z][a-z]{${len-1}}`,'g');
return par.test(word);
};
  1. 寻找缺失的数字:给定数组1 ≤ a[i] ≤ n (n = size of array),寻找缺失的数字

Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

Find All Numbers Disappeared in an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDisappearedNumbers = function(nums) {
var result = [];
for (var i = 0; i < nums.length; i++) {
var index = Math.abs(nums[i]) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
}
}
console.log(nums);
for (var j = 0; j < nums.length; j++) {
if (nums[j] > 0) {
result.push(j + 1);
}
}
return result;
};
  1. 求树的最大深度

Maximum Depth of Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (!root) {
return 0;
}
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
  1. 寻找字符串不同的字符:给定两个相同的字符串s和t,向t中随机插入一个字符,找出这个字符

    Input:
    s = “abcd”
    t = “abcde”
    Output:
    e

Find the Difference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {string} s
* @param {string} t
* @return {character}
*/
var findTheDifference = function(s, t) {
var n = t.length;
var result = t.split('');
for (var i = 0; i < s.length; i++) {
if (result.indexOf(s.charAt(i)) !== -1){
result.splice(result.indexOf(s.charAt(i)), 1)
}
}
return result[0];
};
  1. 不使用+-完成两个整数加法

Input:1,3
Output: 4

Sum of Two Integers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
// 首先第一步0+1=1,1+1=2(进位后为0),1+0=1,0+0=0,和异或逻辑一样
// 然后进位问题,只有1+1=2的时候进位。即先进行逻辑与运算然后再左移一位即可,这个过程持续到一方为0截止
var getSum = function(a, b) {
var sum = 0;
while (b !== 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
};
  1. 求数根

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Add Digits

1
2
3
4
5
6
7
/**
* @param {number} num
* @return {number}
*/
var addDigits = function(num) {
return num === 0 ? 0 :num % 9 === 0 ? 9 : num % 9;
};
  1. 返回两个数组共同元素下标和最小的集合

Input:
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
Output: [“Shogun”]Input:
[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
[“KFC”, “Shogun”, “Burger King”]
Output: [“Shogun”]
Explanation: The restaurant they both like and have the least index sum is “Shogun” with index sum 1 (0+1).
Explanation: The only restaurant they both like is “Shogun”.

Minimum Index Sum of Two Lists

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
/**
* @param {string[]} list1
* @param {string[]} list2
* @return {string[]}
*/
// 使用两个循环目的是找出相同元素中下标和的最小值时间复杂度感觉O(m+n)比较好
var findRestaurant = function(list1, list2) {
var result = [];
var len = list1.length + list2.length;
for (var i = 0; i < list1.length; i++) {
var target = list2.indexOf(list1[i]);
if (target !== -1) {
if (target + i < len) {
len = target + i;
}
}
}
for (var j = 0; j < list1.length; j++) {
target = list2.indexOf(list1[j]);
if (target !== -1) {
if (target + j === len) {
result.unshift(list2[target]);
}
}
}
return result.length >= 30 ? result : result.slice(0,30);
};
  1. 移动0元素

given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0]

Move Zeroes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var moveZeroes = function(nums) {
var j = 0, temp;
for (var i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j++;
}
}
};
  1. 设计网页区域
  1. 长宽相乘等于所给区域
    2.宽<=长
    3.长宽相差最小
    Input: 4
    Output: [2, 2]

Construct the Rectangle

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
/**
* @param {number} area
* @return {number[]}
*/
var constructRectangle = function(area) {
var minDiff = area;
var len, width;
var result = [];
for (var i = 1; i <= Math.ceil(Math.sqrt(area)); i++) {
if (area%i === 0) {
len = area / i > i ? area / i : i;
width = area / len;
}
if (len - width < minDiff) {
result[0] = len;
result[1] = width;
minDiff = len - width;
}
}
return result;
};
// 网上看到这种解法...提升了不是一点半点,羞愧
/**
* @param {number} area
* @return {number[]}
*/
var constructRectangle = function(area) {
var w = Math.floor(Math.sqrt(area));
while (area%w !== 0) w--;
return [area/w, w];
};
  1. 寻找最大数的数量

给定一个m*n的矩阵,根据一个数组元素对矩阵元素进行+1操作,求操作完成最大数的数目
Input:
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation:
Initially, M =
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
After performing [2,2], M =
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]
After performing [3,3], M =
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]
So the maximum integer in M is 2, and there are four of it in M. So return 4.

Range Addition II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number} m
* @param {number} n
* @param {number[][]} ops
* @return {number}
*/
var maxCount = function(m, n, ops) {
var w = m,
h = n;
for (var i = 0; i < ops.length; i++) {
w = w < ops[i][0] ? w : ops[i][0];
h = h < ops[i][1] ? h : ops[i][1];
}
return w * h;
};
  1. 寻找目标和

给定数字数组(已排序)和目标数字,返回数组中相加等于目标数字的位置
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
// 指针法
var twoSum = function(numbers, target) {
var start = 0;
var end = numbers.length - 1;
while (numbers[start] + numbers[end] !== target) {
if (numbers[start] + numbers[end] < target) {
start += 1;
} else {
end -= 1;
}
}
console.log(start,end);
return [start + 1, end + 1];
};
  1. 寻找二叉搜索树节点的最小差

Input:
1
\
3
/
2
Output:
1

Minimum Absolute Difference in BST

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
// 关键在于二叉搜索树中序遍历的结果即是升序排列的结果
var getMinimumDifference = function(root) {
var min = Number.MAX_VALUE;
var prev = null;
var inOrder = function (root) {
if (root === null) {
return;
}
inOrder(root.left);
if (prev !== null) {
min = Math.min(min, root.val - prev);
}
prev = root.val;
inOrder(root.right);
}
inOrder(root);
return min;
};
  1. 链接两个已排序的链表

Merge Two Sorted Lists

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
var l = new ListNode(0);
var temp = l;
while (l1 && l2) {
if (l1.val >= l2.val) {
temp.next = new ListNode(l2.val);
temp = temp.next;
l2 = l2.next;
} else {
temp.next = new ListNode(l1.val);
temp = temp.next;
l1 = l1.next;
}
}
temp.next = l1 ? l1 : l2;
return l.next;
};
  1. 合并两个二叉树

Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7
对应节点相加

Merge Two Binary Trees

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} t1
* @param {TreeNode} t2
* @return {TreeNode}
*/
var mergeTrees = function(t1, t2) {
if (t1 === null && t2 === null) {
return null;
}
var value = (t1 === null ? 0 : t1.val) + (t2 === null ? 0 : t2.val);
var tree = new TreeNode(value);
tree.left = mergeTrees(t1 ? t1.left : null, t2 ? t2.left : null);
tree.right = mergeTrees(t1 ? t1.right : null, t2 ? t2.right : null);
return tree;
};
  1. 计算二叉树的倾斜度

二叉树倾斜度是指所有节点的左右子树和的差的绝对值相加

Binary Tree Tilt

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findTilt = function(root) {
if (root === null) {
return 0;
}
var postOrder = function(root) {
if (root === null) {
return 0;
}
return root.val + postOrder(root.left) + postOrder(root.right);
}
var left = postOrder(root.left);
var right = postOrder(root.right);
return Math.abs(left - right) + findTilt(root.left) + findTilt(root.right);
};
  1. 计算二叉树的直径

节点之前最远距离

Diameter of Binary Tree

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function(root) {
if (root === null) {
return 0;
}
var max = 0;
var depth = function (root) {
if (root === null) {
return 0;
}
var left = depth(root.left);
var right = depth(root.right);
max = Math.max(max, left + right);
return Math.max(left, right) + 1;
}
depth(root);
return max;
};
  1. 树的固定值

给定二叉树和固定值,求二叉树中是否有连续节点之和等于固定值

Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {boolean}
*/
var hasPathSum = function(root, sum) {
if (root === null) {
return false;
}
if (root.val === sum && root.left === null && root.right === null) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val)
};
  1. 左子叶之和

求二叉树左子叶的和

Sum of Left Leaves

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
// 应该是根左子叶之和吧...
var sumOfLeftLeaves = function(root) {
var res = 0;
var sum = function (root) {
if (root === null) {
return 0;
}
if (root.left !== null && root.left.right === null && root.left.left === null) {
res = res + root.left.val;
}
sum(root.left);
sum(root.right);
};
sum(root);
return res;
};
  1. 判断两个树是否存在父子关系

核心利用前面判断两颗树是否相等的算法解决

Subtree of Another Tree

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} s
* @param {TreeNode} t
* @return {boolean}
*/
var isSubtree = function(s, t) {
if (s === null) {
return false;
}
var isSameTree = function(p, q) {
if (p && q && p.val === q.val) {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
if ((p && q && p.val !== q.val) || (!p && q) || (p && !q)) {
return false;
}
if (!p && !q) {
return true;
}
};
if (isSameTree(s, t)) {
return true;
}
return isSubtree(s.left, t) || isSubtree(s.right, t);
};
  1. 树的最小深度

定义树的最小深度是树根节点到最短路径之间的节点数

Minimum Depth of Binary Tree

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
var min = 0;
if (root === null) {
return 0;
}
var findMin = function(root) {
if (root === null) {
return 0;
}
var left = findMin(root.left);
var right = findMin(root.right);
if (left === 0 && right !== 0) {
min = 1 + right;
} else if (right === 0 && left !== 0) {
min = 1 + left;
} else {
min = 1 + Math.min(left, right);
}
return min;
};
findMin(root);
return min;
};
  1. 平衡二叉树

定义平衡二叉树是每个节点的两个子树深度不超过1

Balanced Binary Tree

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
if (root === null) {
return true;
}
var depth = function(root) {
if (root === null) {
return 0;
}
return 1 + Math.max(depth(root.left), depth(root.right));
}
var left = depth(root.left);
var right = depth(root.right);
return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};
  1. 已排序的数组转为二叉搜索平衡树

Convert Sorted Array to Binary Search Tree

刚开始觉得直接分为两部分即可,左子树和右子树,然而case不允许,并不觉得这样有啥错误,也符合要求啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} nums
* @return {TreeNode}
*/
var sortedArrayToBST = function(nums) {
var len = nums.length;
var root = Math.floor(len / 2);
var tree = new TreeNode(nums[root]);
if (nums.length === 0) {
return null;
}
tree.left = sortedArrayToBST(nums.slice(0, root));
tree.right = sortedArrayToBST(nums.slice(root + 1, len));
return tree;
};
  1. 二叉树转数组

Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]

Binary Tree Level Order Traversal

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
var res = [];
var breadth = function(root, depth) {
if (root === null) {
return null;
}
if (res[depth] === undefined) {
res[depth] = [];
}
console.log(res[depth])
res[depth].push(root.val);
breadth(root.left, depth + 1);
breadth(root.right, depth +1);
}
breadth(root, 0);
return res;
};
  1. 后序遍历二叉树

这题难度竟然是hard…

Binary Tree Postorder Traversal

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var postorderTraversal = function(root) {
if (root === null) {
return [];
}
var res = [];
var postOrder = function(root) {
if (root === null) {
return null;
}
postOrder(root.left);
postOrder(root.right);
console.log(root.val);
res.push(root.val);
};
postOrder(root);
console.log(res);
return res;
};
// 2. 借助栈
var postorderTraversal = function(root) {
if (root === null) {
return [];
}
var stack = [];
var result = [];
var node = root;
var temp;
stack.push(root);
while (stack.length !== 0) {
temp = stack[stack.length - 1];
if (temp.left && node !== temp.left && node !== temp.right) {
stack.push(temp.left);
} else if (temp.right !== null && node !== temp.right) {
stack.push(temp.right);
} else {
temp = stack.pop();
result.push(temp.val);
node = temp;
}
}
console.log(stack);
return result;
};
  1. 前序遍历二叉树

Binary Tree Preorder Traversal

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// 1. 递归
var preorderTraversal = function(root) {
if (root === null) {
return [];
}
var res = [];
var preOrder = function(root) {
if (root === null) {
return null;
}
console.log(root.val);
res.push(root.val);
preOrder(root.left);
preOrder(root.right);
};
preOrder(root);
console.log(res);
return res;
};
// 2. 借助栈
var preorderTraversal = function(root) {
if (root === null) {
return [];
}
var temp;
var result = [];
var stack = [];
stack.push(root);
while (stack.length !== 0) {
temp = stack.pop();
result.push(temp.val);
if (temp.right !== null) {
stack.push(temp.right);
}
if (temp.left !== null) {
stack.push(temp.left);
}
}
return result;
}
  1. 寻找二叉树每一列的最大值

Input:
1
/ \
3 2
/ \ \
5 3 9
Output: [1, 3, 9]

Find Largest Value in Each Tree Row

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var largestValues = function(root) {
var res = [];
var breadth = function(root, depth) {
if (root === null) {
return null;
}
if (res[depth] === undefined) {
res[depth] = -Infinity;
}
res[depth] = res[depth] > root.val ? res[depth] : root.val;
breadth(root.left, depth + 1);
breadth(root.right, depth + 1);
}
breadth(root, 0);
return res;
};
  1. 寻找树底部最左边的元素

Find Bottom Left Tree Value

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findBottomLeftValue = function(root) {
var res = [];
var findLeft = function(root, depth) {
if (root === null) {
return null;
}
if (res[depth] === undefined) {
res[depth] = [];
}
res[depth].push(root.val);
findLeft(root.left, depth + 1);
findLeft(root.right, depth + 1);
};
findLeft(root, 0);
return res[res.length - 1][0];
};
  1. 移除指定元素

Given input array nums = [3,2,2,3], val = 3

Remove Element

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
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
// 1. 递归方法
var removeElement = function(nums, val) {
for (var i = 0, len = nums.length; i < len; i++) {
if (nums[i] === val) {
nums.splice(i, 1);
console.log(nums);
removeElement(nums, val);
}
}
console.log(nums);
return nums.length;
};
// 2. 双指针法
var removeElement = function(nums, val) {
var start = 0;
var len = nums.length;
for (var i = 0; i < len; i++) {
if (nums[i] !== val) {
nums[start++] = nums[i];
}
}
return start;
};
  1. 求两个数组的交集

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
要求返回内容不能重复

Intersection of Two Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function(nums1, nums2) {
var res = [];
nums2 = Array.from(new Set(nums2));
for (var i = 0; i < nums2.length; i++) {
if (nums1.indexOf(nums2[i]) !== -1) {
res.push(nums2[i]);
}
}
return res;
};
  1. 求两个数组交集2

Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
var res = [];
for (var i = 0; i < nums2.length; i++) {
var loca = nums1.indexOf(nums2[i]);
if (loca !== -1) {
res.push(nums2[i]);
nums1.splice(loca, 1);
}
}
return res;
};
  1. 寻找重复数组中重复的元素

假设数组中只有一个重复元素

Find the Duplicate Number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number[]} nums
* @return {number}
*/
// 1. 空间复杂度比较高
var findDuplicate = function(nums) {
var temp = [];
for (var i = 0; i < nums.length; i++) {
if (temp.indexOf(nums[i]) === -1) {
temp.push(nums[i]);
} else {
return nums[i];
}
}
};
// 2. 利用indexOf特性
var findDuplicate = function(nums) {
var temp = [];
for (var i = 0; i < nums.length; i++) {
if (nums.indexOf(nums[i], i + 1) !== -1) {
return nums[i];
}
}
};
  1. 数组最小元素和

给定数组和一个固定值,求数组中相邻元素相加等于该固定值的最小长度
ex: [2,3,1,2,4,3] and s = 7

Minimum Size Subarray Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number} s
* @param {number[]} nums
* @return {number}
*/
// 借鉴的网友Java实现代码,时间复杂度n,之前自己写的时间复杂度n2...测试超时了
var minSubArrayLen = function(s, nums) {
var min = Infinity;
var start = 0;
var sum = 0;
var end = 0;
while (end < nums.length) {
sum += nums[end++];
while (sum >= s) {
min = Math.min(min, end - start);
sum -= nums[start++];
}
}
return min === Infinity ? 0 : min;
};
  1. 实现字符串indexOf方法

给定字符串needle 和 haystack,求needle在haystack的位置,如果不存在返回-1

Implement strStr()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
if (needle === '') {
return 0;
}
var start = 0;
var len = needle.length;
while (start < haystack.length) {
if (haystack.slice(start, len + start) === needle) {
return start;
} else {
start += 1;
}
}
return -1;
};
  1. 给定数组求每个元素之后的第一个比该元素大的值(可循环)

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number;
The second 1’s next greater number needs to search circularly, which is also 2.

Next Greater Element II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number[]} nums
* @return {number[]}
*/
var nextGreaterElements = function(nums) {
var result = [];
var len = nums.length;
for (var i = 0, temp = 0; i < len; i++) {
temp = i + 1;
while (temp < i + len) {
if (nums[temp % len] > nums[i]) {
result.push(nums[temp % len]);
break;
}
temp += 1;
}
if (temp === i + len) {
result.push(-1);
}
console.log(temp)
temp = 0;
}
return result;
};
  1. 中序遍历二叉树

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
38
39
40
41
42
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
// 1. 递归法
var inorderTraversal = function(root) {
var result = [];
var inOrder = function(root) {
if (root === null) {
return null;
}
inOrder(root.left);
result.push(root.val);
inOrder(root.right);
}
inOrder(root);
return result;
};
// 2. 转化为栈
var inorderTraversal = function(root) {
var result = [];
var stack = [];
var temp = root;
while (temp !== null || stack.length !== 0) {
while (temp !== null) {
stack.push(temp);
temp = temp.left;
}
temp = stack.pop();
console.log(temp.val);
result.push(temp.val);
temp = temp.right;
}
return result;
};
  1. 寻找二叉树最右元素

1 <—
/ \
2 3 <—
\ \
5 4 <—
You should return [1, 3, 4].

Binary Tree Right Side View

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
var res = [];
var breadth = function(root, depth) {
if (root === null) {
return null;
}
if (res[depth] === undefined) {
res[depth] = [];
}
res[depth] = root.val;
breadth(root.left, depth + 1);
breadth(root.right, depth +1);
}
breadth(root, 0);
return res;
};
  1. 判断对称树

1
/ \
2 2
/ \ / \
3 4 4 3
对称树

Symmetric Tree

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if (root === null) {
return true;
}
var helper = function(l, r) {
if (!l && !r) {
return true;
} else if (!l || !r) {
return false;
}
if (l.val !== r.val) {
return false;
}
return helper(l.left, r.right) && helper(l.right, r.left);
}
return helper(root.left, root.right);
};
  1. 寻找二叉树所有的根-叶路径

1
/ \
2 3
\
5
All root-to-leaf paths are:
[“1->2->5”, “1->3”]

Binary Tree Paths

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
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {string[]}
*/
var binaryTreePaths = function(root) {
var res= [];
if (root === null) {
return res;
}
var str = '';
var treePath = function(root, path) {
if (root === null) {
return null;
}
if (root.left === null && root.right === null) {
res.push(path + root.val);
}
treePath(root.left, path + root.val + '->' );
treePath(root.right, path + root.val + '->');
}
treePath(root, '');
return res;
};
  1. 链表排序

Sort List

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
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
// 看了讨论区的Java实现,尝试使用快排失败...
var sortList = function(head) {
if (head === null || head.next === null) {
return head;
}
var prev = null,
slow = head,
fast = head;
while (fast !== null && fast.next !== null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
var l1 = sortList(head);
var l2 = sortList(slow);
return merge(l1, l2);
};
var merge = function(l1, l2) {
var l = new ListNode(0),
temp = l;
while (l1 !== null && l2 !== null) {
if (l1.val < l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
if (l1 !== null){
temp.next = l1;
}
if (l2 !== null) {
temp.next = l2;
}
return l.next;
}
  1. 排列最大数字

给定数字数组,排列出最大的数字组合
given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Largest Number

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
/**
* @param {number[]} nums
* @return {string}
*/
// 起初直接使用sort方法进行排序,发现某些case是错误的(大于100个数),猜想应该是sort方法内部实现当小于10用InsertionSort,比10大的数组则使用 QuickSort,这里使用快速排序解决
var largestNumber = function(nums) {
var quickSort = function(nums) {
console.log(nums)
if (nums.length <= 1) {
return nums.toString();
}
var pivot = nums.splice(0, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < nums.length; i++) {
var p = pivot.toString();
var q = nums[i].toString();
if (p + q < q + p) {
left.push(nums[i]);
} else {
right.push(nums[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
}
var res = quickSort(nums);
return res.charAt(0) === '0' ? '0' : res;
};
  1. 插入排序链表

使用插入排序算法排序链表

Insertion Sort List

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
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var insertionSortList = function(head) {
if (head === null) {
return null;
}
var res = new ListNode(-Infinity);
var temp = res;
while (head !== null) {
while (temp !== null && temp.next !== null) {
if (temp.val <= head.val && temp.next.val > head.val) {
break;
}
temp = temp.next;
}
var rep = temp.next;
temp.next = new ListNode(head.val);
temp.next.next = rep;
temp = res;
head = head.next;
}
return res.next;
};
  1. 判断数组是否有重复元素

Contains Duplicate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
var obj = {};
for (var i = 0; i < nums.length; i++) {
if (!obj.hasOwnProperty(nums[i])) {
obj[nums[i]] = nums[i];
} else {
return true;
}
}
return false;
};
  1. 键盘行

判断某一字符串能不能通过处在一行的键盘字母输出

Keyboard Row

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
/**
* @param {string[]} words
* @return {string[]}
*/
var findWords = function(words) {
var obj = {
'q': 0, 'w': 0, 'e': 0, 'r': 0, 't': 0, 'y': 0, 'u': 0, 'i': 0, 'o': 0, 'p': 0,
'a': 1, 's': 1, 'd': 1, 'f': 1, 'g': 1, 'h': 1, 'j': 1, 'k': 1, 'l': 1,
'z': 2, 'x': 2, 'c': 2, 'v': 2, 'b': 2, 'n': 2, 'm': 2
};
var res = [];
var word = '';
for (var i = 0; i < words.length; i++) {
word = words[i].toLowerCase();
for (var j = 0; j < word.length - 1; j++) {
if (obj[word.charAt(j)] !== obj[word.charAt(j + 1)]) {
break;
}
}
if (j === word.length - 1) {
res.push(words[i]);
}
}
return res;
};
  1. 子串和父串

给定两个字符串,判断第一个字符串是否能够用后一个字符串的元素组成

Ransom Note

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {string} ransomNote
* @param {string} magazine
* @return {boolean}
*/
var canConstruct = function(ransomNote, magazine) {
for (var i = 0; i < ransomNote.length; i++) {
var pos = magazine.indexOf(ransomNote.charAt(i));
if (pos === -1) {
return false;
}
magazine = magazine.slice(0, pos) + magazine.slice(pos + 1, magazine.length);
}
return true;
};
  1. 矩阵重置

Reshape the Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[][]} nums
* @param {number} r
* @param {number} c
* @return {number[][]}
*/
var matrixReshape = function(nums, r, c) {
var n = nums.length, m = nums[0].length;
var res = [];
if (n * m !== r * c) {
return nums;
}
for (var i = 0; i < r * c; i++) {
if (res[Math.floor(i / c)] === undefined) {
res[Math.floor(i / c)] = [];
}
res[Math.floor(i / c)][i % c] = nums[Math.floor(i / m)][i % m];
}
return res;
};
  1. Fizz Buzz

Fizz Buzz

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {number} n
* @return {string[]}
*/
var fizzBuzz = function(n) {
var res = [];
var temp = '';
for (var i = 1; i <= n; i++) {
temp = i;
if (i % 3 === 0 && i % 5 === 0) {
temp = 'FizzBuzz';
} else if (i % 3 === 0) {
temp = 'Fizz';
} else if (i % 5 === 0) {
temp = 'Buzz';
} else {
temp = i.toString();
}
res.push(temp);
}
return res;
};
  1. 16进制转10进制
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var number = readline();
var buf = {
'A': 10,
'B': 11,
'C': 12,
'D': 13,
'E': 14,
'F': 15
}
var int16 = number.slice(2, number.length);
var res = 0;
var len = int16.length - 1;
var temp;
for (var i = len; i >= 0; i--) {
temp = len - i;
if(!isNaN(int16[i])) {
res += Math.pow(16, temp) * int16[i];
} else {
res += Math.pow(16, temp) * buf[int16[i]];
}

}
console.log(res)
  1. 绑定函数,要求:
    调用:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    bind(person, function() {
    console.log(`name:${this.name}`)
    })
    bind(person, function() {
    console.log(`age:${this.age}`)
    })
    person.name = 111;
    //输出name:111
    //输出age:21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var result = []
function bind(target, func) {
result.push(func);
for (let key in target) {
let temp = target[key]
Object.defineProperty(target, key, {
get: function() {
return temp
},
set: function(value) {
temp = value
for(var i = 0; i < result.length; i++) {
result[i].call(target)
}
},
enumerable : true,
configurable : true
});
}
}
  1. 寻找数组重复数字

Find All Duplicates in an Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number[]} nums
* @return {number[]}
*/
var findDuplicates = function(nums) {
var obj= {};
var res = [];
for (var i = 0; i < nums.length; i++) {
if (obj[nums[i]] === undefined) {
obj[nums[i]] = nums[i];
} else {
res.push(nums[i]);
}
}
return res;
};
文章目录
  1. 1. 摘要: 整理常见算法与数据结构面试题
|