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