Code@浮生记HomeArchivesTagsCategoriesGallery
LeetCode Notes 001
字数总计: 1,708|阅读时长: 11 分钟

Matrix

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input:

1
2
3
0 0 0
0 1 0
0 0 0

Output:

1
2
3
0 0 0
0 1 0
0 0 0

Example 2:

Input:

1
2
3
0 0 0
0 1 0
1 1 1

Output:

1
2
3
0 0 0
0 1 0
1 2 1

Note:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var updateMatrix = function(matrix) {
  // BFS
  let q = [];
  let hash = [];
  let [m, n] = [matrix.length, matrix[0].length];
  const dir = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  for (let i = 0; i < m; i++) {
    hash[i] = [];
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === 0) {
        q.push({x: i, y: j, step: 0});
        hash[i][j] = 0;
      }
    }
  }

  while (q.length) {
    let item = q.shift();
    let {x, y, step} = item;

    for (let i = 0; i < 4; i++) {
      let _x = x + dir[i][0];
      let _y = y + dir[i][1];
      if (_x < 0 || _x >= m || _y < 0 || _y >= n) continue;
      if (hash[_x][_y] !== undefined) continue;
      hash[_x][_y] = step + 1;
      q.push({x: _x, y: _y, step: step + 1});
    }
  }

  return hash;
};

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  nums.sort((a, b) => a - b)

  let ans = []
  let len = nums.length

  // enumerate the array, and assume the item to be the smallest one
  for (let i = 0; i < len; i++ ) { 

    // have already enumerate the item as the smallest one among the three
    // then continue
    if (i && nums[i] === nums[i - 1]) continue 

    // the sum of another two should be
    let target = -nums[i]

    // the indexes of another two 
    let [start, end] = [i + 1, len - 1]

    while (start < end) {
      let sum = nums[start] + nums[end]

      if (sum > target) {
        end--
      } else if (sum < target) {
        start++
      } else {
        ans.push([nums[i], nums[start], nums[end]])
        
        // remove the duplication
        while (nums[start] === nums[start + 1]) 
          start++
        start++

        // remove the duplication
        while (nums[end] === nums[end - 1])
          end--
        end--
      }
    }
  }

  return ans
}

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

function binarySearch(a, target) {
  var start = 0
    , end = a.length - 1;

  while(start <= end) {
    var mid = ~~((start + end) >> 1);
    if (a[mid] >= target)
      end = mid - 1;
    else 
      start = mid + 1;
  }

  return start;
}


var threeSumClosest = function(nums, target) {
  nums.sort(function(a, b) {
    return a - b;
  });

  var len = nums.length;
  var ans = Infinity;

  for (var i = 0; i < len; i++)
    for (var j = i + 1; j < len; j++) {
      var a = target - nums[i] - nums[j];
      var pos = binarySearch(nums, a);
      
      for (var k = Math.max(0, pos - 1); k <= Math.min(pos + 0, len - 1); k++) {
        if (k === i || k === j) 
          continue;

        var sum = nums[i] + nums[j] + nums[k];
        if (Math.abs(sum - target) < Math.abs(ans - target))
          ans = sum;
      }

    }

  return ans;
};

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
  nums.sort(function(a, b) {
    return a - b;
  });

  var hash = [];

  var len = nums.length;

  for (var i = 0; i < len; i++)
    for (var j = i + 1; j < len; j++) {
      var a = nums[i]
        , b = nums[j]
        , c = a + b;

      if (hash[c] === undefined) 
        hash[c] = [[i, j]];
      else 
        hash[c].push([i, j]);
    }

  var ans = [];

  var hashSet = {};

  for (var i = 0; i < len; i++)
    for (var j = i + 1; j < len; j++) {
      var a = nums[i]
        , b = nums[j]
        , sum = target - a - b;

      if (!hash[sum])
        continue;

      for (var k = 0, _len = hash[sum].length; k < _len; k++) {
        var item = hash[sum][k];

        if (item[0] === i || item[1] === i || item[0] === j || item[1] === j)
          continue;

        var c = nums[item[0]]
          , d = nums[item[1]];

        var tmp = [a, b, c, d].sort(function(a, b) {
          return a - b;
        });

        var str = tmp.join(',');
        if (!hashSet[str]) {
          hashSet[str] = true;
          ans.push(tmp);
        }
      }
    }

    return ans;
};

4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} A
 * @param {number[]} B
 * @param {number[]} C
 * @param {number[]} D
 * @return {number}
 */
var fourSumCount = function(A, B, C, D) {
  let p = new Map();
  for (let i = 0, lenA = A.length; i < lenA; i++)
    for (let j = 0, lenB = B.length; j < lenB; j++) {
      let sum = A[i] + B[j];
      let count = ~~p.get(sum);
      p.set(sum, count + 1);
    }

  let ans = 0;
  for (let i = 0, lenC = C.length; i < lenC; i++)
    for (let j = 0, lenD = D.length; j < lenD; j++) {
      let sum = C[i] + D[j];
      ans += ~~p.get(-sum);
    }

  return ans;
};

Add and Search Word – Data structure design

Design a data structure that supports the following two operations:

1
2
void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
function Node() {
  this.nodes = [];
  this.endFlag = false;
}

/**
 * @constructor
 */
var WordDictionary = function() {
  this.startNode = new Node();
  // 以该 node 结尾的单词存在
  this.startNode.endFlag = true;
};

/**
 * @param {string} word
 * @return {void}
 * Adds a word into the data structure.
 */
WordDictionary.prototype.addWord = function(word) {
  var node = this.startNode;

  for (var i = 0, len = word.length; i < len; i++) {
    var item = word.charCodeAt(i) - 97;
    if (!node.nodes[item]) {
      node.nodes[item] = new Node();
    }
    node = node.nodes[item];
  }

  node.endFlag = true;
};

/**
 * @param {string} word
 * @return {boolean}
 * Returns if the word is in the data structure. A word could
 * contain the dot character '.' to represent any one letter.
 */
WordDictionary.prototype.search = function(word) {
  var node = this.startNode;
  var isFound = false;

  dfs(node, 0);

  function dfs(node, index) {
    if (isFound)
      return;

    if (index === word.length) {
      isFound = node.endFlag;
      return;
    }

    if (word[index] === '.') {
      for (var i = 0; i < 26; i++) {
        if (node.nodes[i])
          dfs(node.nodes[i], index + 1);
      }
    } else {
      var item = word.charCodeAt(index) - 97;
      if (node.nodes[item])
        dfs(node.nodes[item], index + 1);
    }
  }

  return isFound;
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * var wordDictionary = new WordDictionary();
 * wordDictionary.addWord("word");
 * wordDictionary.search("pattern");
 */
文章作者: Monad Kai
文章链接: onlookerliu.github.io/2017/12/28/LeetCode-Notes-001/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Code@浮生记！
leetcodejavascript
支付宝打赏
微信打赏