1. 1. 1 Two Sum
    1. 1.1. Description
    2. 1.2. Solution
    3. 1.3. Perf
  2. 2. Range Sum of BST
    1. 2.1. Description
    2. 2.2. Solution
  3. 3. 709. To Lower Case
    1. 3.1. Solution
  4. 4. 1021. Remove Outermost Parentheses
    1. 4.1. 题解
  5. 5. 905. Sort Array By Parity
    1. 5.1. 题解
Table of Contents

Leetcode First Round

工作四年后,算法几乎不会写了。每次面试,都会让候选人写一些简单的算法,不知道是岗位问题还是时代变了,很少遇到能给出比较合理的方案的;只是转念一想,自己现在恐怕也好不到哪去,不禁唏嘘不安,在此每天坚持更新一道 leetcode 题目,从简到难。

1 Two Sum

Description

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].

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const numsMap = {};
  nums.forEach((num, index) => {
    if(numsMap[num] === undefined) {
      numsMap[num] = index;
    }
  });

  for(let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if(numsMap[complement] !== undefined && numsMap[complement] !== i) {
      return [i, numsMap[complement]];
    }
  }

  return [];
};

Perf

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const numsMap = {};
  for(let i = 0; i < nums.length; i++){
    if(numsMap[nums[i]] !== undefined) {
      return [numsMap[nums[i]], i];
    }

    // reduce unnecessary compulation
    numsMap[target - nums[i]] = i;
  }
};

Complexity Analysis

  • Time complexity: O(n).

  • Space comlexity: O(n).


Range Sum of BST

Description

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R(inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32

Example 2:

Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} L
 * @param {number} R
 * @return {number}
 */
var rangeSumBST = function(root, L, R) {
  if(root === null) {
    return 0;
  }

  let sum = 0;
  if(root.val >= L && root.val <= R) {
    sum += root.val;
  }

  const left = root.left && L < root.val ? rangeSumBST(root.left, L, R) : 0;
  const right = root.right && R > root.val ? rangeSumBST(root.right, L, R) : 0;

  return sum + left + right;
};

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

709. To Lower Case

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

Example 1:

Input: "Hello"
Output: "hello"

Example 2:

Input: "here"
Output: "here"

Example 3:

Input: "LOVELY"
Output: "lovely"

Solution

/**
 * @param {string} str
 * @return {string}
 */
var toLowerCase = function(str) {
    return str.toLowerCase()
};

本题很简单,但确可以引出另外的问题,看下面的解法:

var toLowerCase = function(str) {
  let result = '';
  for(let i = 0; i < str.length; i++) {
    result += String.fromCharCode(str[i].charCodeAt(0) | 32);
  }
  return result;
};

A 的 ASCII 码是65,a 97,两者正好相差32,2^5 。

注意 32 和 65,大写字母二进制的第6位(1000000)一定为0,那将第6位变成1(加上32)正好就是其对应的小写字母,按位或就非常适合这类场景。

注: 该方法是有缺陷的,若输入包含其他非字母符号,需要对这些符号单独处理。

既然有大写转换为小写,同样的思路,如何实现小写转大写。小写转大写即将第6为位从 1 变为 0。所以这个问题可以转换成,将某二进制位n设置为0。

1 => 0
0 => 0

有什么方法实现上述逻辑, code & 0

a & ~(1 << 5)

那大小写反转呢,那就使用按位异或吧

a ^ (1 << 5)

总结,按位运算可以极大提升运算效率,但位运算理解起来并不直观,多总结其特性和常见使用场景。


1021. Remove Outermost Parentheses

A valid parentheses string is either empty (""), "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + ... + P_k, where P_i are primitive valid parentheses strings.

Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.

Example 1:

Input: "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".

Example 2:

Input: "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".

Example 3:

Input: "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".

题解

题目大意是去掉最外层的括号,用可以操作的语言描述就是,打印除了最外层括号外的所有括号。注意看题目描述的括号拆分(primitive decomposition)的规律。
举个例子: 如果 S = (A + B),那就输出AB,其实A,B是非空有效括号字符串。

题目意思明白这题基本就解决了,括号的问题一般用会想到栈,先进后出的特性非常适合解决配对的问题,试着用栈做:

  1. init ans = '', 循环遍历S
  2. if S[i] === '(', 压栈;如果栈长度为 1,记录此时的下标 start = i
  3. if S[i] === ')' 出栈;如果栈为空,记录下标 end = i;
  4. 追加 S[start + 1]S[end - 1] 之间(包含)的字符串到 ans

该方法思路简单,但输出繁琐,考虑到该题目只是要求去掉外层括号,所以遍历的时候打印除外层括号外的所有括号即可:

  1. init opened = 0; ans = '';
  2. if S[i] === '(' && ++opened > 1, ans += '(';
  3. if S[i] === ')' && --opened > 0, ans += ')'
var removeOuterParentheses = function(S) {
  let ans = '';
  let opened = 0;
  for(let i = 0; i < S.length; i++) {
    if(S[i] === '(' && ++opened > 1) {
      ans += '(';
    }
    if(S[i] === ')' && --opened > 0) {
      ans += ')';
    }
  }

  return ans;
};

905. Sort Array By Parity

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

  1. 1 <= A.length <= 5000
  2. 0 <= A[i] <= 5000

题解

创建两个数组,分别存储奇数和偶数,最后合并两个数组。

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParity = function(A) {
  const odds = [];
  const evens = [];
  A.forEach(item => {
    if(item % 2 === 0){
      return evens.push(item);
    }
    return odds.push(item);
  })
  return evens.concat(odds);
};

复杂度分析

  • 空间复杂度: O(n)
  • 时间复杂度:O(n)