liuchuo – 第161页

LeetCode 153. Find Minimum 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).

Find the minimum element.

You may assume no duplicate exists in the array.

分析：二分搜索法，即使旋转过了也会一半的任何一个元素始终比另一半的任何一个元素大，所以如果nums[mid] < nums[high]，说明最小元素一定在[left, mid]中，所以令high = mid；否则一定在[mid + 1, high]中，令low = mid + 1～～

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

class Solution {

public:

int findMin(vector<int>& nums) {

int low = 0, high = nums.size() - 1;

while(low < high) {

int mid = (low + high) / 2;

if(nums[mid] < nums[high])

high = mid;

else

low = mid + 1;

}

return nums[low];

}

};

LeetCode 167. Two Sum II – Input array is sorted

Given an array of integers that is already sorted in ascending order, 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

分析：每个数遍历找他的后面是否存在与它相加等于target的数，如果存在就放入result数组中～

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result(2);
        for(int i = 0; i < numbers.size(); i++) {
            for(int j = i + 1; j < numbers.size(); j++) {
                if(numbers[i] + numbers[j] == target) {
                    result[0] = i + 1;
                    result[1] = j + 1;
                    break;
                } else if(numbers[i] + numbers[j] > target) {
                    break;
                }
            }
            if(result[0] != 0)
                break;
        }
        return result;
    }
};

class Solution {

public:

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

vector<int> result(2);

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

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

if(numbers[i] + numbers[j] == target) {

result[0] = i + 1;

result[1] = j + 1;

break;

} else if(numbers[i] + numbers[j] > target) {

break;

}

if(result[0] != 0)

break;

}

return result;

}

};

LeetCode 209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there is not one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

分析：sum为前i个数的和，长度比nums多一个，sum[0] = 0。这样从0开始一直到len，遍历sum计算sum[j]与sum[i]的差大于等于s的时候的j-i长度，把它与minlen比较，如果比minlen小就更新minlen。
一开始minlen的初始化值是len + 1，如果最后minlen的值仍旧为len + 1，说明没有找到这样的minlen满足题意。则直接返回0；否则返回minlen的值～～

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        int minlen = len + 1;
        vector<int> sum(len + 1);
        for(int i = 1; i <= len; i++) {
            sum[i] = sum[i-1] + nums[i-1];
        }
        for(int i = 0; i <= len; i++) {
            for(int j = i + 1; j <= len; j++) {
                if(sum[j] - sum[i] >= s) {
                    minlen = min(minlen, j - i);
                    break;
                }
            }
        }
        if(minlen == len + 1)
            return 0;
        return minlen;
    }
};

class Solution {

public:

int minSubArrayLen(int s, vector<int>& nums) {

int len = nums.size();

int minlen = len + 1;

vector<int> sum(len + 1);

for(int i = 1; i <= len; i++) {

sum[i] = sum[i-1] + nums[i-1];

}

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

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

if(sum[j] - sum[i] >= s) {

minlen = min(minlen, j - i);

break;

}

if(minlen == len + 1)

return 0;

return minlen;

}

};

LeetCode 216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

分析：一个dfs回溯解决，如果当前k == 0而且 n == 0说明一定达到了k个数，和为n，则将当前path压入result数组中；从start开始一直到9，分别压入path中深度优先搜索。深度优先搜索完了之后记得回溯path中pop出最后一个元素～
因为题目要求结果集合必须是按照集合顺序，也就是从小到大而且没有重复元素，那么就要设立一个start变量，每次for循环的时候从start开始，一开始start为0，每次规定start为i+1，即只能从当前数字的下一个数字开始，这样就能保证结果是递增无重复数字的集合序列～～

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return result;
    }
    
    void dfs(int k, int n, int start) {
        if(k == 0) {
            if(n == 0)
                result.push_back(path);
            return ;
        }
        for(int i = start; i <= 9; i++) {
            path.push_back(i);
            dfs(k - 1, n - i, i + 1);
            path.pop_back();
        }
    }
};

class Solution {

public:

vector<vector<int>> result;

vector<int> path;

vector<vector<int>> combinationSum3(int k, int n) {

dfs(k, n, 1);

return result;

}

void dfs(int k, int n, int start) {

if(k == 0) {

if(n == 0)

result.push_back(path);

return ;

}

for(int i = start; i <= 9; i++) {

path.push_back(i);

dfs(k - 1, n - i, i + 1);

path.pop_back();

}

};

LeetCode 228. Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2″,”4->5″,”7”].

分析：判断当前nums[i]与nums[i-1]是否是相连，如果是相连就令flag = 1，如果不相连了就将前面的结果放入result数组中。最后for循环之外还要记得把temp字符串再压入数组result中，因为当前最后一次的temp还未被处理。最后返回结果～

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;
        if(nums.size() == 0)
            return result;
        string temp = "";
        int flag = 0;
        temp += to_string(nums[0]);
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] != nums[i-1] + 1 && flag == 1) {
                flag = 0;
                temp += "->" + to_string(nums[i-1]);
                result.push_back(temp);
                temp = "" + to_string(nums[i]);
            } else if(nums[i] != nums[i-1] + 1) {
                result.push_back(temp);
                temp = "" + to_string(nums[i]);
            } else {
                flag = 1;
            }
        }
        if(flag == 1) {
            temp += "->" + to_string(nums[nums.size() - 1]);
        }
        result.push_back(temp);
        return result;
    }
};

class Solution {

public:

vector<string> summaryRanges(vector<int>& nums) {

vector<string> result;

if(nums.size() == 0)

return result;

string temp = "";

int flag = 0;

temp += to_string(nums[0]);

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

if(nums[i] != nums[i-1] + 1 && flag == 1) {

flag = 0;

temp += "->" + to_string(nums[i-1]);

result.push_back(temp);

temp = "" + to_string(nums[i]);

} else if(nums[i] != nums[i-1] + 1) {

result.push_back(temp);

temp = "" + to_string(nums[i]);

} else {

flag = 1;

}

if(flag == 1) {

temp += "->" + to_string(nums[nums.size() - 1]);

}

result.push_back(temp);

return result;

}

};

229. Majority Element II

229. Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?
分析：用的常规做法，map计算每个数出现的次数，超过n/3的就放到集合里面，最后遍历集合放入数组中～

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> result;
        set<int> s;
        map<int, int> m;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            m[nums[i]]++;
            if(m[nums[i]] > n / 3)
                s.insert(nums[i]);
        }
        for(auto it = s.begin(); it != s.end(); it++)
            result.push_back(*it);
        return result;
    }
};

class Solution {

public:

vector<int> majorityElement(vector<int>& nums) {

vector<int> result;

set<int> s;

map<int, int> m;

int n = nums.size();

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

m[nums[i]]++;

if(m[nums[i]] > n / 3)

s.insert(nums[i]);

}

for(auto it = s.begin(); it != s.end(); it++)

result.push_back(*it);

return result;

}

};