腾讯云建设个人网站,桂林象鼻山介绍,流量网站怎么盈利,上海建设厅网站首页文章目录 竞赛链接Q1#xff1a;2848. 与车相交的点解法1——排序后枚举解法2——差分数组⭐差分数组相关题目列表#x1f4d5;1094. 拼车1109. 航班预订统计2381. 字母移位 II2406. 将区间分为最少组数解法1——排序贪心优先队列解法2——差分数组 2772. 使数组中的所有元素… 文章目录 竞赛链接Q12848. 与车相交的点解法1——排序后枚举解法2——差分数组⭐差分数组相关题目列表1094. 拼车1109. 航班预订统计2381. 字母移位 II2406. 将区间分为最少组数解法1——排序贪心优先队列解法2——差分数组 2772. 使数组中的所有元素都等于零2528. 最大化城市的最小供电站数目⭐差分数组 二分查找答案最大化最小化相关题目列表 Q22849. 判断能否在给定时间到达单元格脑筋急转弯、贪心Q32850. 将石头分散到网格图的最少移动次数⭐⭐⭐全排列和状态压缩解法1——枚举全排列解法2——最小费用最大流 TODO解法3——状压DP涉及到「匹配」的题目列表1947. 最大兼容性评分和解法1——枚举全排列解法2——状态压缩DP 1349. 参加考试的最大学生数状态压缩DPLCP 04. 覆盖TODO 二分图匹配 状态压缩DP解法1——二分图匹配解法2——状态压缩DP 1879. 两个数组最小的异或值之和状态压缩DP2172. 数组的最大与和状态压缩DP Q42851. 字符串转换⭐解法1——KMP 矩阵快速幂优化 DP 解法2——找规律无需矩阵快速幂TODO[矩阵快速幂] 题目列表 成绩记录 竞赛链接
https://leetcode.cn/contest/weekly-contest-362/
Q12848. 与车相交的点
https://leetcode.cn/problems/points-that-intersect-with-cars/description/ 提示 1 nums.length 100 nums[i].length 2 1 starti endi 100
解法1——排序后枚举
排序之后按顺序枚举每次比较和上个区间结束位置之间的关系。
class Solution {public int numberOfPoints(ListListInteger nums) {int ans 0, last -1;Collections.sort(nums, (x, y) - x.get(0) - y.get(0));for (ListInteger x: nums) {ans Math.max(0, x.get(1) - Math.max(last 1, x.get(0)) 1);last Math.max(last, x.get(1));}return ans;}
}解法2——差分数组⭐
https://leetcode.cn/problems/points-that-intersect-with-cars/solutions/2435384/chai-fen-shu-zu-xian-xing-zuo-fa-by-endl-3xpm/
关于差分可见【算法基础】1.5 前缀和与差分
class Solution {public int numberOfPoints(ListListInteger nums) {int[] diff new int[102];// 利用差分将区间内所有位置 1for (ListInteger p: nums) {diff[p.get(0)];diff[p.get(1) 1]--;}int ans 0, s 0;// 检查各个位置 如果0则ansfor (int d: diff) {s d;if (s 0) ans;}return ans;}
}差分数组相关题目列表
题目列表来源分享【算法小课堂】差分数组Python/Java/C/Go/JS
1094. 拼车
https://leetcode.cn/problems/car-pooling/ 提示
1 trips.length 1000 trips[i].length 3 1 numPassengersi 100 0 fromi toi 1000 1 capacity 10^5
用差分 表示 from 到 to 的范围内增加了多少人然后再还原。
class Solution {public boolean carPooling(int[][] trips, int capacity) {int[] diff new int[1002];// 构造差分数组for (int[] t: trips) {diff[t[1]] t[0];diff[t[2]] - t[0];}// 差分数组的还原for (int i 0; i 1000; i) {if (diff[i] capacity) return false;diff[i 1] diff[i];}return true;}
}1109. 航班预订统计
https://leetcode.cn/problems/corporate-flight-bookings/ 提示 1 n 2 * 10^4 1 bookings.length 2 * 10^4 bookings[i].length 3 1 firsti lasti n 1 seatsi 10^4
class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] ans new int[n], diff new int[n 1];for (int[] booking: bookings) {diff[booking[0] - 1] booking[2];diff[booking[1]] - booking[2];}for (int i 0; i n; i) {ans[i] diff[i];diff[i 1] diff[i];}return ans;}
}2381. 字母移位 II
https://leetcode.cn/problems/shifting-letters-ii/ 提示 1 s.length, shifts.length 5 * 10^4 shifts[i].length 3 0 starti endi s.length 0 directioni 1 s 只包含小写英文字母。
class Solution {public String shiftingLetters(String s, int[][] shifts) {int n s.length();// 构造差分数组int[] diff new int[n 1];for (int[] shift: shifts) {int t shift[2] 1? 1: -1;diff[shift[0]] t;diff[shift[1] 1] - t;}// 差分数组和答案的还原char[] ans new char[n];for (int i 0; i n; i) {ans[i] op(s.charAt(i), diff[i]);diff[i 1] diff[i];}return String.valueOf(ans);}// 对字符 a 移动 xpublic char op(char a, int x) {return (char)(((a - a x % 26) 26) % 26 a);}
}2406. 将区间分为最少组数
https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/ 提示
1 intervals.length 1^05 intervals[i].length 2 1 lefti righti 10^6
解法1——排序贪心优先队列
按照区间的开始位置从小到大排序。 想象每个组合就是一个列表我们使用有限队列维护这些列表的末尾位置。 这样每次枚举到一个新的区间检查是否可以放入已有列表中如果可以就将一个已有列表的末尾位置换成当前区间的结尾位置。
class Solution {public int minGroups(int[][] intervals) {Arrays.sort(intervals, (x, y) - x[0] - y[0]);PriorityQueueInteger pq new PriorityQueue((x, y) - x - y);for (int[] interval: intervals) {if (!pq.isEmpty() pq.peek() interval[0]) pq.poll();pq.offer(interval[1]);}return pq.size();}
}解法2——差分数组
差分还原中出现的最大值就是答案。
class Solution {public int minGroups(int[][] intervals) {TreeMapInteger, Integer diff new TreeMap();int ans 0, sum 0;// 计算差分for (int[] interval: intervals) {diff.merge(interval[0], 1, Integer::sum);diff.merge(interval[1] 1, -1, Integer::sum);}// 还原差分for (Map.EntryInteger, Integer entry: diff.entrySet()) {sum entry.getValue();ans Math.max(ans, sum);}return ans;}
}2772. 使数组中的所有元素都等于零
https://leetcode.cn/problems/apply-operations-to-make-all-array-elements-equal-to-zero/ 提示
1 k nums.length 10^5 0 nums[i] 10^6
有点差分的思想又不太一样。
贪心地从前往后枚举每一个位置只要 0 就减 0 就返回 false。
class Solution {public boolean checkArray(int[] nums, int k) {int n nums.length, diff 0, ans 0;int[] x new int[n];for (int i 0; i n; i) {if (i k) diff - x[i - k];if (nums[i] diff) {if (n - i k) return false;ans nums[i] - diff; // 更新答案x[i] nums[i] - diff; // 记录这个位置减去了多少diff nums[i]; // 更新diff} else if (nums[i] diff) return false;}return true;}
}2528. 最大化城市的最小供电站数目⭐差分数组 二分查找答案
https://leetcode.cn/problems/maximize-the-minimum-powered-city/ 提示 n stations.length 1 n 10^5 0 stations[i] 10^5 0 r n - 1 0 k 10^9
看到「最大化最小值」或者「最小化最大值」就要想到二分答案这是一个固定的套路。
class Solution {public long maxPower(int[] stations, int r, int k) {int n stations.length;long mn Long.MAX_VALUE;// 计算差分数组long[] cnt new long[n 1];for (int i 0; i n; i) {cnt[Math.max(0, i - r)] stations[i];cnt[Math.min(n, i r 1)] - stations[i];}// 差分数组的还原for (int i 0; i n; i) {cnt[i 1] cnt[i];mn Math.min(mn, cnt[i]);}// 二分查找答案long left mn, right mn k;while (left right) {long mid left right 1 1;if (!check(cnt, mid, r, k)) right mid - 1;else left mid;}return left;}// check过程类似 T2772. 使数组中的所有元素都等于零public boolean check(long[] cnt, long x, int r, int k) {long diff 0;int n cnt.length - 1;long[] d new long[n];for (int i 0; i n; i) {if (i 2 * r 1) diff - d[i - 2 * r - 1];if (cnt[i] diff x) {d[i] x - cnt[i] - diff;k - d[i];diff x - cnt[i];}}return k 0;}
}最大化最小化相关题目列表
见【算法】二分答案 对应部分。
Q22849. 判断能否在给定时间到达单元格脑筋急转弯、贪心
https://leetcode.cn/problems/determine-if-a-cell-is-reachable-at-a-given-time/ 提示 1 sx, sy, fx, fy 109 0 t 10^9
斜着走一步顶两步——相当于可以同时横着走和竖着走。 那么只要满足垂直和水平方向中最长的那个距离就好了。
注意有个特例是只走一步时如果起点和终点相同就不可以了。
class Solution {public boolean isReachableAtTime(int sx, int sy, int fx, int fy, int t) {if (sx fx sy fy t 1) return false; // 特例return t Math.max(Math.abs(sx - fx), Math.abs(sy - fy));}
}Q32850. 将石头分散到网格图的最少移动次数⭐⭐⭐全排列和状态压缩
https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/
提示
grid.length grid[i].length 3 0 grid[i][j] 9 grid 中元素之和为 9
解法1——枚举全排列
https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/solutions/2435313/tong-yong-zuo-fa-zui-xiao-fei-yong-zui-d-iuw8/
将起始点和终点分别放入两个列表做全排列匹配。 枚举所有全排列比较各种情况下的移动次数得出最小移动次数。
class Solution {int ans Integer.MAX_VALUE, sum 0;boolean[] st new boolean[9];public int minimumMoves(int[][] grid) {// 将起始点和终点放入列表Listint[] src new ArrayList(), dst new ArrayList();for (int i 0; i 3; i) {for (int j 0; j 3; j) {while (grid[i][j] 1) {src.add(new int[]{i, j});grid[i][j]--;}if (grid[i][j] 0) dst.add(new int[]{i, j});}}// dfs全排列dfs(0, src, dst);return ans;}public void dfs(int i, Listint[] src, Listint[] dst) {if (i src.size()) {ans Math.min(ans, sum);return;}for (int j 0; j dst.size(); j) {if (!st[j]) {int[] s src.get(i), d dst.get(j);sum Math.abs(s[0] - d[0]) Math.abs(s[1] - d[1]);st[j] true;dfs(i 1, src, dst);sum - Math.abs(s[0] - d[0]) Math.abs(s[1] - d[1]);st[j] false;}}}
}解法2——最小费用最大流 TODO
https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/solutions/2435313/tong-yong-zuo-fa-zui-xiao-fei-yong-zui-d-iuw8/
在这里插入代码片解法3——状压DP
https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/solutions/2435319/zhuang-ya-dp-by-tsreaper-jiw0/
状态压缩DP相比全排列速度更快48ms vs 3ms
class Solution {public int minimumMoves(int[][] grid) {// 起始点和目的点放入两个列表Listint[] L new ArrayList(), R new ArrayList();for (int i 0; i 3; i) {for (int j 0; j 3; j) {if (grid[i][j] 0) R.add(new int[]{i, j});else {for (; grid[i][j] 1; grid[i][j]--) {L.add(new int[]{i, j});}}}}// 状态压缩DPint n L.size();int[] dp new int[1 n];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] 0;for (int i 1; i (1n); i) {// 计算 i 中有几个二进制等于 1——为了确定当前目的点是哪个int cnt 0;for (int j 0; j n; j) {cnt i j 1;}// 状态转移for (int j 0; j n; j) { // 枚举所有目标点if ((i j 1) 1) { // 检查是否为1即是否可以从前面转移过来dp[i] Math.min(dp[i], dp[i ^ (1 j)] cost(R.get(cnt - 1), L.get(j)));}}}return dp[(1n) - 1];}public int cost(int[] a, int[] b) {return Math.abs(a[0] - b[0]) Math.abs(a[1] - b[1]);}
}涉及到「匹配」的题目列表
题单来源https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/solutions/2435313/tong-yong-zuo-fa-zui-xiao-fei-yong-zui-d-iuw8/
1947. 最大兼容性评分和
https://leetcode.cn/problems/maximum-compatibility-score-sum/ 提示 m students.length mentors.length n students[i].length mentors[j].length 1 m, n 8 students[i][k] 为 0 或 1 mentors[j][k] 为 0 或 1
解法1——枚举全排列
数据范围很小可以枚举出所有学生和老师之间匹配的方案。
class Solution {int ans 0;boolean[] st new boolean[8];public int maxCompatibilitySum(int[][] students, int[][] mentors) {// 全排列dfs(students, mentors, 0, 0);return ans;}public void dfs(int[][] students, int[][] mentors, int i, int sum) {if (i students.length) {ans Math.max(ans, sum);return;}for (int j 0; j mentors.length; j) {if (st[j]) continue;st[j] true;dfs(students, mentors, i 1, sum cp(students[i], mentors[j]));st[j] false;}}// 计算某个学生和某个老师的兼容性评分public int cp(int[] s, int[] t) {int res 0;for (int i 0; i s.length; i) {if (s[i] t[i]) res;}return res;}
}解法2——状态压缩DP
class Solution {public int maxCompatibilitySum(int[][] students, int[][] mentors) {int n students.length;int[][] dp new int[n 1][1n]; // dp[i][j]表示匹配完i个老师和集合j的学生的最大匹配和// 枚举每个状态for (int i 1; i (1n); i) {int idx Integer.bitCount(i); // 计算该匹配哪个老师了// 枚举每个学生for (int j 0; j n; j) {if ((i j 1) 1) { // 如果可以转移dp[idx][i] Math.max(dp[idx][i], dp[idx - 1][i ^ (1j)] cp(students[j], mentors[idx - 1]));}}}return dp[n][(1n) - 1];}// 计算某个学生和某个老师的兼容性评分public int cp(int[] s, int[] t) {int res 0;for (int i 0; i s.length; i) {if (s[i] t[i]) res;}return res;}
}1349. 参加考试的最大学生数状态压缩DP
https://leetcode.cn/problems/maximum-students-taking-exam/
提示 seats 只包含字符 . 和# m seats.length n seats[i].length 1 m 8 1 n 8
将每一行选择的位置用一个int变量表示。
枚举每一行再枚举该行的状态然后枚举上一行的状态检测是否合理且可以转移过来。 最后的答案就是最后一行各个状态的最大值。 这里的合理包括
该行本身要合理—— 都要坐在正常的椅子上同一行的两个学生不能挨边坐。每一行和上一行之间不能有冲突——如果上一行的某一列已经坐人了那么该行该列的左右两侧就不能坐人了。
class Solution {public int maxStudents(char[][] seats) {int m seats.length, n seats[0].length;int[] states new int[m];for (int i 0; i m; i) {states[i] getMask(seats[i]);}// 一共m行每行1n种状态int[][] dp new int[m 1][1 n];for (int i 0; i 1n; i) {// 判断 i 是不是 states[0] 的子集 自己不冲突if (check(states[0], i) op(i)) {dp[0][i] Integer.bitCount(i);}}// 枚举每一行for (int i 1; i m; i) {// 枚举这一行的每个状态for (int j 0; j 1n; j) {if (!check(states[i], j)) continue; // 如果这个状态不合理就跳过// 枚举上一行的每个状态for (int k 0; k 1n; k) {if (!check(states[i - 1], k)) continue; // 如果这个状态不合理就跳过if (!confilt(k, j)) { // 如果这个状态和上一行不冲突dp[i][j] Math.max(dp[i][j], dp[i - 1][k] Integer.bitCount(j));}}}System.out.println();}return Arrays.stream(dp[m - 1]).max().getAsInt();}// 将一行的状态用一个int表示public int getMask(char[] state) {int res 0;for (int i 0; i state.length; i) {if (state[i] .) res | 1 i;}return res;}// 检查状态x是否是状态state的子集即是否可选 这个状态x本身合法public boolean check(int state, int x) {if ((state | x) ! state) return false; // 需要x是state的子集return op(x); }// 检查x是否和y作为上一行冲突public boolean confilt(int x, int y) {for (int i 0; i 10; i) {if ((x i 1) 1) { // 如果x这个位置有了// 那么y的相差一列的位置就不能有了if ((y i 1 1) 1 || (y i - 1 1) 1) {return true;}}}return false;}// 检查这一行的状态本身是否合理即检查是否有两个学生坐在挨边的位置上public boolean op(int x) {for (int i 0; i 9; i) {if ((x i 1) 1 (x i 1 1) 1) return false;}return true;}
}LCP 04. 覆盖TODO 二分图匹配 状态压缩DP
https://leetcode.cn/problems/broken-board-dominoes/ 限制 1 n 8 1 m 8 0 b n * m
解法1——二分图匹配
在这里插入代码片解法2——状态压缩DP
在这里插入代码片1879. 两个数组最小的异或值之和状态压缩DP
https://leetcode.cn/problems/minimum-xor-sum-of-two-arrays/ 提示 n nums1.length n nums2.length 1 n 14 0 nums1[i], nums2[i] 10^7
class Solution {public int minimumXORSum(int[] nums1, int[] nums2) {int n nums1.length;int[][] dp new int[n 1][1 n];for (int i 0; i n; i) Arrays.fill(dp[i], Integer.MAX_VALUE / 2);dp[0][0] 0;// 枚举nums1的每个状态for (int i 1; i 1n; i) {int cnt Integer.bitCount(i);// 枚举每个位置for (int j 0; j n; j) {if ((i j 1) 1) {dp[cnt][i] Math.min(dp[cnt][i], dp[cnt - 1][i ^ (1j)] (nums1[j] ^ nums2[cnt - 1]));}}}return dp[n][(1n) - 1];}
}2172. 数组的最大与和状态压缩DP
https://leetcode.cn/problems/maximum-and-sum-of-array/
提示 n nums.length 1 numSlots 9 1 n 2 * numSlots 1 nums[i] 15
每个篮子可以放最多 2 个数字那么可以分成有 2 组一模一样的篮子处理。
注意——要将篮子的使用集合作为状态。
class Solution {public int maximumANDSum(int[] nums, int numSlots) {int n nums.length, m 2 * numSlots, ans 0;int[] dp new int[1m]; // m个篮子的状态// 枚举每个篮子被选择情况for (int i 1; i 1m; i) {// 计算该放入那个num了int cnt Integer.bitCount(i);if (cnt n) continue;// 枚举每个被选择的篮子for (int j 0; j m; j) {if ((i j 1) 1) {dp[i] Math.max(dp[i], dp[i ^ (1j)] (nums[cnt - 1] (j % numSlots 1)));}}ans Math.max(ans, dp[i]);}return ans;}
}Q42851. 字符串转换⭐
https://leetcode.cn/problems/string-transformation/
提示 2 s.length 5 * 10^5 1 k 10^15 s.length t.length s 和 t 都只包含小写英文字母。
解法1——KMP 矩阵快速幂优化 DP
https://leetcode.cn/problems/string-transformation/solutions/2435348/kmp-ju-zhen-kuai-su-mi-you-hua-dp-by-end-vypf/
计算有多少个 s 的循环同构字符串等于 t记作 c。这可以用 KMP 等字符串匹配算法解决即寻找 t 在 ss去掉最后一个字符中的出现次数。用KMP计算出 s s 中有几个 t 关于 KMP 可见我一定要 学会KMP字符串匹配
下面使用动态规划来解决该问题—— 定义 f[i][0] 表示 i 次操作后等于 t 的方案数f[i][1] 表示 i 次操作后不等于 t 的方案数。 发现 DP 递推式可以写成矩阵乘法形式因此可以使用矩阵快速幂来优化。所谓矩阵快速幂和普通快速幂的思想是一样的。 快速幂可以完成从 O ( n ) O(n) O(n) 到 O ( log n ) O(\log{n}) O(logn) 的优化。
Q为什么必须要使用矩阵快速幂 A因为 k 的数据范围很大。 log n \log{n} logn 对应的数据范围是 1 0 18 10^{18} 1018
class Solution {final long MOD (long)1e9 7;public int numberOfWays(String s, String t, long k) {int n s.length();// kmp 求出 ss(去掉最后一个字符) 中有几个 tint c kmpSearch(s s.substring(0, n - 1), t);// 递推矩阵long[][] m {{c - 1, c},{n - c, n - 1 - c},};m pow(m, k); // 矩阵快速幂求结果// 根据 st 判断初始状态 对应的答案return s.equals(t)? (int) m[0][0]: (int) m[0][1];}// kmp 返回 s 中有多少个 tpublic int kmpSearch(String s, String t) {int[] next getNext(s.toCharArray());int c 0;for (int i 0, j -1; i s.length(); i) {while (j ! -1 s.charAt(i) ! t.charAt(j 1)) j next[j];if (s.charAt(i) t.charAt(j 1)) j;if (j t.length() - 1) {c;j next[j]; // 匹配成功之后记得要更新 j next[j]}}return c;}// 求 next 数组public int[] getNext(char[] s) {int n s.length;int[] next new int[n];next[0] -1;for (int i 1, j -1; i n; i) {while (j ! -1 s[i] ! s[j 1]) j next[j];if (s[i] s[j 1]) j;next[i] j;}return next;}// 矩阵快速幂public long[][] pow(long[][] a, long n) {long[][] res {{1, 0}, {0, 1}};for (; n 0; n / 2) {if (n % 2 1) {res multiply(res, a);}a multiply(a, a);}return res;}// 矩阵乘法public long[][] multiply(long[][] a, long[][] b) {long[][] c new long[2][2];for (int i 0; i 2; i) {for (int j 0; j 2; j) {c[i][j] (a[i][0] * b[0][j] a[i][1] * b[1][j]) % MOD;}}return c;}
}解法2——找规律无需矩阵快速幂TODO
https://leetcode.cn/problems/string-transformation/solutions/2435714/cjavapython-bu-xu-yao-ju-zhen-kuai-su-mi-cukc/
在这里插入代码片[矩阵快速幂] 题目列表
见【算法】矩阵快速幂优化动态规划
成绩记录
本次没有参加竞赛。
