【JavaScript】LeetCode：26-30

26 矩阵置零

• 2次双重for循环。
• 第1次：将matrix[i][j]为0时的i、j分别存放于数组res_i、res_j，记录有哪些行、列应该置为0。
• 第2次：将记录中的行、列置为0。

/**- @param {number[][]} matrix- @return {void} Do not return anything, modify matrix in-place instead.*/
var setZeroes = function(matrix) {var row = matrix.length;var col = matrix[0].length;var res_i = [];var res_j = [];for(var i = 0; i < row; i++){for(var j = 0; j < col; j++){if(matrix[i][j] == 0){res_i.push(i);res_j.push(j);}}}for(var i = 0; i < row; i++){for(var j = 0; j < col; j++){if(res_i.includes(i) || res_j.includes(j)){matrix[i][j] = 0;}}}return matrix;
};

27 螺旋矩阵

• 创建方向数组dir[[0, 1], [1, 0], [0, -1], [-1, 0]]，分别对应“向右”，“向下”，“向左”，“向上”。
• 创建访问数组vis，记录该元素是否被访问。
• 当i或j超界，或元素已经被访问时，换方向。

/*** @param {number[][]} matrix* @return {number[]}*/
var spiralOrder = function(matrix) {var m = matrix.length;var n = matrix[0].length;var vis = new Array(m).fill(0).map(() => new Array(n).fill(0));var dir = [[0, 1], [1, 0], [0, -1], [-1, 0]];var count = 1, total = m * n;var x = 0, y = 0, d = 0;vis[0][0] = 1;var res = [];res.push(matrix[0][0]);while(count < total){x_ = x + dir[d][0];y_ = y + dir[d][1];if(x_ < 0 || x_ >= m || y_ < 0 || y_ >= n || vis[x_][y_] == 1){d = (d + 1) % 4}x = x + dir[d][0];y = y + dir[d][1];vis[x][y] = 1;count++;res.push(matrix[x][y]);}return res;
};

28 旋转图像

• 按照规律旋转：
  temp = matrix[i][j];
  matrix[i][j] = matrix[n - 1 - j][i];
  matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
  matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
  matrix[j][n - 1 - i] = temp;
• 图解如下：
  5    1   9   11  |  5    1   9    11  |  5    1   9   11  |  5    1   9   11
  2    4   8   10  |  2    4   8   10  |  2    4   8   10  |  2    4   8   10
  13  3   6    7   | 13   3   6    7   | 13   3   6    7   | 13   3   6    7
  15 14 12  16  | 15  14 12  16  | 15  14 12  16  | 15  14 12  16
  顺时针旋转，例：temp = 5，15 -> 5，16 -> 15，11 -> 16，temp -> 11。
• 当n为偶数时，取前n / 2行，前n / 2列元素为起点旋转。
  当n为奇数时，取前n / 2行，前(n + 1) / 2列元素为起点旋转。
  注意：使用Math.floor()向下取整。
  5    1   9   11
  2    4   8   10
  13  3   6    7
  15 14 12  16
  n = 4，取前2行、前2列元素为起点进行旋转。

/*** @param {number[][]} matrix* @return {void} Do not return anything, modify matrix in-place instead.*/
var rotate = function(matrix) {var n = matrix.length;var row = Math.floor(n / 2);var col = Math.floor((n + 1) / 2);for(var i = 0; i < row; i++){for(var j = 0; j < col; j++){var temp = matrix[i][j];matrix[i][j] = matrix[n - 1 - j][i];matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];matrix[j][n - 1 - i] = temp;}}return matrix;
};

29 搜索二维矩阵Ⅱ

• 从右上角matrix[0][col - 1]开始查找，i：0 ~ row，j：col ~ 0。
• 当matrix[i][j] = target时，说明已经找到目标值。
  当matrix[i][j] < target时，matrix[i][j]已经为该行的最大值，第i行最大值 < 目标值，说明目标值不在这行，i++。
  当matrix[i][j] > target时，matrix[i][j]已经为该列的最大值，第j列最大值 > 目标值，说明目标值不在这列，j–。

/*** @param {number[][]} matrix* @param {number} target* @return {boolean}*/
var searchMatrix = function(matrix, target) {var row = matrix.length;var col = matrix[0].length;var i = 0, j = col - 1;while(i < row && j >= 0){if(matrix[i][j] == target){return true;}else if(matrix[i][j] < target){i++;}else{j--;}}return false;
};

30 相交链表

• 方法1：哈希集合Set
• 将链表A的节点全部放入Set中，然后检查Set中是否存在链表B中的节点，若存在，则该节点为相交节点，否则返回null。

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} headA* @param {ListNode} headB* @return {ListNode}*/
var getIntersectionNode = function(headA, headB) {var set = new Set();while(headA != null){set.add(headA);headA = headA.next;}while(headB != null){if(set.has(headB)){return headB;}headB = headB.next;}return null;
};

• 方法2：链接两个链表
• (1) A和B长度相同且相交
• (2) A和B长度不同且相交
  A = a1 -> a2 -> c1 -> c2 -> c3
  B = b1 -> b2 -> b3 -> c1 -> c2 -> c3
  A + B = B + A
  a1 -> a2 -> c1 -> c2 -> c3 -> b1 -> b2 -> b3 -> c1 -> c2 -> c3 =
  b1 -> b2 -> b3 -> c1 -> c2 -> c3 -> a1 -> a2 -> c1 -> c2 -> c3
• (3) A和B不相交
• 若链表A遍历到最后一个节点了，则将其链接到链表B的头节点；若链表B遍历到最后一个节点了，则将其链接到链表A的头节点。

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*//*** @param {ListNode} headA* @param {ListNode} headB* @return {ListNode}*/
var getIntersectionNode = function(headA, headB) {var a = headA;var b = headB;while(a != b){if(a != null){a = a.next;}else{a = headB;}if(b != null){b = b.next;}else{b = headA;}}return a;
};