LeetCode OJ – 第22页

LeetCode 18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

题目大意：给一个整型数组，求abcd序列，使得a+b+c+d=target，返回所有不重复的abcd序列结果集合～

分析：对整型数组进行排序，先用i和j确定了前两个元素，然后用begin和end分别从j+1和最后一个元素n-1开始查找，根据sum的值移动begin和end指针，如果sum==target，就将结果放入结果集中；如果sum>target，将end向前移动一个，如果sum<target，就讲begin向后移动一个……为了避免重复，当i、j、begin、end和它们的前一个元素相同的时候，就跳过当前元素，直接移动到下一个～

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
       vector<vector<int>> result;
       int n = nums.size();
       if(n < 4) return result;
       sort(nums.begin(), nums.end());
       vector<int> temp(4);
       for(int i = 0; i < n - 3; i++) {
            if(i != 0 && nums[i] == nums[i-1]) continue;
           for(int j = i + 1; j < n - 2; j++) {
               if(j != i + 1 && nums[j] == nums[j-1]) continue;
               int begin = j + 1, end = n - 1;
               while(begin < end) {
                   int sum = nums[i] + nums[j] + nums[begin] + nums[end];
                   if(sum == target) {
                       temp[0] = nums[i];
                       temp[1] = nums[j];
                       temp[2] = nums[begin];
                       temp[3] = nums[end];
                       result.push_back(temp);
                       begin++;
                       end--;
                       while(begin < end && nums[begin] == nums[begin-1]) begin++;
                       while(begin < end && nums[end] == nums[end+1]) end--;
                   } else if(sum > target) {
                       end--;
                   } else {
                       begin++;
                   }
               }
           }
       }
       return result;
    }
};

class Solution {

public:

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

vector<vector<int>> result;

int n = nums.size();

if(n < 4) return result;

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

vector<int> temp(4);

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

if(i != 0 && nums[i] == nums[i-1]) continue;

for(int j = i + 1; j < n - 2; j++) {

if(j != i + 1 && nums[j] == nums[j-1]) continue;

int begin = j + 1, end = n - 1;

while(begin < end) {

int sum = nums[i] + nums[j] + nums[begin] + nums[end];

if(sum == target) {

temp[0] = nums[i];

temp[1] = nums[j];

temp[2] = nums[begin];

temp[3] = nums[end];

result.push_back(temp);

begin++;

end--;

while(begin < end && nums[begin] == nums[begin-1]) begin++;

while(begin < end && nums[end] == nums[end+1]) end--;

} else if(sum > target) {

end--;

} else {

begin++;

}

return result;

}

};

LeetCode 16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

题目大意：给定一个整型数组，在数组中找xyz，使x+y+z最接近target，返回最接近的x+y+z的值～

分析：对nums排序，先确定第一个数为nums[i], 使begin = i + 1，end = n – 1,如果当前sum == target，就令begin++，end–，指针分别向前向后移动一个，如果sum比较大，就令end往前一个；如果sum比较小，就令begin往后一个～每次根据sum更新result的值，result设置为long型，避免一开始是INT最大值、加了负数后溢出～

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        long result = INT_MAX;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for(int i = 0; i < n; i++) {
            int begin = i + 1, end = n - 1;
            while(begin < end) {
                int sum = nums[i] + nums[begin] + nums[end];
                if(sum == target) {
                    begin++;
                    end--;
                } else if(sum > target) {
                    end--;
                } else {
                    begin++;
                }
                if(abs(sum - target) < abs(result - target))
                    result = sum;
            }
        }
        return (int)result;
    }
};

class Solution {

public:

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

long result = INT_MAX;

int n = nums.size();

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

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

int begin = i + 1, end = n - 1;

while(begin < end) {

int sum = nums[i] + nums[begin] + nums[end];

if(sum == target) {

begin++;

end--;

} else if(sum > target) {

end--;

} else {

begin++;

}

if(abs(sum - target) < abs(result - target))

result = sum;

}

return (int)result;

}

};

LeetCode 15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

题目大意：给一个整数数组，从中选三个元素abc，使a + b + c = 0，返回所有满足条件的abc集合，结果集合中的结果不能有重复～

分析：将sum数组排序，先确定nums[i]为第一个元素，为了避免重复，如果nums[i]和刚刚的nums[i-1]相同就跳过continue，然后begin指向i+1，end指向n-1，判断此时的sum是否等于0，如果等于0就将结果放入result数组中，且begin++，end – -，为了避免重复，如果begin++后的元素依旧和刚才的元素相同，继续begin++，end同理～如果sum>0就将end – -，如果sum<0就将begin++，最后返回result结果集～～

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();
        if(n < 3) return result;
        sort(nums.begin(), nums.end());
        vector<int> temp(3);
        for(int i = 0; i < n; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int begin = i + 1, end = n - 1;
            while(begin < end) {
                int sum = nums[i] + nums[begin] + nums[end];
                if(sum == 0) {
                    temp[0] = nums[i]; 
                    temp[1] = nums[begin]; 
                    temp[2] = nums[end];
                    result.push_back(temp);
                    begin++; 
                    end--;
                    while(begin < end && nums[begin] == nums[begin - 1]) begin++;
                    while(begin < end && nums[end] == nums[end + 1]) end--;
                } else if(sum > 0) {
                    end--;
                } else {
                    begin++;
                }
            }
        }
        return result;
    }
};

class Solution {

public:

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

vector<vector<int>> result;

int n = nums.size();

if(n < 3) return result;

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

vector<int> temp(3);

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

if(nums[i] > 0) break;

if(i > 0 && nums[i] == nums[i-1]) continue;

int begin = i + 1, end = n - 1;

while(begin < end) {

int sum = nums[i] + nums[begin] + nums[end];

if(sum == 0) {

temp[0] = nums[i];

temp[1] = nums[begin];

temp[2] = nums[end];

result.push_back(temp);

begin++;

end--;

while(begin < end && nums[begin] == nums[begin - 1]) begin++;

while(begin < end && nums[end] == nums[end + 1]) end--;

} else if(sum > 0) {

end--;

} else {

begin++;

}

return result;

}

};

LeetCode 392. Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100). A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not). Example 1: s = “abc”, t = “ahbgdc” Return true. Example 2: s = “axc”, t = “ahbgdc” Return false. Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

题目大意：判断s是否是t的子串～

分析：设立两个指针p和q，分别指向s[0]和t[0]，只要p和q没有超出s和t的长度范围，不断判断当前s[p]与t[q]是否相等，如果不相等就将q指针不断后移，直到相等为止～相等后p和q指针同时后移，依次判断～
最终判断p指针是否等于lens，即p指针是否指完了s字符串的所有字符～

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int p = 0, q = 0, lens = s.length(), lent = t.length();
        while(p < lens && q < lent) {
            while(q < lent && s[p] != t[q]) q++;
            if(s[p] == t[q]) {
                p++;
                q++;
            }
        }
        return p == lens;
    }
};

class Solution {

public:

bool isSubsequence(string s, string t) {

int p = 0, q = 0, lens = s.length(), lent = t.length();

while(p < lens && q < lent) {

while(q < lent && s[p] != t[q]) q++;

if(s[p] == t[q]) {

p++;

q++;

}

return p == lens;

}

};

LeetCode 384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

题目大意：实现洗牌算法。给定一个没有重复元素的数组，写shuffle和set函数，shuffle函数要求对nums数组进行洗牌然后返回，set函数要求返回原来的nums数组～
分析：设立两个数组nums和origin，如果set就返回不会更改的origin数组，如果要洗牌，从nums的最后一位开始，设index为0～n-1中的一个随机数，产生后将index与最后一位元素进行交换，这样最后一位就算敲定了，然后再往前一位，假设当前位的下标是k，那就产生0～k之间的一个随机数，然后交换，以此类推，rand() % (i + 1)表示生成0～i中的一个随机数～直到第一位为止～

class Solution {
private:
    vector<int> nums;
    vector<int> origin;
public:
    Solution(vector<int> nums) {
        this->nums = nums;
        this->origin = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return origin;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int n = nums.size();
        for(int i = n - 1; i >= 0; i--) {
            int index = rand() % (i + 1);
            swap(nums[i], nums[index]);
        }
        return nums;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * vector<int> param_1 = obj.reset();
 * vector<int> param_2 = obj.shuffle();
 */

class Solution {

private:

vector<int> nums;

vector<int> origin;

public:

Solution(vector<int> nums) {

this->nums = nums;

this->origin = nums;

}

/** Resets the array to its original configuration and return it. */

vector<int> reset() {

return origin;

}

/** Returns a random shuffling of the array. */

vector<int> shuffle() {

int n = nums.size();

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

int index = rand() % (i + 1);

swap(nums[i], nums[index]);

}

return nums;

}

};

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(nums);

* vector<int> param_1 = obj.reset();

* vector<int> param_2 = obj.shuffle();

LeetCode 357. Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Hint:

A direct way is to use the backtracking approach.
Backtracking should contains three states which are (the current number, number of steps to get that number and a bitmask which represent which number is marked as visited so far in the current number). Start with state (0,0,0) and count all valid number till we reach number of steps equals to 10n.
This problem can also be solved using a dynamic programming approach and some knowledge of combinatorics.
Let f(k) = count of numbers with unique digits with length equals k.
f(1) = 10, …, f(k) = 9 * 9 * 8 * … (9 – k + 2) [The first factor is 9 because a number cannot start with 0].

题目大意：给一个数n，求0～n位数间所有数字中，每一位数字都各不相同的数字的个数～

分析：根据提示中所给的公式，1位数字有10个，第k位有f(k) = 9 * 9 * 8 * … (9 – k + 2)个，累加从2位到n位的f(k)的总和，再加上1位的10个数字，即为所求～

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0) return 1;
        int result = 10, cnt = 9;
        for(int i = 2; i <= n; i++) {
            cnt *= (11 - i);
            result += cnt;
        }
        return result;
    }
};

class Solution {

public:

int countNumbersWithUniqueDigits(int n) {

if(n == 0) return 1;

int result = 10, cnt = 9;

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

cnt *= (11 - i);

result += cnt;

}

return result;

}

};