【刷题】力扣每日一题： 381、2300、765

前言

本篇文章用于记录在做力扣每日一题的时候遇到的一些知识点以及自己的思路

381

题干

题目链接

我的思路及做题过程

思路1

我的想法是记录每个字符串的字母出现个数然后比较两个字符串是否有字母同时出现

class Solution {
public:
    int judge(string s1, string s2, int l1, int l2) {
        int n1[30] = { 0 }, n2[30] = { 0 };

        for (int i = 0; i < l1; i++) {
            n1[s1[i] - 97]++;
        }
        for (int i = 0; i < l2; i++) {
            n2[s2[i] - 97]++;
        }
        for (int i = 0; i < 26; i++) {
            if (n1[i] * n2[i] > 0) {
                return 0;
            }
        }
        return l1 * l2;
    }

    int maxProduct(vector<string>& words) {
        for (int i = 0; i < words.size(); i++) {
            for (int j = 0; j < words.size(); j++) {
                le = judge(words[i], words[j], words[i].size(), words[j].size());

                if (le > max) {
                    max = le;
                }
            }
        }
        return max;
    }
private:
    int num[1010], le, max = 0;
};

re了我写的时候就感觉它会re

优化1

judge函数没必要去记录字母出现个数直接两两比较如果相等直接返回0即可

    int judge(string s1, string s2, int l1, int l2) {
        for (int i = 0; i < l1; i++){
            for (int j = 0; j < l2; j++) {
                if (s1[i] == s2[j]){
                    return 0;
                }
            }
        }
        return l1 * l2;
    }

优化2

maxProduct函数中for循环的范围可以修改一下（比较简单的优化方式）
j的范围变为

            for (int j = i + 1; j < words.size(); j++) {

优化3

数据比较大的时候每次调用judge函数都需要比较长的运行时间
我们可以进一步缩小使用judge函数的范围

当l1*l2>max的时候再去进行一一比较

最终代码

class Solution {
public:
    int judge(string s1, string s2, int l1, int l2, int max) {
        if(l1 * l2 > max){
            for (int i = 0; i < l1; i++) {
                for (int j = 0; j < l2; j++) {
                    if (s1[i] == s2[j]) {
                        return 0;
                    }
                }
            }
            return l1 * l2;
        }
        return 0;
    }

    int maxProduct(vector<string>& words) {

        for (int i = 0; i < words.size(); i++) {
            for (int j = i + 1; j < words.size(); j++) {
                le = judge(words[i], words[j], words[i].size(), words[j].size(), max);
                if(le){
                    max = le;
                }
            }
        }
        return max;
    }
private:
    int num[1010], le, max = 0;
};

题解中的其他做法

位运算

跟我的思路一有一些相同之处：统计每个字母出现次数
不同的是它使用了位运算
移位操作符、按位或和 &

先计算出每个单词中有什么字母出现（数组的映射 不再解释了）左移一位
之后与原数值进行按位或

                masks[i] |= 1 << (word[j] - 'a');

最后将两个数组中的值进行按位与为0 就与max进行比较
（位运算太妙了

还有用哈希表进行优化的（我是蒟蒻我不会呜呜呜呜呜呜呜呜呜

2300

题干

题目链接

我的思路及做题过程

思路1

第一遍写的时候
我直接两个for循环遍历了一下

re了很正常 ~~毕竟是中等题~~

思路2

用二分法 和 双指针
先用sort排序之后再利用双指针逐渐缩小范围减少程序运行时间

二分法部分的代码

int le = 0, ri = po.size() - 1, mid;
while (le <= ri)
{
	mid = (le + ri) / 2;
	
	a = sp[i], b = po[mid];
	
	if (a * b < su)
	{
	    le = mid + 1;
	}
	else
	{
	    ri = mid - 1;
	}
}

最终代码

class Solution {
public:
    vector<int> successfulPairs(vector<int>& sp, vector<int>& po, long long su) {
        sort(po.begin(), po.end());

        for (int i = 0; i < sp.size(); i++)
        {
            int le = 0, ri = po.size() - 1, mid;
            while (le <= ri)
            {
                //mid = le + (ri - le) >> 1;
                mid = (le + ri) / 2;

                a = sp[i], b = po[mid];

                if (a * b < su)
                {
                    le = mid + 1;
                }
                else
                {
                    ri = mid - 1;
                }
            }
            pairs.push_back(po.size() - le);
        }
        return pairs;
    }

private:
    vector<int>pairs;
    long long a, b, c;
};

注意点

在学习二分算法的时候我们肯定都接触过位运算并且知道位运算比乘除法要快
那在这道题中我们可不可以用位运算呢大家可以试一下
下面提供一下我调试时的代码

class Solution {
public:
    vector<int> successfulPairs(vector<int>& sp, vector<int>& po, long long su) {
        sort(po.begin(), po.end());

        for (int i = 0; i < sp.size(); i++)
        {
            int le = 0, ri = po.size() - 1, mid;
            while (le <= ri)
            {
                mid = le + (ri - le) >> 1;
                a = sp[i], b = po[mid];

                if (a * b < su)
                {
                    le = mid + 1;
                }
                else
                {
                    ri = mid - 1;
                }
            }
            pairs.push_back(po.size() - 1);
        }
        return pairs;
    }

private:
    vector<int>pairs;
    int flag = 1;
    long long x = 0;
    long long a, b, c;
};


int main() {
    Solution s1;
    vector<int>po, sp;
    po.push_back(1);
    po.push_back(2);
    po.push_back(3);
    po.push_back(4);
    po.push_back(5);
    sp.push_back(5);
    sp.push_back(1);
    sp.push_back(3);
    s1.successfulPairs(sp, po, 7);

    return 0;
}

答案是不可以会陷入死循环

分析

我们先循环两次变成下面这种情况
在这里插入图片描述

接下来关键的要来了
我们来到第三次循环遇到了这条语句

mid = left + (right - left) >>1;

那么(right - left)此时是 1-1 为0
0>>1仍未0
接下来进入if的第一种情况

left = mid + 1;

left = 1

第四次循环中与第三次循环情况相同
所以陷入了死循环

而

mid = (le + ri) / 2;

不会死循环因为1+1/2 == 1

题解中的其他做法

我看到官解中虽然思路和我写的差不多但是他用到了新的知识
upper_bound函数它返回一个迭代器，指向在排序序列中第一个大于或等于给定值的元素。如果不存在大于或等于给定值的元素，则返回序列的尾迭代器。

lower_bound和upper_bound的区别是后者返回的是大于给定值的元素的迭代器
前者返回的是大于等于给定值元素的迭代器

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

765

温馨提示

下面是我写着玩的能过纯粹是~~数据量小~~
所以下面的题解也不具有参考性

题干

题目链接

我的思路及做题过程

第一遍代码

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        for (int i = 1; i < row.size(); i++) {
            if (!(abs(row[i - 1] - row[i]) == 1)) {
                for (int j = i; j < row.size(); j++) {
                    if ((abs(row[j] - row[i]) == 1)) {
                        swap(row[j], row[i]);
                        num++;
                        break;
                    }
                }
            }
        }
        return num;
    }
private:
    int num = 0;
};

~~惨不忍睹~~

问题

我找出来了两个问题

1. for循环
我因为担心越界所以把范围写成1~n-1

但实际上可以一对一对的去判断（并且题目已经说明row的长度是偶数）即i += 2

2. if语句
if语句的判断条件有问题
不能用取绝对值的方法因为2 和 3不是一对但绝对值是1 这不符合题意
可以通过判断奇偶性来进行加一或者减一

修改之后的代码

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        for (int i = 0; i < row.size(); i += 2) {
            if (((row[i] % 2 == 0) ? row[i] + 1 : row[i] - 1) != row[i + 1]) {
                for (int j = i + 2; j < row.size(); j++) {
                    if (((row[i] % 2 == 0) ? row[i] + 1 : row[i] - 1) == row[j]) {
                        swap(row[j], row[i + 1]);
                        num++;
                    }
                }
            }
        }
        return num;
    }
private:
    int num = 0;
};

题解中的其他做法

官解中的并查集和bfs我都不会所以没仔细看
我在其他的题解中看到了一种做法 利用异或

以下代码转自
这个博主的解法

简单来说就是 2和3这一对情侣通过与1异或可以得到另一半（又是美妙的位运算）

class Solution {
public:
    //参考大佬的异或，2与1异或得到3，3与1异或得到2；也就是说每一对只要异或就能得到彼此的“另一半”，只要找到并交换就行
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        int cnt = 0;
    
        for(int i = 0; i < n - 1; i++){
            int x = row[i];   //某个人
            int y = x ^ 1;  //他的另一半

            if(row[i + 1] != y){  //情侣不挨着,就往后搜
                for(int k = i + 2; k < n; k++){
                    if(row[k] == y){
                        //找到了另一半,交换
                        int temp = row[i + 1];
                        row[i + 1] = row[k];
                        row[k] = temp;
                        cnt++;
                        break;   //找到就退回上一层循环，判断下一对是不是情侣坐一起
                    }
                }
            }
        }
        return cnt;
    }
};