24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

題意很簡單，就是遇到第偶數個Node就跟上一個交換

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        
        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        int count = 1;
        
        dummy->next = head;
                    
        while (head != nullptr)
        {
            //偶數時交換
            if (count % 2 == 0)
            {
                swap(pre->val, head->val);
            }
            
            pre = head;
            head = head->next;
            count++;
        }
        
        head = dummy->next;
        delete dummy;
        return head;
    }
};

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

這一題的邏輯非常簡單
重複的就跳過就是如此

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
       
        ListNode* ans = head;
        
        while(head != nullptr && head->next != nullptr)
        {
            if(head->val == head->next->val)
            {
                head->next = head->next->next;
            }
            else
            {
                head = head->next;
            }
        }
        
        return ans;
    }
};

列舉元素組合

最近在研究iota，發現他是使用平衡三進制{-1,0,1}的方式。所以在寫code時，必須將二進制轉換成三進制。

而tryte就是三進制的3次方，地位等同於二進制中的byte。 我們把它想像成三進制中的程式變數基本單位好了。程式上的變數通常也是用幾個byte幾個byte來表達。

當二進制轉換成三進制必須檢查是否符合tryte的合法元素。
但是哪些元素是符合的。我這邊懶得自己列舉，就交給程式來跑

程式碼如下

#include <vector>

using namespace std;

void find_element_set(const vector<int> &elements, vector<int> &element_collector,vector<vector<int>> &elements_set)
{
    if (element_collector.size() == 3)
    {
        elements_set.push_back(element_collector);
        return;
    }

    for(int i = 0; i < elements.size(); i++)
    {
        element_collector.push_back(elements[i]);
        find_element_set(elements, element_collector, elements_set);
        element_collector.pop_back();
    }
}

int main()
{
    vector<vector<int>> element_set;
    vector<int> elements{0,1,-1}, element_collector;

    find_element_set(elements, element_collector, element_set);

    return 0;
}

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        // 用一個hash table來紀錄有重複字元出現在array的第幾個element
        unordered_map<char, int> charmap;
        // 最大的不重複字元substring長度跟每次要去定位每一個substring的endflag
        int maxlength = 0, flag = -1;
        
        for (int i = 0; i < s.size(); i++)
        {
            // 一開始發現s[i]不出現
            if (charmap.count(s[i]) > 0)
            {
                //比大小更新end
                flag = max(charmap[s[i]], flag);
            }
            
            //標記它已經出現過了
            charmap[s[i]] = i;
            
            //更新目前為止最大的不重複字元substring長度
            maxlength = max(maxlength,(i - flag));
        }
        
        return maxlength;
        
    }
};

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