Leetcode Hacking Practice -- Solution in C++ Part 3 (发表于9年前)

webdriver

LeetCode (used to call i has 1337 code) is a social platform for preparing IT technical interviews. We strive to provide you with the best learning experience in preparing interviews for companies in the IT industry.

To be successful in a technical interview, we believe it is mainly repeating these three important steps:

Code. Read. Discuss.

We strive to provide you the LeetCode platform as the ultimate solution for preparing technical interviews.

1. Code -&gt; Code solution using the Online Judge system.
2. Read -&gt; Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -&gt; Discuss your thoughts about the problem with other LeetCoders.

We hope that through our platform, you will grow into a LeetCoder. Not only will you be successful in all of your interviews, and most importantly, you will be a better coder in general !

This is Part 3 （第三部分）

第一部分： www.westca.com/Forums/...inese.html
第二部分： www.westca.com/Forums/...inese.html

webdriver

Problem Name: Path Sum 2
Description:
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]

webdriver

Now comes the solution (in C++) ...

DFS.

代码:




/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<vector<int> > pathSum(TreeNode *root, int sum) {

        vector<vector<int>> res;

        vector<int> path;

        pathSumRe(root, sum, res, path);

        return res;

    }

    void pathSumRe(TreeNode *root, int sum, vector<vector<int>> &res, vector<int> &path)

    {

        if (!root) return;

        if (!root->left && !root->right)

        {

            if (sum == root->val)

            {

                path.push_back(root->val);

                res.push_back(path);

                path.pop_back();

            }

            return;

        }

        path.push_back(root->val);

        pathSumRe(root->left, sum - root->val, res, path);

        pathSumRe(root->right, sum - root->val, res, path);

        path.pop_back();

    }

};

webdriver

Problem Name: Permutations
Description:
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

webdriver

Now comes the solution (in C++) ...

dfs...

代码:




class Solution {

public:

    vector<vector<int>> res;



    vector<vector<int>> permute(vector<int> &num) {

        res.clear();

        vector<bool> avail(num.size(), true);

        vector<int> pum;

        permuteRe(num, avail, pum);

        return res;

    }



    void permuteRe(const vector<int> &num, vector<bool> &avail, vector<int> &pum)

    {

        if (pum.size() == num.size())

        {

            res.push_back(pum);

            return;

        }

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

        {

            if (avail[i])

            {

                avail[i] = false;

                pum.push_back(num[i]);

                permuteRe(num, avail, pum);

                pum.pop_back();

                avail[i] = true;

            }

        }

    }

};

webdriver

Now comes the solution (in C++) ...

...

代码:




class Solution {

public:

    string getPermutation(int n, int k) {

        string num, res;

        int total = 1;

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

        {

            num.push_back(i + '0');

            total *= i;

        }

        k--;

        while (n)

        {

            total /= n;

            int i = k / total;

            k %= total;

            res.push_back(num[i]);

            num.erase(i, 1);

            n--;

        }

        return res;

    }

};

webdriver

Problem Name: Permutations II
Description:
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

webdriver

Now comes the solution (in C++) ...

dfs...

代码:




class Solution {

public:

    vector<vector<int>> res;

    vector<vector<int>> permuteUnique(vector<int> &num) {

        res.clear();

        sort(num.begin(), num.end());

        bool avail[num.size()];

        memset(avail, true, sizeof(avail));

        vector<int> pum;

        permuteUniqueRe(num, pum, avail);

        return res;

    }



    void permuteUniqueRe(vector<int> &num, vector<int> &pum, bool avail[])

    {

        if (pum.size() == num.size())

        {

            res.push_back(pum);

            return;

        }

        int last_index = -1;

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

        {

            if (!avail[i]) continue;

            if (last_index != -1 && num[i] == num[last_index]) continue;

            

            avail[i] = false;

            pum.push_back(num[i]);

            permuteUniqueRe(num, pum, avail);

            pum.pop_back();

            avail[i] = true;

            last_index = i;

        }

    }

};

webdriver

Problem Name: Plus One
Description:
Given a number represented as an array of digits, plus one to the number.

webdriver

Now comes the solution (in C++) ...

...

代码:




class Solution {

public:

    vector<int> plusOne(vector<int> &digits) {

        int carry = 1, N = digits.size();

        for (int i = N-1; i >= 0 && carry; --i)

        {

            int sum = carry + digits[i];

            carry = sum / 10;

            digits[i] = sum % 10;

        }

        if (carry == 1)

            digits.insert(digits.begin(), 1);

        return digits;

    }

};