[LeetCode] 822. Card Flipping Game

Description

On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).

We flip any number of cards, and after we choose one card.

If the number X on the back of the chosen card is not on the front of any card, then this number X is good.

What is the smallest number that is good? If no number is good, output 0.

Here, fronts[i] and backs[i] represent the number on the front and back of card i.

A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.

Example:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]

Output: 2

Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3].

We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.

Note:

1 <= fronts.length == backs.length <= 1000.
1 <= fronts[i] <= 2000.
1 <= backs[i] <= 2000.

Analyse

桌子上有N张牌，正反面都印有正整数

可以翻转任意张牌，然后选一张牌，如果这张牌背面的数字X在牌的正面没有，这个数字X就是要输出的答案

一张牌的正反面如果是同一个数字，那这个数字肯定不是答案，这个例子里的1，4就不可能是答案，在剩下的元素中输出最小的那个

fronts = [1,2,4,4,7]

backs  = [1,3,4,1,3]

写出的第一个版本

bool isExist(int value, vector<int>& vec)

{

    vector<int>::iterator it = find(vec.begin(), vec.end(), value);

    if (it != vec.end())

    {

        return true;

    }

    return false;

}

int flipgame(vector<int>& fronts, vector<int>& backs) {

    int min = 2001;

    int tmp;

    vector<int> intersect = {};

    for (int i = 0; i < fronts.size(); i++)

    {

        if (fronts[i] == backs[i])

        {

            intersect.push_back(fronts[i]);

            continue;

        }

    }

    for (int i = 0; i < fronts.size(); i++)

    {

        if (!isExist(fronts[i], intersect))

        {

            tmp = fronts[i] <

            if (isExist(backs[i], intersect))

            {

                continue;

            }

            else

            {

                tmp = backs[i];

            }

        }

        else

        {

            if (isExist(backs[i], intersect))

            {

                tmp = fronts[i];

            }

            else

            {

                tmp = fronts[i] < backs[i] ? fronts[i] : backs[i];

            }

        }

        min = min < tmp ? min : tmp;

    }

    return min == 2001 ? 0 : min;

}

把代码简化一下

bool isExist(int value, vector<int>& vec)

{

    vector<int>::iterator it = find(vec.begin(), vec.end(), value);

    if (it != vec.end())

    {

        return true;

    }

    return false;

}

int flipgame(vector<int>& fronts, vector<int>& backs) {

    int min = 2001;

    int tmp;

    vector<int> intersect = {};

    for (int i = 0; i < fronts.size(); i++)

    {

        if (fronts[i] == backs[i])

        {

            intersect.push_back(fronts[i]);

            continue;

        }

    }

    for (int i = 0; i < fronts.size(); i++)

    {

        if (!isExist(fronts[i], intersect))

        {

            tmp = fronts[i] <

            if (isExist(backs[i], intersect))

            {

                continue;

            }

            else

            {

                tmp = backs[i];

            }

        }

        else

        {

            if (isExist(backs[i], intersect))

            {

                tmp = fronts[i];

            }

            else

            {

                tmp = fronts[i] < backs[i] ? fronts[i] : backs[i];

            }

        }

        min = min < tmp ? min : tmp;

    }

    return min == 2001 ? 0 : min;

}

继续优化，把vector换成unordered_set，在LeetCode上就会有巨大的提升

int flipgame(vector<int>& fronts, vector<int>& backs) {

    int min = 2001;

    int tmp;

    unordered_set<int> intersect = {};

    for (int i = 0; i < fronts.size(); i++)

    {

        if (fronts[i] == backs[i])

        {

            intersect.insert(fronts[i]);

            continue;

        }

    }

    for (int i = 0; i < fronts.size(); i++)

    {

        if (intersect.count(fronts[i]) == 0)

        {

            min = min < fronts[i] ? min : fronts[i];

        }

        if (intersect.count(backs[i]) == 0)

        {

            min = min < backs[i] ? min : backs[i];

        }

    }

    return min == 2001 ? 0 : min;

}

看看LeetCode上评价最高的版本

思路是差不多的，改成了用数组存储，有点bitmap的思想，

int flipgame(vector<int>& fronts, vector<int>& backs) {

    int res[2002] = {0};  // -1: bad. 1:exist.

    for (int i = 0; i < fronts.size(); i++)

    {

        if (fronts[i] == backs[i])

        {

            res[fronts[i]] = -1;

        }

        else

        {

            if (res[fronts[i]] != -1)

                res[fronts[i]] = 1;

            if (res[backs[i]] != -1)

                res[backs[i]] = 1;

        }

    }

    for (int i = 0; i < 2002; i++)

    {

        if (res[i] == 1)

            return i;

    }

    return 0;

}

比如

fronts = [1,2,4,4,7]

backs  = [1,3,4,1,3]

res[1] = -1;

res[2] = 1;

res[3] = 1;

res[4] = -1;

res[7] = 1;

for循环的时候从index小的开始，遇到的第一个值为1的就是要找的值

巴特西

[LeetCode] 822. Card Flipping Game

Description

Analyse

Reference

最新文章

热门文章