523. 连续的子数组和
难度中等365收藏分享切换为英文接收动态反馈
给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
- 子数组大小 至少为 2 ，且
- 子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。
如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
示例 1：
输入：nums = [23,2,4,6,7], k = 6 输出：true 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
示例 2：
输入：nums = [23,2,6,4,7], k = 6 输出：true 解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 42 是 6 的倍数，因为 42 = 7 6 且 7 是一个整数。
示例 3：
输入：nums = [23,2,6,4,7], k = 13 *输出：false
提示：
- 1 <= nums.length <= 105
- 0 <= nums[i] <= 109
- 0 <= sum(nums[i]) <= 231 - 1
- 1 <= k <= 231 - 1
暴力解 TLE 超时
/*** @param {number[]} nums* @param {number} k* @return {boolean}*/var checkSubarraySum = function(nums, k) {const sums = [nums[0]];for (let i = 1; i< nums.length; i++) {sums[i] = sums[i-1] + nums[i];}for (let i = 0; i < nums.length; i++) {for (let j = i + 1; j < nums.length; j++) {const subSum = sums[j] - sums[i] + nums[i];if (subSum === 0 ) {return true}if (subSum % k === 0 && Math.floor(subSum/k) === subSum/k) {return true;}}}return false;};
73. 矩阵置零
难度中等550收藏分享切换为英文接收动态反馈
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶：
- 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个仅使用常量空间的解决方案吗？
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -231 <= matrix[i][j] <= 231 - 1
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
if (!matrix.length) {
return [];
}
let row0 = false;
let col0 = false;
for (let i = 0, len = matrix.length; i < len; i++) {
if (matrix[i][0] === 0) {
col0 = true;
break;
}
}
for (let i = 0, len = matrix[0].length; i < len; i++) {
if (matrix[0][i] === 0) {
row0 = true;
break;
}
}
for (let i = 0, len = matrix.length; i < len; i++) {
for (let j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] === 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (let i = 1, len = matrix.length; i < len; i++) {
for (let j = 1; j < matrix[i].length; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
if (col0) {
for (let i = 0; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
if (row0) {
for (let i = 0; i < matrix[0].length; i++) {
matrix[0][i] = 0;
}
}
return matrix;
};
49. 字母异位词分组
难度中等835收藏分享切换为英文接收动态反馈
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
示例 2:
输入: strs = [“”] 输出: [[“”]]
示例 3:
输入: strs = [“a”] 输出: [[“a”]]
提示：
- 1 <= strs.length <= 104
- 0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
/** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function(strs) { const getKey = (word) => { return word.split('').sort().join(''); }; return Object.values(strs.reduce((r, item, i) => { const key = getKey(item); r[key] = r[key] || []; r[key].push(item); return r; }, {})); };
334. 递增的三元子序列
难度中等341收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5] 输出：true 解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1] 输出：false 解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6] 输出：true 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示：
- 1 <= nums.length <= 105
- -231 <= nums[i] <= 231 - 1
/** * @param {number[]} nums * @return {boolean} */ var increasingTriplet = function (nums) { if (nums.length < 3) { return false; } let min = Number.MAX_SAFE_INTEGER; let max = Number.MAX_SAFE_INTEGER; for (let i = 0, len = nums.length; i < len; i++) { if (nums[i] > max) { return true; } else if (nums[i] > min) { max = nums[i]; } else { min = nums[i]; } } return false; };2. 两数相加
难度中等6690收藏分享切换为英文接收动态反馈
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围 [1, 100] 内
- 0 <= Node.val <= 9
- 题目数据保证列表表示的数字不含前导零
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
const base = 10;
let flag = 0;
let up = l1;
let down = l2;
let r = new ListNode(flag);
let current = r;
while (up || down) {
if (up) {
current.val += up.val;
up = up.next;
}
if (down) {
current.val += down.val;
down = down.next;
}
flag = Math.floor(current.val / base);
current.val = current.val % base;
if (up || down || flag) {
current.next = new ListNode(flag);
current = current.next;
}
}
return r;
};
328. 奇偶链表
难度中等463收藏分享切换为英文接收动态反馈
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL
说明:
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
/**
* 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 oddEvenList = function(head) {
if (!head) {
return head;
}
let evenHead = head.next;
let odd = head;
let even = evenHead;
while (odd.next && even.next) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
};
199. 二叉树的右视图
难度中等528收藏分享切换为英文接收动态反馈
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2:
输入: [1,null,3] 输出: [1,3]
示例 3:
输入: [] 输出: []
提示:
- 二叉树的节点个数的范围是 [0,100]
- -100 <= Node.val <= 100
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var rightSideView = function(root) {
const result = [];
if (!root) {
return result;
}
const qs = [[root]];
while (qs.length) {
const nodes = qs.shift();
if (nodes.length) {
result.push(nodes[nodes.length - 1].val);
}
const nextLevels = [];
for (let i = 0; i < nodes.length; i++) {
if (nodes[i].left) {
nextLevels.push(nodes[i].left);
}
if (nodes[i].right) {
nextLevels.push(nodes[i].right);
}
}
if (nextLevels.length) {
qs.push(nextLevels);
}
}
return result;
};
300. 最长递增子序列
难度中等1846收藏分享切换为英文接收动态反馈
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
提示：
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
进阶：
- 你可以设计时间复杂度为 O(n2) 的解决方案吗？
- 你能将算法的时间复杂度降低到 O(n log(n)) 吗?
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
if (nums.length === 0) {
return 0;
}
const dp = [];
dp.length = nums.length;
dp.fill(1);
let maxLen = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(1 + dp[j], dp[i]);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
};
406. 根据身高重建队列
难度中等979收藏分享切换为英文接收动态反馈
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
示例 2：
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
提示：
- 1 <= people.length <= 2000
- 0 <= hi <= 106
- 0 <= ki < people.length
- 题目数据确保队列可以被重建
/**
* @param {number[][]} people
* @return {number[][]}
*/
var reconstructQueue = (people) => {
const arrs = people.sort(childrenComparator);
const r = [];
for (let i = 0; i < arrs.length; i++) {
r.splice(arrs[i][1], 0, arrs[i]);
}
return r;
};
function childrenComparator(left, right) {
if (left[0] > right[0]) {
return -1;
} else if (left[0] === right[0]) {
return left[1] < right[1] ? -1 : 1;
}
return 1;
}
712. 两个字符串的最小ASCII删除和
难度中等229收藏分享切换为英文接收动态反馈
给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。
示例 1:
输入: s1 = “sea”, s2 = “eat” 输出: 231 解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。 在 “eat” 中删除 “t” 并将 116 加入总和。 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。
示例 2:
输入: s1 = “delete”, s2 = “leet” 输出: 403 解释: 在 “delete” 中删除 “dee” 字符串变成 “let”， 将 100[d]+101[e]+101[e] 加入总和。在 “leet” 中删除 “e” 将 101[e] 加入总和。 结束时，两个字符串都等于 “let”，结果即为 100+101+101+101 = 403 。 如果改为将两个字符串转换为 “lee” 或 “eet”，我们会得到 433 或 417 的结果，比答案更大。
注意:
- 0 < s1.length, s2.length <= 1000。
- 所有字符串中的字符ASCII值在[97, 122]之间。
/**
* @param {string} s1
* @param {string} s2
* @return {number}
*/
var minimumDeleteSum = function(s1, s2) {
const sl1 = s1.length, sl2 = s2.length;
const dp = new Array(sl1 + 1);
for (let i = 0; i <= sl1; i++) {
dp[i] = new Array(sl2 + 1).fill(0);
}
dp[0][0] = 0;
for (let i = 1; i <= sl2; i++) {
dp[0][i] = dp[0][i-1] + s2.charCodeAt(i-1);
}
for (let i = 1; i <= sl1; i++) {
dp[i][0] = dp[i-1][0] + s1.charCodeAt(i-1);
}
for (let i = 1; i <= sl1; i++) {
for (let j = 1; j <= sl2; j++) {
if (s1[i-1] === s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
}
else {
dp[i][j] = Math.min(
dp[i-1][j] + s1.charCodeAt(i-1),
dp[i][j-1] + s2.charCodeAt(j-1)
);
}
}
}
console.log(dp);
return dp[sl1][sl2];
};
若有收获，就点个赞吧
0 人点赞
