Exercises VII

Single Number III

Medium

原题链接

描述

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

Follow up: Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

例子

Input: nums = [1,2,1,3,2,5]

Output: [3,5]

Explanation: [5, 3] is also a valid answer.

解法 XOR

出处

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

• In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value '1') in the XOR result. Find out an arbitrary set bit (for example, the rightmost set bit).

• In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the before mentioned bit unset. Two different numbers we need to find must fall into the two district groups. XOR numbers in each group, we can find a number in either group.

Complexity:

• Time: O (n)

• Space: O (1)

A Corner Case:

• When diff == numeric_limits<int>::min(), -diff is also numeric_limits<int>::min(). Therefore, the value of diff after executing diff &= -diff is still numeric_limits<int>::min(). The answer is still correct.

class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        // Pass 1 : 
        // Get the XOR of the two numbers we need to find
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        // Get its last set bit
        diff &= -diff;

        // Pass 2 :
        vector<int> rets = {0, 0}; // this vector stores the two numbers we will return
        for (int num : nums)
        {
            if ((num & diff) == 0) // the bit is not set
            {
                rets[0] ^= num;
            }
            else // the bit is set
            {
                rets[1] ^= num;
            }
        }
        return rets;
    }
};

Count Good Triplets

原题链接

easy

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int res=0; int n=arr.size();
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                for(int k=j+1; k<n; k++){
                    if(abs(arr[i]-arr[j])<=a&&abs(arr[j] - arr[k])<=b; abs(arr[i] - arr[k])<=c) res++;
                }
            }
        }
        return res; 
    }
};

这题其实出的挺烂的，但是有人做了优化->time: O(n^2)。

Count Number of Teams

Medium

原题链接

Count left and right

For each soldier, count how many soldiers on the left and right have less and greater ratings.

This soldier can form less[left] * greater[right] + greater[left] * less[right] teams.

解释

class Solution {
public:
    int numTeams(vector<int>& rating) {
        int res = 0;
        for(int i = 1; i < rating.size(); i++){
            int less[2] = {}, greater[2] = {};
            for(int j = 0; j < rating.size(); j++){
                if(rating[i] < rating[j])
                    ++less[j>i];
                if(rating[i] > rating[j])
                    ++greater[j>i];
            }
            res += less[0] * greater[1] + greater[0] * less[1];
        }
        return res;
    }
};

Time: O(n^2)

Sum of All Odd Length Subarrays

原题链接

easy

Consider the subarray that contains A[i], we can take 0,1,2..,i elements on the left, from A[0] to A[i], we have i + 1 choices.

we can take 0,1,2..,n-1-i elements on the right, from A[i] to A[n-1], we have n - i choices.

In total, there are (i + 1) * (n - i) subarrays, that contains A[i]. And there are ((i + 1) * (n - i) + 1) / 2 subarrays with odd length, that contains A[i]. A[i] will be counted ((i + 1) * (n - i) + 1) / 2 times.

Example of array [1,2,3,4,5]

1 2 3 4 5 subarray length 1 1 2 X X X subarray length 2 X 2 3 X X subarray length 2 X X 3 4 X subarray length 2 X X X 4 5 subarray length 2 1 2 3 X X subarray length 3 X 2 3 4 X subarray length 3 X X 3 4 5 subarray length 3 1 2 3 4 X subarray length 4 X 2 3 4 5 subarray length 4 1 2 3 4 5 subarray length 5

5 8 9 8 5 total times each index was added. 3 4 5 4 3 total times in odd length array with (x + 1) / 2 2 4 4 4 2 total times in even length array with x / 2

class Solution {
public:
  int sumOddLengthSubarrays(vector<int>& A) {
        int res = 0, n = A.size();
        for (int i = 0; i < n; ++i) {
            res += ((i + 1) * (n - i) + 1) / 2 * A[i];
        }
        return res;
    }
};

Time：O(N)

Space: O(1)