LeetCode OJ – 第26页

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;

}

};

LeetCode 442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

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

Output:
[2,3]

分析：题目说不能用额外的空间，就想办法直接利用nums数组标记，考虑到nums数组中的所有数都为正数，那么比如i出现过，把num[i]的值标记为负数，那么每次去看num[i]是正是负就能知道i以前有没有出现过～因为所有数都是1～n的，而下标只能0～n-1，可以把i-1标记成负数来符合这个条件～
所以说可以令当前nums[i]的绝对值是num，如果nums[num-1]这个值是负数，说明以前遇到过num，那么就把num这个数字放入result数组中；如果不是负数，说明以前没有出现过这个数，就把这个数变成自己本身的负数～即：nums[num – 1] = 0 – nums[num – 1];

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> result;
        for(int i = 0; i < nums.size(); i++) {
            int num = abs(nums[i]);
            if(nums[num - 1] < 0)
                result.push_back(num);
            else
                nums[num - 1] = 0 - nums[num - 1];
        }
        return result;
    }
};

class Solution {

public:

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

vector<int> result;

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

int num = abs(nums[i]);

if(nums[num - 1] < 0)

result.push_back(num);

else

nums[num - 1] = 0 - nums[num - 1];

}

return result;

}

};

LeetCode 400. Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

Input:
3

Output:
3
Example 2:

Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.

分析：个位数：1-9，一共9个,共计9个数字；2位数：10-99,一共90个，共计180个数字； 3位数：100-999，一共900个，共计270个数字……以此类推，所以先算出它在几位数的区间，然后算出它是在这个区间内的第几个数，最后算出在这个数的第几位～

class Solution {
public:
    int findNthDigit(int n) {
        long digit = 1, sum = 9;
        while(n > digit * sum) {
            n = n - digit * sum;
            sum = sum * 10;
            digit++;
        }
        int index = n % digit;
        if(index == 0)
            index = digit;
        long num = pow(10, digit - 1);
        num += (index == digit) ? (n / digit - 1) : (n / digit);
        for(int i = index; i < digit; i++)
            num = num / 10;
        return num % 10;
    }
};

class Solution {

public:

int findNthDigit(int n) {

long digit = 1, sum = 9;

while(n > digit * sum) {

n = n - digit * sum;

sum = sum * 10;

digit++;

}

int index = n % digit;

if(index == 0)

index = digit;

long num = pow(10, digit - 1);

num += (index == digit) ? (n / digit - 1) : (n / digit);

for(int i = index; i < digit; i++)

num = num / 10;

return num % 10;

}

};