快捷導(dǎo)航

Go語言題解LeetCode888公平糖果交換示例詳解

更新時(shí)間：2022年12月28日 14:13:12 作者：劉09k11

這篇文章主要為大家介紹了Go語言題解LeetCode888公平糖果交換示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

一描述

888. 公平的糖果交換 - 力扣（LeetCode） (leetcode-cn.com)

愛麗絲和鮑勃擁有不同總數(shù)量的糖果。給你兩個(gè)數(shù)組 aliceSizes 和 bobSizes ，aliceSizes[i] 是愛麗絲擁有的第 i 盒糖果中的糖果數(shù)量，bobSizes[j] 是鮑勃擁有的第 j 盒糖果中的糖果數(shù)量。

兩人想要互相交換一盒糖果，這樣在交換之后，他們就可以擁有相同總數(shù)量的糖果。一個(gè)人擁有的糖果總數(shù)量是他們每盒糖果數(shù)量的總和。

返回一個(gè)整數(shù)數(shù)組 answer，其中 answer[0] 是愛麗絲必須交換的糖果盒中的糖果的數(shù)目，answer[1] 是鮑勃必須交換的糖果盒中的糖果的數(shù)目。如果存在多個(gè)答案，你可以返回其中 任何一個(gè) 。題目測試用例保證存在與輸入對應(yīng)的答案。

示例 1：

輸入：aliceSizes = [1,1], bobSizes = [2,2]
輸出：[1,2]

示例 2：

輸入：aliceSizes = [1,2], bobSizes = [2,3]
輸出：[1,2]

示例 3：

輸入：aliceSizes = [2], bobSizes = [1,3]
輸出：[2,3]

示例 4：

輸入：aliceSizes = [1,2,5], bobSizes = [2,4]
輸出：[5,4]

提示：

1 <= aliceSizes.length, bobSizes.length <= 10^4

1 <= aliceSizes[i], bobSizes[j] <= 10^5

愛麗絲和鮑勃的糖果總數(shù)量不同。

題目數(shù)據(jù)保證對于給定的輸入至少存在一個(gè)有效答案。

二分析

計(jì)算若A與B相同時(shí)，A所需要的糖果大小，遍歷B，尋找該糖果

首先計(jì)算A與B的糖果總和
A與B相等所需要的糖果差值是(sum_B-sum_a)/2
構(gòu)建哈希表，哈希表為A的每個(gè)元素，加上2的差值
遍歷B，尋找B中是否有某一糖果與哈希表某一數(shù)值相等
輸出數(shù)值

三答案

class Solution {
public:
    vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
        int sum_A=0;//1 首先計(jì)算A與B的糖果總和
        int sum_B=0;
        for(auto a:A)
        {
            sum_A=sum_A+a;
        }
        for(auto b:B)
        {
            sum_B=sum_B+b;
        }
        unordered_map<int,int> map;//2 A與B相等所需要的糖果差值是(sum_B-sum_a)/2
        for(auto a:A)//3 構(gòu)建哈希表，哈希表為A的每個(gè)元素，加上2的差值
        {
            map[a+(sum_B-sum_A)/2];
        }
        for(auto b:B)//4 遍歷B，尋找B中是否有某一糖果與哈希表某一數(shù)值相等
        {
            if(map.find(b)!=map.end())
            {
                return{b+(sum_A-sum_B)/2,b};//5 輸出數(shù)值
            }
        }
        return {};
    }
};

以上就是Go語言題解LeetCode888公平糖果交換示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go題解公平糖果交換的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: