Find th Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
  s = s.split('').sort();
  t = t.split('').sort();

  for (var i = 0, len = t.length; i < len; i++) {
    if (s[i] !== t[i])
      return t[i];
  }
};

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

`
Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

/**
 * @param {number[]} nums
 * @return {number}
 */

// 时间复杂度O(n) & 空间复杂度O(n)
// 如果要求时间复杂度O(nlogn) & 空间复杂度O(1) 的解法
// 提供一种思路。用一个 string 存储数字，用一个特殊字符隔开
// 比如 "1,2,2,3,3,4,5,6"
// 然后二分查找，插入，因为插入只是 string 的简单拼接，所以速度应该不慢

var findDuplicate = function(nums) {
  var hash = {};
  for (var i = 0, len = nums.length; i < len; i++) {
    var item = nums[i];
    if (!hash[item])
      hash[item] = true;
    else 
      return item;
  }
};

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

n

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */

// easy binary search
// 有个坑，数据量很大，不能用位运算 ~~ 以及 >> 1
// 用 Math.floor(), Math.ceil() 以及 / 2 代替

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
      var start = 1
        , end = n;

      while (start <= end) {
        var mid = Math.floor((start + end) / 2);
        if (isBadVersion(mid) === true) 
          end = mid - 1;
        else 
          start = mid + 1;
      }

      return start;
    };
};

First Missing Positive

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3

Example 2:

Input: [3,4,-1,1]
Output: 2

Example 3:

Input: [7,8,9,11,12]
Output: 1

First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
  for (var i = 0, len = s.length; i < len; i++) {
    var item = s[i];
    if (s.lastIndexOf(item) === s.indexOf(item))
      return i;
  }

  return -1;
};