LeetCode 1496 – 1499

LeetCode 1496 – 1499判断路径是否相交检查数组对是否可以被k整除满足条件的子序列数目满足不等式的最大值_leetcode非空子序列

判断路径是否相交

LeetCode 1496 - 1499

LeetCode 1496 - 1499

LeetCode 1496 - 1499

一开始原点有一个小人,给这个小人一堆指令,这些指令分别为 ‘N’、’S’、’D’、’W’(东南西北四个方向),对于每个指令会朝着四个方向中的某一个走 1 个单位的长度(此题左右互换无所谓,由于是对称的,答案是一样的)

示例 1:

LeetCode 1496 - 1499

我们可以根据给出的指令走出一条路线,问:在走的过程中,有没有出现重复的点

LeetCode 1496 - 1499

如果走的过程中有重复的点就输出 True,如果没有重复的点就输出 False

数据范围:10^4,时间复杂度要控制在 O( n√ n ) 或者 O(nlogn)

每次只走一单位的距离,而且是横平竖直的方式走,每次走完之后走过的所有点都一定是整数点(横纵坐标都一定是整数),如果走过重复的点一定是某一个线段的两端,不可能走到两条线之间中点的位置,只需要考虑它所有走过的端点有没有重复的点即可(可以用哈希表判断一堆点里面有没有重复的点)

用哈希表把所有走过的点都存储下来,每次走到一个新的点之后,如果我们发现这个新的点之前走过,就返回 True,否则返回 False

注意哈希表只能哈希一部分的变量类型,例如:哈希表可以哈希 string,但是不能哈希 pair,给我们一个坐标(x,y),需要把它变成哈希表能够哈希的类型(一种比较简单的方式是把 x、y 拼接成一个字符串)

LeetCode 1496 - 1499

时间复杂度与走过的点数成正比,时间复杂度为 O( n )

class Solution {
public:
    bool isPathCrossing(string path) {
        //定义一个哈希表
        unordered_set<string> hash;
        //先把起点(0,0)加到哈希表中
        hash.insert("0 0");
        //起点(0,0)
        int x = 0, y = 0;
        //枚举每一个指令
        for(auto c: path) {
            //如果指令为'N' 表示我们应该向上走
            if(c == 'N') x --;
            else if(c == 'S') x ++;
            //向左走
            else if(c == 'W') y --;
            else y++;
        //把当前坐标变成一个字符串
        string s = to_string(x) + ' ' + to_string(y);
        //如果s在之前出现过-> 说明有重复的点
        if(hash.count(s)) return true;
        //否则把当前坐标加到哈希表中
        hash.insert(s);
        }
        //如果整个过程没有发现重复的点 返回false
        return false;
    }
};

检查数组对是否可以被 k 整除

LeetCode 1496 - 1499

LeetCode 1496 - 1499

给出一个数组,再给一个 k,数组长度是偶数,希望把数组中的所有数分成两两一组配对,使得每一对的数字之和都恰好能够被 k 整除,如果可以满足返回 True,否则,返回 False

数据范围:10^5,时间复杂度要控制在 O(nlogn)

配对的方式有很多种,方案数可能有指数级别。要让每一对的数的和能够被 k 整除,我们关心应该不是 a、b 的绝对值,应该是 a 和 b 除以 k 的余数:如果 a  + b 能够被 k 整除,意味着 k / (a + b) 的余数是 0,应该关心每一个数对里面每一个数的余数是多少

先将数组里面的所有数分成 k 类(根据它对于 k 的余数分成 k 类)

余数从 0 ~ k – 1,一共有 k 种

在配对的过程中:

如果当前这个数除以 k 的余数是 0,如果想让这一对数的和除以 k 的余数也是 0,必须要求与它配对的这个数除以 k 的余数也是 0,余数是 0 的数只能和 0 配对,余数是 1 的数只能余数是 k – 1 的数配对余数是 2 的数只能余数是 k – 2 的数配对. . .以此类推,可以发现虽然方案很多,但是是确定性的配对,我们只需要检查一下:按照这种配对方式,能不能恰好分成 k 组即可(每一个数都找到它配对的数)

先统计一下每一类的数的个数,先判断余数是 0 这一类的个数是不是偶数( 0 只能和 0 配对),再判断余数是 1 这一类的个数和余数是 k – 1 这一类的个数是不是一样的. . .以此类推

LeetCode 1496 - 1499

直接模拟,一个个数配对:对于 0 要与 0 配对,对于 1 要与 k – 1 配对,每有一个 1 就要有一个 k – 1 和它配对,当有一个 1 但是没有 k – 1 就矛盾了,把 1 配对完后再看 2,以此类推. . .如果每一个数都可以配对,返回 True;如果不可以配对,返回 False

对于负数情况的判断参考题解: leetcode1497_Jackybored的博客-CSDN博客_力扣1497

仔细读题可发现突破点,首先每对数字,是否存在说明我们需要遍历数组并且记录下数字的某些信息,这样才能用于之后的存在查找操作。匹配条件是被k整除就该想到使用取模操作。这时将匹配条件转换成取模操作就可解决。如果两个整数相加是k的倍数,那么两个数均取模再相加和必为k。这里分三种情况讨论:

1.一个数是正的,一个数是负的,这样两数和为 0,可以被 k 整除,那么我们该如何匹配这两个数呢,应该如下操作,对于负数 num,进行 (num%k) + k 操作,如 num = -1,k = 3,那么 (-1%3) + 3 = 2,和 -1 匹配的数是 1,对正数进行 num%k 操作,1%3 = 1。可以发现这两个操作之后的数相加为 3,即2 +1 = 3,因此可转化为进行上述操作后结果相加为 k,类似于两数之和的匹配问题。
2.两个数都是正的,和为k的倍数,如 num1 = 4,num2 = 5,k = 3,那么进行 num%k 操作可得到 4%3 = 1,5%3 = 2,1+2=3,匹配条件和上述相同。
3.如果两个数本身就是k的倍数,如num1 = 3,num2 = 3,k = 3,那么 3%3 = 0,这时我们需要记录取余操作为 0 的个数,如果个数是奇数个,必定有一个数无法匹配。

其实对于取余操作来说,进行多次取余操作对结果是没有影响的,如 5%3 = 2,5%3%3 = 2,因此正数情况和负数情况可以合并到一起,即((num%k)+k)%k,这样我们就可以写出代码,不一定需要使用hash_map记录,其它的数据结构 vector 等均可记录

class Solution {
public:
    bool canArrange(vector<int>& arr, int k) {
        //开一个哈希表记录每一类数的个数
        unordered_map<int,int> cnt;
        //统计每一类数
        //取模负数余数为负数需要做考虑-> 需要把所有的余数变成非负数
        for(auto x : arr) cnt[(x % k + k) % k] ++;

        //先判断第 0 类是不是满足要求-> cnt[0] %2 ?= 1 偶数个成立、奇数个不成立
        if(cnt[0] % 2) return false;
        //从第 1 类开始一直到第 k - 1 类
        for(int i = 1;i < k;i++) {
            //如果当前类有数
            while(cnt[i]) {
                //当前类--
                cnt[i] --;
                //看第 k - i 类有没有对应的一个数 如果第 k - i 类已经小于等于 0,说明当前第 i 类这个数无法配对
                if(cnt[k - i] <= 0) return false;
                //减去与当前数配对的数
                cnt[k - i] --;
            }
        }
        //每一个数都可以配对
        return true;
    }
};

满足条件的子序列数目

LeetCode 1496 - 1499

LeetCode 1496 - 1499

给出一个数组 nums 和一个目标值 target,统计数组中有多少个非空子序列,使得子序列中的最小元素与最大元素的和小于等于 target,返回其数目

数据范围:10^5,时间复杂度要控制在 O(nlogn)

找一个序列的子序列等价于找它的子集:任何一个子序列都是一个集合,任何一个集合按照下标排序都是一个子序列

给出我们一堆数,要看一下这堆数里面,有多少个非空子集,使得非空子集的最大数加最小数小于等于目标值 target,要考虑一个集合的最大元素和最小元素,为了方便找到集合的最大元素和最小元素,可以先将整个数组从小到大排序,最靠前的就是最小值,最靠后的就是最大值

LeetCode 1496 - 1499

统计有多少个子集,使得最小数和最大数的和是小于等于目标值 target

带有所有子集的集合如下所示:

LeetCode 1496 - 1499

为了方便统计子集的数量,可以把所有子集分类,按最大元素分类(或者按照最小元素分类),所有最小元素是第 0 个数的子集是第 1 类,所有最小元素是第 1 个数的子集是第 2 类,以此类推一直到第 n – 1 类,只需分别求出每一类的子集数量,加在一起,就是所有满足要求的非空子集的数量

LeetCode 1496 - 1499

考虑当前第 i 类,假设最小元素是 ai(由于 ai 是最小值,所以 ai 左边的数都不能选或者没有左边的数),由于 ai 是最小元素,所以在选择元素的时候,只能在 ai 的右边选,要求最大元素加最小元素要小于目标值:从 i 开始,在右边找最大元素最大是多少的时候可以满足要求

假设对于 ai 来说,可以找到一个最大的 aj,ai + aj 是小于等于目标值 target,并且 aj 是临界点(aj 是最大的所有满足要求的数,aj 右边所有的数都不能选)

最小元素是 ai 的,所有满足要求的非空子集有多少个?怎么计数?

只能从 ai 到 aj 之间的这些数中做选择,由于是第 i 类,首先必须包含 ai

LeetCode 1496 - 1499

剩下的 ai-1 ~ aj-i 之间的 j – i 个数选或者不选都是满足要求的,每个数都有两种选法

LeetCode 1496 - 1499

第 i 类总共的方案数是 2^j-i 个

 LeetCode 1496 - 1499

只要对于每一个 ai ,找到一个最大的 aj,就可以统计出第 i 类满足要求的子集数量

怎么对于每一个 ai 找 aj?由于整个序列递增,可以用双指针

如果从前往后枚举 ai 的值,ai 是不断变大的,与之对应的 aj 是不断变小的

一开始 i 在第 0 个位置,i 从左往右走,j 在最后一个位置,从右往左走,i 越大,j 越小

LeetCode 1496 - 1499

双指针能够使用的前提:有单调性,当 i 从前往后走的时候,j 一定会从后往前走,j 不可能往后走,j 的走法是单调的

当 i 从 i 走到 i ‘ 的时候,与 i ‘ 相对应的 j ‘ 不可能在 j 的后面,如果 i ‘ + j ‘ 这两个数小于等于目标值,那么 i  + j ‘ 这两个数也一定小于等于目标值,(因为 i 变小了),意味着第 i 个数对应的 j 就不是最大的 j,就会出现矛盾,所以 j 的走法具有单调性,可以用双指针

LeetCode 1496 - 1499

要考虑重复计数的问题,题目并没有告诉我们所有的数是不重复的,当我们有相同的数据的时候怎么处理?

当某一个集合中包含两个 5 的时候,最小值应该取哪个 5?(取第 1 个 5、取第 2 个 5、都可以取)会不会出现重复计数?会不会导致这个子集在枚举一个 5 的时候被记录一次,在枚举第 2 个 5 的时候,又被记录一次从而导致重复计数?

LeetCode 1496 - 1499

答案是肯定的,但是我们可以把它规避:虽然这两个 5 的数值是一样的,但是,可以人为规定它们的先后顺序:规定排序后靠前的 5 比靠后的 5 要小,这样就不会出现重复计数的问题

从而保证每一个集合的最小值和最大值都是唯一的,每个集合在计数的时候,只会被它的唯一最小值记录一次,从而不会出现重复计数

LeetCode 1496 - 1499

整个算法的时间复杂度为 O(nlogn) (排序)

双指针时间复杂度:O(n)

需要计算 2^j-i,2^j-i 可能很大,需要先预处理

leetcode1498. 满足条件的子序列数目(Python3)_AndyLiu1997的博客-CSDN博客

首先我们发现,非空子序列不需要是子数组,也就是说,与数组原有顺序无关。且满足条件的序列满足最大值和最小值的和小于等于target。因此我们可以直接对数组进行排序,这样我们就可以划定范围,对某一个子数组,最左边的值一定是子数组的最小值,最右边的值一定是最大值。

下面我们考虑上面的子数组,如果对于一个子数组,使用双指针,left表示子数组的左边界,right表示数组右边界,那如果

left+right <= target,那么这个子数组中有多少序列满足条件呢?答案是2 ^ (right-left)。

这里面我们的序列必须包含nums[left],以子数组[2,3,4,6],target=9为例:

我们必须含有2,那么所有符合条件的序列为[2]、[2,3]、[2,4]、[2,6]、[2,3,4]、[2,3,6]、[2,4,6]、[2,3,4,6]。一共2 ^ 3=8个。

解释起来就是,在必须包含2的基础上,后面的3个数可以选0个、选1个、选2个、选3个。即Cn0 + Cn1 + … + Cnn = 2 ^ n。

那么我们为什么必须包含2呢,为什么不考虑[3]、[4]等等呢?

原因是这些答案在之后的循环中会被找到。

所以我们每次计算的是以left位置为起止的,所有满足条件的序列。

我们首先将左右指针设为整个数组的左右两端;如果此时不满足条件,则右指针right–,直到找到与此时的left满足条件的right。当左右指针的和满足条件(小于等于target),那么计算此时以left为起始的所有子序列;然后left++,继续计算。

【C++ 取模mod易错点】由于答案可能会很大,请你将结果对1e9+7取模后再返回_白马金羁侠少年的博客-CSDN博客_c++ mod

取模运算(C++)_还没想好~的博客-CSDN博客_c++整除符号

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        int n = nums.size(),mod = 1e9 + 7;
        vector<int> p(n);
        //预处理 2 的所有次幂
        //p[0]为2^0
        p[0] = 1;
        for(int i = 1;i < n; i++ ) p[i] = p[i - 1] * 2 % mod;
        //给数组排序
        sort(nums.begin(),nums.end());
        int res = 0;
        //从前往后用双指针算法枚举
        for(int i = 0,j = n - 1;i < n;i++ ) {
            //j不能在i的前面-> i是最小值 不能选i前面的数
            while(j >= i && nums[i] + nums[j] > target) j--;
            if(j >= i && nums[i] + nums[j] <= target) {
                //满足要求记录答案 res加上2^j-i
                res = (res + p[j - i]) % mod; 
            }
        }
        return res;
    }
};

满足不等式的最大值

LeetCode 1496 - 1499

LeetCode 1496 - 1499

今天的文章LeetCode 1496 – 1499分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/63665.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注