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 isn't 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.

解法 :
         基本上就是動態規劃的精神，很難口語描述，配合程式碼一起講。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        
        int n = nums.size(), start = 0, sum = 0, minlen = INT_MAX;
        
        for (int i = 0; i < n; i++) 
        { 
            //將此index的值加進來  
            sum += nums[i];
            
            //發現sum的值大於等於 s後進去條件式
            //跟目前發現的最小長度比大小
            //並且把sum的減去現在的起始點的值，再把起始點往前
            //嘗試找滿足條件的最小值
            while (sum >= s) 
            {
                minlen = min(minlen, i - start + 1);
                sum -= nums[start++];
            }
        }
        
        return minlen == INT_MAX ? 0 : minlen;
    }
};

628. Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

1. The length of the given array will be in range [3,10⁴] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

 解法 :
          將這一串的array先做排序，這樣就可以讓最後面的三個數字的積或是最前面的兩個數跟最後一個數的積變成最大值(ex. [-9,-8,1,9])

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        
        if (nums.size() < 3)
        {
            return 0;
        }
        
        sort(nums.begin(), nums.end());
        
        int firsthree =  nums[0] * nums[1] * nums[nums.size() -1]
            ,lastthree = nums[nums.size() -1] * nums[nums.size() -2] * nums[nums.size() -3];
            
        return firsthree >  lastthree ?  firsthree : lastthree;
    }
};

26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

解法
        其實這一題就是將array中重複的元素給排除掉。 在C++11的algorithm當中有一個unique的邏輯判斷剛好可以利用
程式碼如下 :

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        
        auto last = std::unique(nums.begin(), nums.end());
        
        nums.erase(last, nums.end());
        return nums.size();
        
    }
};

輕輕鬆鬆搞定

112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

解法 :
          基本上就是用DFS, DFS有兩種。一種是遞迴，另外一種是用stack

遞迴法

    邏輯大概是這樣，遞迴的function中先檢查傳進來的節點的三種條件
1. nullptr
    這不用多說，直接回false

2. 葉子
    如果是的話就在檢查傳進來的值是不是等於此節點的值，是的話就回傳true,不是就是false

3. 不是上面兩種情況
     將此節點的左右子節點帶入遞迴的function然後傳入sum - 此節點的值，取兩者遞迴function的OR值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        
        if (root == nullptr)
            return false;
        
        return hasPathSumDFS(root, sum);    
    }
    
    bool hasPathSumDFS(TreeNode* node, int sum)
    {
        if (node == nullptr)
        {
            return false;
        }
        
        if (node->left == nullptr && node->right == nullptr)
        {
            if(node->val == sum)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

        return hasPathSumDFS(node->left, sum - node->val) || hasPathSumDFS(node->right, sum - node->val);

    }
};

206. Reverse Linked List

Reverse a singly linked list.


解法 :
      其實資料結構的課本上就有，但是實在懶得再去翻書了，所以在這邊註記一下

      假設Linked-List是長這樣
     
      1 -> 2 -> 3 -> 4 -> 5

      那麼在這邊先給定三個變數，分別是previous(上一個)，current(當前的)，以及下一個(later)
      一開始的初始值給定
      previous = nullptr
      current當然就是 1
      later 就是 2

      接下來一直進行以下的動作
      回合1
      1.current->next改成指向previous而不是指向2
        nullptr <- 1  2 -> 3 -> 4 -> 5
           p       c  l

      2.previous設為1
        nullptr <- 1 2 -> 3 -> 4 -> 5
                       c l
                       p
      3.將current設為2
        nullptr <- 1 2 -> 3 -> 4 -> 5
                       p c
                       l
      4.將last設為3
        nullptr <- 1 2 -> 3 -> 4 -> 5
                        p c    l
      接下來的回合完全一樣只是起始點變了

程式碼                 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        if(head == nullptr)
            return head;
        
        ListNode *previous = nullptr,
                 *current = head,
                 *later = head->next;
        
        while(later != nullptr)
        {
            current->next = previous;
            previous = current;
            current = later;
            later = later->next;
        }
        //current最後的next還要再重新指回上一個才可以接起來
        current->next = previous;
        
        return current;
    }
};

7. Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Subscribe to see which companies asked this question.

解法 :
         本來以為這是一個非常簡單的題目，就先檢查進來的數字是不是有overflow然後再將它反轉，結果... 還是錯誤??

後來發現原因是這樣，假設你在做反轉的公式時。他的數字 * 10 就會超過 int的最大或是最小值的話，一樣會發生overflow的情況。

因此你必須將解答的變數用比 int 還要大的type來裝，像longlong，反轉完之後的解答要再次檢查是否是overflow

程式碼如下

class Solution {
public:
    int reverse(int x) {
        
        if (x > INT_MAX || x < INT_MIN)
        {
            return 0;
        }

        long long temp = 0;
        
        while (x != 0)
        {
            temp = (temp * 10) + x % 10;
            x /= 10;
        }

        if (temp > INT_MAX || temp < INT_MIN)
        {
            return 0;
        }           

        return temp; 
    }
};

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]. 

解法 :  

顧名思義就是要你找出這個array中有兩個數字是符合你所給定的條件，當然這一題假設只有唯一解 

解法有兩種 一個是 O(N^2) 另外一種是O(N) 

第一種就類似sort的方式，我就不用再多說了。

第二種解法的邏輯是這樣

用一個hash值儲存你到目前為止所找到的值的index，在for中每當i+1，就跟回去hash中找有沒有跟

target - nums[i] 符合的值

程式碼如下

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        unordered_map<int, int> twoSumMap;
        vector<int> answer;
        
        for (int i = 0; i < nums.size(); i++)
        {
            if (twoSumMap.count(target - nums[i]) > 0)
            {
                answer.push_back(twoSumMap[target - nums[i]]);
                answer.push_back(i);
                break;
            }
            else
            {
                twoSumMap[nums[i]] = i;
            }
        }
        
        return answer;
    }
};

90. Subsets II

 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

承 前一題 這題要求我們要改成此array不重複的元素的子集合，解法的思維跟上題差不多。

而這次的排序就非常重要了， 可以將重複的元素集中在一起。

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
       
       vector<vector<int>> ans;
       vector<int> sub{};
       
       //先將空集合加入
       ans.push_back(sub);
       //做排序
       sort(nums.begin(), nums.end());
       subsetsDFS(nums, sub, 0, ans);
       return ans; 
    }
    
    void subsetsDFS(const vector<int>& nums, vector<int> &sub, int start, vector<vector<int>> &output)
    {
        for(int i = start; i < nums.size(); i++)
        {
           //將重複的元素過濾掉    
           if(i > start && nums[i] == nums[i -1]) continue;
           
           sub.push_back(nums[i]);    
           output.push_back(sub);
           subsetsDFS(nums, sub, i+1, output);
           //找過的給清掉
           sub.pop_back();
        }
    }
}; 

78. Subsets

78. Subsets

Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

不用再多描述了，就是求子集合

解法 :  

一開始要先將空集合加入，然後對於array做排序(第一題的邏輯其實是不需要，但是題目的解答中{2,1}跟{1,2}不算同一集合), 接下來開始做DFS

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
       
       vector<vector<int>> ans;
       vector<int> sub{};
       
       //先將空集合加入
       ans.push_back(sub);
       //做排序
       sort(nums.begin(), nums.end());
       subsetsDFS(nums, sub, 0, ans);
       return ans; 
    }
    
    void subsetsDFS(const vector<int>& nums, vector<int> &sub, int start, vector<vector<int>> &output)
    {
        for(int i = start; i < nums.size(); i++)
        {
           sub.push_back(nums[i]);    
           output.push_back(sub);
           subsetsDFS(nums, sub, i+1, output);
           //找過的給清掉
           sub.pop_back();
        }
    }
};

532. K-diff Pairs in an Array

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).


解法 :
      用一個map 一個儲存這個array中會有幾個element以及他出現幾次 然後找尋這些元素中有沒有符合 i + k也存在的
不過這邊要特別注意，當k = 0時要特別處理，不然第三種條件下你會變成每個元素通通符合。 處理k = 0的條件是這樣，只要同樣元素的數量大於一就代表也算一個pair。

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        
        int counter = 0;
        unordered_map<int, int> elementmap;
        
        for (int i : nums)
        {
            elementmap[i]++;
        }
        
        for (auto pair : elementmap) 
        {
            if (k == 0 && pair.second > 1) 
            {
                counter++;
            }
            
            if (k > 0 && elementmap.count(pair.first + k))
            {
                counter++;
            }
        }
        
        return counter;
    }
};

561. Array Partition I

Description :

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), ..., (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.

Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

 解法 :
          這題要求我們把array想像成一個pair的群，然後求每個pair的最小值並加總起來的和
，求出最大者。
          其實很簡單，先將這個array進行排序這樣就可以保證，每個pair的最左邊數字一定是最小，而且下一個pair的最小值又會比上一個pair的最大值大。

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
    
        int pairmax = 0;
        
        sort(nums.begin(), nums.end());
        
        for(int i = 0; i < nums.size(); i+=2)
        {
            pairmax += nums[i]; 
        }
        
        return pairmax;
    }
};