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].
#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)
};
注意：这里有两个需要注意的点
- 输入的listNode有可能为空或者为0，不可以直接使用
!list.val判断 -
sort函数不传入参数时默认是按照元素的ascii码增序排序的，负数排序存在问题，故传入(a, b) => a-b进行简单排序。
