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;
    }
};