问题： 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。 示例 1： 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出：2 示例 2： 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3 回答： var findCircleNum = function(isConnected) { let province = 0; let n = isConnected.length; let visted = new Array(n).fill(false); var dfs = function(city) { visted[city] = true; for (let i = 0; i < n; i++) { //如果和其他城市相连，并且其他城市没去过 if (isConnected[city][i] == 1 && !visted[i]) { dfs(i) } } } for (let i = 0; i < n; i++) { if (!visted[i]) { dfs(i); province++; } } return province; };

问题： 实现 pow( x , n ) ，即计算 x 的整数 n 次幂函数（即， xn ）。 示例 1： 输入：x = 2.00000, n = 10 输出：1024.00000 示例 2： 输入：x = 2.10000, n = 3 输出：9.26100 示例 3： 输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25 回答： 一开始想着几次幂就相乘多少次，时间复杂度n会超时，采用递归 var myPow = function(x, n) { if (x == 1 || n == 0) return 1; if (n < 0) { x = 1 / x; n = -n; } var pow = function(x, n) { //递归终止条件 if (n == 0) return 1; let half = pow(x, Math.floor(n / 2)); if (n % 2 == 0) { return half * half } else { return half * half * x; } } return pow(x, n) };

问题： 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意： 有效的算符为 '+' 、 '-' 、 '*' 和 '/' 。 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。 示例 1： 输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 示例 2： 输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 示例 3： 输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 回答： var evalRPN = function(tokens) { let stack = []; for (let token of tokens) { if (['+', '-', '*', '/'].indexOf(token) != -1) { let back = stack.pop(); let front = stack.pop(); let cur = 0; if (token == '+') { cur = front + back; } else if (token == '-') { cur = front - back; } else if (token == '*') { cur = front * back; } else { cur = Math.trunc(front / back); } stack.push(cur) } else { stack.push(Number(token)); } } return stack.pop(); };

问题： 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2 。 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。 你所设计的解决方案必须只使用常量级的额外空间。 示例 1： 输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 示例 2： 输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。 示例 3： 输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。 回答： var twoSum = function(numbers, target) { let left = 0; let right = numbers.length - 1; while (left < right) { let sum = numbers[left] + numbers[right] if (sum == target) { return [left + 1, right + 1] } else if (sum > target) { right--; } else { left++; } } };

问题： 给你一个数组 nums 和一个值 val ，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k ，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。 nums 的其余元素和 nums 的大小并不重要。 返回 k 。 用户评测： 评测机将使用以下代码测试您的解决方案： int[] nums = [...]; // 输入数组 int val = ...; // 要移除的值 int[] expectedNums = [...]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。 int k = removeElement(nums, val); // 调用你的实现 assert k == expectedNums.length; sort(nums, 0, k); // 排序 nums 的前 k 个元素 for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } 如果所有的断言都通过，你的解决方案将会 通过 。 示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2,_,_] 解释：你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。 示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3,_,_,_] 解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。 回答： var removeElement = function(nums, val) { let left = 0; let right = nums.length - 1; while (left <= right) { if (nums[left] == val) { [nums[left], nums[right]] = [nums[right], nums[left]]; right--; } else { left++; } } return left; };

问题： 返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。 请注意， 除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如， 01 有一个前导零，所以是无效的；但 0 是有效的。 你可以按 任何顺序 返回答案。 示例 1： 输入：n = 3, k = 7 输出：[181,292,707,818,929] 解释：注意，070 不是一个有效的数字，因为它有前导零。 示例 2： 输入：n = 2, k = 1 输出：[10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98] 示例 3： 输入：n = 2, k = 0 输出：[11,22,33,44,55,66,77,88,99] 示例 4： 输入：n = 2, k = 2 输出：[13,20,24,31,35,42,46,53,57,64,68,75,79,86,97] 回答： var numsSameConsecDiff = function(n, k) { let res = []; let target = 0; let len = 0; var backTrack = function() { if (len == n) { res.push(target); return }; for (let i = 0; i <= 9; i++) { if (len == 0 && i == 0) continue; if (len > 0 && Math.abs(target % 10 - i) != k) continue; target = target * 10 + i; len++ backTrack(); target = Math.floor(target / 10); len--; } } backTrack(); return res; };

问题： 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词 。 示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false 回答： var isAnagram = function(s, t) { let map = new Map(); for (let i = 0; i < s.length; i++) { map.set(s[i], (map.get(s[i]) || 0) + 1); } for (let i = 0; i < t.length; i++) { if (map.has(t[i]) && map.get(t[i]) >= 1) { map.set(t[i], map.get(t[i]) - 1) if (map.get(t[i]) == 0) { map.delete(t[i]) } } else { return false; } } return map.size == 0; };

问题： 有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。 在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1 ，否则 grumpy[i] = 0 。 当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。 书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。 请你返回 这一天营业下来，最多有多少客户能够感到满意 。 示例 1： 输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3 输出：16 解释：书店老板在最后 3 分钟保持冷静。 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16. 示例 2： 输入：customers = [1], grumpy = [0], minutes = 1 输出：1 回答： 固定窗口大小的滑动窗口 var maxSatisfied = function(customers, grumpy, minutes) { let n = customers.length let max = 0; let common = 0; //正常顾客满意的数量 let extra = 0; //使用minutes后额外增幅 for (let i = 0; i < n; i++) { if (grumpy[i] == 0) { common = common + customers[i]; } if (i < minutes && grumpy[i] == 1) { extra = extra + customers[i]; } } max = extra; for (let i = minutes; i < n; i++) { if (grumpy[i - minutes] == 1) { extra = extra - customers[i - minutes]; } if (grumpy[i] == 1) { extra = extra + customers[i]; } max = Math.max(max, extra) } return common + max; };

问题： nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中 nums1 是 nums2 的子集。 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。 示例 1： 输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 示例 2： 输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。 回答： var nextGreaterElement = function(nums1, nums2) { let stack = []; let map = new Map(); for (let i = 0; i < nums2.length; i++) { while (stack.length && nums2[i] > stack[stack.length - 1]) { map.set(stack.pop(), nums2[i]) } stack.push(nums2[i]); } return nums1.map((num) => map.get(num) || -1) }

问题： 给你一个非负整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ： 例如， nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 示例 1： 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3 示例 2： 输入：nums = [1], target = 1 输出：1 回答： 思路： 假设所有+的数的总和是a, 所有-的数的总和是b 那么 a + b 为nums所有数总和sum， a - b 为target， 所以可以得出 2a = sum + target，也就是 a = (sum + target) / 2; var findTargetSumWays = function(nums, target) { let sum = nums.reduce((a, b) => a + b, 0); let total = sum + target; if (total < 0 || total % 2 != 0) { return 0 }; let goal = total / 2; let dp = new Array(goal + 1).fill(0); dp[0] = 1; for (let num of nums) { for (let i = goal; i >= num; i--) { dp[i] = dp[i] + dp[i - num]; } } return dp[goal] };