本週題目

1. Single Number
2. Happy Number
3. Maximum Subarray
4. Move Zeroes
5. Best Time to Buy and Sell Stock II
6. Group Anagrams
7. Counting Elements

Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

Solution 1

1. 建一個 hashmap，用來紀錄每個數字出現的次數。
2. 我們遍歷一次數列，若該數字不存在 hashmap 中，表示它第一次出現，ans 加上它的值。
3. 如果該數字存在 hashmap 中，表示它曾經出現過，ans 減去它的值。
4. 因為除了答案之外其他每個數字只會出現兩次，ans 一加一減後為 0，最後 ans 即為所求。

class Solution {
   public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hmap;
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (hmap.count(nums[i]))
                ans -= nums[i];
            else
                ans += nums[i];

            hmap[nums[i]] = i;
        }

        return ans;
    }
};

Solution 2

1. 使用 XOR (eXclusive OR) 的特性：
   -- T ^ T = F
   -- T ^ F = 1
   -- F ^ T = 1
   -- F ^ F = 0
2. 數字是使用二進位儲存的，舉 Example 2: Input = [4,1,2,1,2] 為例：
   -- 4 ^ 1 = 5 (10'd4 = 2'b100, 10'd1 = 2'b001 -> 2'b100 ^ 2'b001 = 2'b101 = 10'd5).
   -- 5 ^ 2 = 7 (10'd5 = 2'b101, 10'd2 = 2'b010 -> 2'b101 ^ 2'b010 = 2'b111 = 10'd7).
   -- 7 ^ 1 = 6 (10'd7 = 2'b111, 10'd1 = 2'b001 -> 2'b111 ^ 2'b001 = 2'b110 = 10'd6).
   -- 6 ^ 2 = 4 (10'd6 = 2'b110, 10'd2 = 2'b010 -> 2'b110 ^ 2'b010 = 2'b100 = 10'd4).
3. 遍歷一次數列，出現兩次的數字 XOR 結果為 0，剩下的就是只出現過一次的數字。

class Solution {
   public: 
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        // for (int i = 0; i < nums.size(); i++) {
        //     ans ^= nums[i];
        // }
        for (const int i : nums) {
            ans ^= i;
        }

        return ans;
    }
};

</br>

Happy Number

Write an algorithm to determine if a number n is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example:
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Solution

1. 每次的 loop 要檢查每個數字每個 digit 的平方和是不是 1，一旦為 1 則為 happy number。
2. 但有可能會進入無窮迴圈，因此用一個 hashmap 紀錄出現過的數字，若遇到曾經出現過的數字則不是 happy number。

class Solution {
   public:
    bool isHappy(int n) {
        unordered_map<int, int> hmap;
        while (n != 1) {
            if (hmap[n])
                return false;
            hmap[n]++;

            int sum = 0;
            while (n) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }

            n = sum;
        }

        if (n == 1)
            return true;
        else
            return false;
    }
};

</br>

Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution 1

1. 設一個 local MAX，local MAX 加上下一個數字如果變大，則更新 local MAX。
2. local MAX 加上下一個數字如果變小，表示 local MAX 要被下一個數字取代。
3. 設一個 global MAX 隨時更新。

class Solution {
   public:
    int maxSubArray(vector<int>& nums) {
        int globalMAX = INT32_MIN;
        int localMAX = 0;
        for (int i = 0; i < nums.size(); i++) {
            int tmp = localMAX + nums[i];
            if (tmp > nums[i])
                localMAX = tmp;
            else
                localMAX = nums[i];

            if (localMAX > globalMAX)
                globalMAX = localMAX;
        }

        return globalMAX;
    }
};

Solution 2

• Solution 1 簡潔一點的寫法。

class Solution {
   public:
    int maxSubArray(vector<int>& nums) {
        int globalMAX = INT32_MIN;
        int localMAX = 0;
        for (int num : nums) {
            localMAX = max(localMAX + num, num);
            globalMAX = max(localMAX, globalMAX);
        }

        return globalMAX;
    }
};

Solution 3

• Follow up: 使用 divide and conquer 的做法。

1. 將數列分為左半邊右半邊，分別去找左右兩邊的 MAX。
2. 根據中間分割點向左向右延伸找出中間的 MAX。
3. 最後回傳左半邊、中間、右半邊的 MAX。

class Solution {
   public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;
        return divideArray(nums, 0, n - 1);
    }

    int divideArray(vector<int>& nums, int left, int right) {
        if (left >= right)
            return nums[left];

        int mid = (left + right) / 2;
        int leftMAX = divideArray(nums, left, mid - 1);
        int rightMAX = divideArray(nums, mid + 1, right);
        int sideMAX = max(leftMAX, rightMAX);

        int midLeftMAX = nums[mid];
        int midLeftSum = nums[mid];
        for (int i = mid - 1; i >= left; i--) {
            midLeftSum += nums[i];
            midLeftMAX = max(midLeftMAX, midLeftSum);
        }
        int midMAX = midLeftMAX;
        int midSum = midLeftMAX;
        for (int i = mid + 1; i <= right; i++) {
            midSum += nums[i];
            midMAX = max(midMAX, midSum);
        }

        int globalMAX = max(midMAX, sideMAX);

        return globalMAX;
    }
};

</br>

Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Hint #1
In-place means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.

Hint #2
A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.

Solution

1. 先找出第一個 0 的位置，記住它的 index。
2. 遍歷一次數列，若不是 0，則和第一個 0 交換，並更新第一個 0 的位置。

class Solution {
   public:
    void moveZeroes(vector<int>& nums) {
        int firstZeroIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]) {
                int tmp = nums[firstZeroIndex];
                nums[firstZeroIndex] = nums[i];
                nums[i] = tmp;
                firstZeroIndex++;
            }
        }
    }
};

</br>

Best Time to Buy and Sell Stock II

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.

Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

Solution

1. 可以任意交易，其實就是最大收益，所有差價都納入考慮。
2. 如果差價是正值，表示我們可以晚點賣出，收益增加差價的值。
3. 如果差價是負值，表示我們會早一天賣出，收益不增加也不減少。

class Solution {
   public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        for (int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0)
                profit += diff;
        }

        return profit;
    }
};

</br>

Group Anagrams

Given an array of strings, group anagrams together.

Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

Note:
All inputs will be in lowercase.
The order of your output does not matter.

Solution

1. 計算每個字串中每個字母的個數，藉此創造分類。
2. 例如 "ate","eat","tea" 都有1個 a、1個 e、1個 t，則屬於 1a1e1t 類。
3. 建一個 hashmap，將同類的放在一起。
4. 依分類將 hashmap 中的 vector<string> 吐出。

class Solution {
   public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hmap;
        for (string str : strs) {
            string category;
            // int count[26] = {};
            vector<int> count(26);
            for (char c : str) {
                count[c - 'a']++;
            }

            for (int i = 0; i < 26; ++i) {
                if (count[i]) {
                    // category += to_string(count[i]) + string(1, i + 'a');
                    category += to_string(count[i]) + to_string(i);
                }
            }

            hmap[category].push_back(str);
        }

        vector<vector<string>> output;
        for (auto h : hmap) {
            output.push_back(h.second);
        }

        return output;
    }
};

</br>

Counting Elements

Given an integer array arr, count element x such that x + 1 is also in arr.

If there're duplicates in arr, count them seperately.

Example 1:
Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:
Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:
Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:
Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:
1 <= arr.length <= 1000
0 <= arr[i] <= 1000

Hint #1
Use hashset to store all elements.

Hint #2
Loop again to count all valid elements.

Solution

1. 建一個 hashmap，用來紀錄每個數字 i 出現的次數。
2. 遍歷數列檢查 i + 1 是否存在，若存在，則答案累加上 i 出現的次數。

class Solution {
   public:
    int countElements(vector<int>& arr) {
        unordered_map<int, int> hmap;
        for (const int i : arr) {
            hmap[i]++;
        }

        int ans = 0;
        for (const int i : arr) {
            if (hmap.count(i + 1))
                ans += hmap.count(i);
        }

        return ans;
    }
};

</br>

• Source code: george16886@GitHub
  • [x] Programming language: C++
  • [x] Environment: ubuntu 16.04
  • [x] Tool: Visual Studio Code
• Category: 30-Day LeetCoding Challenge
• Original post @george16886's blog