好记性不如烂笔头。A very handy charm that lights the tip of your wand in case. It’s like the flashlight on your iPhone, except magic. An added bonus spell is Lumos Maxima, which allows the bulb of light to fling into the sky and provide light all around a dark room, for example.
public class P5561_获取生成数组中的最大值 {
public int getMaximumGenerated(int n) {
if (n <= 1) {
return n;
}
int[] nums = new int[n + 1];
nums[1] = 1;
int ret = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
nums[i] = nums[i / 2];
} else {
nums[i] = nums[i / 2] + nums[i / 2 + 1];
}
ret = Math.max(ret, nums[i]);
}
return ret;
}
public static void main(String[] args) {
P5561_获取生成数组中的最大值 solution = new P5561_获取生成数组中的最大值();
System.out.println(solution.getMaximumGenerated(7));
}
}贪心，Entry（出现频率，次数）按照出现频率从高到低排列，依次寻找还没有使用的低频率放置
public class P5562_字符频次唯一的最小删除次数 {
public int minDeletions(String s) {
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
}
TreeMap<Integer, Integer> frequency = new TreeMap<>(Comparator.reverseOrder());
for (int j : count) {
if (j == 0) {
continue;
}
frequency.put(j, frequency.getOrDefault(j, 0) + 1);
}
Set<Integer> occupied = new HashSet<>();
int ret = 0;
for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
int k = entry.getKey(), v = entry.getValue();
int i = k - 1;
while (i > 0) {
if (v == 1) {
break;
}
if (frequency.containsKey(i) || occupied.contains(i)) {
i--;
continue;
}
occupied.add(i);
ret += k - i;
i--;
v--;
}
if (i == 0) {
ret += k * (v - 1);
}
}
return ret;
}
public static void main(String[] args) {
P5562_字符频次唯一的最小删除次数 solution = new P5562_字符频次唯一的最小删除次数();
System.out.println(solution.minDeletions("aab"));
System.out.println(solution.minDeletions("aaabbbcc"));
System.out.println(solution.minDeletions("ceabaacb"));
System.out.println(solution.minDeletions("accdcdadddbaadbc"));
}
}直接使用优先队列会超时。
使用二分查找到i，使得减i之和小于orders，减i-1之和大于等于orders
public class P5563_销售价值减少的颜色球 {
public int maxProfit(int[] inventory, int orders) {
int mod = (int) (1e9 + 7);
Arrays.sort(inventory);
int n = inventory.length;
/**
* orders = 12
* invents = [6, 10, 10]
* 1 2 3 4 5 6 use 1
* 1 2 3 4 5 6 7 8 9 10 use 5
* 1 2 3 4 5 6 7 8 9 10 use 6
* |
* nums[costs >=5] = 14
* nums[costs >=6] = 11
* 所以找到第五列，随便选择12 - 11 个5 补齐
* 即二分查找，找到i，使得减i之和小于orders，减i-1之和大于等于orders
*/
int l = 0, r = inventory[n - 1];
while (l < r) {
int m = (l + r) / 2;
if (sumSmallerThan(inventory, m, orders)) {
r = m;
} else {
l = m + 1;
}
}
int total = 0;
for (int i : inventory) {
if (i >= l) {
total += i - l;
}
}
int redundant = orders - total;
long ret = 0;
for (int i : inventory) {
if (i >= l) {
if (redundant > 0) {
ret = (ret + rangeSumMod(l, i, mod)) % mod;
redundant--;
} else {
ret = (ret + rangeSumMod(l + 1, i, mod)) % mod;
}
}
}
return (int) (ret % mod);
}
private int rangeSumMod(long from, long to, int mod) {
long sum = (from + to) * (to - from + 1) / 2;
return (int) (sum % mod);
}
private boolean sumSmallerThan(int[] inventory, int mid, int target) {
long sum = 0;
for (int i : inventory) {
sum += Math.max(i - mid, 0);
}
return sum < target;
}
public static void main(String[] args) {
P5563_销售价值减少的颜色球 solution = new P5563_销售价值减少的颜色球();
System.out.println(solution.maxProfit(new int[] {2, 5}, 4));
System.out.println(solution.maxProfit(new int[] {3, 5}, 6));
System.out.println(solution.maxProfit(new int[] {2,8,4,10,6}, 20));
System.out.println(solution.maxProfit(new int[] {1000000000}, 1000000000));
}
}涉及到前缀和的查询和更新，使用树状数组。
public class P5564_通过指令创建有序数组 {
public int createSortedArray(int[] instructions) {
int mod = (int) (1e9 + 7);
int m = Arrays.stream(instructions).max().getAsInt();
FenwickTree tree = new FenwickTree(m);
int ret = 0;
for (int i = 0; i < instructions.length; i++) {
int x = instructions[i];
int smaller = tree.query(x - 1);
int bigger = i - tree.query(x);
ret = (ret + Math.min(smaller, bigger)) % mod;
tree.update(x, 1);
}
return ret;
}
static class FenwickTree {
/**
* 预处理数组
*/
private int[] tree;
private int len;
public FenwickTree(int n) {
this.len = n;
tree = new int[n + 1];
}
/**
* 单点更新
*
* @param i 原始数组索引 i
* @param delta 变化值 = 更新以后的值 - 原始值
*/
public void update(int i, int delta) {
// 从下到上更新，注意，预处理数组，比原始数组的 len 大 1，故 预处理索引的最大值为 len
while (i <= len) {
tree[i] += delta;
i += lowbit(i);
}
}
/**
* 查询前缀和
*
* @param i 前缀的最大索引，即查询区间 [0, i] 的所有元素之和
*/
public int query(int i) {
// 从右到左查询
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
public int lowbit(int x) {
return x & (-x);
}
}
}leetcode周赛题目，老规矩，做出了三道:(，希望能坚持下去
public class P5511_二进制矩阵中的特殊位置 {
public int numSpecial(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[] rowSum = new int[m], colSum = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
rowSum[i] += mat[i][j];
colSum[j] += mat[i][j];
}
}
int ret = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1 && rowSum[i] == 1 && colSum[j] == 1) {
ret += 1;
}
}
}
return ret;
}
}public class P5512_统计不开心的朋友 {
private Set<Integer> set;
public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
set = new HashSet<>();
int[][] rank = new int[n][n];
for (int i = 0; i < n; i++) {
int count = n - 1;
for (int idx : preferences[i]) {
if (idx == i) {
continue;
}
rank[i][idx] = count;
count -= 1;
}
}
for (int i = 0; i < pairs.length; i++) {
for (int j = i + 1; j < pairs.length; j++) {
unhappy(pairs[i], pairs[j], rank);
unhappy(pairs[j], pairs[i], rank);
}
}
return set.size();
}
private void unhappy(int[] xy, int[] uv, int[][] rank) {
int x = xy[0], y = xy[1];
int u = uv[0], v = uv[1];
int ret = 0;
judge(x, y, u, v, rank);
judge(y, x, u, v, rank);
judge(x, y, v, u, rank);
judge(y, x, v, u, rank);
}
private void judge(int x, int y, int u, int v, int[][] rank) {
if (!set.contains(x)) {
if (rank[x][u] > rank[x][y] && rank[u][x] > rank[u][v]) {
set.add(x);
}
}
}
}public class P5513_连接所有点的最小费用 {
public int minCostConnectPoints(int[][] points) {
int minCost = 0, n = points.length;
UF uf = new UF(n);
PriorityQueue<Line> pq = new PriorityQueue<>(Comparator.comparingInt(Line::getDistance));
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
pq.add(new Line(i, j, manhattan(points, i, j)));
}
}
while (!pq.isEmpty()) {
Line line = pq.poll();
if (!uf.connected(line.i, line.j)) {
minCost += line.distance;
uf.union(line.i, line.j);
}
}
return minCost;
}
static class Line {
int i, j;
int distance;
public int getDistance() {
return distance;
}
public Line(int i, int j, int distance) {
this.i = i;
this.j = j;
this.distance = distance;
}
}
private int manhattan(int[][] points, int i, int j) {
int[] p1 = points[i], p2 = points[j];
return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}
static class UF {
private int[] id; // id[i] = component identifier of i
private int count; // number of components
/**
* Initializes an empty union-find data structure with
* {@code n} elements {@code 0} through {@code n-1}.
* Initially, each elements is in its own set.
*
* @param n the number of elements
* @throws IllegalArgumentException if {@code n < 0}
*/
public UF(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
/**
* Returns the number of sets.
*
* @return the number of sets (between {@code 1} and {@code n})
*/
public int count() {
return count;
}
/**
* Returns the canonical element of the set containing element {@code p}.
*
* @param p an element
* @return the canonical element of the set containing {@code p}
* @throws IllegalArgumentException unless {@code 0 <= p < n}
*/
public int find(int p) {
validate(p);
return id[p];
}
// validate that p is a valid index
private void validate(int p) {
int n = id.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
/**
* Returns true if the two elements are in the same set.
*
* @param p one element
* @param q the other element
* @return {@code true} if {@code p} and {@code q} are in the same set;
* {@code false} otherwise
* @throws IllegalArgumentException unless
* both {@code 0 <= p < n} and {@code 0 <= q < n}
* @deprecated Replace with two calls to {@link #find(int)}.
*/
public boolean connected(int p, int q) {
validate(p);
validate(q);
return id[p] == id[q];
}
/**
* Merges the set containing element {@code p} with the
* the set containing element {@code q}.
*
* @param p one element
* @param q the other element
* @throws IllegalArgumentException unless
* both {@code 0 <= p < n} and {@code 0 <= q < n}
*/
public void union(int p, int q) {
validate(p);
validate(q);
int pID = id[p]; // needed for correctness
int qID = id[q]; // to reduce the number of array accesses
// p and q are already in the same component
if (pID == qID) return;
for (int i = 0; i < id.length; i++)
if (id[i] == pID) id[i] = qID;
count--;
}
}
}public class P5514_检查字符串是否可以通过排序子字符串得到另一个字符串 {
public boolean isTransformable(String s, String t) {
List<Queue<Integer>> pos = new ArrayList<>();
for (int i = 0; i < 10; i++) {
pos.add(new LinkedList<>());
}
for (int i = 0; i < s.length(); i++) {
int d = s.charAt(i) - '0';
pos.get(d).add(i);
}
for (int i = 0; i < t.length(); i++) {
int d = t.charAt(i) - '0';
// 检查字符个数相同
if (pos.get(d).isEmpty()) {
return false;
}
for (int j = 0; j < d; j++) {
if (!pos.get(j).isEmpty() && pos.get(j).peek() < pos.get(d).peek()) {
return false;
}
}
pos.get(d).poll();
}
return true;
}
}A ship on the beach is a lighthouse to the sea.
前方有坑，请绕行。
一个商用产品花费的时间是一个可用产品的9倍！
程序员要做到完美，完美遵守计算机规则；
目标是别人设置的，程序员要根据别人提供的生产资料工作 ；
one's authority is not sufficient for his responsibility.
依赖其他系统组件和程序，有可能是糟糕的设计、文档和实现；
设计概念很有趣，工作很大一部分确是捉虫；
调试可能是线性收敛的，更糟糕的情况是，最后一个bug需要花费比第一个bug更长的时间找到；
压死程序员的最后一根稻草，产品上线就落伍了
The challenge and the mission are to find real solutions to real problems on actual schedules with available resources.
This then is programming, both a tar pit in which many efforts have floundered and a creative activity with joys and woes all its own. For many, the joys far outweigh the woes.
Good cooking takes time. If you are made to wait, it is to serve you better, and to please you.
排期造成的软件失败是其他失败原因之和。
程序员时乐观主义者，可能是计算机技术吸引相信幸福结尾的人，也可能是琐碎的事情赶走了很多人，只留下了习惯性专注目标达成的人，也有可能是计算机的出现时间并不长，程序员就更年轻了，年轻人总是乐观的。不管程序员甄选的过程是如何工作的，结果是毋庸置疑的，这次程序肯定能运行，或者我刚发现了最后一个bug。
所以进度安排的第一个错误假设就是：一切顺利，每项任务只花费它应该花费的时间。
创作活动分为三个阶段：想法，实现和交互。创作的完成标志是有人阅读了这本书或者运行了这个程序，从而完成和作者的**交互。
程序的创作介质-计算机是很规矩的，所以我们在实现时预期不会遇到困难，因为我们的想法可能会出现错误，程序写的有bug，所以乐观主义是未经证明的。
在单个任务中，遇到delay的概率是有限的，但是大项目由很多任务组成，有些任务是端到端的，每个任务都进行顺利的概率就很低了。
估算和进度安排的第二个错误想法就是工作量单位：人月。
成本跟人员和月数有关，但是进度和人月无关。
Hence the man-month as a unit for measuring the size of a job is a dangerous and deceptive myth.
这句话隐含了人和月是可替换的。
当任务可被拆分给不同的程序员，且他们之间无需交流时，人和月是可以替换的，比如收小麦和摘棉花，但在系统编程中，这都不能说是近似正确。
新增的交流负担主要由两部分组成，培训和程序员间的交流。培训和新增人员个数是线性关系，但是成对的交流和新增人员个数是平方关系。
增加人力，实际上是延长了时间进度，而不是缩短。
顺序限制影响最多的是调试和系统测试，更糟糕的是，影响时间也和遇到的错误数目和微妙程度有关系。因此测试是编程中最被误排期的部分。
作者遵循如下的排期规则：
和传统的排期有以下不同：
很多项目并不会给测试排一半的时间，但事实上确实花费了一半的时间。很多项目都是按照工期来的，直到或者说除了系统测试。没有分配给系统测试足够的时间是灾难性的，因为延期发生在排期结尾的时候，直到交付才意识到了问题。此时的延期有很严重的经济上和心理上的影响，因为项目已经全马力进行中，每日成本都是最多的。为了能搞按时交付，二次成本也很高，甚至超过了其他的成本。所以给系统测试预留足够的时间很重要。
顾客可以控制任务的计划完成时间，但是却不能控制实际进度。为了匹配客户的期望交付时间而进行错误的排期，在软件行业中比其他工程行业更普遍。没有量化的方法、没有支撑数据、主要靠经理的直觉，很难去做一个勇敢的，合理的甚至冒着失业的风险的预估计划。
有两份方法：
1. 开发推行生产率表，缺陷表和估算规则等，这些数据的分享将使整个行业将受益；
2. 在可靠的估算出现之前，项目经理要挺直脊梁，坚持自己的估计，确信自己的直觉比一厢情愿的预估更靠谱。
进度已经落后，只完成了第一个里程碑，项目经理有哪些选择呢：
前两个选择会导致
Adding manpower to a late software project makes it later
这就是去除神话色彩的人月。项目需要的时间依赖于顺序性限制，项目人数依赖独立的子任务。根据这两个性质，项目经理可以推算出使用更少人力和更长时间的排期（风险就是产品上线就落伍），并不能推出使用更多的人力和更少的时间的排期。
在众多软件项目中，缺乏合理的时间进度是造成项目滞后的最主要原因，它比其他所有因素加起来的影响还要大。
模拟
public class P5629_重新格式化电话号码 {
public String reformatNumber(String number) {
List<Character> nums = new ArrayList<>();
for (int i = 0; i < number.length(); i++) {
if (Character.isDigit(number.charAt(i))) {
nums.add(number.charAt(i));
}
}
int n = nums.size();
StringBuilder sb = new StringBuilder();
int j = 0;
for (int i = 0; i < n / 3 - 1; i++) {
sb.append(nums.get(j++));
sb.append(nums.get(j++));
sb.append(nums.get(j++));
sb.append("-");
}
if (n - j < 4) {
for (; j < n; j++) {
sb.append(nums.get(j));
}
} else {
for (; j < n - 2; j++) {
sb.append(nums.get(j));
}
sb.append("-");
for (; j < n; j++) {
sb.append(nums.get(j));
}
}
return sb.toString();
}
}双指针（滑动窗口）
public class P5630_删除子数组的最大得分 {
public int maximumUniqueSubarray(int[] nums) {
int n = nums.length;
int l = 0, r = 0;
int ret = 0;
Set<Integer> seen = new HashSet<>();
int sum = 0;
while (r < n) {
sum += nums[r];
boolean flag = seen.add(nums[r]);
if (flag) {
ret = Math.max(ret, sum);
} else {
while (nums[l] != nums[r]) {
seen.remove(nums[l]);
sum -= nums[l];
l++;
}
sum -= nums[l];
l++;
}
r++;
}
return ret;
}
}单调队列 + DP，参考239题
public class P5631_跳跃游戏VI {
public int maxResult(int[] nums, int k) {
int n = nums.length;
int[] f = new int[n];
f[0] = nums[0];
Deque<Integer> dq = new ArrayDeque<>();
dq.offerLast(0);
for (int i = 1; i < n; i++) {
while (!dq.isEmpty() && i - dq.peekFirst() > k) {
dq.pollFirst();
}
f[i] = nums[i] + f[dq.peekFirst()];
while (!dq.isEmpty() && f[dq.peekLast()] <= f[i]) {
dq.pollLast();
}
dq.offerLast(i);
}
return f[n - 1];
}
}排序 + 并查集
并查集实现参考algs4
public class P5632_检查边长度限制的路径是否存在 {
private WeightedQuickUnionUF uf;
public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
uf = new WeightedQuickUnionUF(n);
Arrays.sort(edgeList, Comparator.comparingInt(edge -> edge[2]));
int m = queries.length;
Integer[] queryIndex = new Integer[m];
for (int i = 0; i < m; i++) {
queryIndex[i] = i;
}
Arrays.sort(queryIndex, Comparator.comparingInt(index -> queries[index][2]));
boolean[] ret = new boolean[m];
int curr = 0;
for (int index : queryIndex) {
int limit = queries[index][2];
while (curr < edgeList.length && edgeList[curr][2] < limit) {
uf.union(edgeList[curr][0], edgeList[curr][1]);
curr++;
}
if (uf.connected(queries[index][0], queries[index][1])) {
ret[index] = true;
}
}
return ret;
}
}模拟操作，注意当前在主文件夹时，执行../还会停留在当前文件夹。
public int minOperations(String[] logs) {
int ret = 0;
for (String log : logs) {
if (log.equals("./")) {
continue;
} else if (log.equals("../")) {
if (ret > 0) {
ret -= 1;
}
} else {
ret += 1;
}
}
return ret;
}题目描述较长，需要仔细理解，模拟执行。
时间复杂度O(sum(customers))
public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
int n = customers.length;
int shifts = 0, profit = 0, maxProfit = 0;
int total = Arrays.stream(customers).sum();
int waiting = 0, served = 0;
int ret = -1;
while (total > 0) {
if (shifts < n) {
waiting += customers[shifts];
}
if (waiting >= 4) {
waiting -= 4;
served = 4;
} else {
served = waiting;
waiting = 0;
}
profit += boardingCost * served - runningCost;
if (profit > maxProfit) {
maxProfit = profit;
ret = shifts + 1;
}
shifts += 1;
total -= served;
}
return ret;
}又是个需要仔细阅读理解的题目，本质是一棵多叉树的建立和前序遍历。
class ThroneInheritance {
private Node king;
Map<String, Node> map;
public ThroneInheritance(String kingName) {
map = new HashMap<>();
king = new Node(kingName);
map.put(kingName, king);
}
public void birth(String parentName, String childName) {
Node parent = map.get(parentName);
Node child = new Node(childName);
parent.subs.add(child);
map.put(childName, child);
}
public void death(String name) {
Node node = map.get(name);
node.dead = true;
}
public List<String> getInheritanceOrder() {
List<String> ret = new ArrayList<>();
dfs(king, ret);
return ret;
}
private void dfs(Node root, List<String> ret) {
if (root != null) {
if (!root.dead) {
ret.add(root.name);
}
for (Node s : root.subs) {
dfs(s, ret);
}
}
}
private static class Node {
String name;
List<Node> subs;
boolean dead;
public Node(String name) {
this.name = name;
this.dead = false;
this.subs = new ArrayList<>();
}
}
}状态压缩+剪枝，其实还是暴力枚举。（考试被阅读理解绊住了，没时间做了，还是有机会A四道的，做了挺多周了，就1次全做出来了，太菜:(。）
public int maximumRequests(int n, int[][] requests) {
int m = requests.length;
int ret = 0;
for (int i = 1; i < (1 << m); i++) {
int count = Integer.bitCount(i);
if (count < ret) {
continue;
}
int[] diff = new int[n];
for (int j = 0; j < m; j++) {
if ((i & (1 << j)) == 0) {
continue;
}
diff[requests[j][0]] -= 1;
diff[requests[j][1]] += 1;
}
boolean canMove = true;
for (int d : diff) {
if (d != 0) {
canMove = false;
break;
}
}
if (canMove) {
ret = Math.max(ret, count);
}
}
return ret;
}public class P5605_检查两个字符串数组是否相等 {
public boolean arrayStringsAreEqual(String[] word1, String[] word2) {
return String.join("", word1).equals(String.join("", word2));
}
}贪心算法
public class P5606_具有给定数值的最小字符串 {
public String getSmallestString(int n, int k) {
char[] xs = new char[n];
while (n > 0) {
int d = k - n + 1;
if (d >= 26) {
d = 26;
}
xs[n - 1] = (char) ('a' + d - 1);
k -= d;
n--;
}
return new String(xs);
}
}前缀和，后缀和
public class P5607_生成平衡数组的方案数 {
public int waysToMakeFair(int[] nums) {
int n = nums.length;
int[] prefixSum = new int[n];
int[] suffixSum = new int[n];
for (int i = 0; i < n; i++) {
prefixSum[i] = (i >= 2 ? prefixSum[i - 2] : 0) + nums[i];
}
for (int i = n - 1; i >= 0; i--) {
suffixSum[i] = (i + 2 < n ? suffixSum[i + 2] : 0) + nums[i];
}
int ret = 0;
for (int i = 0; i < n; i++) {
int oddSum = 0, evenSum = 0;
if (i % 2 == 1) {
oddSum += i >= 2 ? prefixSum[i - 2] : 0;
evenSum += i >= 1 ? prefixSum[i - 1] : 0;
oddSum += i + 1 < n ? suffixSum[i + 1] : 0;
evenSum += i + 2 < n ? suffixSum[i + 2] : 0;
} else {
oddSum += i >= 1 ? prefixSum[i - 1] : 0;
evenSum += i >= 2 ? prefixSum[i - 2] : 0;
oddSum += i + 2 < n ? suffixSum[i + 2] : 0;
evenSum += i + 1 < n ? suffixSum[i + 1] : 0;
}
if (oddSum == evenSum) {
ret++;
}
}
return ret;
}
public static void main(String[] args) {
P5607_生成平衡数组的方案数 solution = new P5607_生成平衡数组的方案数();
System.out.println(solution.waysToMakeFair(new int[] {2,1,6,4}));
System.out.println(solution.waysToMakeFair(new int[] {2, 2, 2}));
System.out.println(solution.waysToMakeFair(new int[] {1, 2, 3}));
System.out.println(solution.waysToMakeFair(new int[] {6,1,7,4,1}));
}
}贪心，首先完成任务后要剩余最小，先按照剩余能量（task[0] - task[1]）从大到小排序，如果剩余能量相同，则按最小需要能量（task[1]）从大到小排序。
public class P5608_完成所有任务的最少初始能量 {
public int minimumEffort(int[][] tasks) {
Arrays.sort(tasks, Comparator.comparingInt((int[] o) -> o[0] - o[1]).thenComparing((int[] o) -> -o[1]));
int n = tasks.length;
int ret = 0;
int curr = 0;
for (int[] task : tasks) {
if (curr < task[1]) {
ret += task[1] - curr;
curr = task[1];
}
curr -= task[0];
}
return ret;
}
}这周的题目不是很难，第四道题花的时间太长了，两次DFS没有考虑清楚，要不就全过了，就差几分钟，要不就是本菜鸡的第二次全AC了。。。
public class P5535_括号的最大嵌套深度 {
public int maxDepth(String s) {
List<Integer> stack = new ArrayList<>();
int n = s.length();
int ret = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') {
stack.add(i);
} else if (s.charAt(i) == ')') {
ret = Math.max(ret, stack.size());
stack.remove(stack.size() - 1);
}
}
return ret;
}
}public class P5536_最大网络秩 {
public int maximalNetworkRank(int n, int[][] roads) {
int[] neighbours = new int[n];
Set<Integer> connected = new HashSet<>();
for (int[] road : roads) {
neighbours[road[0]]++;
neighbours[road[1]]++;
connected.add(road[0] * n + road[1]);
connected.add(road[1] * n + road[0]);
}
int ret = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int tmp = neighbours[i] + neighbours[j];
if (connected.contains(i * n + j) || connected.contains(j * n + i)) {
tmp--;
}
ret = Math.max(ret, tmp);
}
}
return ret;
}
}public class P5537_分割两个字符串得到回文串 {
public boolean checkPalindromeFormation(String a, String b) {
if (isPalindrome(a) || isPalindrome(b)) {
return true;
}
return checkFormerValid(a, b) || checkFormerValid(b, a);
}
// a前缀 + b 后缀
private boolean checkFormerValid(String a, String b) {
int len = 0;
int n = a.length();
while (len < n / 2) {
if (a.charAt(len) != b.charAt(n - len - 1)) {
break;
}
len++;
}
return isPalindrome(a.substring(len, n - len)) || isPalindrome(b.substring(len, n - len));
}
private boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
if (s.charAt(l) != s.charAt(r)) {
return false;
}
l++; r--;
}
return true;
}
}public class P5538_统计子树中城市之间最大距离 {
public int[] countSubgraphsForEachDiameter(int n, int[][] edges) {
List<List<Integer>> graph = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0] - 1).add(edge[1] - 1);
graph.get(edge[1] - 1).add(edge[0] - 1);
}
int[] ret = new int[n - 1];
for (int i = 0; i < (1 << n); i++) {
List<Integer> comb = new ArrayList<>();
for (int j = 0; j < n; j++) {
if (((i >> j) & 1) == 1) {
comb.add(j);
}
}
if (comb.size() < 2) {
continue;
}
int distance = calculateDistance(comb, graph);
if (distance > 0) {
ret[distance - 1]++;
if (distance == 3) {
System.out.println(comb);
}
}
}
return ret;
}
private int calculateDistance(List<Integer> vts, List<List<Integer>> graph) {
// first check connectivity
int cons = 0;
int m = vts.size();
Map<Integer, Integer> count = new HashMap<>();
for (int v : vts) {
for (int u : graph.get(v)) {
if (vts.contains(u)) {
cons++;
count.put(v, count.getOrDefault(v, 0) + 1);
}
}
}
if (cons != (m - 1) * 2) {
return -1;
}
Set<Integer> edges = new HashSet<>();
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
if (entry.getValue() == 1) {
edges.add(entry.getKey());
}
}
return calculateMaxDistance(vts, edges.iterator().next(), graph, 0);
}
private int calculateMaxDistance(List<Integer> vts, int start, List<List<Integer>> graph, int times) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
Map<Integer, Integer> distance = new HashMap<>();
distance.put(start, 0);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : graph.get(u)) {
if (vts.contains(v)) {
if (!distance.containsKey(v) || distance.get(v) > distance.get(u) + 1) {
distance.put(v, distance.get(u) + 1);
q.offer(v);
}
}
}
}
int maxDistance = 0;
int newStart = start;
for (Map.Entry<Integer, Integer> entry : distance.entrySet()) {
if (entry.getValue() > maxDistance) {
maxDistance = entry.getValue();
newStart = entry.getKey();
}
}
if (times > 0) {
return maxDistance;
}
return calculateMaxDistance(vts, newStart, graph, times + 1);
}
}public int numberOfSets(int n, int k) {
int mod = (int) (1e9 + 7);
int[][] f = new int[n][k + 1];
int[][] g = new int[n][k + 1];
f[0][0] = g[0][0] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
f[i][j] = f[i - 1][j] % mod;
if (j > 0) {
f[i][j] = (f[i][j] + g[i - 1][j - 1]) % mod;
}
g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
}
}
return f[n - 1][k];
}最长公共子序列的衍生题，类似俄罗斯套娃354题
public int bestTeamScore(int[] scores, int[] ages) {
int n = scores.length;
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node(scores[i], ages[i]);
}
Arrays.sort(nodes);
int[] f = new int[n];
f[0] = nodes[0].score;
int ret = nodes[0].score;
for (int i = 1; i < n; i++) {
f[i] = nodes[i].score;
for (int j = 0; j < i; j++) {
if (nodes[i].age == nodes[j].age || (nodes[i].age > nodes[j].age && nodes[i].score > nodes[j].score)) {
f[i] = Math.max(f[i], f[j] + nodes[i].score);
}
}
ret = Math.max(ret, f[i]);
System.out.println(Arrays.toString(f));
}
return ret;
}
private static class Node implements Comparable<Node> {
int score;
int age;
public Node(int score, int age) {
this.score = score;
this.age = age;
}
@Override
public int compareTo(Node o) {
if (this.age == o.age) {
return Integer.compare(this.score, o.score);
}
return Integer.compare(this.age, o.age);
}
}并查集+筛选法
常规gcd会超时，反着枚举出n以内大于阈值的数的倍数
并查集模板推荐算法4的实现
public class P5128_带阈值的图连通性 {
private WeightedQuickUnionUF uf;
public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
uf = new WeightedQuickUnionUF(n + 1);
for (int i = threshold + 1; i <= n; i++) {
for (int j = i * 2; j <= n; j += i) {
uf.union(i, j);
}
}
List<Boolean> ret = new ArrayList<>();
for (int[] query : queries) {
ret.add(uf.connected(query[0], query[1]));
}
return ret;
}
}“When you wish to instruct, be brief.
– Cicero”
“The first thing we do, let’s kill all the language lawyers.
– Henry VI, Part II”
“When structured binding is used for a class with no private data, it is easy to see how the binding is done: there must be the same number of names defined for the binding as there are data members in the class object, and each name introduced in the binding names the corresponding member. There will not be any difference in the object code quality compared to explicitly using a composite object.”
“The throw transfers control to a handler for exceptions of type out_of_range in some function that directly or indirectly called Vector::operator. To do that, the implementation will unwind the function call stack as needed to get back to the context of that caller. That is, the exception handling mechanism will exit scopes and functions as needed to get back to a caller that has expressed interest in handling that kind of exception, invoking destructors (§5.2.2) along the way as needed. ”
public String interpret(String command) {
return command.replace("()", "o").replace("(al)", "al");
}public class P5618_K和数对的最大数目 {
public int maxOperations(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
int ret = 0;
for (int n : nums) {
if (count.containsKey(k - n) && count.get(k - n) > 0) {
ret++;
count.put(k -n, count.get(k - n) - 1);
} else {
count.put(n, count.getOrDefault(n, 0) + 1);
}
}
return ret;
}
}public class P5620_连接连续二进制数字 {
private static final int MOD = 1000000007;
public int concatenatedBinary(int n) {
long ret = 1;
for (int i = 2; i <= n; i++) {
String bin = Integer.toBinaryString(i);
ret = ((ret << bin.length()) % MOD + i) % MOD;
}
return (int) ret;
}
public static void main(String[] args) {
P5620_连接连续二进制数字 solution = new P5620_连接连续二进制数字();
System.out.println(solution.concatenatedBinary(1));
System.out.println(solution.concatenatedBinary(3));
System.out.println(solution.concatenatedBinary(12));
}
}TODO
40双周赛不难，第三次AC全部周赛题，217场周赛就定格在前两题，:(
暴力
public int maxRepeating(String sequence, String word) {
int m = sequence.length(), n = word.length();
int i = 0, j = 0;
int ret = 0;
int k = 0;
while (i < m) {
if (sequence.charAt(i) != word.charAt(j)) {
i -= j;
j = 0;
k = 0;
} else {
if (j == n - 1) {
j = 0;
k++;
ret = Math.max(ret, k);
} else {
j++;
}
}
i++;
}
return ret;
}题目保证了不用特别注意cornercase
public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
ListNode ret = list1;
ListNode h = list1, t = list1;
for (int i = 0; i < b; i++) {
if (i == a - 1) {
h = list1;
}
list1 = list1.next;
}
t = list1;
h.next = list2;
for (; list2.next != null; list2 = list2.next) {}
list2.next = t.next;
return ret;
}两个双端队列模拟，每当pushMid或者popMid的时候rebalance一下
public class FrontMiddleBackQueue {
private Deque<Integer> front;
private Deque<Integer> back;
public FrontMiddleBackQueue() {
front = new ArrayDeque<>();
back = new ArrayDeque<>();
}
public void pushFront(int val) {
front.addFirst(val);
}
public void pushMiddle(int val) {
int m = front.size(), n = back.size();
int mid = (m + n) / 2;
if (m > mid) {
while (m > mid) {
back.addFirst(front.pollLast());
m--;
}
} else if (m < mid) {
while (m < mid) {
front.addLast(back.pollFirst());
m++;
}
}
front.addLast(val);
}
public void pushBack(int val) {
back.addLast(val);
}
public int popFront() {
if (front.isEmpty() && back.isEmpty()) {
return -1;
}
if (!front.isEmpty()) {
return front.pollFirst();
} else {
return back.pollFirst();
}
}
public int popMiddle() {
int m = front.size(), n = back.size();
if (m + n == 0) {
return -1;
}
int mid = (m + n - 1) / 2;
if (m > mid) {
while (m > mid) {
back.addFirst(front.pollLast());
m--;
}
} else if (m < mid) {
while (m < mid) {
front.addLast(back.pollFirst());
m++;
}
}
return back.pollFirst();
}
public int popBack() {
if (front.isEmpty() && back.isEmpty()) {
return -1;
}
if (!back.isEmpty()) {
return back.pollLast();
} else {
return front.pollLast();
}
}
}最长公共子序列衍生题
public int minimumMountainRemovals(int[] nums) {
int n = nums.length;
int[] front = new int[n], back = new int[n];
Arrays.fill(front, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
front[i] = Math.max(front[i], front[j] + 1);
}
}
}
Arrays.fill(back, 1);
for (int i = n - 2; i >= 0; i--) {
for (int j = n - 1; j > i; j--) {
if (nums[i] > nums[j]) {
back[i] = Math.max(back[i], back[j] + 1);
}
}
}
int ret = 0;
for (int i = 0; i < n; i++) {
if (front[i] > 1 && back[i] > 1) {
ret = Math.max(ret, back[i] + front[i] - 1);
}
}
return n - ret;
}同402题，单调栈
public int[] mostCompetitive(int[] nums, int k) {
k = nums.length - k;
List<Integer> stack = new ArrayList<>();
for (int d : nums) {
while (!stack.isEmpty() && stack.get(stack.size() - 1) > d && k > 0) {
stack.remove(stack.size() - 1);
k -= 1;
}
stack.add(d);
}
while (k > 0) {
stack.remove(stack.size() - 1);
k -= 1;
}
int[] ret = new int[stack.size()];
for (int i = 0; i < stack.size(); i++) {
ret[i] = stack.get(i);
}
return ret;
}public class P5554_能否连接形成数组 {
public boolean canFormArray(int[] arr, int[][] pieces) {
Map<Integer, int[]> indexMap = new HashMap<>();
for (int[] piece : pieces) {
indexMap.put(piece[0], piece);
}
int n = arr.length, i = 0;
while (i < n) {
if (!indexMap.containsKey(arr[i])) {
return false;
}
int[] piece = indexMap.get(arr[i]);
int j = 0;
while (i < n && j < piece.length) {
if (arr[i] != piece[j]) {
return false;
}
i++;
j++;
}
if (j < piece.length) {
return false;
}
}
return true;
}
}public class P5555_统计字典序元音字符串的数目 {
public int countVowelStrings(int n) {
int[] count = new int[5];
Arrays.fill(count, 1);
for (int i = 1; i < n; i++) {
for (int j = 3; j >= 0; j--) {
count[j] += count[j + 1];
}
}
return Arrays.stream(count).sum();
}
public static void main(String[] args) {
P5555_统计字典序元音字符串的数目 solution = new P5555_统计字典序元音字符串的数目();
System.out.println(solution.countVowelStrings(2));
System.out.println(solution.countVowelStrings(3));
System.out.println(solution.countVowelStrings(4));
}
}public class P5556_可以到达的最远建筑 {
// 贪心，先消耗砖块，记录在大根堆中
// 后面砖块不够，用梯子替换前面最多消耗（且大于本次消耗）的砖块，再减去本次消耗
// 终止条件是走到最后或者使用完了砖块和梯子
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
int n = heights.length;
for (int i = 0; i < n - 1; i++) {
if (heights[i] < heights[i + 1]) {
int d = heights[i + 1] - heights[i];
q.offer(d);
if (bricks >= d) {
bricks -= d;
} else if (ladders > 0) {
ladders--;
if (!q.isEmpty() && q.peek() > d) {
bricks += q.poll();
q.offer(d);
bricks -= d;
}
} else {
return i;
}
}
}
return n - 1;
}
public static void main(String[] args) {
P5556_可以到达的最远建筑 solution = new P5556_可以到达的最远建筑();
System.out.println(solution.furthestBuilding(new int[] {4,2,7,6,9,14,12}, 5, 1));
System.out.println(solution.furthestBuilding(new int[] {4,12,2,7,3,18,20,3,19}, 10, 2));
System.out.println(solution.furthestBuilding(new int[] {14,3,19,3}, 17, 0));
}
}public class P5600_第K条最小指令 {
public String kthSmallestPath(int[] destination, int k) {
int hs = destination[1], vs = destination[0];
int n = hs + vs;
int[][] C = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0) {
C[i][j] = 1;
} else {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}
}
StringBuilder sb = new StringBuilder(n);
while (hs > 0 && vs > 0) {
int c = C[hs + vs - 1][vs];
// try to place H
if (k <= c) {
sb.append('H');
hs--;
} else {
sb.append('V');
k -= c;
vs--;
}
}
while (hs > 0) {
sb.append('H');
hs--;
}
while (vs > 0) {
sb.append('V');
vs--;
}
return sb.toString();
}
public static void main(String[] args) {
P5600_第K条最小指令 solution = new P5600_第K条最小指令();
for (int i = 1; i <= 10; i++) {
System.out.println(solution.kthSmallestPath(new int[]{2, 3}, i));
}
}
}类层次中的Root，每个类，包括数组的超类；
getClass返回Class<? extends |X|>，|X|是getClass调用者的静态类型（声明类型）的类型擦除后类型；
List<Integer> xs = Arrays.asList(1, 2, 3);
Class<? extends List> cls = xs.getClass();clone()参考Effective Java条目13，如果要实现Cloneable，重写clone方法，需要先调用super.clone()，然后修改需要修复的属性，比如stack的element数组，这意味着深拷贝，或者有唯一id，需要修改为新的id，复制方法和复制工厂是更好的选择，例外是数组；
hashcode和equals方法重写规约，参考Effective Java条目10，11；
finalize，The finalization mechanism is inherently problematic；
wait，notify，线程同步原语，看过最明白的解释，https://www.artima.com/insidejvm/ed2/threadsynch.html，总结如下图
Figure 20-1 shows three threads suspended in the entry set and four threads suspended in the wait set. These threads will remain where they are until the current owner of the monitor--the active thread--releases the monitor. The active thread can release the monitor in either of two ways: it can complete the monitor region it is executing or it can execute a wait command. If it completes the monitor region, it exits the monitor via the door at the bottom of the central rectangle, door number five. If it executes a wait command, it releases the monitor as it travels through door number three, the door to the wait set.
If the former owner did not execute a notify before it released the monitor (and none of the waiting threads were previously notified and were waiting to be resurrected), then only the threads in the entry set will compete to acquire the monitor. If the former owner did execute a notify, then the entry set threads will have to compete with one or more threads from the wait set. If a thread from the entry set wins the competition, it passes through door number two and becomes the new owner of the monitor. If a thread from the wait set wins the competition, it exits the wait set and reacquires the monitor as it passes through door number four. Note that doors three and four are the only ways a thread can enter or exit the wait set. A thread can only execute a wait command if it currently owns the monitor, and it can't leave the wait set without automatically becoming again the owner of the monitor.
另外，始终应该使用 wait 循环模式来调用 wait 方法，参考Effective Java条目81
synchronized (obj) {
while (<condition does not hold>)
obj.wait();
// (Releases lock, and reacquires on wakeup)
... // Perform action appropriate to condition
}原因：
A thread can wake up without being notified, interrupted, or timing out, a so-called spurious wakeup. While this will rarely occur in practice, applications must guard against it by testing for the condition that should have caused the thread to be awakened, and continuing to wait if the condition is not satisfied.
关于spurious wakeup，虚假唤醒，参考https://www.zhihu.com/question/271521213
wait notify 生产者消费者例子参考https://docs.oracle.com/javase/tutorial/essential/concurrency/guardmeth.html
Chapter 2. Subtyping and Wildcards
Chapter 3. Comparison and
Chapter 4. Declarations
Chapter 6. Reification
Chapter 7. Reflection
Chapter 9. Design Patterns
// TODO
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.