一.1494.并行课程 II
不得不说，灵神确实牛啊。看完灵神解析，恍然大悟啊。
首先这道题采用位运算+递归+记忆化搜索。我们先看灵神的解析
思路整理：
接下来详细解析一下，首先整理一下思路。
1.建立数组，存储每个课程的先行课有哪些。
2.求完成所有课程所需要的最短时间。
第一步：也许很容易想到我们可以用一个二维数组来存储每个课程的先行课，例如bool arr[i][j] 代表第j个课程是否是第i个课程的先行课。是为true，不是为false。很容易想到，但是题目说最多有15个课程，那么很容易想到状态压缩。我们用一个一维数组优化掉二维数组。int类型有32位我们取低位，分别代表一门课程的先行课。例如建立pre1[i]=0000 0000 0000 0000 0000 0000 0000 00101 代表1号课程和3号是i课程的先行课。
第二步：数组有了，接下来考虑怎么得出最短时间。我每次递归从所有学科中选取可以学的学科，也就是先行课学完或者没有先行课的课程。如果小于k就一次性学习所有可以学习的课。如果大于k，遍历所有学k个课程的可能取最小值即可。注意学完要将学完的课变为0，以便下一层递归检测某一课程的先行课是否完成
代码：
class Solution { public: int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k) { vector<int> pre1(n,0); //存储1-n的先行课，1为先行课 for (auto &r: relations) pre1[r[1] - 1] |= 1 << (r[0] - 1); // r[1] 的先修课程集合，下标改从 0 开始 int u = (1 << n) - 1; // 全集，全部的课都变为1 int memo[1 << n]; memset(memo, -1, sizeof(memo)); // -1 表示没有计算过 function<int(int)> dfs = [&](int i) -> int { if (i == 0) return 0; // 空集，证明课上完了 int &res = memo[i]; // 注意这里是引用 //int* const res=&memo[i] //*res=100; if (res != -1) return res; // 之前算过了 int i1 = 0, ci = u ^ i; // u为全1，i是上课的为1，ci为上完的为1 for (int j = 0; j < n; j++) if ((i >> j) & 1 && (pre1[j] | ci) == ci) //(i >> j) & 1判断这一位是否为1，是1代表没学， //pre1[j]代表j的先行课，要上的先行课为1， //pre1[j] | ci代表先行课都上了，可以学习j课程 //pre1[j] 在 i 的补集中，可以学（否则这学期一定不能学） i1 |= 1 << j; //i1用来记录这一学期哪一课程可以学，1为可以学 if (__builtin_popcount(i1) <= k) // 如果个数小于 k，则可以全部学习，不再枚举子集 return res = dfs(i ^ i1) + 1; //i存储没学的课程，i1存储可以学的课程， //i ^ i1代表学完之后没有学习的课程 res = INT_MAX; //大于k，枚举每次上k个课程，取最小值 for (int j = i1; j; j = (j - 1) & i1) // 枚举 i1 的子集 j //从大到小，判断正好能学k个的情况,牛皮 if (__builtin_popcount(j) == k) res = min(res, dfs(i ^ j) + 1); //取最小值返回 return res; }; return dfs(u); } };
二.剑指Offer 05.替换空格
思路：
首先第一遍遍历，检测有几个空格。然后将该字符串扩容，每有一个空格，字符串长度增加2。然后设置右指针为字符串末尾，左指针为原字符串的末尾。不遇空格不断向前复制即可，遇到空格右指针向前移动并且赋值为“%20”,左指针左移一个跳过空格即可。
代码：
class Solution { public: string replaceSpace(string s) { int len=s.size(),count=0; for(int i=0;i<len;i++){ if(s[i]==' ') count++; } int left=len-1,right=left+2*count; s.resize(right+1); while(right!=left){ if(s[left]!=' '){ s[right]=s[left],right--,left--; }else{ s[right--]='0',s[right--]='2',s[right--]='%',left--; } } return s; } };
三.剑指 Offer 27.二叉树的镜像
思路：
根据二叉树镜像的定义，考虑递归遍历（dfs）二叉树，交换每个节点的左 / 右子节点，即可生成二叉树的镜像。
递归解析：
1.终止条件： 当节点 root 为空时（即越过叶节点），则返回 nullptr；
2.递推工作：
（1）初始化节点 tmp ，用于暂存 root 的左子节点；
（2）开启递归 右子节点 mirrorTree(root.right) ，并将返回值作为 root 的 左子节点 。
（3）开启递归 左子节点mirrorTree(tmp) ，并将返回值作为 root 的 右子节点 。
3.返回值： 返回当前节点
代码：
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* mirrorTree(TreeNode* root) { if(root==nullptr) return nullptr; TreeNode* tmp=root->left; root->left=root->right; root->right=tmp; mirrorTree(root->right); mirrorTree(root->left); return root; } };
