11.21-559. N 叉树的最大深度
题面
给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
没什么好说的，dfs/bfs板子题。
要点
图论 dfs/bfs
代码
/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */ class Solution { public: int maxDepth(Node* root) { if (root==NULL) return 0; else{ int res=0; for (auto node:root->children) res=max(res,maxDepth(node)); res=res+1; return res; } } };
完成情况
独立完成
11.22-384. 打乱数组
题面
给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shuffle-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
要点
洗牌算法
代码
class Solution { public: vector<int> nums; vector<int> orig; Solution(vector<int>& nums) { this->nums=nums; this->orig.resize(nums.size()); copy(nums.begin(),nums.end(),orig.begin()); } vector<int> reset() { copy(orig.begin(),orig.end(),nums.begin()); return nums; } vector<int> shuffle() { for(int i=0;i<nums.size();i++){ int j=i+rand()%(nums.size()-i); swap(nums[i],nums[j]); } return nums; } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(nums); * vector<int> param_1 = obj->reset(); * vector<int> param_2 = obj->shuffle(); */
完成情况
借助题解
11.23-859. 亲密字符串
题面
给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
例如，在 “abcd” 中交换下标 0 和下标 2 的元素可以生成 “cbad” 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/buddy-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
本题需要计数26个字母每个字母出现的次数。但要考虑的细节非常多：如果两个字符串长度不同，则直接返回false。如果两个字符串相同，则需要考虑是否有某个字符出现过两次。如果两个字符串不同，则需要考虑是不是有且只有2位字符不同。
代码
class Solution { public: int cnts[26]; int cntg[26]; bool buddyStrings(string s, string goal) { if(s.size()!=goal.size()) return false; int len=s.size(); int sum=0; for(int i=0;i<len;i++){ cntg[goal[i]-'a']++; cnts[s[i]-'a']++; if(goal[i]!=s[i]) sum++; } bool swapflag=false; for(int i=0;i<26;i++) if (cnts[i]>=2){ swapflag=true; break; } for(int i=0;i<26;i++) if(cnts[i]!=cntg[i]) return false; if(sum==2||sum==0&&swapflag) return true; else return false; } };
完成情况
独立完成
11.24-423. 从英文中重建数字
题面
给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字
思路
计数。z的个数为0的个数；w的个数为2的个数；u的个数为4的个数；x的个数为6的个数；g的个数为8的个数。这五个数字都能直接重建出来。接下来
，3和8都有h；5和4都有f；7和6都有s，这些也能重建。1、0、2、4都有o，重建1；5、6、8、9都有i，重建9。
代码
class Solution { public: int nums[10]; int st[26]; string res; string originalDigits(string s) { int len=s.size(); for(int i=0;i<len;i++) st[s[i]-'a']++; nums[0]=st['z'-'a']; nums[2]=st['w'-'a']; nums[4]=st['u'-'a']; nums[6] = st['x'-'a']; nums[8]=st['g'-'a']; nums[3] = st['h'-'a'] - nums[8]; nums[5] = st['f'-'a'] - nums[4]; nums[7] = st['s'-'a'] - nums[6]; nums[1] = st['o'-'a'] - nums[0] - nums[2] - nums[4]; nums[9] = st['i'-'a'] - nums[5] - nums[6] - nums[8]; for (int i = 0; i < 10; ++i) { for (int j = 0; j < nums[i]; ++j) { res += char(i + '0'); } } return res; } };
完成情况
独立完成，但不是最优解。
11.25-458. 可怜的小猪
题面
有 buckets 桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有 minutesToTest 分钟时间来确定哪桶液体是有毒的。
喂猪的规则如下：
选择若干活猪进行喂养
可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。
小猪喝完水后，必须有 minutesToDie 分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。
过了 minutesToDie 分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。
重复这一过程，直到时间用完。
给你桶的数目 buckets ，minutesToDie 和 minutesToTest ，返回在规定时间内判断哪个桶有毒所需的 最小 猪数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/poor-pigs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
要点
数论。进制表示。状态压缩
代码
class Solution { public: int poorPigs(int buckets, int minutesToDie, int minutesToTest) { int k=minutesToTest/minutesToDie; return ceil(log(buckets)/log(k+1)); } };
完成情况
借助题解
11.26-700. 二叉搜索树中的搜索
题面
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
思路
没什么好说的，dfs。
代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* searchBST(TreeNode* root, int val) { if(root==NULL) return NULL; TreeNode* res=NULL; if (root->val>val) res=searchBST(root->left,val); if(root->val==val) res=root; if(root->val<val) res=searchBST(root->right,val); return res; } };
完成情况
独立完成
11.27-519. 随机翻转矩阵
题面
给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。
尽量最少调用内置的随机函数，并且优化时间和空间复杂度。
实现 Solution 类：
Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
void reset() 将矩阵中所有的值重置为 0
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/random-flip-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
利用哈希表存储矩阵中的1位。矩阵的第i , j i,ji,j位用一位k kk表示。k=i∗n+j。剩下的操作类似于洗牌算法。
要点
哈希表。用一个数表示矩阵下标。洗牌算法
代码
class Solution { public: int m,n,cnt; map<int,int> st; Solution(int m, int n) { this->m=m; this->n=n; this->cnt=m*n; } vector<int> flip() { int x=rand()%cnt; vector<int> ans; cnt--; if(!st.count(x)) ans={x/n,x%n}; else ans={st[x]/n,st[x]%n}; if(st.count(cnt)) st[x]=st[cnt]; else st[x]=cnt; return ans; } void reset() { cnt=m*n; st.clear(); } }; /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(m, n); * vector<int> param_1 = obj->flip(); * obj->reset(); */
完成情况
看了题解。而且看了题解才想起来前几天做过一道洗牌算法的题。果然容易前看后忘啊。
