LeetCode刷题笔记_leetcode csdn

 目录

一.1494.并行课程 II

题目：

灵神解析：

 思路整理：

代码：

二.剑指Offer 05.替换空格 

题目：

 思路：

代码：

   三.剑指 Offer 27.二叉树的镜像

题目：

 思路：

代码：

---

一.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;
    }
};