Leetcode Hacking Practice -- Solution in C++ Part 5

文章內容

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 5 （第五部分）

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

點擊: 0 | 評論: 51 | 分類: 缺省 | 論壇: IT人生 | 論壇帖子

分享:

分享到微信

文章評論

webdriver

無題

算法問題: Text Justification
問題描述:
Given an array of words and a length L, format the text such that each line has exactly L
characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line.
Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces
on a line do not divide evenly between words, the empty slots on the left will be assigned more
spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[
"This is an",
"example of text",
"justification. "
]
Note: Each word is guaranteed not to exceed L in length.
Corner Cases:
A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left-justified.

2014-09-25 00:35:42 | 引用

無題

推薦答案來了 (in C++) ...

...

代碼:




class Solution {

public:

    vector<string> fullJustify(vector<string> &words, int L) {

        vector<string> res;

        int i = 0, N = words.size();

        while (i < N)

        {

            int length = words[i].size();

            int j = i + 1;

            while (j < N && length + words[j].size() + (j-i) <= L)

                length += words[j++].size();

            // build line

            string s(words[i]);

            bool isLastLine = (j == N);

            bool oneWord = (j == i + 1);

            int average = isLastLine || oneWord ? 1 : (L - length) / (j - i - 1);

            int extra = isLastLine || oneWord ? 0 : (L - length) % (j - i - 1);

            for (int k = i + 1; k < j; ++k) {

                s.append(extra > 0 ? average + 1 : average, ' ');

                s.append(words[k]);

                extra--;

            }

            s.append(L - s.size(), ' ');

            // push line

            res.push_back(s);

            i = j;

        }

        return res;

    }

};

2014-09-25 00:36:13 | 引用

webdriver

無題

算法問題: Trapping Rain Water
問題描述:
Given n non-negative integers representing an elevation map where the width of
each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

2014-09-25 00:37:13 | 引用

無題

推薦答案來了 (in C++) ...

Find left bound and right bound for each element. O(n).

代碼:




class Solution {

public:

    int trap(int A[], int n) {

        if (n == 0) return 0;

        int left[n];

        int right[n];



        int lmax = A[0];

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

        {

            lmax = max(lmax, A[i]);

            left[i] = lmax;

        }



        int rmax = A[n-1];

        for (int i = n - 1; i >= 0; --i)

        {

            rmax = max(rmax, A[i]);

            right[i] = rmax;

        }



        int res = 0;

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

            res += min(left[i], right[i]) - A[i];



        return res;

    }

};

2014-09-25 00:37:53 | 引用

webdriver

無題

算法問題: Triangle
問題描述:
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number
of rows in the triangle.

2014-09-25 00:39:13 | 引用

無題

推薦答案來了 (in C++) ...

Note that there are n elements in the n-th row (n starts from 1).
1. DFS. (Time Limit Exceeded for large test data).
2. DP. Do not need additional spaces (happen in-place).
3. DP. O(n) space (If the input 'triangle' can not be changed).

代碼:




class Solution {

public:

    int minimumTotal(vector<vector<int>> &triangle) {

        return minimumTotal_2(triangle);

    }



    int minimumTotal_1(vector<vector<int>> &triangle) {

        int res = INT_MAX;

        minimumTotal_1_Re(triangle, 0, res, 0, 0);

        return res;

    }



    void minimumTotal_1_Re(vector<vector<int>> &triangle, int partSum, int &res, int deep, int j)

    {

        if (deep == triangle.size()) {

            res = min(res, partSum);

            return;

        }

        for (int i = j; i < triangle[deep].size() && i <= j + 1; ++i)

            minimumTotal_1_Re(triangle, partSum + triangle[deep][i], res, deep + 1, i);

    }



    int minimumTotal_2(vector<vector<int>> &triangle) {

        for (int i = triangle.size() - 2; i >= 0; --i)

            for (int j = 0; j < i + 1; ++j)

                triangle[i][j] = triangle[i][j] + min(triangle[i+1][j], triangle[i+1][j+1]);

        return triangle[0][0];

    }



    int minimumTotal_3(vector<vector<int>> &triangle) {

        int N = triangle.size();

        int *dp = new int[N];

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

            dp[i] = triangle[N-1][i];

        for (int i = N - 2; i >= 0; --i)

            for (int j = 0; j < i + 1; ++j)

                dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);

        int res = dp[0];

        delete [] dp;

        return res;

    }

};

2014-09-25 00:39:54 | 引用

webdriver

無題

算法問題: Two Sum
問題描述:
Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target,
where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

2014-09-25 00:41:14 | 引用

無題

推薦答案來了 (in C++) ...

1. Sort first. O(nlgn)
2. Hash table. O(n)

Note: Hash Table solution has been updated. In case that the two elements are the same,
all the indices should be stored in the map.

代碼:




bool compare(pair<int, int> a, pair<int, int> b) {

    return a.first < b.first;

}



class Solution {

public:

    vector<int> twoSum(vector<int> &numbers, int target) {

        return twoSum_1(numbers, target);

    }

    

    vector<int> twoSum_1(vector<int> &numbers, int target) {

        vector<pair<int, int>> nums(numbers.size());

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

            nums[i] = make_pair(numbers[i], i+1);

        sort(nums.begin(), nums.end(), compare);

        

        int l = 0, r = nums.size() - 1;

        while (l < r)

        {

            int sum = nums[l].first + nums[r].first;

            if (sum == target) break;

            else if (sum < target) l++;

            else r--;

        }



        vector<int> res;

        res.push_back(min(nums[l].second, nums[r].second));

        res.push_back(max(nums[l].second, nums[r].second));

        return res;

    }

    

    typedef unordered_map<int, vector<int> > MAP;

    

    vector<int> twoSum_2(vector<int> &numbers, int target) {

        MAP map;

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

            map[numbers[i]].push_back(i+1);

        

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

        {

            MAP::iterator it = map.find(target - numbers[i]);

            if (it == map.end()) continue;

            

            int index1 = it->second[0], index2 = i + 1;

            

            if (numbers[i] == target - numbers[i]) { // two elements are the same

                if (it->second.size() == 1) continue;

                index2 = it->second[1];

            }

            

            vector<int> res;

            res.push_back(min(index1, index2));

            res.push_back(max(index1, index2));

            return res;

        }

    }

};

2014-09-25 00:42:04 | 引用

webdriver

無題

算法問題: Unique Binary Search Trees
問題描述:
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

2014-09-25 00:43:44 | 引用

無題

推薦答案來了 (in C++) ...

dp.

代碼:




class Solution {

public:

    int numTrees(int n) {

        int dp[n+1];

        memset(dp, 0, sizeof(dp));

        dp[0] = 1;

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

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

                dp[i] += dp[j] * dp[i-j-1];

        return dp[n];

    }

};

2014-09-25 00:44:35 | 引用

webdriver

發表評論

回到頂部▲