LeetCode刷题笔记
目录
一.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;
}
};
- 点赞
- 收藏
- 关注作者
评论（0）