电影网站开发现状,linux系统运行wordpress,社区网站建设平台,漳州做网站建设的公司【题解】—— 每日一道题目栏 上接#xff1a;【题解】—— LeetCode一周小结9
4.用栈实现队列
题目链接#xff1a;232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作#xff08;push、pop、peek、empty#xff09;#xff1a…
【题解】—— 每日一道题目栏 上接【题解】—— LeetCode一周小结9
4.用栈实现队列
题目链接232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空返回 true 否则返回 false 说明
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。
示例 1
输入 [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2], [], [], []] 输出 [null, null, null, 1, 1, false] 解释 MyQueue myQueue new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false 提示 1 x 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作 题解 方法两个栈来模拟队列 入队操作直接将元素压入输入栈。出队或获取队首元素时如果输出栈为空则将输入栈的元素依次弹出并压入输出栈这样输出栈的栈顶元素即为队首元素。
import java.util.ArrayDeque;
import java.util.Deque;class MyQueue {DequeInteger inStack; // 输入栈用于入队操作DequeInteger outStack; // 输出栈用于出队操作/** Initialize your data structure here. */public MyQueue() {inStack new ArrayDequeInteger(); // 初始化输入栈outStack new ArrayDequeInteger(); // 初始化输出栈}/** Push element x to the back of queue. */public void push(int x) {inStack.push(x); // 将元素入栈}/** Removes the element from in front of queue and returns that element. */public int pop() {if (outStack.isEmpty()) { // 如果输出栈为空则将输入栈的元素转移到输出栈in2out();}return outStack.pop(); // 从输出栈中出栈元素}/** Get the front element. */public int peek() {if (outStack.isEmpty()) { // 如果输出栈为空则将输入栈的元素转移到输出栈in2out();}return outStack.peek(); // 查看输出栈的栈顶元素}/** Returns whether the queue is empty. */public boolean empty() {return inStack.isEmpty() outStack.isEmpty(); // 输入栈和输出栈都为空时队列为空}// 将输入栈的元素转移到输出栈private void in2out() {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}
} 5.到达目的地的方案数
题目链接1976. 到达目的地的方案数
你在一个城市里城市由 n 个路口组成路口编号为 0 到 n - 1 某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口且任意两个路口之间最多有一条路。
给你一个整数 n 和二维整数数组 roads 其中 roads[i] [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大将结果对 109 7 取余 后返回。
示例 1 输入n 7, roads [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]] 输出4 解释从路口 0 出发到路口 6 花费的最少时间是 7 分钟。 四条花费 7 分钟的路径分别为 0 ➝ 60 ➝ 4 ➝ 60 ➝ 1 ➝ 2 ➝ 5 ➝ 60 ➝ 1 ➝ 3 ➝ 5 ➝ 6 示例 2 输入n 2, roads [[1,0,10]] 输出1 解释只有一条从路口 0 到路口 1 的路花费 10 分钟。 提示 1 n 200 n - 1 roads.length n * (n - 1) / 2 roads[i].length 3 0 ui, vi n - 1 1 timei 109 ui ! vi 任意两个路口之间至多有一条路。 从任意路口出发你能够到达其他任意路口。 题解 方法朴素 Dijkstra适用于稠密图 计算从起点到终点的路径数量。使用了 Dijkstra 算法来计算最短路径同时记录了每个节点处的路径数量。
import java.util.Arrays;class Solution {public int countPaths(int n, int[][] roads) {long[][] g new long[n][n]; // 邻接矩阵for (long[] row : g) {Arrays.fill(row, Long.MAX_VALUE / 2); // 防止溢出}for (int[] r : roads) {int x r[0];int y r[1];int d r[2];g[x][y] d;g[y][x] d;}long[] dis new long[n];Arrays.fill(dis, 1, n, Long.MAX_VALUE / 2);int[] f new int[n];f[0] 1;boolean[] done new boolean[n];while (true) {int x -1;for (int i 0; i n; i) {if (!done[i] (x 0 || dis[i] dis[x])) {x i;}}if (x n - 1) {// 不可能找到比 dis[n-1] 更短或者一样短的最短路了注意本题边权都是正数return f[n - 1];}done[x] true; // 最短路长度已确定无法变得更小for (int y 0; y n; y) { // 尝试更新 x 的邻居的最短路long newDis dis[x] g[x][y];if (newDis dis[y]) {// 就目前来说最短路必须经过 xdis[y] newDis;f[y] f[x];} else if (newDis dis[y]) {// 和之前求的最短路一样长f[y] (f[y] f[x]) % 1_000_000_007;}}}}
}方法堆优化 Dijkstra适用于稀疏图 计算从起点到终点的路径数量。使用了 Dijkstra 算法来计算最短路径并在遍历过程中记录了每个节点处的路径数量。
import javafx.util.Pair;import java.util.*;class Solution {public int countPaths(int n, int[][] roads) {Listint[][] g new ArrayList[n]; // 邻接表Arrays.setAll(g, i - new ArrayList());for (int[] r : roads) {int x r[0];int y r[1];int d r[2];g[x].add(new int[]{y, d});g[y].add(new int[]{x, d});}long[] dis new long[n];Arrays.fill(dis, 1, n, Long.MAX_VALUE);int[] f new int[n];f[0] 1;PriorityQueuePairLong, Integer pq new PriorityQueue(Comparator.comparingLong(Pair::getKey));pq.offer(new Pair(0L, 0));while (true) {PairLong, Integer pair pq.poll();long dx pair.getKey();int x pair.getValue();if (x n - 1) {// 不可能找到比 dis[n-1] 更短或者一样短的最短路了注意本题边权都是正数return f[n - 1];}if (dx dis[x]) {continue;}for (int[] e : g[x]) { // 尝试更新 x 的邻居的最短路int y e[0];long newDis dx e[1];if (newDis dis[y]) {// 就目前来说最短路必须经过 xdis[y] newDis;f[y] f[x];pq.offer(new Pair(newDis, y));} else if (newDis dis[y]) {// 和之前求的最短路一样长f[y] (f[y] f[x]) % 1_000_000_007;}}}}
}
题单Dijkstra 算法
743. 网络延迟时间 2642. 设计可以求最短路径的图类 1514. 概率最大的路径 1631. 最小体力消耗路径 做法不止一种 1368. 使网格图至少有一条有效路径的最小代价 可以 0-1 BFS 1786. 从第一个节点出发到最后一个节点的受限路径数 1976. 到达目的地的方案数 2662. 前往目标的最小代价 2045. 到达目的地的第二短时间 可以 BFS 882. 细分图中的可到达节点 2203. 得到要求路径的最小带权子图 2577. 在网格图中访问一个格子的最少时间 2699. 修改图中的边权 2093. 前往目标城市的最小费用会员题 2473. 购买苹果的最低成本会员题 2714. 找到最短路径的 K 次跨越会员题 2737. 找到最近的标记节点会员题 LCP 35. 电动车游城市 6.找出数组中的 K-or 值
题目链接2917. 找出数组中的 K-or 值
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
nums 中的 K-or 是一个满足以下条件的非负整数
只有在 nums 中至少存在 k 个元素的第 i 位值为 1 那么 K-or 中的第 i 位的值才是 1 。 返回 nums 的 K-or 值。
注意 对于整数 x 如果 (2iAND x) 2i 则 x 中的第 i 位值为 1 其中 AND 为按位与运算符。
示例 1 输入nums [7,12,9,8,9,15], k 4 输出9 解释 nums[0]、nums[2]、nums[4] 和 nums[5] 的第 0 位的值为 1 。 nums[0] 和 nums[5] 的第 1 位的值为 1 。 nums[0]、nums[1] 和 nums[5] 的第 2 位的值为 1 。 nums[1]、nums[2]、nums[3]、nums[4] 和 nums[5] 的第 3 位的值为 1 。 只有第 0 位和第 3 位满足数组中至少存在 k 个元素在对应位上的值为 1 。因此答案为 2^0 2^3 9 。 示例 2 输入nums [2,12,1,11,4,5], k 6 输出0 解释因为 k 6 nums.length 所以数组的 6-or 等于其中所有元素按位与运算的结果。因此答案为 2 AND12 AND 1 AND 11 AND 4 AND 5 0 。 示例 3 输入nums [10,8,5,9,11,6,8], k 1 输出15 解释因为 k 1 数组的 1-or 等于其中所有元素按位或运算的结果。因此答案为 10 OR 8 OR 5 OR 9 OR 11OR 6 OR 8 15 。 提示 1 nums.length 50 0 nums[i] 231 1 k nums.length 题解 方法位运算 目的是找到数组 nums 中的元素的二进制表示中每一位上出现次数至少为 k 次的位。它通过逐位检查数组中所有元素的二进制表示统计每一位上为 1 的个数如果某一位上为 1 的个数不小于 k则将结果中对应位置为 1。
知识点从集合论到位运算常见位运算技巧分类总结
class Solution {public int findKOr(int[] nums, int k) {int ans 0;// 遍历每一位从最低位到最高位for (int i 0; i 31; i) {int cnt1 0;// 统计数组中当前位为 1 的个数for (int x : nums) {cnt1 x i 1;}// 如果当前位为 1 的个数不小于 k则在结果中将当前位置为 1if (cnt1 k) {ans | 1 i;}}return ans;}
}7.找出字符串的可整除数组
题目链接2575. 找出字符串的可整除数组
给你一个下标从 0 开始的字符串 word 长度为 n 由从 0 到 9 的数字组成。另给你一个正整数 m 。
word 的 可整除数组 div 是一个长度为 n 的整数数组并满足
如果 word[0,…,i] 所表示的 数值 能被 m 整除div[i] 1 否则div[i] 0 返回 word 的可整除数组。
示例 1 输入word “998244353”, m 3 输出[1,1,0,0,0,1,1,0,0] 解释仅有 4 个前缀可以被 3 整除“9”、“99”、“998244” 和 “9982443” 。 示例 2 输入word “1010”, m 10 输出[0,1,0,1] 解释仅有 2 个前缀可以被 10 整除“10” 和 “1010” 。 提示 1 n 105 word.length n word 由数字 0 到 9 组成 1 m 109 题解 方法模运算 计算给定字符串的模 m 可被整除的前缀长度数组。通过从左到右遍历 word。 设 ak1mr1, bk2mr2。 那么 (ab) mod m(r1r2) mod m(a mod mb mod m) mod m 初始化 x0每遇到一个数字 d就把 x 更新为 (10xd) mod m。
class Solution {/*** 计算给定字符串的模 m 可被整除的前缀长度数组。* 从左到右计算每个前缀的模运算结果并记录下能整除 m 的前缀长度。* param word 给定的字符串* param m 给定的模数* return 每个前缀的模 m 可被整除的长度数组*/public int[] divisibilityArray(String word, int m) {char[] s word.toCharArray();int[] ans new int[s.length]; // 用于存放结果的数组long x 0; // 存放当前前缀的模 m 的结果for (int i 0; i s.length; i) {x (x * 10 (s[i] - 0)) % m; // 从左到右依次计算前缀的模 m 结果if (x 0) { // 如果当前前缀的模 m 结果为 0则表示当前前缀可以被 m 整除ans[i] 1; // 标记当前前缀长度为能被 m 整除的长度}}return ans; // 返回结果数组}
} 8.找出美丽数组的最小和
题目链接2834. 找出美丽数组的最小和
给你两个正整数n 和 target 。
如果数组 nums 满足下述条件则称其为 美丽数组 。
nums.length n.nums 由两两互不相同的正整数组成。在范围 [0, n-1] 内不存在 两个 不同 下标 i 和 j 使得 nums[i] nums[j] target 。
返回符合条件的美丽数组所可能具备的 最小 和并对结果进行取模 109 7。
示例 1 输入n 2, target 3 输出4 解释nums [1,3] 是美丽数组。 nums 的长度为 n 2 。nums 由两两互不相同的正整数组成。不存在两个不同下标 i 和 j 使得 nums[i] nums[j] 3 。 可以证明 4 是符合条件的美丽数组所可能具备的最小和。 示例 2 输入n 3, target 3 输出8 解释 nums [1,3,4] 是美丽数组。 nums 的长度为 n 3 。nums 由两两互不相同的正整数组成。不存在两个不同下标 i 和 j 使得 nums[i] nums[j] 3 。 可以证明 8 是符合条件的美丽数组所可能具备的最小和。 示例 3 输入n 1, target 1 输出1 解释nums [1] 是美丽数组。 提示 1 n 109 1 target 109 题解 方法O(1) 数学公式
知识点O(1) 数学公式
class Solution {public int minimumPossibleSum(int n, int k) {long m Math.min(k / 2, n);return (int) ((m * (m 1) (n - m - 1 k * 2) * (n - m)) / 2 % 1_000_000_007);}
} 9.2386. 找出数组的第 K 大和
题目链接2386. 找出数组的第 K 大和
给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。
数组的 第 k 大和 定义为可以获得的第 k 个 最大 子序列和子序列和允许出现重复
返回数组的 第 k 大和 。
子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组且派生过程不改变剩余元素的顺序。
注意空子序列的和视作 0 。
示例 1 输入nums [2,4,-2], k 5 输出2 解释所有可能获得的子序列和列出如下按递减顺序排列 -6、4、4、2、2、0、0、-2 数组的第 5 大和是 2 。 示例 2 输入nums [1,-2,3,4,-10,12], k 16 输出10 解释数组的第 16 大和是 10 。 提示 n nums.length 1 n 105 -109 nums[i] 109 1 k min(2000, 2n) 题解 题目要计算 nums 中所有非负数的和记作 sum。 我们可以看到nums 的任意一个子序列的元素和都等价于从 sum 中减去某些非负数 / 加上某些负数得到。因为减去非负数和加上负数都相当于减去 ∣nums[i]∣。所以sum 减去的数越小nums 的子序列和就越大。 现在要解决得是 把每个 nums[i] 取绝对值后nums 的第 k 小的子序列和是多少
方法二分答案 爆搜
知识点二分原理
知识点子集型回溯 class Solution {public long kSum(int[] nums, int k) {long sum 0, right 0;for (int i 0; i nums.length; i) {if (nums[i] 0) {sum nums[i];} else {nums[i] -nums[i];}right nums[i];}Arrays.sort(nums);long left -1;while (left 1 right) { // 开区间二分原理见【前置知识】long mid (left right) / 2;cnt k - 1; // 空子序列算一个dfs(0, mid, nums);if (cnt 0) { // 找到 k 个元素和不超过 mid 的子序列right mid;} else {left mid;}}return sum - right;}private int cnt;// 反向递归增加改成减少这样可以少传一些参数private void dfs(int i, long s, int[] nums) {if (cnt 0 || i nums.length || s nums[i]) {return;}cnt--;dfs(i 1, s - nums[i], nums); // 选dfs(i 1, s, nums); // 不选}
}
方法最小堆
class Solution {public long kSum(int[] nums, int k) {long sum 0;for (int i 0; i nums.length; i) {if (nums[i] 0) {sum nums[i];} else {nums[i] -nums[i];}}Arrays.sort(nums);PriorityQueuePairLong, Integer pq new PriorityQueue((a, b) - Long.compare(a.getKey(), b.getKey()));pq.offer(new Pair(0L, 0)); // 空子序列while (--k 0) {PairLong, Integer p pq.poll();long s p.getKey();int i p.getValue();if (i nums.length) {// 在子序列的末尾添加 nums[i]pq.offer(new Pair(s nums[i], i 1)); // 下一个添加/替换的元素下标为 i1if (i 0) { // 替换子序列的末尾元素为 nums[i]pq.offer(new Pair(s nums[i] - nums[i - 1], i 1));}}}return sum - pq.peek().getKey();}
}10.猜数字游戏
题目链接299. 猜数字游戏
你在和朋友一起玩 猜数字Bulls and Cows游戏该游戏规则如下
写出一个秘密数字并请朋友猜这个数字是多少。朋友每猜测一次你就会给他一个包含下述信息的提示
猜测数字中有多少位属于数字和确切位置都猜对了称为 “Bulls”公牛 有多少位属于数字猜对了但是位置不对称为 “Cows”奶牛。也就是说这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。 给你一个秘密数字 secret 和朋友猜测的数字 guess 请你返回对朋友这次猜测的提示。
提示的格式为 “xAyB” x 是公牛个数 y 是奶牛个数A 表示公牛B 表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
示例 1 输入secret “1807”, guess “7810” 输出“1A3B” 解释数字和位置都对公牛用 ‘|’ 连接数字猜对位置不对奶牛的采用斜体加粗标识。 “1807” | “7810” 示例 2 输入secret “1123”, guess “0111” 输出“1A1B” 解释数字和位置都对公牛用 ‘|’ 连接数字猜对位置不对奶牛的采用斜体加粗标识。 “1123” “1123” | or | “0111” “0111” 注意两个不匹配的 1 中只有一个会算作奶牛数字猜对位置不对。通过重新排列非公牛数字其中仅有一个 1 可以成为公牛数字。 提示 1 secret.length, guess.length 1000 secret.length guess.length secret 和 guess 仅由数字组成 题解 方法模拟 对 secret 和 guess 进行诸位比较统计公牛数量 a 和奶牛数量 b。 对于字符相同的位置我们可以直接对 a 进行自增对于字符不同的位置使用哈希表进行分别统计 secret 和 guess 的词频某个数字 x 在两者词频中的较小值即为该数字对应的奶牛数量统计所有数字 [0,9]的奶牛数量总和即为 b。
class Solution {public String getHint(String secret, String guess) {int n secret.length();int a 0, b 0;int[] cnt1 new int[10], cnt2 new int[10];for (int i 0; i n; i) {int c1 secret.charAt(i) - 0, c2 guess.charAt(i) - 0;if (c1 c2) {a;} else {cnt1[c1];cnt2[c2];}}for (int i 0; i 10; i) b Math.min(cnt1[i], cnt2[i]);return a A b B;}
} 下接【题解】—— LeetCode一周小结11
