每月封存: 二月 2015

Rotate Array

Posted on by

這題目我以前在臉書就看過了，也還不知道如何解釋

題意，給一整數陣列，陣列長度n，以及一整數k，將陣列向右移動k次，往右邊移動的那一位填補到最左邊的空位

例如

[1,2,3],1 ->[3,1,2]

[1,2,3,4,5,6,7],2 -> [6,7,1,2,3,4,5]

操作方法是先將全部reverse，再reverse前面第零個到第k個，最後reverse第k個後面到結尾

考慮進去三次reverse，時間複雜度為O(2n)

class Solution {
public:
    void rotate(int nums[], int n, int k) {
        reverse(nums, nums+n);
        reverse(nums, nums+k%n);
        reverse(nums+k%n, nums+n);
    }
};

想出解釋的方法了

向右移動 k 次，代表會有末尾 k 位跑到右邊去

所以先將整個數列反轉一次之後，把前面 k 位再反轉一次，就可以讓前面 k 位保持原本的順序

然後在將後面 n-k 位翻轉一次，讓後面剩下的位數也都保持原本的順序

這樣就完成了

Remove Element

Posted on by

https://oj.leetcode.com/problems/remove-element/

題意，輸入一整數陣列、陣列長度，數值A

移除該整數陣列中的數值A，並且回傳移除之後的陣列長度，長度之後的元素值無所謂，陣列中的元素順序也無所謂

例如122334，移除2，則變成133422回傳4，或者143322回傳4，第4個數字後面的值是什麼無所謂

操作方法是：遍歷每個元素，如果元素是要移除的，則往後找尋不等於要移除的元素並且找到之後進行交換

如果找到了最後一個元素都沒有找到可以交換的，那就代表整個陣列操作完成

時間複雜度是O(n+m)

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int i=0, j=0;
        int d=0;
        bool end=false;
        while(i<n){
            if(A[i]==elem){
                if(n==1){
                    break;
                }
                j=i;
                while(1){
                    j++;
                    if(j==n){
                        end=true;
                        break;
                    }
                    if(A[j]!=elem){
                        swap(A[j],A[i]);
                        d++;
                        break;
                    }
                }
            }
            else{
                d++;
            }
            if(end){
                break;
            }
            i++;
        }
        return d;
    }
};

Remove Duplicates from Sorted Array

Posted on by

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/

題目輸入一個已經從小到大排序完成的整數陣列，以及陣列長度

移除該陣列中重複的元素

操作方法是：依序讀取每一個元素，如果與前一個元素相同的話就做i++讀取下一個

如果前一個元素不同的話就做d++並且把A[i]寫到A[d]裡面去，然後做i++讀取下一個

這樣的時間複雜度是O(n)

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int i=0;
        int d=0;
        if(n==0){
            return 0;
        }
        while(i<n){
            if(i==0){
                i++;
                d++;
                continue;
            }
            if(A[i]==A[i-1]){
            }
            else{
                A[d]=A[i];
                d++;
            }
            i++;
        }
        return d;
    }
};

Same Tree

Posted on by

https://oj.leetcode.com/problems/same-tree/

題目輸入兩個二元樹，判斷兩個樹是否長的一模一樣

操作邏輯是，遞迴方式檢查每一個節點的左子節點和右子節點

時間複雜度是O(n)

/**
 * Definition for binary tree
 * 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==NULL && q==NULL){
            return true;
        }
        if(p==NULL || q==NULL){
            return false;
        }
        if(p->val != q->val){
            return false;
        }
        if(!isSameTree(p->left, q->left)){
            return false;
        }
        if(!isSameTree(p->right, q->right)){
            return false;
        }
        return true;
    }
};

Symmetric Tree

Posted on by

https://oj.leetcode.com/problems/symmetric-tree/

題目：判斷一個二元樹是否對稱

操作的邏輯是，建樹的時候遇到節點左或右子樹空缺，則補-1

每一層建立完成之後取值進行比較

這個方法的時間複雜度是O(n^2)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if(root==NULL){
            return true;
        }
        if(root->left==NULL&&root->right==NULL){
            return true;
        }
        list<int> int_list;
        queue<TreeNode*> tn_queue1;
        queue<TreeNode*> tn_queue2;
        TreeNode* tmp;
        tn_queue1.push(root);
        while(!tn_queue1.empty()){
            tmp = tn_queue1.front();
            if(tmp->left!=NULL){
                tn_queue2.push(tmp->left);
                int_list.push_back(tmp->left->val);
            }
            else{
                int_list.push_back(-1);
            }
            if(tmp->right!=NULL){
                tn_queue2.push(tmp->right);
                int_list.push_back(tmp->right->val);
            }
            else{
                int_list.push_back(-1);
            }
            tn_queue1.pop();
            if(tn_queue1.empty()){
                tn_queue1 = tn_queue2;
                tn_queue2 = queue<TreeNode*>();
                while(int_list.size()>1){
                    if(int_list.front() != int_list.back()){
                        return false;
                    }
                    int_list.pop_front();
                    int_list.pop_back();
                }
                int_list.clear();
            }
        }
        return true;
    }
};

看討論區裡面有個O(n)的作法，概念是把節點的L node, R node作為參數放入helper()

然後比較L->val, R->val

如果相同的話再比較helper(L->left, R->right) and helper(L->right, r->left)

只要有一個回傳 false 就算不對稱了

Binary Tree Level Order Traversal II

Posted on by

https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

目前只有想到O(2N)的解法

第一個N是建立正序 myvector

第二個N是將 myvector 顛倒過來

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode *root) {
        vector<vector<int>> myvector;
        vector<vector<int>> myvector2;
        if(root==NULL){
            return myvector;
        }
        TreeNode* tmp;
        queue<TreeNode*> queue_node1;
        queue<TreeNode*> queue_node2;
        vector<int> vector_num1;
        queue_node1.push(root);
        while(!queue_node1.empty()){
            tmp = queue_node1.front();
            if(tmp->left!=NULL){
                queue_node2.push(tmp->left);
            }
            if(tmp->right!=NULL){
                queue_node2.push(tmp->right);
            }
            vector_num1.push_back(tmp->val);
            queue_node1.pop();
            if(queue_node1.empty()){
                queue_node1 = queue_node2;
                queue_node2 = queue<TreeNode*>();
                myvector.push_back(vector_num1);
                vector_num1.clear();
            }
        }
        vector<vector<int>>::reverse_iterator rit = myvector.rbegin();
        for(; rit!=myvector.rend(); rit++){
            myvector2.push_back(*rit);
        }
        return myvector2;
    }
};

Binary Tree Level Order Traversal

Posted on by

https://oj.leetcode.com/problems/binary-tree-level-order-traversal/

題目輸入一個二元樹

由淺至深由左至右依序輸出value

先把 root 放入 queue1

我的操作方法是，while 迴圈裡面判斷 queue1 是否為 NULL，如果不是的話就把該節點放入 queue2， queue1 pop() 一次，該點的 value push_back 到 vector1 裡面

queue1 為 NULL 的時候代表一整層跑完

此時把 vector1 放到 myvector

queue2 賦值給 queue1

vector1 清空準備儲存下一層的值

也就是一層一層建立出myvector

myvector就是要回傳的答案

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        vector<vector<int>> myvector;
        vector<int> int_vector; // for value of each level
        queue<TreeNode*> tn_queue1; // for TreeNode of current level
        queue<TreeNode*> tn_queue2; // for TreeNode of next level
        TreeNode *tmp;
        
        if(root==NULL){
            return myvector;
        }
        tn_queue1.push(root);
        while(!tn_queue1.empty()){
            tmp = tn_queue1.front();
            tn_queue1.pop();
            int_vector.push_back(tmp->val);
            if(tmp->left!=NULL){
                tn_queue2.push(tmp->left);
            }
            if(tmp->right!=NULL){
                tn_queue2.push(tmp->right);
            }
            if(tn_queue1.empty()){
                myvector.push_back(int_vector);
                tn_queue1 = tn_queue2;
                tn_queue2 = queue<TreeNode*>();
                int_vector.clear();
            }
        }
        return myvector;
    }
};

Balanced Binary Tree

Posted on by

https://oj.leetcode.com/problems/balanced-binary-tree/

按照題目定義的balance tree，任意節點的左右子樹深度差距至多為一

操作方法是，走遍每個節點，每走到一個節點就計算該節點的左右子樹深度

差距超過一，就 return false

走遍整棵樹都沒有 return false 的話就代表可以 return true 了

值得注意的是，由於我用來計算左右子樹深度的tmp, max是 global變數

所以必須在find_max之前先設定為1，否則會紀錄上次儲存的深度值

tmp, max必須是global ，因為我用tmp, max在find_max裡面遞迴計算子樹最大深度

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int tmp=1;
    int max=1;
    int find_max(TreeNode *root) {
        if(root->left!=NULL){
            tmp++;
            max = (tmp>max)?tmp:max;
            find_max(root->left);
            tmp--;
        }
        if(root->right!=NULL){
            tmp++;
            max = (tmp>max)?tmp:max;
            find_max(root->right);
            tmp--;
        }
        return max;
    }
    bool isBalanced(TreeNode *root) {
        if(root==NULL){
            return true;
        }
        int l=0;
        int r=0;
        int d=0;
        if(root->left!=NULL){
            tmp=1;
            max=1;
            l=find_max(root->left);
        }
        if(root->right!=NULL){
            tmp=1;
            max=1;
            r=find_max(root->right);
        }
        d=(l-r)>0?(l-r):(r-l);
        if(d>1){
            return false;
        }
        if(root->left!=NULL){
            if(!isBalanced(root->left)){
                return false;
            }
        }
        if(root->right!=NULL){
            if(!isBalanced(root->right)){
                return false;
            }
        }
        return true;
    }
};

Maximum Depth of Binary Tree

Posted on by

本題題目是，輸入一個二元樹，回傳最深深度

使用的方法是

判斷如果左子樹不為空，則tmp++，並且判斷目前tmp是否有比max大，有的話就把tmp賦值到max

並且把左子樹作為參數傳入maxDepth再一次做左子樹是否為空的判斷

如果左子樹和右子樹都為空的時候會return到前一個呼叫maxDepth的地方，這時候做tmp–

最後return max就是答案了

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int tmp=1;
    int max=1;
    int maxDepth(TreeNode *root) {
        if(root==NULL){
            return 0;
        }
        if(root->left!=NULL){
            tmp++;
            max = (tmp>max)?tmp:max;
            maxDepth(root->left);
            tmp--;
        }
        if(root->right!=NULL){
            tmp++;
            max = (tmp>max)?tmp:max;
            maxDepth(root->right);
            tmp--;
        }
        return max;
    }
};

Count and Say

Posted on by

本題題意是，從"1″開始

“1″描述為一個一，也就是"11″

“11″描述為兩個一，也就是"21″

“21″描述為一個二一個一，也就是"1211″

“1211″描述為一個一一個二兩個一，也就是"111221″

“111221″描述為三個一兩個二一個一，也就是"312211″

輸入N，回傳第N個字串

class Solution {
public:
    string countAndSay(int n) {
        string str1("1");
        string str2;
        unsigned int j=0;
        int x=1;
        for(int i=1; i&lt;n; i++){
            j=0;
            while(j&lt;str1.length()){
                if(str1[j]==str1[j+1]){
                    j++;
                    x++;
                    continue;
                }
                str2.append(to_string(x));
                str2.push_back(str1[j]);
                x=1;
                j++;
            }
            str1.assign(str2);
            str2.clear();
        }
        return str1;
    }
};