lc25

发表于

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
  let slow = 0
  for(let fast = 0; fast < nums.length; fast++){
    if(val !== nums[fast]) nums[slow++] = nums[fast]
  }
  return slow
};

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
  let n = nums.length - 1
  let ans = new Array(n).fill(0)
  for(let i = 0, j = nums.length - 1; i <= j;){
    if(nums[i] * nums[i] > nums[j] * nums[j]) ans[n--] = nums[i] * nums[i++]
    else ans[n--] = nums[j] * nums[j--]
  }
  return ans
};

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
  let l = 0, r = 0, minLen = Number.MAX_VALUE , sum = 0, subLen = 0
  while(r < nums.length){
    sum += nums[r]
    while(sum >= target){
      subLen = r - l + 1
      minLen = minLen < subLen ? minLen : subLen
      sum -= nums[l++]
    }
    r++
  }
  return minLen === Number.MAX_VALUE ? 0 : minLen
};

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
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
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
  if(matrix.length === 0) return []
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1
  let res = []
  while(top < bottom && left < right){
    for (let i = left; i < right; i++) res.push(matrix[top][i]); 
    for (let i = top; i < bottom; i++) res.push(matrix[i][right]);
    for (let i = right; i > left; i--) res.push(matrix[bottom][i]);
    for (let i = bottom; i > top; i--) res.push(matrix[i][left]);
    right--;
    top++;
    bottom--;
    left++;

  } 

  if(top === bottom) {
    for(let i = left; i <= right; i++) res.push(matrix[top][i])
  }

  else if(left === right) {
    for(let i = top; i <= bottom; i++) res.push(matrix[i][left])
  }
  return res
};

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

1
2
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

1
2
输入：n = 1
输出：[[1]]
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
/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
  const ans = new Array(n).fill(0).map(() => new Array(n).fill(0))
  let left = 0, right = n - 1, top = 0, bottom = n - 1
  let k = 1
  while(left < right && top < bottom){
    for(let i = left; i < right; i++) ans[top][i] = k++
    for(let i = top; i < bottom; i++) ans[i][right] = k++
    for(let i = right; i > left; i--) ans[bottom][i] = k++
    for(let i = bottom; i > top; i--) ans[i][left] = k++
    bottom--
    right--
    left++
    top++
  }

  if(top === bottom) {
    for(let i = left; i <= right; i++) ans[top][i] = k++
  }
  else if(left === right) {
    for(let i = top; i <= bottom; i++) ans[i][left] = k++
  }
  return ans
};

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：

输入：head = [], val = 1
输出：[]
示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

1
2
3
4
5
var removeElements = function(head, val) {
  if(head === null) return null
  head.next = removeElements(head.next, val)
  return head.val === val ? head.next : head
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var removeElements = function(head, val) {
  let dummy = new ListNode(-1)
  dummy.next = head
  let cur = head, pre = dummy
  while(cur){
    while(cur && cur.val === val){
      pre.next = cur.next
      cur = pre.next
    }
    
    if(cur) {
      cur = cur.next
      pre = pre.next
    }
  }

  return dummy.next
};

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

示例 3：

1
2
输入：head = []
输出：[]
1
2
3
4
5
6
7
8
9
10
11
var reverseList = function(head) {
  
  let cur = head, pre = null
  while(cur){
    let temp = cur.next
    cur.next = pre
    pre = cur
    cur = temp
  }
  return pre
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  return reverse(null, head)
};

function reverse(pre, cur){
  if(cur === null) return pre
  let temp = cur.next
  cur.next = pre
  pre = cur
  cur = temp
  return reverse(pre, cur)
}