個人學習日誌: 2017

2017年12月13日星期三

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

這一題其實跟104. Maximum Depth of Binary Tree 很類似，只是差在一個要最大，一個要最小。

解法也只要稍微調整一下。當你的左或右的leaf node為0時另外一個就是最小了，因為root不列入計算(求最大時不用考慮)

   class Solution {  
    public:  
        int minDepth(TreeNode *root) {  
 
            if (root == nullptr)
            {
                return 0;
            }
            
            if (root->left == nullptr)
            {
                return 1 + minDepth(root->right);
            }
            
            if (root->right == nullptr)
            {
                return 1 + minDepth(root->left);
            }
            
            return 1 + min( minDepth(root->left), minDepth(root->right) );  
        }  
    };

2017年12月5日星期二

20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

這一題的範例給得很爛...
他沒有把"({[]})" 例子給用出來
不過這一題的應用非常好，compiler的語法檢查，我想也可以用這種方式做

程式碼如下

class Solution {
public:
    
    bool isValid(string s) 
    {
        //分別利用set跟map 將 左半邊的符號 以及他對應右半邊的符號紀錄起來
        unordered_set<char> leftset({'(', '{', '['});
        unordered_map<char, char> closemap({{'(', ')'}, {'{', '}'}, {'[', ']'}});
        //利用stack
        stack<char> Stack;
        
        for(int i = 0; i < s.size(); i++)
        {
            //如果是左邊的符號 就將它加入stack
            if (leftset.count(s[i]) > 0)
            {
                Stack.push(s[i]);
            }
            else
            {
                //如果不是的話 就檢查stack是否已經空掉了或是它跟現在stack top的pair是不一樣的
                if (Stack.empty() || s[i] != closemap[Stack.top()])
                {
                    return false;
                }
                
                //通過後移除top
                Stack.pop();
            }
        }
        
        //最後檢查它還有沒有剩下的
        return Stack.empty();       
    }
};

2017年11月20日星期一

476. Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.
Note:
1，The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2，You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

簡單來說就是要他的補數拉
本來我想的非常簡單
就是直接
return ~num就好

但是後來才發現因為他是用int 32bit表示
所以假設你是題目的範例5 => 101的話他的補數會變成前面多出29個1再來才是010
最後就是-6...

因此邏輯上需要將前面的0通通遮起來
作法如下

class Solution {
public:
    int findComplement(int num) 
    {  
        unsigned int mask = ~0;
        //根據num的bit數調整mask  
        while(num&mask) mask <<= 1;  
        return ~mask & ~num;  
    }  
};

2017年11月1日星期三

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

呼，這題花了很多的時間寫。大約用了兩週的時間。雖然不是全部時間都在寫

其實這題就是Two Sum 的衍生，但是答案不只有一組所以你必須將所有的組合通通記錄下來

我本來的解法

class Solution {
public:
    vector<vector<int>> reallyanswer;
    set<vector<int>> answer;
    unordered_map<int, int> twoSumMap;

    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        if (nums.size() < 3)
        {
            return {};
        }
        
        sort(nums.begin(), nums.end());        
        
        
        for (int i = 0; i < nums.size() - 2; i++)
        {           
            twoSumMap.clear();
            
            if (i > 0 && nums[i] == nums[i - 1])
            {
                continue;
            }

            for (int j = i + 1; j < nums.size(); j++)
            {
                if (twoSumMap.count(-nums[i] - nums[j]) > 0)
                {
                    answer.insert({ nums[i], nums[twoSumMap[-nums[i] - nums[j]]], nums[j] });
                }
                else
                {
                    twoSumMap[nums[j]] = j;
                }
            }
        }

        for (auto v : answer)
        {
            reallyanswer.push_back(move(v));
        }

        return reallyanswer;
    }
};

   上面的寫法問題在於你會重複很多次找到相同的組合，雖然你是用map紀錄，最後再放到vector中。

但是時間就比人家慢非常多。

後來看到人家的解法如下

class Solution {
public:
 vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> triples;
    sort(nums.begin(), nums.end());
    int i = 0, last = nums.size() - 1;
    while (i < last) {
        int a = nums[i], j = i+1, k = last;
        
        //開始two sum的邏輯
        while (j < k) {
            //有點雙指標的寫法 從頭尾一路逼近中間
            int b = nums[j], c = nums[k], sum = a+b+c;

            //這個組合符合所以加入
            if (sum == 0) triples.push_back({a, b, c});
            //後面的while loop是因為要過濾掉重複的b
            if (sum <= 0) while (nums[j] == b && j < k) j++;
            //後面的while loop是因為要過濾掉重複的c
            if (sum >= 0) while (nums[k] == c && j < k) k--;
        }
        //while loop是因為要略過重複的a
        while (nums[i] == a && i < last) i++;
    }
    return triples;
}       
};

2017年10月11日星期三

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.
For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

看題目大概就知道要做什麼了

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t x;
        for(auto i = 31; n; ) {
            x |= (n & 1) << i;
            n >>= 1;
            -- i;
        }
        return x;
    }
};

2017年10月5日星期四

110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

檢查這個一顆二元樹是不是高度平衡(這邊的定義為左右兩邊的子樹高度不可以相差大於1)

解法

看code就清楚了

/**
 * 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 isBalanced(TreeNode* root) 
        {  
            return maxDepth(root) != -1;
        }  
          
        int maxDepth(TreeNode* node)
        {  
            if(!node) 
            {
                return 0;
            }
            
            auto ldepth = maxDepth(node->left);
            auto rdepth = maxDepth(node->right);
            
            if(ldepth == -1 || rdepth == -1 || abs(ldepth - rdepth) > 1)
            {
                return -1;
            }
            
            return max(ldepth, rdepth) + 1;  
        }  
    };

2017年10月4日星期三

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

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

return

[
   [5,4,11,2],
   [5,8,4,5]
]

簡單來說，就是要你找出所有符合條件的路徑。

解法也沒有很難，跟78. Subsets的邏輯是差不多的

/**
 * 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:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        
        vector<vector<int>> answer;
        vector<int> output;
        
        if (root == nullptr)
        {
            return answer;   
        }
        
        PathSumDFS(root, sum, answer, output);         
        return answer; 
                     
    }
    
    void PathSumDFS(TreeNode* node, int sum, vector<vector<int>> &answer, vector<int> &output)
    {         
        if (node == nullptr)
        {
            return;
        }
        
        output.push_back(node->val);
        
        if (node->left == nullptr && node->right == nullptr)
        {
            if(node->val == sum)
            {
                answer.push_back(output);
            }
        }
        
        PathSumDFS(node->left, sum - node->val, answer, output); 
        PathSumDFS(node->right, sum - node->val, answer, output);
        //返回上一層時需要把這個element清除
        output.pop_back();
        
    }    
};

2017年9月27日星期三

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

把一個排序過的array轉成一個高度平衡二元搜尋樹中。

coding的邏輯

由於是sorted過的array 所以只要將最中間的元素當成root 然後一直不斷的遞迴下去

/**
 * 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:
    
    TreeNode* ArrayToBST(vector<int>& nums, int begin, int end)
    {
        if (begin > end)
        {
            return nullptr;
        }
        
        int mid = (end + begin)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        
        root->left = ArrayToBST(nums, begin, mid - 1);
        root->right = ArrayToBST(nums, mid + 1, end);

        return root;
    }
    
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        return ArrayToBST(nums, 0, nums.size() - 1);
    }
};

2017年9月20日星期三

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

我想不用多說了吧
code也很簡單...

   class Solution {  
    public:  
        int maxDepth(TreeNode *root) {  
 
            if(root == NULL)
            {
                return 0;
            }
            
            return 1 + max( maxDepth(root->left), maxDepth(root->right) );  
        }  
    };

搞定

2017年9月13日星期三

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

簡單來說，判斷是否為對稱樹

程式碼

class Solution {
public:
    bool isSymmetric(TreeNode* root) 
    {
        
        if (root == NULL) return true;
        
        return isSymc(root->left, root->right);
        
    }
    
    bool isSymc(TreeNode* left, TreeNode* right)
    {
        if (left == nullptr)
        {
            return right == nullptr;
        }
        
        if (right == nullptr)
        {
            return left == nullptr;
        }
        
        if (left->val != right->val)
        {
            return false;
        }
        
        // 檢查是否對稱
        if (!isSymc(left->right, right->left))
        {
            return false;
        }
        
        if (!isSymc(left->left, right->right))
        {
            return false;
        }
            
        return true;
    }
    
};

2017年8月16日星期三

226. Invert Binary Tree

Invert a binary tree.

     4
   /   \
2     7
/ \   / \
1   3 6   9

to

     4
   /   \
7     2
/ \   / \
9   6 3   1

不用多說了，就是反轉二元樹

方法有好幾種。我這邊用最快的方法BFS的作法來做

/**
 * 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:
  
  TreeNode* invertTree(TreeNode* root) {

    if(nullptr == root) return root;

    stack<TreeNode*> myQueue;   // our queue to do BFS
    myQueue.push(root);         // push very first item - root

    while(!myQueue.empty()){    // run until there are nodes in the queue 
        TreeNode *node = myQueue.top();  // get element from queue
        myQueue.pop();                     // remove element from queue

        if(node->left != nullptr){         // add left kid to the queue if it exists
            myQueue.push(node->left);
        }
        if(node->right != nullptr){        // add right kid 
            myQueue.push(node->right);
        }

        // invert left and right pointers      
        swap(node->left, node->right);

    }
    return root;
}       
};

2017年7月26日星期三

40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

39. Combination Sum的衍生

邏輯大同小異，只是array中的每個元素,只能使用一次。

解法如下

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        
        vector<vector<int>> answerset;
        vector<int> combination;
        sort(candidates.begin(), candidates.end());
        
        combinationSumDFS(candidates, 0, target -0, combination, answerset);
        
        return answerset;
    }
    
    void combinationSumDFS(const vector<int>& candidates, int start, int target, vector<int> &combination, vector<vector<int>>              
                           &answerset)
    {
        // 小於0代表，再找下去也不可能會有符合的數字了
        if (target < 0)
        {
            return;
        }
        // 這個數字組合剛好符合
        else if (target == 0)
        {
            answerset.push_back(combination);
        }
        else
        {
            for (int i = start; i < candidates.size(); i++)
            {
                //排除掉重複的元素
                if (i > start && candidates[i] == candidates[i - 1]) continue;
                
                combination.push_back(candidates[i]);
                //因為已經加入這個元素了，所以要從下一個元素開始
                combinationSumDFS(candidates, i + 1, target - candidates[i], combination, answerset);
                combination.pop_back();
            }
        }        
    }
};

2017年7月24日星期一

643. Maximum Average Subarray I

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Note:

1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].

這題的思維，要想像一個k大小的sub array 從 0開始一路前進到 vector的盡頭。

class Solution {
public:
double findMaxAverage(vector<int>& nums, int k)
{
    //先算出nums[0]到nums[k]的總和
    int sum = accumulate(nums.begin(), nums.begin() + k, 0), max_number = sum, n = nums.size();
    
    for (int i = k; i < n; i++)
    {
        //每前進一格就比一次大小
        sum += nums[i] - nums[i - k];
        max_number = max(max_number, sum);
    }
    
    return double(max_number) / k;
}
};

2017年7月5日星期三

39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

要求你從一串array中找出符合某個目標加總的集合

解法的邏輯都是以DFS為主 有點類似Subset的作法，但是不同點在於要符合條件的元素才可以加入

。

不多說，來看code

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        
        vector<vector<int>> answerset;
        vector<int> combination;
        sort(candidates.begin(), candidates.end());
        
        combinationSumDFS(candidates, 0, target -0, combination, answerset);
        
        return answerset;
    }
    
    void combinationSumDFS(const vector<int>& candidates, int start, int target, vector<int> &combination, vector<vector<int>>              
                           &answerset)
    {
        // 小於0代表，再找下去也不可能會有符合的數字了
        if (target < 0)
        {
            return;
        }
        // 這個數字組合剛好符合
        else if (target == 0)
        {
            answerset.push_back(combination);
        }
        else
        {
            for (int i = start; i < candidates.size(); i++)
            {
                combination.push_back(candidates[i]);
                combinationSumDFS(candidates, i, target - candidates[i], combination, answerset);
                combination.pop_back();
            }
        }        
    }
};

2017年7月4日星期二

100. Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

題意沒有什麼，就是要你檢查兩棵tree是不是一樣的。

懶得講了直接貼code一下就了解了...

/**
 * 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 isSameTree(TreeNode* p, TreeNode* q) {
        
        if (p == nullptr || q == nullptr)
        {
            return (p == q);
        }
        
        return  (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

2017年7月3日星期一

35. Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

解法 :
看到有排序又要你找裡面的東西，二話不說，一定就是binary search的概念
如果找不到，再將target加入nums中再排序一次後，一樣用binary search。
而C++11有提供了 binary search的演算法，有分lower_bound以及upper_bound

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        
        //利用binary search去找
        auto first = std::lower_bound(nums.begin(), nums.end(), target);
        
        //沒有就加入
        if (first == nums.end())
        {
           //加入後sort
            nums.push_back(target);
            sort(nums.begin(), nums.end());
                        
            //再一次binary search去找
            first = std::lower_bound(nums.begin(), nums.end(), target);

        }
        
        //最後iterator跟begin相減就知道是第幾個了
        return first - nums.begin();
    }
};

2017年6月28日星期三

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

2017年6月27日星期二

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:

The length of the given array will be in range [3,10⁴] and all elements are in the range [-1000, 1000].
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;
    }
};

2017年6月26日星期一

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

輕輕鬆鬆搞定

2017年6月21日星期三

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

    }
};

2017年6月20日星期二

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

2017年6月19日星期一

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

2017年6月14日星期三

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

2017年6月13日星期二

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

2017年6月12日星期一

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

2017年6月7日星期三

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

2017年6月5日星期一

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:

n is a positive integer, which is in the range of [1, 10000].
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;
    }
};

訂閱：文章 ( Atom )

2017年12月13日 星期三

2017年12月5日 星期二

2017年11月20日 星期一

2017年11月1日 星期三

2017年10月11日 星期三

2017年10月5日 星期四

2017年10月4日 星期三

2017年9月27日 星期三

2017年9月20日 星期三

2017年9月13日 星期三

2017年8月16日 星期三

2017年7月26日 星期三

2017年7月24日 星期一

2017年7月5日 星期三

2017年7月4日 星期二

2017年7月3日 星期一

2017年6月28日 星期三

2017年6月27日 星期二

2017年6月26日 星期一

2017年6月21日 星期三

2017年6月20日 星期二

2017年6月19日 星期一

2017年6月14日 星期三

2017年6月13日 星期二

2017年6月12日 星期一

2017年6月7日 星期三

2017年6月5日 星期一

2017年12月13日星期三

2017年12月5日星期二

2017年11月20日星期一

2017年11月1日星期三

2017年10月11日星期三

2017年10月5日星期四

2017年10月4日星期三

2017年9月27日星期三

2017年9月20日星期三

2017年9月13日星期三

2017年8月16日星期三

2017年7月26日星期三

2017年7月24日星期一

2017年7月5日星期三

2017年7月4日星期二

2017年7月3日星期一

2017年6月28日星期三

2017年6月27日星期二

2017年6月26日星期一

2017年6月21日星期三

2017年6月20日星期二

2017年6月19日星期一

2017年6月14日星期三

2017年6月13日星期二

2017年6月12日星期一

2017年6月7日星期三

2017年6月5日星期一