1178. 猜字谜
      外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

采用字典树解题。

struct TrieNode {int frequency = 0;TrieNode* child[26];TrieNode() {for (int i = 0; i < 26; ++i) {child[i] = nullptr;}}
};class Solution {
private:TrieNode* root;public:vector findNumOfValidWords(vector& words, vector& puzzles) {root = new TrieNode();auto add = [&](const string& word) {TrieNode* cur = root;for (char ch: word) {if (!cur->child[ch - 'a']) {cur->child[ch - 'a'] = new TrieNode();}cur = cur->child[ch - 'a'];}++cur->frequency;};// 在回溯的过程中枚举 puzzle 的所有子集并统计答案// find(puzzle, required, cur, pos) 表示 puzzle 的首字母为 required, 当前搜索到字典树上的 cur 节点，并且准备枚举 puzzle 的第 pos 个字母是否选择（放入子集中）// find 函数的返回值即为谜底的数量function find = [&](const string& puzzle, char required, TrieNode* cur, int pos) {// 搜索到空节点，不合法，返回 0if (!cur) {return 0;}// 整个 puzzle 搜索完毕，返回谜底的数量if (pos == 7) {return cur->frequency;}// 选择第 pos 个字母int ret = find(puzzle, required, cur->child[puzzle[pos] - 'a'], pos + 1);// 当 puzzle[pos] 不为首字母时，可以不选择第 pos 个字母if (puzzle[pos] != required) {ret += find(puzzle, required, cur, pos + 1);}return ret;};for (string word: words) {// 将 word 中的字母按照字典序排序并去重sort(word.begin(), word.end());word.erase(unique(word.begin(), word.end()), word.end());// 加入字典树中add(word);}vector ans;for (string puzzle: puzzles) {char required = puzzle[0];sort(puzzle.begin(), puzzle.end());ans.push_back(find(puzzle, required, root, 0));}return ans;}
};

1179. 重新格式化部门表
      编写一个 SQL 查询来重新格式化表，使得新的表中有一个部门 id 列和一些对应 每个月 的收入（revenue）列。

聚合函数就用来输入多个数据，输出一个数据的。如SUM()或MAX()，而每个聚合函数的输入就是每一个多数据的单元格。

# Write your MySQL query statement below
select id,sum(case month when 'Jan' then revenue end) as Jan_Revenue,sum(case month when 'Feb' then revenue end) as Feb_Revenue,sum(case month when 'Mar' then revenue end) as Mar_Revenue,sum(case month when 'Apr' then revenue end) as Apr_Revenue,sum(case month when 'May' then revenue end) as May_Revenue,sum(case month when 'Jun' then revenue end) as Jun_Revenue,sum(case month when 'Jul' then revenue end) as Jul_Revenue,sum(case month when 'Aug' then revenue end) as Aug_Revenue,sum(case month when 'Sep' then revenue end) as Sep_Revenue,sum(case month when 'Oct' then revenue end) as Oct_Revenue,sum(case month when 'Nov' then revenue end) as Nov_Revenue,sum(case month when 'Dec' then revenue end) as Dec_Revenue
from Department
group by id

1184. 公交站间的距离
      环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。环线上的公交车都可以按顺时针和逆时针的方向行驶。返回乘客从出发点 start 到目的地 destination 之间的最短距离。

过于简单以至于不知道该说什么

class Solution {
public:int distanceBetweenBusStops(vector& distance, int start, int destination) {if (start > destination) {swap(start, destination);}return min(accumulate(distance.begin() + start, distance.begin() + destination, 0),accumulate(distance.begin(), distance.begin() + start, 0) +accumulate(distance.begin() + destination, distance.end(), 0));}
};

1185. 一周中的第几天
      给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。输入为三个整数：day、month 和 year，分别表示日、月、年。您返回的结果必须是这几个值中的一个 {“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”, “Saturday”}

只要知道一个最早的日期和星期几，然后减法求一下即可1

class Solution {
public:string dayOfTheWeek(int day, int month, int year) {vector week = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};vector monthDays = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30};/* 输入年份之前的年份的天数贡献 */int days = 365 * (year - 1971) + (year - 1969) / 4;/* 输入年份中，输入月份之前的月份的天数贡献 */for (int i = 0; i < month - 1; ++i) {days += monthDays[i];}if ((year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) && month >= 3) {days += 1;}/* 输入月份中的天数贡献 */days += day;return week[(days + 3) % 7];}
};

1186. 删除一次得到子数组最大和
      给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。注意，删除一个元素后，子数组 不能为空。

这道题由求子数组的最大和演变而来，唯一的不同的是子数组中，有可能被删除一项，为了分析问题方便，我们这边用一个标志位来表示子数组中是否已经删除了一项，因此这里状态表示可以用f[i][2]来表示。
其中f[i][0]表示以arr[i]结尾的且未删除元素的子数组的最大和
f[i][1]表示以arr[i]结尾的且删除了一个元素的子数组的最大和
f[i][0] = max(f[i - 1][0] + a[i],a[i]);
f[i][1] = max(f[i - 1][0],f[i - 1][1] + a[i]);

class Solution {
public:int maximumSum(vector& arr) {int dp0 = arr[0];// First deletion will leads to empty string as a potential answer,// which should be avoided. So we set a out of range valueint dp1 = -100000;int maximum = dp0;for (int i = 1; i < arr.size(); ++i) {int ndp0 = max(dp0 + arr[i], arr[i]);int ndp1 = max(dp0, dp1 + arr[i]);maximum = max(maximum, max(ndp0, ndp1));dp0 = ndp0;dp1 = ndp1;}return maximum;}
};

1187. 使数组严格递增
      给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。如果无法让 arr1 严格递增，请返回 -1。

本题首先对arr2除重和排序，这个毫无疑问。然后就是关键点了：从后往前操作，每次尽可能取大的值替换。下一个就是dp的核心：每次可以选择，改变当前的值或者改变前一个值，因此可以完成min(dp[i - 2], dp[i - 1])

class Solution {
public:int maxv = 1e9;int makeArrayIncreasing(vector& arr1, vector& arr2) {// 预处理：排序，去重，加哨兵sort(arr2.begin(), arr2.end());arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());arr1.push_back(maxv + 5); // 右侧哨兵 infarr1.insert(arr1.begin(), -1); // 左侧哨兵 -1vector dp(arr1.size(), maxv);dp[0] = 0;for(int i = 1; i < arr1.size(); ++i) {int j = lower_bound(arr2.begin(),arr2.end(), arr1[i]) - arr2.begin();for(int k = 1; k <= min(i-1,j); ++k){ // 1. 枚举替换的个数 k = 1 to min(i-1,j)if(arr1[i-k-1] < arr2[j-k]) {dp[i] = min(dp[i], dp[i-k-1] + k);}}if(arr1[i-1] < arr1[i]) { // 2. 不替换 arr1[i-1]dp[i] = min(dp[i], dp[i-1]);}}int res = dp[arr1.size()-1];return (res >= maxv)? -1 : res;}
};

1189. “气球” 的最大数量
      给你一个字符串 text，你需要使用 text 中的字母来拼凑尽可能多的单词 “balloon”（气球）。字符串 text 中的每个字母最多只能被使用一次。请你返回最多可以拼凑出多少个单词 “balloon”。

用数组分别存储各不同字母的数量，对l和o除2，然后取最小数即为可以拼凑多少个单词。

class Solution {
public:int maxNumberOfBalloons(string text) {vector cnt(5);for (auto & ch : text) {if (ch == 'b') {cnt[0]++;} else if (ch == 'a') {cnt[1]++;} else if (ch == 'l') {cnt[2]++;} else if (ch == 'o') {cnt[3]++;} else if (ch == 'n') {cnt[4]++;}}cnt[2] /= 2;cnt[3] /= 2;return *min_element(cnt.begin(), cnt.end());}
};