前言
与其站在原地思考，不如一步一步地往前走吧，就算昨天的足迹会消失不见，哪怕通往明天的道路隐没在黑暗中，即便如此……也不要一味地回首过去，不要对未来悲观失望，只需尽情地感受当下。因为不管你如何反抗，时间总是会不断推着你前进。
整体评价
挺有爱的一场比赛，13常规周赛题，46难度/码量就陡增，不过每一题都有机会拼一下，所以整体感觉挺好的。
团队赛和队友都是萌新，但非常给力，也彼此信任。总之重在参与，Just For Fun!
1. 最小展台数量
简单模拟，维护集合中每个种类的最大值即可，主要是如何写才优雅的问题.
因为在字母表中，可以用26大小的数组维护，更新合并。
Java
go
class Solution {
public int minNumBooths(String[] demand) {
int[] ans = new int[26];
for (String d: demand) {
// 构建新集合
int[] tmp = new int[26];
for (char c: d.toCharArray()) {
tmp[c - 'a']++;
}
// 合并&更新 (求max)
for (int i = 0; i < 26; i++) {
ans[i] = Math.max(ans[i], tmp[i]);
}
}
return Arrays.stream(ans).sum();
}
}2. 装饰树
感觉dfs和bfs都可以做，只是插入节点，但不破坏原先的结构，所以比较简单。
Java
go
class Solution {
public TreeNode expandBinaryTree(TreeNode root) {
if (root == null) return null;
if (root.left != null) {
TreeNode lp = root.left;
root.left = new TreeNode(-1);
root.left.left = expandBinaryTree(lp);
}
if (root.right != null) {
TreeNode lp = root.right;
root.right = new TreeNode(-1);
root.right.right = expandBinaryTree(lp);
}
return root;
}
}3. 美观的花束
经典滑窗题，用双指针实现.
核心的逻辑，就是用map记录所有值的出现次数，然后进行滑动.
注意，计数的结果，以右指针为准，按有效窗口大小进行累加。
整体的时间复杂度为。
Java
go
class Solution {
final int mod = 10_0000_0007;
public int beautifulBouquet(int[] flowers, int cnt) {
Map<Integer, Integer> windowsMap = new HashMap<>();
int ans = 0;
int j = 0;
for (int i = 0; i < flowers.length; i++) {
int f = flowers[i];
windowsMap.put(f, windowsMap.getOrDefault(f, 0) + 1);
int tv = windowsMap.get(f);
if (tv > cnt) {
while (j < i) {
int f1 = flowers[j];
windowsMap.put(f1, windowsMap.getOrDefault(f1, 0) - 1);
j++;
if (f == f1) {
break;
}
}
}
ans = (ans + (i - j + 1)) % mod;
}
return ans;
}
}4. Hello LeetCode!
经典的状压DP, 不过这题码量真心大，思维也不简单。
本质用了两次DP， 一次0-1状压DP针对单个单词，一个向量状压DP针对全局。
具体来阐述下 这两个DP
-
0-1状压DP （可以用dfs全排列代替）
这个是针对单个单词的，全枚举单词中的字母（单词长度）
这个过程比较常规，0-1状压也很常见。
时间复杂度为 -
向量状压DP
这个是面向全局最优解的
那为啥称呼为向量呢
主要是把，抽象为向量总共7个维度
怎么维护这个向量呢？
一种就是引入7维数组，另一种根据最大字母l为4，把它状态压缩为一个整数，可以理解为8进制，给每个字母分配3位bit，为啥用3位，8进制，主要是2的幂次方便位运算操作。
大概就这样，中间需要额外一个操作就是把0-1状态转.
Java
class Solution {
// "helloleetcode"
// 这是hash表
int[] hash = new int[26];
int[] nums = new int[26];
int fstate = 0;
void prebuild() {
Arrays.fill(hash, -1);
// h: 0, 1
hash['h' - 'a'] = 0;
nums[0] = 1;
fstate |= 1;
// e: 1, 4
hash['e' - 'a'] = 1;
nums[1] = 4;
fstate |= (4 << 3);
// l: 2, 3
hash['l' - 'a'] = 2;
nums[2] = 3;
fstate |= (3 << 6);
// o: 3, 2
hash['o' - 'a'] = 3;
nums[3] = 2;
fstate |= (2 << 9);
// t: 4, 1
hash['t' - 'a'] = 4;
nums[4] = 1;
fstate |= (1 << 12);
// c: 5, 1
hash['c' - 'a'] = 5;
nums[5] = 1;
fstate |= (1 << 15);
// d: 6, 1
hash['d' - 'a'] = 6;
nums[6] = 1;
fstate |= (1 << 18);
}
int compute(char[] buf, int k, int state) {
int left = 0, right = 0;
for (int i = 0; i < k; i++) {
if (((1 << i) & state) == 0) {
left++;
}
}
for (int i = k + 1; i < buf.length; i++) {
if (((1 << i) & state) == 0) {
right++;
}
}
return left * right;
}
// *) 预处理，反而难
TreeMap<Integer, Integer> solve(String w) {
TreeMap<Integer, Integer> resMap = new TreeMap<>();
char[] buf = w.toCharArray();
int wn = buf.length;
int wrange = 1 << wn;
int[] wopt = new int[wrange];
Arrays.fill(wopt, -1);
wopt[0] = 0;
for (int i = 0; i < wrange; i++) {
if (wopt[i] == -1) continue;
for (int j = 0; j < buf.length; j++) {
if ((i & (1 << j)) == 0 && "helloleetcode".indexOf(buf[j]) != -1) {
int tv = compute(buf, j, i);
if (wopt[i | (1 << j)] == -1 || wopt[i | (1 << j)] > wopt[i] + tv) {
wopt[i | (1 << j)] = wopt[i] + tv;
}
}
}
// 状态转化
boolean f = true;
int state = 0;
for (int j = 0; j < wn; j++) {
if ((i & (1 << j)) == 0) continue;
int p = buf[j] - 'a';
if (hash[p] == -1) {
continue;
}
int tv = (state >> (hash[p] * 3)) & 0x07;
if (tv + 1 > nums[hash[p]]) {
f = false;
break;
}
state = state + (1 << (hash[p] * 3));
}
if (f) {
if (!resMap.containsKey(state)) {
resMap.put(state, wopt[i]);
} else if (resMap.get(state) > wopt[i]) {
resMap.put(state, wopt[i]);
}
}
}
return resMap;
}
// *)
boolean valid(int s1, int s2) {
for (int i = 0; i < 7; i++) {
int t1 = (s1 >> (i * 3)) & 0x07;
int t2 = (s2 >> (i * 3)) & 0x07;
if (t1 + t2 > nums[i]) {
return false;
}
}
return true;
}
// 状压DP
public int Leetcode(String[] words) {
// 预处理
prebuild();
int n = words.length;
TreeMap<Integer, Integer> prev = new TreeMap<>();
prev.put(0, 0);
for (int i = 0; i < n; i++) {
// 对每个单词进行状态抽取
TreeMap<Integer, Integer> stage = solve(words[i]);
TreeMap<Integer, Integer> next = new TreeMap<>(prev);
// 动态主流程
for (Map.Entry<Integer, Integer> e: prev.entrySet()) {
for (Map.Entry<Integer, Integer> e2: stage.entrySet()) {
if (valid(e.getKey(), e2.getKey())) {
int ns = e.getKey() + e2.getKey();
if (!next.containsKey(ns) || next.get(ns) > e.getValue() + e2.getValue()) {
next.put(ns, e.getValue() + e2.getValue());
}
}
}
}
prev = next;
}
return prev.getOrDefault(fstate, -1);
}
}5. 沙地治理
比赛的时候没做出来，后续补上代码。
不过赛后，学会了一招，有意思
6. 集水器
比赛的时候没做出来，后续补上代码。
其实想到了并查集，但是思绪非常的混乱，下笔的时候，其实挺没信心的，做不出来不冤。
写在最后
团队赛真的是卧虎藏龙，期待下次有更好的表现。
评论 (9)
