5.6 解码异或后的数组

class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        int n=encoded.size()+1;
        vector<int> arr(n);
        arr[0]=first;
        for (int i=1; i<n; i++) {
            arr[i]=arr[i-1]^encoded[i-1];
        }
        return arr;
    }
};

异或是满足交换律和结合律的,就是x和y异或=z,已知x和z,y是能求出来的x\oplus y=z,x\oplus z=y
那对于这道题,我知道encode[i]=arr[i]\oplus arr[i+1],我还知道第一个元素是什么,那我们自然而然的就往下做了

5.7 数组的异或操作:这个不想说了,太简单了

5.8 完成工作的最短时间
这道题我犯了四个很低级的错误:
1.二分查找的时候没有更新mid
2.传参数没有传引用,导致所有的结果都没变
3.判断能否完成的时候没有考虑刚好完成所带来
4.工作时间加了之后,如果判断不行没减回去
给你一个整数数组 jobs ,其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人,且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案,使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1:
输入:jobs = [3,2,3], k = 3
输出:3
解释:给每位工人分配一项工作,最大工作时间是 3 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题是一道搜索类型的题目,是一道直接搜索答案的题目,总的思路就两点
1.主函数做二分搜索
2.子函数验证这个结果对不对,来帮助主函数做二分搜索

这道题要注意一点,要不然时间这一块把握不住
1.建议使用贪心算法,就是把大的任务先安排下去
2.在任务已经明确不能完成或者说是一定能够完成的情况下自动退出

判断的方法也稍微提一下:就是给每个工人分配任务,分配任务的形式就是更改一个数组,这个数组存放了每个工人工作的总时间,分配就是依据每个总时间进行分配的,分配的方式就是递归,有一步出现问题就返回报错,到达叶节点(分配完成)就返回OK

如果有思路,写出代码来还是很简单的,这一种题真的和滑动窗口很像

class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        sort(jobs.begin(), jobs.end(), greater<int>());
        int first = jobs[0], total = accumulate(jobs.begin(), jobs.end(), 0);
        //没有达到最优解
        while(first<total){
            //检查一下mid行不行
            int mid = (first+total)/2;
            if(ok(jobs,k,mid)){
                total=mid;
            }
            else{
                first=mid+1;
            }
        }
        return first;
    }
    bool ok(vector<int>& jobs, int k, int value){
        vector<int> workers(k,0);
        return check(jobs,workers,0,value);
    }
    //递归寻找
    bool check (vector<int>& jobs,vector<int> workers, int now,int value){
        if(jobs.size()<=now){
            return true;
        }
        else{
            int cur=jobs[now];
            for (auto& workload : workers) {
                if (workload+cur<=value) {
                    workload+=cur;
                    if (check(jobs,workers,now+1,value)) {
                        return true;
                    }
                    workload-=cur;
                }
                if (workload==0||workload+cur==value) {
                    break;
                }
            }
            return false;
        }
        
    }
};

5.9 制作花束的最少天数
给你一个整数数组 bloomDay,以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时,需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花,第 i 朵花会在 bloomDay[i] 时盛开,恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

示例 1:
输入:bloomDay = [1,10,3,10,2], m = 3, k = 1
输出:3
解释:让我们一起观察这三天的花开过程,x 表示花开,而 _ 表示花还未开。
现在需要制作 3 束花,每束只需要 1 朵。
1 天后:[x, , , , ] // 只能制作 1 束花
2 天后:[x, , , , x] // 只能制作 2 束花 3 天后:[x, , x, _, x] // 可以制作 3 束花,答案为 3

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-number-of-days-to-make-m-bouquets
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题的思路和昨天的其实很像,就说说判断在某一天之内能否生产那么多花束的思路:其实就是一个遍历+模拟就可以完成的,就是假设这一天已经来到,看看有哪些花盛开了.就取哪些花,有连续的几朵就可以组成一个花束,这么简单

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if(bloomDay.size()<m*k){
            return -1;
        }
        int high=0,low=INT_MAX;
        for (int i = 0; i < bloomDay.size(); i++) {
            low=min(low, bloomDay[i]);
            high=max(high, bloomDay[i]);
        }
        
        while(high>low){
            int mid=(high+low)/2;
            if(check(bloomDay,m,k,mid)){
                high=mid;
            }
            else{
                low=mid+1;
            }
        }
        return low;
    }
    bool check(vector<int>& bloomDay, int m, int k,int days){
        int hua=0,huashu=0;
        for(int i=0;i<bloomDay.size()&&huashu<m;i++){
            if(bloomDay[i]<=days){
                hua++;
                if(hua==k){
                    huashu++;
                    hua=0;
                }
            }
            else{
                    hua=0;
            }
        }
        return huashu>=m;
    }   
};

上面两题向我们展示了一个利用二分搜索搜索答案的思路:
1.主函数二分搜索
2.子函数验证
众所周知,求解比验证难许多

5.10 叶子相似的树

前序遍历就可以了.前序遍历能保证叶子是从左到右被遍历到的

class Solution {
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        vector<int> a1;
        vector<int> a2;
        if(root1) forwardTraverse(root1,a1);
        if(root2) forwardTraverse(root2,a2);
        return a1==a2;
    }
    void forwardTraverse(TreeNode* root,vector<int>&list){
        if(!(root->left)&&!(root->right)){
            list.push_back(root->val);
            return;
        }
        if(root->left) forwardTraverse(root->left,list);
        if(root->right) forwardTraverse(root->right,list);
        return;
    }
};

5.11 解码异或后的排列
给你一个整数数组 perm ,它是前 n 个正整数的排列,且 n 是个 奇数 。
它被加密成另一个长度为 n – 1 的整数数组 encoded ,满足 encoded[i] = perm[i] XOR perm[i + 1] 。比方说,如果 perm = [1,3,2] ,那么 encoded = [2,1] 。
给你 encoded 数组,请你返回原始数组 perm 。题目保证答案存在且唯一。
示例 1:
输入:encoded = [3,1]
输出:[1,2,3]
解释:如果 perm = [1,2,3] ,那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
示例 2:

之前我们就做过异或之后的数组怎么解码:最重要的就是寻找到那个first元素,这里我们也可以寻找到first元素

我们知道x\lxor x=0,那我们寻找到第一个元素,就是(x_0\oplus x_1\oplus x_2...\oplus x_n)\oplus (x_1 \oplus x_2\oplus x_3....x_n)=x1

我们还知道encode[2k+1]=a[2k]\oplus a[2k+1]刚好对所有奇数元素的数列一异或就可以把上述式子异或符号右边的元素求出来

注意,原来的数据是从1-n的排列

class Solution {
public:
    vector<int> decode(vector<int>& encode) {
        int n=encode.size()+1;
        vector<int> decode(n,0);
        int total=0;
        int except_0=0;
        for(int i=0;i<=n;i++){
            total=total^i;
        }
        for(int i=1;i<n;i+=2){
            except_0=except_0^encode[i];
        }
        decode[0]=except_0^total;
        for(int i=1;i<n;i++){
            decode[i]=decode[i-1]^encode[i-1];
        }
        return decode;
    }
};

5.12 字数组异或查询
有一个正整数数组 arr,现给你一个对应的查询数组 queries,其中 queries[i] = [Li, Ri]。
对于每个查询 i,请你计算从 Li 到 Ri 的 XOR 值(即 arr[Li] xor arr[Li+1] xor … xor arr[Ri])作为本次查询的结果。
并返回一个包含给定查询 queries 所有结果的数组。
示例 1:
输入:arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出:[2,7,14,8]
解释:
数组中元素的二进制表示形式是:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xor-queries-of-a-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一个式子就可以明白:这里截取官方题解了:

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> result;
        vector<int> xors(arr.size()+1);
        for (int i=0;i<arr.size();i++) {
            xors[i+1]=xors[i]^arr[i];
        }
        for(vector<int>temp:queries){
            int total=0;
            total=xors[temp[0]]^xors[temp[1]+1];
            result.push_back(total);
        }
        return result;
    }
};

5.13 停在原地的方案数
有一个长度为 arrLen 的数组,开始有一个指针在索引 0 处。
每一步操作中,你可以将指针向左或向右移动 1 步,或者停在原地(指针不能被移动到数组范围外)。
给你两个整数 steps 和 arrLen ,请你计算并返回:在恰好执行 steps 次操作以后,指针仍然指向索引 0 处的方案数。
由于答案可能会很大,请返回方案数 模 10^9 + 7 后的结果。
示例 1
输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
public:
    const int MODULO = 1000000007;
    int numWays(int steps, int arrLen) {
        int maxc=min(arrLen-1,steps/2);
        vector<vector<int>> dp(steps+1, vector<int>(maxc+1));
        dp[0][0]=1;
        for(int i=1;i<=steps;i++){
            for(int j=0;j<=maxc;j++){
                dp[i][j]=dp[i-1][j];
                if(j-1>=0){
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MODULO;
                }
                if(j+1<=maxc){
                    dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MODULO;
                }
                
            }
        }
        return dp[steps][0];
    }
};

动态规划:dp[行动的步数][获得的这个结果]=走的方案数
官方题解还可以优化,比如说压缩到一维动态规划
动态规划最重要的就是:初态+状态转移,这里的初态:
dp[0][0]=1,dp[0][i]=0,状态转移:来源于三个操作:一个是向左,一个是向右,一个是不动:dp[i][j]=dp[i-1][j]+dp[i-1][j+1]+dp[i-1][j-1](if j+1,j-1 exists)

5.14 整数转罗马数字
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给你一个整数,将其转为罗马数字。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

变相的数位转换罢了,注意的是1000-900-500-400-100-90-50-40-10-9-5-4-1这套转化法则,一开始就是没反应过来23333

5.15 罗马数字转整数

还是一样的,读取罗马数字,如果下一个罗马数字对应的值比我这个大,那么说明应该是IX之类的问题,就要减去这个罗马数字对应的值如果小,就加这个罗马数字对应的值就行

5.16 数组中最大的异或值

输入:nums = [3,10,5,25,2,8]
输出:28
解释:最大运算结果是 5 XOR 25 = 28.

这个代码是题解里面的

第一种方法是贪心算法,就是我们已经知道x=a_i \oplus a_j所以说我们就假设x,然后找有没有适合的a_i和a_j就好了,我们按位查找,从高位到低位查找:
首先看最高位有没有a_i\oplus a_j=x有的话就取1:就是2x+1没有的话就取0,就是2x,以此类推

第二种方法就是字典法:

这个是一个字典树,每个元素从高位到低位按照0和1的顺序建立树
当检查x的最大性的时候的做法:
因为要让异或最大,那就读取一个数,从高位到低位判断,如果这个位为0,那就看看这个位有没有位1的数,反之亦然.有的话异或的值就可以2x+1,没有的话就是2x

这里需要说明一下二进制的求值方法:从高位到低位扫描,扫描到1的话2y+1,扫描到0的时候就为2y

struct Trie {
    // 左子树指向表示 0 的子节点
    Trie* left = nullptr;
    // 右子树指向表示 1 的子节点
    Trie* right = nullptr;

    Trie() {}
};

class Solution {
private:
    // 字典树的根节点
    Trie* root = new Trie();
    // 最高位的二进制位编号为 30
    static constexpr int HIGH_BIT = 30;

public:
    void add(int num) {
        Trie* cur = root;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                if (!cur->left) {
                    cur->left = new Trie();
                }
                cur = cur->left;
            }
            else {
                if (!cur->right) {
                    cur->right = new Trie();
                }
                cur = cur->right;
            }
        }
    }

    int check(int num) {
        Trie* cur = root;
        int x = 0;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (bit == 0) {
                // a_i 的第 k 个二进制位为 0,应当往表示 1 的子节点 right 走
                if (cur->right) {
                    cur = cur->right;
                    x = x * 2 + 1;
                }
                else {
                    cur = cur->left;
                    x = x * 2;
                }
            }
            else {
                // a_i 的第 k 个二进制位为 1,应当往表示 0 的子节点 left 走
                if (cur->left) {
                    cur = cur->left;
                    x = x * 2 + 1;
                }
                else {
                    cur = cur->right;
                    x = x * 2;
                }
            }
        }
        return x;
    }

    int findMaximumXOR(vector<int>& nums) {
        int n = nums.size();
        int x = 0;
        for (int i = 1; i < n; ++i) {
            // 将 nums[i-1] 放入字典树,此时 nums[0 .. i-1] 都在字典树中
            add(nums[i - 1]);
        }
        for (int i = 1; i < n; ++i){
            // 将 nums[i] 看作 ai,找出最大的 x 更新答案
            x = max(x, check(nums[i]));
        }
        return x;
    }
};

5.17 二叉树的堂兄弟节点

这个东西就是做一遍二叉树的遍历,找到:层数+父节点,比较就行了.传参数比较麻烦的话就开全局变量就好了

class Solution {
public:
    // x 的信息
    int x;
    TreeNode* x_parent;
    int x_depth;

    // y 的信息
    int y;
    TreeNode* y_parent;
    int y_depth;

    void level1(TreeNode* root,int x,int k){
        if(!root){
            return;
        }
        if(root->val==x){
            x_depth=k;
        }
        if(root->left){
            level1(root->left,x,k+1);
        }
        if(root->right){
            level1(root->right,x,k+1);
        }
        return;
    }
    void level2(TreeNode* root,int y,int k){
        if(!root){
            return;
        }
        if(root->val==y){
            y_depth=k;
        }
        if(root->left){
            level2(root->left,y,k+1);
        }
        if(root->right){
            level2(root->right,y,k+1);
        }
        return;
    }
    void parent2(TreeNode* root,int y){
        if(!root){
            return;
        }
        if(root->right&&root->right->val==y){
            y_parent=root;
        }
        if(root->left&&root->left->val==y){
            y_parent=root;
        }
        if(root->left){
            parent2(root->left,y);
        }
        if(root->right){
            parent2(root->right,y);
        }
        return;
    }
    void parent1(TreeNode* root,int x){
        if(!root){
            return;
        }
        if(root->right&&root->right->val==x){
            x_parent=root;
        }
        if(root->left&&root->left->val==x){
            x_parent=root;
        }
        if(root->left){
            parent1(root->left,x);
        }
        if(root->right){
            parent1(root->right,x);
        }
        return;
    }
    bool isCousins(TreeNode* root, int x, int y) {
        parent1(root,x);
        parent2(root,y);
        level1(root,x,0);
        level2(root,y,0);
        return (x_depth==y_depth)&&(x_parent!=y_parent);
    }
};

5.18 形成两个异或相等的三元组数目

给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ,其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下:
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
注意:^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

还是那张图

此图像的alt属性为空;文件名为image-1024x205.png
class Solution {
public:
    int countTriplets(vector<int>& arr) {
        int ans=0;
        int count=arr.size();
        vector<int> abab(count+1);
        for(int i=0;i<count;i++){
            abab[i+1]=abab[i]^arr[i];
        }
        for(int i=0;i<count;i++){
            for(int j=i+1;j<count;j++){
                for(int k=j;k<count;k++){
                    if(abab[i]==abab[k+1]){
                        ++ans;
                    }
                }
            }
        }
        return ans;
    }
};

5.19 找出第K大的异或坐标值

最近力扣是和这个公式杠上了么…,这道题就是一个模拟就行的了,但是我们可以建表来记录(m,k)之内的元素异或的和,这三项刚好可以表示

给你一个二维矩阵 matrix 和一个整数 k ,矩阵大小为 m x n 由非负整数组成。
矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j](下标从 0 开始计数)执行异或运算得到。
请你找出 matrix 的所有坐标中第 k 大的值(k 的值从 1 开始计数)。
示例 1:
输入:matrix = [[5,2],[1,6]], k = 1
输出:7
解释:坐标 (0,1) 的值是 5 XOR 2 = 7 ,为最大的值。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

隐藏