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

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

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

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

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

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

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