天池开发者1024编程battle赛

Michael阿明

发布于 2021-02-19 12:41:05

2840

发布于 2021-02-19 12:41:05

部分题目如下：

1.笛卡尔积

描述我们采用二维数组setList[][]表示集合数组，其中setList[i]中的每个元素都为整数，且不相同。求集合setList[0],setList[1],…,setList[setList.length - 1]的笛卡尔积。一般地，集合A和集合B的笛卡尔积A×B = {(x,y)|x∈A∧y∈B}。

1 <= setList.length <= 5 1 <= setList[i].length <= 5

示例

样例1
输入:
setList = [[1,2,3],[4],[5,6]]
输出: [[1,4,5],[1,4,6],[2,4,5],[2,4,6],[3,4,5],[3,4,6]]
解释:
[1,2,3]和[4]和[5,6]的笛卡尔积为
[[1,4,5],[1,4,6],[2,4,5],[2,4,6],[3,4,5],[3,4,6]]

样例2
输入:
setList = [[1,2,3],[4]]
输出: [[1,4],[2,4],[3,4]]
解释:
[1,2,3]和[4]的笛卡尔积为[[1,4],[2,4],[3,4]]

解题：

回溯

class Solution {
public:
    /**
     * @param setList: The input set list
     * @return: the cartesian product of the set list
     */
    vector<vector<int>> ans;
    vector<int> lv;
    vector<vector<int>> getSet(vector<vector<int>> &setList) {
        // Write your code here
        dfs(setList, 0);
        return ans;
    }
    void dfs(vector<vector<int>> &setList, int i)
    {
        if(i == setList.size())
        {
            ans.push_back(lv);
            return;
        }
        for(int j = 0; j < setList[i].size(); j++)
        {
            lv.push_back(setList[i][j]);
            dfs(setList, i+1);
            lv.pop_back();
        }
    }
};

3.数字消除

描述给定一个数字构成的字符串，如果连着两个数字都相同，则可以消除，消除后前部分和后部分会连在一起，可以继续进行消除，现在问你能消除几次？

示例
Example 1:
Input: "43211234"
Output: 4

Example 2:
Input: "101"
Output: 0

栈解题

class Solution {
public:
    /**
     * @param Numbers: a string of Numbers
     * @return: returns the number of eliminations
     */
    int NumberOfErasures(string &Numbers) {
        // write your code here.
        stack<char> s;
        int ans = 0;
        for(int i = 0; i < Numbers.size(); i++)
        {
            if(s.empty() || s.top() != Numbers[i])
            {
                s.push(Numbers[i]);
            }
            else
            {
                s.pop();
                ans++;
            }
        }
        return ans;
    }
};

4.连接两个字符串中的不同字符

描述给出两个字符串, 你需要修改第一个字符串，将所有与第二个字符串中相同的字符删除, 并且第二个字符串中不同的字符与第一个字符串的不同字符连接

示例

样例 1:
输入 : s1 = "aacdb", s2 = "gafd"
输出 : "cbgf"

样例 2:
输入 : "abcs", s2 = "cxzca"
输出 : "bsxz"

解题：

按题意来即可

class Solution {
public:
    /**
     * @param s1: the 1st string
     * @param s2: the 2nd string
     * @return: uncommon characters of given strings
     */
    string concatenetedString(string &s1, string &s2) {
        // write your code here
        unordered_set<char> set1(s1.begin(), s1.end());
        unordered_set<char> set2(s2.begin(), s2.end());
        string ans;
        for(char c : s1)
        {
            if(set2.count(c))
                continue;
            else
                ans += c;
        }
        for(char c : s2)
        {
            if(set1.count(c))
                continue;
            else
                ans += c;
        }
        return ans;
    }
};

3.数组划分

描述给一个有 2n 个整数的数组，你的任务是把这些整数分成 n 组，如(a1, b1)，(a2, b2)，…，(an, bn)。并且使得 i 从 1 到 n 的 min(ai, bi)之和尽可能的大。

n 是一个正整数，且范围为 [1, 10000]. 数组中的元素范围为[-10000, 10000]。

示例
样例1:
输入: [1,4,3,2]
输出: 4
解释: n 是 2, 最大的数对和为 4 = min(1, 2) + min(3, 4).

样例 2:
输入: [5,6]
输出: 5
解释: n 是 1, 最大的数对和为 5 = min(5, 6) .

解题：

排序后，取两两较小的

class Solution {
public:
    /**
     * @param nums: an array
     * @return: the sum of min(ai, bi) for all i from 1 to n
     */
    int arrayPairSum(vector<int> &nums) {
        // Write your code here
        sort(nums.begin(),nums.end());
        int ans = 0, i = 0;
        for( ; i < nums.size(); i+=2)
            ans += nums[i];
        return ans;
    }
};

还有几题是LeetCode上的原题

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/10/24 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度