leetcode349-387

LeetCode 探索：发散你的思维

[349] 两个数组的交集

描述：给定两个数组，编写一个函数来计算它们的交集。

解题思路：使用哈希表

/*
 * @lc app=leetcode.cn id=349 lang=cpp
 *
 * [349] 两个数组的交集
 */

// @lc code=start
class Solution
{
public:

    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        set<int> s1;
        set<int> s2;
        for (int i = 0; i < nums1.size(); i++)
        {
            s1.insert(nums1[i]);
        }
        for (int i = 0; i < nums2.size(); i++)
        {
            s2.insert(nums2[i]);
        }
        if (s1.size() < s2.size())
        {
            swap(s1, s2);
        }
        vector<int> res;
        for (int n : s2)
        {
            if (s1.count(n) != 0)
                res.push_back(n);
        }
        return res;
    }

}; 
// @lc code=end

[350] 两个数组的交集Ⅱ

描述：给定两个数组，编写一个函数来计算它们的交集。

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

解题思路：使用哈希表

/*
 * @lc app=leetcode.cn id=350 lang=cpp
 *
 * [350] 两个数组的交集 II
 */

// @lc code=start
class Solution
{
public:

    vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
    {
        if (nums1.size() > nums2.size())
            swap(nums1, nums2);
        map<int, int> table;
        vector<int> res;
        for (int n : nums1)
        {
            table[n]++;
        }
        for (int n : nums2)
        {
            if (table[n] > 0)
            {
                res.push_back(n);
                table[n]--;
            }
        }
        return res;
    }

}; 
// @lc code=end

[367] 有效的完全平方数

描述：给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

二分查找

解题思路：

• 将left设置为2，right设置为num / 2
• 当left <= right时，mid = (left + right) / 2
• 比较square = mid * mid与num的大小

• 当square比num小时，left = mid + 1
• 当square比num大时，right = mid - 1
• 否则，返回true

• 当循环退出时，返回false

/*
 * @lc app=leetcode.cn id=367 lang=cpp
 *
 * [367] 有效的完全平方数
 */

// @lc code=start
class Solution
{
public:

    bool isPerfectSquare(int num)
    {
        if (num < 2)
            return true;
        int left = 2;
        int right = num / 2;
        while (left <= right)
        {
            long mid = (left + right) / 2;
            if (mid * mid > num)
                right = mid - 1;
            else if (mid * mid < num)
                left = mid + 1;
            else
                return true;
        }
        return false;
    }

}; 
// @lc code=end

[371] 两数之和

不使用运算符 + 和 - ​​​​​​​，计算两整数 ​​​​​​​a 、b ​​​​​​​之和。

解题思路：使用位运算和与运算

/*
 * @lc app=leetcode.cn id=371 lang=cpp
 *
 * [371] 两整数之和
 */

// @lc code=start
class Solution
{
public:

    int getSum(int a, int b)
    {
        return b == 0 ? a : getSum(a ^ b, ((unsigned int)a & b) << 1);
    }

}; 
// @lc code=end

[374] 猜数字大小

我们正在玩一个猜数字游戏。 游戏规则如下：
我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1(小)，1(大) 或 0(猜对了)）

解题思路：二分查找

/*
 * @lc app=leetcode.cn id=374 lang=cpp
 *
 * [374] 猜数字大小
 */

// @lc code=start
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num); 

class Solution
{
public:

    //二分查找
    int guessNumber(int n)
    {
        long left = 1;
        long right = n;
        while (left <= right)
        {
            long mid = (left + right) / 2;
            if (guess(mid) == 1)
                left = mid + 1;
            else if (guess(mid) == -1)
                right = mid - 1;
            else
                return mid;
        }
        return left;
    }

}; 
// @lc code=end

[383] 赎金信

描述：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。)

解题思路：使用哈希表

/*
 * @lc app=leetcode.cn id=383 lang=cpp
 *
 * [383] 赎金信
 */

// @lc code=start
class Solution
{
public:

    bool canConstruct(string ransomNote, string magazine)
    {
        if (ransomNote.length() > magazine.size())
            return false;
        int maga[128] = {0};
        for (int i = 0; i < magazine.length(); i++)
        {
            maga[magazine[i]]++;
        }
        for (int i = 0; i < ransomNote.length(); i++)
        {
            if (!maga[ransomNote[i]]--)
                return false;
        }
        return true;
    }

}; 
// @lc code=end

[387] 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

解题思路：使用哈希表

/*
 * @lc app=leetcode.cn id=387 lang=cpp
 *
 * [387] 字符串中的第一个唯一字符
 */

// @lc code=start
class Solution
{
public:

    int firstUniqChar(string s)
    {
        int table[128] = {0};
        for (int i = 0; i < s.length(); i++)
        {
            table[s[i]]++;
        }
        for (int i = 0; i < s.length(); i++)
        {
            if (table[s[i]] == 1)
                return i;
        }
        return -1;
    }

}; 
// @lc code=end