LeetCode OJ – 第9页

LeetCode 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

题目大意：给一组区间，合并他们所有的重叠区间

分析：先对所有区间按左区间从小到大排序，排序后将第一个区间放入ans结果数组中，遍历原数组，如果当前ans数组的最后一个区间的end小于intervals[i]的start，说明与其没有交集，那么就将这个intervals[i]放入结果数组中。否则说明有交集，就将当前ans数组的最后一个区间的end更新为ans.back().end和intervals[i].end()中较大的那一个，最后返回ans数组即为所求～注意如果intervals中不含元素要返回空集～

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> ans;
        if (intervals.size() == 0) return ans;
        sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
        ans.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if(ans.back().end < intervals[i].start) 
                ans.push_back(intervals[i]);
            else
                ans.back().end = max(ans.back().end, intervals[i].end);
        }
        return ans;
    }
};

/**

* Definition for an interval.

* struct Interval {

* int start;

* int end;

* Interval() : start(0), end(0) {}

* Interval(int s, int e) : start(s), end(e) {}

* };

class Solution {

public:

vector<Interval> merge(vector<Interval>& intervals) {

vector<Interval> ans;

if (intervals.size() == 0) return ans;

sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});

ans.push_back(intervals[0]);

for (int i = 1; i < intervals.size(); i++) {

if(ans.back().end < intervals[i].start)

ans.push_back(intervals[i]);

else

ans.back().end = max(ans.back().end, intervals[i].end);

}

return ans;

}

};

LeetCode 49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note: All inputs will be in lower-case.

题目大意：给一组字符串，将这些字符串分组，按照同字母异序词为一组

分析：每一个s排序后的字符串为t，将s保存在以t为键的map中，这样同字母异序词即为一组。遍历map中的每一个vector<string>，将其保存在ans中，ans即为结果～

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        map<string, vector<string>> mp;
        for (auto s : strs) {
            string t = s;
            sort(t.begin(), t.end());
            mp[t].push_back(s);
        }
        for (auto m : mp) {
            vector<string> temp(m.second.begin(), m.second.end());
            ans.push_back(temp);
        }
        return ans;
    }
};

class Solution {

public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {

vector<vector<string>> ans;

map<string, vector<string>> mp;

for (auto s : strs) {

string t = s;

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

mp[t].push_back(s);

}

for (auto m : mp) {

vector<string> temp(m.second.begin(), m.second.end());

ans.push_back(temp);

}

return ans;

}

};

LeetCode 561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

题目大意：给2n个数，请把数字分为2个一组，问所有组（取每组数的较小的那一数字）累加的和最大为多少～

分析：把数组从小到大排列，第1个、第3个、…第2n-1个数字之和即为所求～

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); i+=2)
            ans += nums[i];
        return ans;
    }
};

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

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

int ans = 0;

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

ans += nums[i];

return ans;

}

};

LeetCode 43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

题目大意：给两个用字符串表示的非负整数，计算他们的乘积，结果用string表示～

分析：先将字符串num1和num2倒置，然后i和j分别遍历num1和num2，将num1[i] * num2[j]的结果加上v[i+j]本身的结果保存为temp，temp的余数保存在v[i+j]中，temp的进位累加在v[i+j+1]中。从后向前从第一个非0数字开始将数字转化为字符保存在result字符串中，result即为所求字符串～

class Solution {
public:
    string multiply(string num1, string num2) {
        string result = "";
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        int len1 = num1.length(), len2 = num2.length();
        vector<int> v(len1 + len2, 0);
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                int temp = v[i + j] + (num1[i] - '0') * (num2[j] - '0');
                v[i + j] = temp % 10;
                v[i + j + 1] += temp / 10;
            }
        }
        int flag = 0;
        for (int i = len1 + len2 - 1; i >= 0; i--) {
            if (flag == 0 && v[i] != 0) flag = 1;
            if (flag == 1) result += to_string(v[i]);
        }
        return result == "" ? "0" : result;
    }
};

class Solution {

public:

string multiply(string num1, string num2) {

string result = "";

reverse(num1.begin(), num1.end());

reverse(num2.begin(), num2.end());

int len1 = num1.length(), len2 = num2.length();

vector<int> v(len1 + len2, 0);

for (int i = 0; i < len1; i++) {

for (int j = 0; j < len2; j++) {

int temp = v[i + j] + (num1[i] - '0') * (num2[j] - '0');

v[i + j] = temp % 10;

v[i + j + 1] += temp / 10;

}

int flag = 0;

for (int i = len1 + len2 - 1; i >= 0; i--) {

if (flag == 0 && v[i] != 0) flag = 1;

if (flag == 1) result += to_string(v[i]);

}

return result == "" ? "0" : result;

}

};

LeetCode 33. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

题目大意：假设按照升序排列的数组在事先未知的某个关键点上旋转。给一个目标数target，找这个数是否存在于这个序列中，如果存在返回下标，不存在返回-1

分析：二分搜索法，如果当前nums[mid] < nums[l]，说明mid在旋转节点的右边，那么如果target也在mid和r之间就将l = mid + 1表示在mid + 1到r的区域找，否则将r = mid – 1在l到mid – 1的区域寻找；如果当前nums[mid] > nums[r]，说明mid在旋转节点的左边，那么如果target也在l和mid之间就将r = mid – 1，在l～mid-1的区域内寻找，否则在mid+1～r的区域内寻找；否则说明当前区间的顺序是正确的，就判断target和mid的大小关系，如果比mid所指数字大则在右边找，否则在左边找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < nums[l]) {
                if (target > nums[mid] && target <= nums[r])
                    l = mid + 1;
                else
                    r = mid - 1;
            } else if (nums[mid] > nums[r]) {
                if (target >= nums[l] && target < nums[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            } else {
                if (target < nums[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        }
        return -1;
    }
};

class Solution {

public:

int search(vector<int>& nums, int target) {

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

while (l <= r) {

int mid = (l + r) / 2;

if (nums[mid] == target) return mid;

if (nums[mid] < nums[l]) {

if (target > nums[mid] && target <= nums[r])

l = mid + 1;

else

r = mid - 1;

} else if (nums[mid] > nums[r]) {

if (target >= nums[l] && target < nums[mid])

r = mid - 1;

else

l = mid + 1;

} else {

if (target < nums[mid])

r = mid - 1;

else

l = mid + 1;

}

return -1;

}

};

LeetCode 671. Second Minimum Node In a Binary Tree

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:
Input:
2
/ \
2 5
/ \
5 7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
Input:
2
/ \
2 2

Output: -1
Explanation: The smallest value is 2, but there is not any second smallest value.

题目大意：给一个非空的树，这个树所有值非负，而且每个结点只有2个孩子或者0个孩子，如果当前结点有两个孩子，则这个结点的值比它的两个孩子的值都小，要求输出这个树第二小的值。

分析：遍历树，将所有的值放入集合中，输出集合的第二个数；如果集合的大小小于等于1，则输出-1

/**
 * 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:
    int findSecondMinimumValue(TreeNode* root) {
        dfs(root);
        return s.size() <= 1 ? -1 : (*++s.begin());
    }
private:
    set<int> s;
    void dfs(TreeNode* root) {
        if (root == NULL) return;
        if (root->left != NULL) dfs(root->left);
        s.insert(root->val);
        if (root->right != NULL) dfs(root->right);
    }
};

/**

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

int findSecondMinimumValue(TreeNode* root) {

dfs(root);

return s.size() <= 1 ? -1 : (*++s.begin());

}

private:

set<int> s;

void dfs(TreeNode* root) {

if (root == NULL) return;

if (root->left != NULL) dfs(root->left);

s.insert(root->val);

if (root->right != NULL) dfs(root->right);

}

};