LeetCode 探索：发散你的思维

[475] 供暖器

冬季已经来临。你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。

所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

说明:

给出的房屋和供暖器的数目是非负数且不会超过 25000。
给出的房屋和供暖器的位置均是非负数且不会超过10^9。
只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
所有供暖器都遵循你的半径标准，加热的半径也一样。

首先将houses和heaters两个数组排序，然后对每一个house，寻找一个离它最近的heater，再取每一个最近距离的最大值

/*
 * @lc app=leetcode.cn id=475 lang=cpp
 *
 * [475] 供暖器
 */

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

    int findRadius(vector<int> &houses, vector<int> &heaters)
    {
        sort(houses.begin(), houses.end());
        sort(heaters.begin(), heaters.end());
        int currMin = 0;
        int j = 0;
        for (int i = 0; i < houses.size(); i++)
        {
            while (j < heaters.size() && heaters[j] < houses[i])
            {
                j++;
            }
            if (j == 0)
            {
                int temp = heaters[j] - houses[i];
                currMin = max(currMin, temp);
            }
            else if (j < heaters.size())
            {
                int temp1 = houses[i] - heaters[j - 1];
                int temp2 = heaters[j] - houses[i];
                currMin = max(currMin, min(temp1, temp2));
            }
            else if (j == heaters.size())
            {
                int temp = abs(houses[i] - heaters[j - 1]);
                currMin = max(currMin, temp);
            }
        }
        return currMin;
    }

}; 
// @lc code=end

[476] 数字的补数

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

解题思路：获取每一位的值累加上去

/*
 * @lc app=leetcode.cn id=476 lang=cpp
 *
 * [476] 数字的补数
 */

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

    int findComplement(int num)
    {
        int res = 0;
        int n = 0;
        while (num)
        {
            res += !(num & 1) << n;
            num >>= 1;
            n++;
        }
        return res;
    }

}; 
// @lc code=end

[482] 密钥格式化

给定一个密钥字符串S，只包含字母，数字以及 ‘-‘（破折号）。N 个 ‘-‘ 将字符串分成了 N+1 组。给定一个数字 K，重新格式化字符串，除了第一个分组以外，每个分组要包含 K 个字符，第一个分组至少要包含 1 个字符。两个分组之间用 ‘-‘（破折号）隔开，并且将所有的小写字母转换为大写字母。

给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。

解题思路：从后往前遍历构造，最后将结果尾部的’-‘除去，然后将其反转

/*
 * @lc app=leetcode.cn id=482 lang=cpp
 *
 * [482] 密钥格式化
 */

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

    string licenseKeyFormatting(string S, int K)
    {
        string res = "";
        int count = 0;
        for (int i = S.length() - 1; i >= 0; i--)
        {
            if (count < K)
            {
                if (S[i] != '-')
                {
                    res += (isalpha(S[i]) != 0 ? char(toupper(S[i])) : char(S[i]));
                    count++;
                }
            }
            if (count == K)
            {
                res += "-";
                count = 0;
            }
        }
        while (!res.empty() && res.back() == '-')
        {
            res.pop_back();
        }
        reverse(res.begin(), res.end());
        return res;
    }

}; 
// @lc code=end

[485] 最大连续1的个数

给定一个二进制数组，计算其中最大连续1的个数。

解题思路：使用一个计数器来记录连续1的数量，若数量较大则更新

/*
 * @lc app=leetcode.cn id=485 lang=cpp
 *
 * [485] 最大连续1的个数
 */

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

    int findMaxConsecutiveOnes(vector<int> &nums)
    {
        int count=0;
        int countMax=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==1)
                count++;
            else
            {
                countMax = max(countMax,count);
                count=0;
            }
        }
        return max(countMax,count);
    }

}; 
// @lc code=end

[492] 构造矩形

作为一位web开发者，懂得怎样去规划一个页面的尺寸是很重要的。现给定一个具体的矩形页面面积，你的任务是设计一个长度为 L 和宽度为 W 且满足以下要求的矩形的页面。要求：

你设计的矩形页面必须等于给定的目标面积。
宽度 W 不应大于长度 L，换言之，要求 L >= W 。
长度 L 和宽度 W 之间的差距应当尽可能小。

你需要按顺序输出你设计的页面的长度 L 和宽度 W。

解题思路：从L = sqrt(area)开始，递减L，直到area % L == 0为止

/*
 * @lc app=leetcode.cn id=492 lang=cpp
 *
 * [492] 构造矩形
 */

// @lc code=start
class Solution
{
public:
    vector<int> constructRectangle(int area)
    {
        int w = sqrt(area);
        while (area % w != 0)
        {
            w--;
        }
        return vector<int>({area / w, w});
    }
};
// @lc code=end

[496] 下一个更大元素 I

给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。

解题思路：使用单调栈

将元素入栈

当栈不为空时，若将要入栈的元素大于栈顶的元素，则将栈顶元素出栈，并将其(top, num[i])加入哈希表中，直到栈顶元素大于等于入栈元素，或栈为空时退出。

若将要入栈的元素小于栈顶的元素，则简单将其入栈

当数组的元素全部入栈后，若此时栈不为空，则将栈顶元素出栈，并将(top, -1)加入哈希表。

/*
 * @lc app=leetcode.cn id=496 lang=cpp
 *
 * [496] 下一个更大元素 I
 */

// @lc code=start
class Solution
{
public:
    vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2)
    {
        map<int, int> table;
        stack<int> stacks;
        vector<int> res;
        for (int i = 0; i < nums2.size(); i++)
        {
            while (!stacks.empty() && nums2[i] > stacks.top())
            {
                table.insert(make_pair(stacks.top(), nums2[i]));
                stacks.pop();
            }
            stacks.push(nums2[i]);
        }
        while (!stacks.empty())
        {
            table.insert(make_pair(stacks.top(), -1));
            stacks.pop();
        }
        for (int i = 0; i < nums1.size(); i++)
        {
            res.push_back(table[nums1[i]]);
        }
        return res;
    }
};
// @lc code=end

[500] 键盘行

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

解题思路：对每一个单词的每一个字母都进行判断在哪一行，若同一个单词在不同行有字母，则退出循环，并判断

/*
 * @lc app=leetcode.cn id=500 lang=cpp
 *
 * [500] 键盘行
 */

// @lc code=start
class Solution
{
public:
    vector<string> findWords(vector<string> &words)
    {
        string patterns[3] = {"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"};
        vector<string> res;
        for (string word : words)
        {
            int flag[3] = {0};
            for (char c : word)
            {
                for (int i = 0; i < 3; i++)
                {
                    if (patterns[i].find(c) != string::npos)
                        flag[i] = 1;
                }
                if (flag[0] + flag[1] + flag[2] > 1)
                    break;
            }
            if (flag[0] + flag[1] + flag[2] == 1)
                res.push_back(word);
        }
        return res;
    }
};
// @lc code=end

[501] 二叉搜索树中的众数

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

解题思路：递归，记录父节点的值，再与子节点的值进行比较

/*
 * @lc app=leetcode.cn id=501 lang=cpp
 *
 * [501] 二叉搜索树中的众数
 */

// @lc code=start
/**
 * 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:
    vector<int> res;
    int maxCount = 0;
    int count = 0;
    TreeNode *pre;

    void travel(TreeNode *root)
    {
        if (root == NULL)
            return;
        travel(root->left);
        if (pre != NULL && pre->val == root->val)
            count++;
        else
            count = 1;
        if (count == maxCount)
            res.push_back(root->val);
        else if (count > maxCount)
        {
            maxCount = count;
            res.clear();
            res.push_back(root->val);
        }
        pre = root;
        travel(root->right);
    }

    vector<int> findMode(TreeNode *root)
    {
        travel(root);
        return res;
    }
};
// @lc code=end

解题思路：使用Hash-table，注意遍历的时候不要使用下标，要使用迭代器

class Solution
{
public:
    void travel(TreeNode *root, map<int, int> &table)
    {
        if (root == NULL)
            return;
        travel(root->left, table);
        table[root->val]++;
        travel(root->right, table);
    }

    vector<int> findMode(TreeNode *root)
    {
        map<int, int> table;
        travel(root, table);
        vector<int> res;
        int M = 0;
        for (auto i = table.begin(); i != table.end(); i++)
        {
            M = max(M, i->second);
        }
        for (auto i = table.begin(); i != table.end(); i++)
        {
            if (i->second == M)
                res.push_back(i->first);
        }
        return res;
    }
};

[504] 七进制数

给定一个整数，将其转化为7进制，并以字符串形式输出。

解题思路：将负数换成正数处理，同时需要单独处理0的情况

/*
 * @lc app=leetcode.cn id=504 lang=cpp
 *
 * [504] 七进制数
 */

// @lc code=start
class Solution
{
public:
    string convertToBase7(int num)
    {
        if (num == 0)
            return "0";
        string str = "";
        int n = num;
        if (num < 0)
        {
            n = -num;
        }
        while (n != 0)
        {
            str += to_string(n % 7);
            n /= 7;
        }
        reverse(str.begin(), str.end());
        return num > 0 ? str : "-" + str;
    }
};
// @lc code=end

[506] 相对名次

给出 N 名运动员的成绩，找出他们的相对名次并授予前三名对应的奖牌。前三名运动员将会被分别授予 “金牌”，“银牌” 和“ 铜牌”（”Gold Medal”, “Silver Medal”, “Bronze Medal”）。

(注：分数越高的选手，排名越靠前。)

解题思路：使用map的有序特性

/*
 * @lc app=leetcode.cn id=506 lang=cpp
 *
 * [506] 相对名次
 */

// @lc code=start
class Solution
{
public:
    static bool compare(const int &n, const int &m)
    {
        return n > m;
    }

    vector<string> findRelativeRanks(vector<int> &nums)
    {
        int size = nums.size();
        vector<string> res(size);
        map<int, int> table;
        for (int i = 0; i < nums.size(); i++)
            table[nums[i]] = i;
        for (auto i = table.begin(); i != table.end(); i++)
        {
            if (size == 1)
                res[i->second] = "Gold Medal";
            else if (size == 2)
                res[i->second] = "Silver Medal";
            else if (size == 3)
                res[i->second] = "Bronze Medal";
            else
                res[i->second] = to_string(size);
            size--;
        }
        return res;
    }
};
// @lc code=end