LeetCode 26 Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example, Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

思路

  • 用count来记录有多少个不重复的元素
  • 遇到重复的元素跳过
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if(nums == null || nums.length == 0) return 0;
    if(nums.length == 1) return 1;
    var count = 0;
    for(var i = 1 ; i < nums.length ; i++){
        if(nums[count] != nums[i]){
            count++;
            nums[count] = nums[i];
        }
    }    
    return ++count;
};

LeetCode 21 Merge Two Sorted Lists

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.

/**
 * 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) {
    var ans  = []
    while(l1 != null){
        ans.push(new ListNode(l1.val));//cut ListNode and push into an array
        l1 = l1.next;
    }
    while(l2 != null){
        ans.push(new ListNode(l2.val)); //cut ListNode and push into an array
        l2 = l2.next
    }

    ans.sort(function(a, b){  //sort the array
        return a.val - b.val;
    })

    if(ans.length==0) return null;
    for(var i = 0; i < ans.length-1; i++){   
        ans[i].next = ans[i+1]
    }

    return ans[0]
};

LeetCode 3 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

求最长非重复子串

比如 “abcabcbb” => “abc” =>长度为3
比如 “bbbbb” => “b” => 长度为1
比如 “pwwkew” => “wke” =>长度为3


/** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(s) { var hash = {}; var start = 0; var ans = 0; for (var i = 0, len = s.length; i < len; i++) { var item = s[i]; if (!hash[item]) // item 不在substring中 hash[item] = true; else { // item 已经在 substring 中存在了 for (; 😉 { if (s[start] === item) { // 开头重复 start++; break; } hash[s[start]] = false; //非开头重复 start++; } }// 结束 for loop ans = Math.max(ans, i - start + 1); } return ans; };

LeetCode 7 Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

解题思路

首先想到需要3种情况: 大于0和小于0的情况,可以用sign变量保存符号,然后在reverse。注意的是,overflow是在reverse完之后判断,因为input默认是没有overflow的.

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x){
    var sign= (x>0)?1: -1;
    x=Math.abs(x);
    var str=x.toString().split("").reverse().join("");
    var result=sign * Number(str);
    if(result > 2147483647 || result < -2147483648) return 0; // reverse 完之后判断
    else return result;
};

缺点是因为用了很多javascript built-in 函数,不适用别的语言

LeetCode 1 Two Sum

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

解题思路

刚开始感觉遍历所有两个元素的组合来判断是否等于目标值,需要n∗(n−1)/2 步。(O(n^2))

第一次尝试

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

测试

// Given nums = [2, 7, 11, 15], target = 9
[0,1]
// Given nums = [2, 8, 11, 15], target = 9
undefined

看起来这种方法应该符合条件,但其实不符合题目,题目说每个元素只能用一次,很明显第一种方法不符合题目(每个元素用了n-1次)

第二次尝试

题目要求每个元素只能用一次,那就意味着大O是O(n). 什么样的的算法可以遍历一遍所有元素判断出来呢?虽然,我想到了应该用map(hash table) 来写,但我对map不熟,看到别人的算法才明白该怎么做。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  var map = {}
  for(var i = 0; i < nums.length; i++){
    var v = nums[i]
    if(map[target - v] >= 0)   //判断target-v是否在map出现过(所有index都是大于等于0的数)
      return [map[target - v], i]
    else map[v]=i //用map储存数字和位置
  }
}

测试

// Given nums = [2, 7, 11, 15], target = 9
[0,1]
// Given nums = [2, 8, 11, 15], target = 9
undefined

这道题的解题关键是对hash table有很好的理解,切入点是每个元素只能用一次 ===> O(n). O(n) 意味着只能用一次for循环和大O是常数的算法,也只剩下hash table 能做到O(1)的search了。