前言
最近在leetcode上做算法题，记录一下心得
（我的答案是用js写的）
由易至难
第一题：669. Trim a Binary Search Tree
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Binary Search Tree 二叉搜索树。 二叉搜索树的特点是，小的值在左边，大的值在右边！
我的答案：
var trimBST = function(root, L, R) {
if(!root){
return null;
}
if(root.val < L){
return trimBST(root.right,L,R);
}
if(root.val > R){
return trimBST(root.left,L,R);
}
root.left = trimBST(root.left,L,R);
root.right = trimBST(root.right,L,R);
return root;
};
第二题：LeetCode 463. 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.
[[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:
`
**题目大意：**
给定一个二维地图，1表示陆地，0表示水域。单元格水平或者竖直相连（不含对角线）。地图完全被水域环绕，只包含一个岛屿（也就是说，一个或者多个相
连的陆地单元格）。岛屿没有湖泊（岛屿内部环绕的水域）。单元格是边长为1的正方形。地图是矩形，长宽不超过100。计算岛屿的周长。
解题思路：
每一个陆地单元格的周长为4，当两单元格上下或者左右相邻时，令周长减2。
解：
var islandPerimeter = function(grid) {
var islands = 0, edges = 0;
for(let i=0;i<grid.length;i++) {
for(let j=0;j<grid[i].length;j++){
if(grid[i][j] === 1) {
islands++;
if(i<grid.length-1 && grid[i+1][j] === 1) {
edges++;
}
if(j<grid[i].length-1 && grid[i][j+1] === 1) {
edges++;
}
}
}
}
return islands*4 - edges*2;
};
第三题：496. Next Greater Element I
You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1’s elements in the corresponding places of nums2.
The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.
Example 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.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3,-1]
Explanation:
For number 2 in the first array, the next greater number for it in the second array is 3.
For number 4 in the first array, there is no next greater number for it in the second array, so output -1.
Note:
All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.
解
var nextGreaterElement = function(findNums, nums) {
var result = [];
for(var i=0;i<findNums.length;i++){
var i_val = findNums[i];
var index = -1;
result[i] = -1;
for(var j=0;j<nums.length;j++){
var j_val = nums[j];
if(i_val == j_val && index<0){
index = j;
}
if((i_val < j_val) && (j> index) && (index >=0)){
result[i] = j_val;
break;
}
}
index = -1;
}
return result;
};
最优解
var nextGreaterElement = function(findNums, nums) {
var map = {};
nums.forEach((num, i) => map[num] = i);
return findNums.map(el => {
for(let i = map[el]; i < nums.length; i++) {
if(nums[i] > el) return nums[i];
}
return -1;
})
};
第四题： 521. Longest Uncommon Subsequence I
Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.
**Example 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.
**Note:
-
Both strings’ lengths will not exceed 100.
-
Only letters from a ~ z will appear in input strings
题目大意：两个字符串中最长的字符串是否为另一字符串的子字符串，如果是，则返回-1，否则返回最长字符串长度。 思路：比较两个字符串的长度，若不相等，则返回长度的较大值，若相等则再判断两个字符串是否相同，若相同则返回-1，否则返回长度。
解
var findLUSlength = function(a, b) {
var m = a.length,n =b.length,result = m;
if(m!=n){
m>n?result = m:result = n;
}else if(a == b){
result = -1;
}
return result;
};
最优解
var findLUSlength = function(a, b) {
if (a === b) {
return -1;
}
return Math.max(a.length, b.length);
};
var findLUSlength = function(a, b) {
return a === b?-1: Math.max(a.length, b.length);
};
第五题：637. Average of Levels in Binary Tree
DescriptionHintsSubmissionsDiscussSolution Discuss Pick One Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node’s value is in the range of 32-bit signed integer.
思路： 一个简单的广度优先搜索，难点在于思考广度优先搜索每一层的个数鉴定
解
var averageOfLevels = function(root) {
var levels = [];
visit(root, 0);
function visit(node, h) {
if (node == null) return;
if (levels.length <= h) levels.push([]);
levels[h].push(node.val);
visit(node.left, h+1);
visit(node.right, h+1);
}
return levels.map(function(e){
return e.reduce(function(a,b){ return a+b; })/e.length;
});
};
第六题：292. Nim Game
You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
` For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend. `
思路
因为只能移动1、2、3块石头，所以只要对手最后拿的时候剩下4块石头，那无论他拿走几块石头，我都可以全部拿完，而之前每次拿石头，不管对手拿几个，
我都以凑够4个为目标拿。所以在我第一个拿石头的前提下，只要总数除以4有余数，我第一次拿余数即可保证对手最后一次拿之前只剩下4颗石
解
var canWinNim = function(n) { return (n%4!== 0); };
第七题：136. Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
思路
数组中有若干个整数，除某个特殊的整数之外，其它的元素都出现了2次。 这个特殊的整数，它只出现了一次。
任意整数与自己进行异或操作（xor），结果都是：0。
var singleNumber = function(nums) {
var n = 0;
for (var i=0;i<nums.length; i++)
{
n ^= nums[i];
}
return n;
};
第八题： 693. Binary Number with Alternating Bits
Example 1:
Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101
Example 2: ` Input: 7 Output: False Explanation: The binary representation of 7 is: 111.`
Example 3: ` Input: 11 Output: False Explanation: The binary representation of 11 is: 1011.`
Example 4:
Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.
解答
var hasAlternatingBits = function(n) {
var str = n.toString(2);
var temp = str[0];
for(var i= 1;i<str.length;i++){
if(temp == str[i]){
return false
}
temp = str[i];
}
return true;
};
第九题： 191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
Credits:
Special thanks to @ts for adding this problem and creating all test case
解
var hammingWeight = function(n) {
var str = n.toString(2);
var res = 0;
for(var i= 0;i<str.length;i++){
if(str[i] == 1){
res++;
}
}
return res;
};
最优解
var hammingWeight = function(n) {
return n.toString(2).replace(/0/g,'').length;
};
第十题 617. 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:
Input: 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.
解
`
var 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;
};
`
优化解
`
var mergeTrees = function(t1, t2) {
if(!t1){return t2;}
if (!t2) {return t1};
t1.val = t1.val + t2.val;
t1.left = mergeTrees(t1.left,t2.left);
t1.right = mergeTrees(t1.right,t2.right);
return t1;
};
`
