Leetcode 解题记录

Two sum

From https://leetcode.com/problems/two-sum/description/

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

#1 for（暴力方式）

Runtime: 195ms

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

---

Climbing Stairs

From https://leetcode.com/problems/climbing-stairs/description/

Description

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output:  3
Explanation:  There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

#1 递归（从上至下）

Time Limit Exceeded

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 0 || n === 1) {
        return 1
    }
    
    return climbStairs(n-1) + climbStairs(n-2)
    
};

#2 使用数组（从下至上）

Runtime: 82ms

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const arr = []
    arr[0] = 1
    arr[1] = 1
    
    for (let i = 2; i <= n+1; i++) {
        arr[i] = arr[i-1] + arr[i-2]
    }
    
    return arr[n]
};

Reference

• 关于爬楼梯算法分析

---

Isomorphic Strings

From https://leetcode.com/problems/isomorphic-strings/description/

Description

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

#1 记录并检查字母第一次出现的位置

Runtime: 88ms

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function(s, t) {
    if (s.length <= 1) return true
    
    let alphabetIndexMap = {
        first: {},
        second: {},
    }
    
    for(let i = 0; i < s.length; i++) {
        const firstWordCurrentAlphabet = s.substr(i, 1)
        const secondWordCurrentAlphabet = t.substr(i, 1)
        
        const firstWordCurrentAlphabetFirstIndex = alphabetIndexMap.first[firstWordCurrentAlphabet]
        const secondWordCurrentAlphabetFirstIndex = alphabetIndexMap.second[secondWordCurrentAlphabet]
        
        if (!firstWordCurrentAlphabetFirstIndex && !secondWordCurrentAlphabetFirstIndex) {
            alphabetIndexMap.first[firstWordCurrentAlphabet] = i
        }
        
        if (!secondWordCurrentAlphabetFirstIndex) {
            alphabetIndexMap.second[secondWordCurrentAlphabet] = i
        }
        
        if (firstWordCurrentAlphabetFirstIndex !== secondWordCurrentAlphabetFirstIndex) {
            return false
        }
    }
    
    return true
}

---

Merge Two Sorted Lists

Description

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

#1 递归查找下一项并push进数组，最后使用sort函数

Runtime: 122 ms

/**
 * 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) {
    let result = []

    const getVal = (list, list2) => {
        if (list && list.val !== null) {
            result.push(list.val)
        }
        
        if ((!list || list.val === null || !list.next) && list2) {
            return getVal(list2)
        }

        if (list && list.next) {
            return getVal(list.next, list2)
        }
        
        return result
    }
    
    return getVal(l1, l2).sort((a, b) => a-b)
    
};

注意：这里有两个需要注意的点

1. 输入的listNode有可能为空或者为0，不可以直接使用 !list.val 判断
2. sort 函数不传入参数时默认是按照元素的ascii码增序排序的，负数排序存在问题，故传入 (a, b) => a-b 进行简单排序。