leetcode weekly contest 43

leetcode649. Dota2 Senate

leetcode649.Dota2 Senate

思路：

模拟规则round by round。

class Solution {

public:

    string predictPartyVictory(string senate) {

        int len = senate.size();

        int r = 0;

        int d = 0;

        int i = 0;

        while(1)

        {

            if(senate[i] == 'R')

            {

                int j = 1;

                while(senate[(i + j) % len] != 'D' && j < len) j++;

                if(senate[(i + j) % len] == 'R') return "Radiant";

                else senate[(i + j) % len] = '#';

            }

            else if(senate[i] == 'D')

            {

                int j = 1;

                while(senate[(i + j) % len] != 'R' && j < len) j++;

                if(senate[(i + j) % len] == 'D') return "Dire";

                else senate[(i + j) % len] = '#';

            }

            i = (i + 1) % len;

        }

    }

};

leetcode650. 2 Keys Keyboard

思路：

找到最大的约数，dp。

注意copy算一步。

class Solution {

public:

    int find(int x)

    {

        for(int i = 2; i <= sqrt(x); i++)

        {

            if(x % i == 0) return i;

        }

        return x;

    }

    int minSteps(int n) {

        vector<int> res(n + 1, 0);

        int temp;

        for(int i = 2; i <= n; i++)

        {

            temp = find(i);

            res[i] = res[i / temp] + temp;

        }

        return res[n];

    }

};

leetcode651. 4 Keys Keyboard

思路：

dp.

res[n] = max{res[n - 1] + 1, res[n - 5] * 4, res[n - 4] * 3, res[n - 3] * 2};

时间O(n),空间O(1)

class Solution {

public:

    int maxA(int N) {

        //vector<int> res(N + 1);

        int four,three,two,one,five,res;

        five = four = three = two = one = res = 0;

        for(int i = 1; i <= N; i++)

        {

            res = max(one + 1,max(four * 3, max(three * 2,five * 4)));

            five = four;

            four = three;

            three = two;

            two = one;

            one = res;

        }

        return res;

    }

};

leetcode652. Find Duplicate Subtrees

思路：

这个思路我感觉特别地棒。既然是找duplicates，可以直接用map。吧树给serialize了变成一个string，让map自己比较。然后找到全部的duplicates。

时间O(n)

/**

 * 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:

    unordered_map<string,vector<TreeNode*> > map;

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {

        vector<TreeNode*> res;

        serialize(root);

        unordered_map<string,vector<TreeNode*>>::iterator it = map.begin();

        while(it != map.end())

        {

            if(it->second.size() > 1 && it->first != "")

            {

                res.push_back(it->second[0]);

            }

            it++;

        }

        return res;

    }

private:

    string serialize(TreeNode* root)

    {

        if(!root) return "";

        string s = '(' + serialize(root->left) + to_string(root->val) + serialize(root->right) + ')';

        map[s].push_back(root);

        return s;

    }

};

巴特西

leetcode weekly contest 43

leetcode weekly contest 43

leetcode649. Dota2 Senate

leetcode649.Dota2 Senate

思路：

leetcode650. 2 Keys Keyboard

leetcode650. 2 Keys Keyboard

思路：

leetcode651. 4 Keys Keyboard

leetcode651. 4 Keys Keyboard

思路：

leetcode652. Find Duplicate Subtrees

leetcode652. Find Duplicate Subtrees

思路：

最新文章

热门文章