题目均源自 LeetCode (ง •̀_•́)ง
Easy
Find Anagram Mappings
Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.
We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.
These lists A and B may contain duplicates. If there are multiple answers, output any of them.
For example, given
1 | A = [12, 28, 46, 32, 50] |
We should return1
[1, 4, 3, 2, 0]
as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of A appears at B[4], and so on.
Solution:1
2
3const anagramMappings = function(A, B) {
return A.map(item => B.indexOf(item));
};
Hamming Distance
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 231.
Example:1
2
3
4
5
6
7
8Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
Solution:1
2
3const hammingDistance = function(x, y) {
return (x ^ y).toString(2).replace(/0/g, '').length
};
如何处理负数呢？(﹁”﹁)
javascript中没有无符号位的数，因此在处理负数时，通过>>>操作符先将其转换为无符号的等价形式
1 | ((x ^ y) >>> 0).toString(2) |
Merge Two Binary Trees
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Example 1:1
2
3
4
5
6
7
8
9
10
11
12
13
14Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7
Note: The merging process must start from the root nodes of both trees.
Solution:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
* 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}
*/
const mergeTrees = function(t1, t2) {
if (!t1 && !t2) return null;
const root = new TreeNode(((t1 || 0).val || 0) + ((t2 || 0).val || 0));
root.left = mergeTrees(t1 && t1.left, t2 && t2.left);
root.right = mergeTrees(t1 && t1.right, t2 && t2.right);
return root;
};
Reverse Words in a String III
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:1
2Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by single space and there will not be any extra space in the string.
Solution:1
2
3
4
5
6
7
8
9
10
11var reverseWords = function(s) {
return s
.split(' ')
.map(item =>
item
.split('')
.reverse()
.join('')
)
.join(' ');
};
Reshape the Matrix
In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.
You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example 11
2
3
4
5
6
7
8
9Input:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 21
2
3
4
5
6
7
8
9
10Input:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
Output:
[[1,2],
[3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
Solution: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} r
* @param {number} c
* @return {number[][]}
*/
const matrixReshape = function(nums, r, c) {
const length = nums.length * nums[0].length;
if ((r * c != length) || (r === nums.length && c === nums[0].length)) return nums;
// 先降维
const newNums = nums.reduce((total, num) => {
return total.concat(num);
}, []);
const matrix = [];
console.log(nums);
// 再构造
newNums.reduce((total, num, idx) => {
if (idx === c - 1 || (idx + 1) % c === 0) {
total.push(num);
matrix.push(total);
total = [];
} else {
total.push(num);
}
return total
}, []);
return matrix;
};
Island Perimeter
You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.
Example:1
2
3
4
5
6[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:
Solution:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
* @param {number[][]} grid
* @return {number}
*/
var islandPerimeter = function(grid) {
let total = 0;
grid.forEach((cell, r) => {
for(let c = 0; c < cell.length; c++) {
if (cell[c] === 1 ) {
total += 4;
// 除却第一行，顶部有重合边
if (r > 0 && grid[r - 1][c] === 1) total -= 2;
// 除却第一列，左边有重合边
if (c > 0 && grid[r][c - 1] === 1) total -= 2;
}
};
});
return total;
};
Find All Numbers Disappeared in an Array
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:1
2
3
4
5Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]
Solution:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
* @param {number[]} nums
* @return {number[]}
*/
const findDisappearedNumbers = function(nums) {
const result = [];
nums.forEach(item => {
const val = Math.abs(item) -1;
if(nums[val] > 0) {
nums[val] = - nums[val];
}
});
nums.forEach((item, idx) => {
if(item > 0) {
result.push(idx + 1);
}
});
return result;
};
Move Zeroes
Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
Note:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
Solution:1
2
3
4
5
6
7
8
9
10
11
12
13
14/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
const moveZeroes = function(nums) {
let insertPos = 0;
// 非零值尽可能向前移
for(num of nums){
if(num != 0) nums[insertPos ++] = num;
}
while(insertPos < nums.length) {
nums[insertPos ++] = 0;
}
};
Two Sum IV - Input is a BST
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:1
2
3
4
5
6
7
8
9
10Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 9
Output: True
Example 2:1
2
3
4
5
6
7
8
9
10Input:
5
/ \
3 6
/ \ \
2 4 7
Target = 28
Output: False
Solution: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/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {boolean}
*/
var findTarget = function(root, k) {
const values = new Set();
let found = false;
function inorder(node) {
if(!node) {
return;
}
// 中序遍历二叉树
inorder(node.left);
if(values.has(k - node.val)) {
found = true;
return;
}
values.add(node.val);
inorder(node.right);
}
inorder(root);
return found;
};
Convert BST to Greater Tree
Solution:
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:1
2
3
4
5
6
7
8
9Input: The root of a Binary Search Tree like this:
5
/ \
2 13
Output: The root of a Greater Tree like this:
18
/ \
20 13
Solution: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} root
* @return {TreeNode}
*/
var convertBST = function(root) {
let sum = 0;
// 逆向，中序遍历二叉树
function inorder(node) {
if(!node) return;
inorder(node.right);
node.val += sum;
sum = node.val;
inorder(node.left);
}
inorder(root);
return root
};