2021.11.14-键值映射
题面
实现一个 MapSum 类，支持两个方法，insert 和 sum：
MapSum() 初始化 MapSum 对象
void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/map-sum-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
文字分析
使用trie树（字典树），物理上用静态链表进行存储。插入时，每到单词结尾处，利用ValWord数组表示当前结点是否为单词结束。如果单词结束，则ValWord表示当前结点的单词的权值。查询时，利用dfs算法，可以得到当前前缀的权值之和。
代码
class MapSum { public: int ne[10005][26]; int idx; int valWord[10005]; MapSum() { idx=0; memset(ne,0,sizeof ne); memset(valWord,0,sizeof valWord); } void insert(string key, int val) { int p=0; for(int i=0;i<key.length();i++){ int u=key[i]-'a'; if (!ne[p][u]) ne[p][u]=++idx; p=ne[p][u]; } valWord[p]=val; } int sum(string prefix) { int p=0; for(int i=0;i<prefix.length();i++){ int u=prefix[i]-'a'; if(!ne[p][u]) return 0; p=ne[p][u]; } return dfs(p); } int dfs(int p){ int ans=valWord[p]; for(int u=0;u<26;u++){ if(ne[p][u]) ans+=dfs(ne[p][u]); } return ans; } }; /** * Your MapSum object will be instantiated and called as such: * MapSum* obj = new MapSum(); * obj->insert(key,val); * int param_2 = obj->sum(prefix); */
2021.11.15-灯泡开关
题面
初始时有n nn个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭一个。
第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i ii 轮，你每 i ii 个灯泡就切换一个灯泡的开关。直到第 n nn 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n nn 轮后有多少个亮着的灯泡。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bulb-switcher
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
文字分析
看了题解才能明白一个数论知识：除了平方数，其余灯泡都会被开关偶数次数。只有平方数位置的灯泡会被开关奇数次数。1 11至n nn个灯泡中有n \sqrt{n}n个平方数。
代码
class Solution { public: int bulbSwitch(int n) { return (int) sqrt(n); }
2021.11.16-完美矩形
题面
如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/perfect-rectangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
文字分析
看到了题解才想到，可以通过x i x_{i}xi, y i y_{i}yi, a i a_{i}ai, b i b_{i}bi计算出每个矩形的四个边界点。在完美矩形中，除了大矩形最外侧的四个边界点，其余小矩形边界点都会出现偶数次数，因为每个边界点是两个小矩形的交界处。可以用哈希表记录小矩形每个点出现的次数。同时也不要忘了小矩形面积和等于大矩形。如果小矩形面积和不等于大矩形，则大矩形不是完美矩形。
代码
typedef pair<int,int> PII; class Solution { public: bool isRectangleCover(vector<vector<int>>& rectangles) { long long areasum=0; int minX=0x3f3f3f3f; int minY=0x3f3f3f3f; int maxX=-0x3f3f3f3f; int maxY=-0x3f3f3f3f; map<PII,int> cnt; int n=rectangles.size(); for(int i=0;i<n;i++){ int x=rectangles[i][0]; int y=rectangles[i][1]; int z=rectangles[i][2]; int w=rectangles[i][3]; areasum+=(z-x)*(w-y); minX=min(x,minX); minY=min(y,minY); maxX=max(z,maxX); maxY=max(w,maxY); PII point0({x,y}); PII point1({x,w}); PII point2({z,y}); PII point3({z,w}); cnt[point0]++; cnt[point1]++; cnt[point2]++; cnt[point3]++; } PII minmin({minX,minY}); PII minmax({minX,maxY}); PII maxmin({maxX,minY}); PII maxmax({maxX,maxY}); long long area=(maxX-minX)*(maxY-minY); if(area!=areasum) return false; if(!cnt.count(minmin) || !cnt.count(minmax) || !cnt.count(maxmin) || !cnt.count(maxmax)) return false; cnt.erase(minmin); cnt.erase(minmax); cnt.erase(maxmin); cnt.erase(maxmax); for(auto &node:cnt) if(node.second%2==1) return false; return true; } };
2021.11.17-最大单词长度乘积
题面
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-of-word-lengths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
文字分析
看到了题解才明白，可以将一个单词按位运算压缩成一个只有32bit的int。因为英文字母共26个，26<32.所以，int每一位记录某个字母是否出现在某个单词中。存储单词时对每一位进行或运算，判断单词是否有相同字母时进行与运算。
代码
class Solution { public: int maxProduct(vector<string>& words) { int hashword[1005]; for(int i=0;i<words.size();i++) for(int j=0;j<words[i].size();j++) hashword[i]|=(1<<(words[i][j]-'a')); int ans=0; for(int i=0;i<words.size();i++) for(int j=i+1;j<words.size();j++){ if ((hashword[i]&hashword[j])==0) ans=max(ans,words[i].size()*words[j].size()); } return ans; } };
2021.11.18-二叉树的坡度
题面
给定一个二叉树，计算 整个树 的坡度 。
一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
整个树 的坡度就是其所有节点的坡度之和。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-tilt
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
文字分析
树的坡度和=左子树坡度和+右子树坡度和+当前结点坡度。可以使用dfs。
代码
class Solution { public: int findsum(TreeNode *root){ if (root==NULL) return 0; else return root->val+findsum(root->left)+findsum(root->right); } int findTilt(TreeNode* root) { if(root==NULL) return 0; int lsum=findsum(root->left); int rsum=findsum(root->right); return abs(lsum-rsum)+findTilt(root->left)+findTilt(root->right); } };
2021.11.19-整数替换
题面
给定一个正整数 n ，你可以做如下操作：
如果n 是偶数，则用 n/2替换n 。
如果n 是奇数，则可以用n+1或n−1替换n 。
n 变为1 所需的最小替换次数是多少？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-replacement
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
文字分析
代码
class Solution { public: int integerReplacement(int n) { int ans=0; while (n>1){ if (n%2==0){ n=n/2; ans++; } else if(n%4==1){ n=n/2; ans+=2; } else if(n%4==3){ if (n==3){ ans+=2; n=1; } else{ n=n/2+1; ans+=2; } } } return ans; } };
2021.11.20-最长和谐子序列
题面
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 11 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-harmonious-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
文字分析
这道题的题面非常具有迷惑性，看似是动态规划，实则没有这么复杂。直接用哈希表存储每个数字出现的次数就行。
代码
class Solution { public: int findLHS(vector<int>& nums) { map<int,int> st; int len=nums.size(); for(int i=0;i<len;i++) st[nums[i]]++; int res=0; for(auto num:st){ if(st.find(num.first-1)!=st.end()){ res=max(res,st[num.first-1]+num.second); } } return res; } };
自我总结
本周题目为数论2题，数据结构与图论2题，哈希表3题。其中有2题为完全独立思考，有2题为思考出了解法但并非最优解，有2题需要借助题解进行理解。
