liuchuo – 第157页 – 我不管，反正我最萌～

LeetCode 454. 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 – 1 and the result is guaranteed to be at most 231 – 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

题目大意：给四个长度相等的整型数组A、B、C、D，寻找i，j，k，l使得A[i] + B[j] + C[k] + D[l] = 0，求问有多少个这样的i，j，k，l组合～

分析：设立两个map，m1和m2，m1中存储A、B数组中的元素两两组合的和以及出现的次数，如m1[i] = j表示A、B两数组中各取一个元素相加的和为i的个数有j个～这样我们就能把A+B+C+D = 0的问题转化成A+B的和为sum，求C+D中有没有-sum可以满足相加等于0～如果m1[sum]的个数是cnt1，m2[0-sum]的个数是cnt2，那么就能构成cnt1*cnt2个组合～将所有满足条件的结果累加即可得到result的值～

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        map<int, int> m1, m2;
        int result = 0, n = A.size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t1 = A[i] + B[j];
                int t2 = C[i] + D[j];
                m1[t1]++;
                m2[t2]++;
            }
        }
        for(auto it = m1.begin(); it != m1.end(); it++)
            result += it->second * m2[0 - it->first];
        return result;
    }
};

class Solution {

public:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

map<int, int> m1, m2;

int result = 0, n = A.size();

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

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

int t1 = A[i] + B[j];

int t2 = C[i] + D[j];

m1[t1]++;

m2[t2]++;

}

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

result += it->second * m2[0 - it->first];

return result;

}

};

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();