leetcode解题: Valid Parenthese (20)

发表于 2016-12-20 | 分类于刷题总结

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.

解法1： Stack O（N） Space + O（N） Time

主要考察stack的用法，用一个stack存储所有的左括号，每当遇到右括号的时候就取stack中寻找是否是match的左括号。
C++

class Solution {
public:
    bool isValid(string s) {
        if (s.empty()) {
            return true;
        }
        
        stack<char> st;
        for (auto c : s) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else {
                if (st.empty()) {
                    return false;
                } else {
                    char top = st.top();
                    if ((top == '(' && c == ')') || (top == '[' && c == ']') || (top == '{' && c == '}')) {
                        st.pop();
                    } else {
                        return false;
                    }
                }
            }
        }
        return st.empty();
    }
};

Java

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.isEmpty()) {
            return true;
        }
        
        Stack<Character> stack = new Stack<Character>();
        
        for (char c: s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if (c == ')' && top == '(') {
                stack.pop();
                } else if (c == ']' && top == '[') {
                    stack.pop();
                } else if (c == '}' && top == '{') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

leetcode解题: Validate Binary Search Tree (98)

发表于 2016-12-20 | 分类于刷题总结

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.

解法1： DFS

本题的思路在题意中已经给出来了。要validate一个BST，要满足的是left 和right都是valid BST,同时root的值要大于left的最大值，要小于right的最小值。这里就提示我们在进行遍历的时候要记录每一个子树的最大值和最小值。
用一个辅助结构struct来记录max，min和是否是validate tree。从左至右判断是否满足BST的条件。
C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct resultSet {
    int maxVal;
    int minVal;
    bool isValid;
    resultSet (int maxv, int minv, bool isv):maxVal(maxv),minVal(minv),isValid(isv){};
};
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (root == NULL) {
            return true;
        }
        resultSet temp = helper(root);
        return temp.isValid;
    }
    resultSet helper(TreeNode* root) {
        if (!root->left && !root->right) {
            return resultSet(root->val, root->val, true);
        }
        int maxVal = root->val;
        int minVal = root->val;
        if (root->left) {
            resultSet left = helper(root->left);
            if (!left.isValid || root->val <= left.maxVal) {
                return resultSet(0, 0, false);
            }
            maxVal = max(maxVal, left.maxVal);
            minVal = min(minVal, left.minVal);
        }
        if (root->right) {
            resultSet right = helper(root->right);
            if (!right.isValid || root->val >= right.minVal) {
                return resultSet(0, 0, false);
            }
            maxVal = max(maxVal, right.maxVal);
            minVal = min(minVal, right.minVal);
        }
        return resultSet(maxVal, minVal, true);
    }
};

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    class Node {
        int min;
        int max;
        boolean isValid;
        public Node(int min, int max, boolean isValid) {
            this.min = min;
            this.max = max;
            this.isValid = isValid;
        }
    };
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Node res = helper(root);
        return res.isValid;
    }
    private Node helper(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return new Node(root.val, root.val, true);
        }
        Node left = helper(root.left);
        Node right = helper(root.right);
        // conquer
        if (left == null) {
            if (!right.isValid || right.min <= root.val) {
                return new Node(-1, -1, false);
            } else {
                return new Node(root.val, right.max, true);
            }
        } else if (right == null) {
            if (!left.isValid || left.max >= root.val) {
                return new Node(-1, -1, false);
            } else {
                return new Node(left.min, root.val, true);
            }
        } else {
            if (!left.isValid || !right.isValid) return new Node(-1, -1, false);
            if (left.max >= root.val || right.min <= root.val) return new Node(-1, -1, false);
            return new Node(Math.min(left.min, root.val), Math.max(right.max, root.val), true);                
        }
    }
}

leetcode解题: Swap Nodes in Pairs (24)

发表于 2016-12-19 | 分类于刷题总结

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.

解法1： O(N), 基本的LinkedList操作

调整后头节点不确定，用dummy node解决。然后就是很普通的node之间的对换。 1 -> 2 -> 3 -> 4, 在换两个node之前，要记录剩下的list的头节点。换好之后（假设两个node分别为first和second，那么就把first指向剩下的list的头节点)
C++

/**
 * 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) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* ptr = dummy;
        while (ptr->next != NULL && ptr->next->next != NULL) {
            ListNode* first = ptr->next;
            ListNode* second = first->next;
            ListNode* remaining = second->next;
            ptr->next = second;
            second->next = first;
            first->next = remaining;
            ptr = first;
        }
        
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

Java

leetcode解题: Hamming Distance (461)

发表于 2016-12-19 | 分类于刷题总结

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

The above arrows point to positions where the corresponding bits are different.

解法1： O(M), M is the number of bits in difference

这题考察了两个基本操作，一个是XOR的消除操作。XOR两个数得出的数含有所有不一样bit，然后再统计set bit的个数就可以了。如果还记得在统计bit的题目里面的做法，用x & (x - 1)消掉最高位的1直到x变为0为止。
C++

class Solution {
public:
    int hammingDistance(int x, int y) {
        int temp = x ^ y; 
        return numberOfBits(temp);
    }
    
    int numberOfBits(int x) {
        int count = 0;
        while (x != 0) {
            ++count;
            x = x & (x - 1);
        }
        return count;
    }
};

Java

Leetcode解题: Convert Sorted Array to Binary Search Tree (108)

发表于 2016-12-19 | 分类于刷题总结

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

解法1： Recursion

很多Tree的问题都可以用Divide & Conquer/递归的思想。这题也如此。要建立balanced tree，我们需要左边和右边的height尽可能相近。就考虑到选择中间作为root。之后就转化为把左array和右array转换的问题，这就是一个递归。

C++

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        if (nums.empty()) {
            return NULL;
        }
        return helper(nums, 0, nums.size() - 1);
    }
    
    TreeNode* helper(vector<int>& nums, int start, int end) {
        if (start > end) {
            return NULL;
        }
        if (start == end) {
            return new TreeNode(nums[start]);
        }
        
        int middle = start + (end - start) / 2;
        TreeNode* root = new TreeNode(nums[middle]);
        TreeNode* left = helper(nums, start, middle - 1);
        TreeNode* right = helper(nums, middle + 1, end);
        root->left = left;
        root->right = right;
        return root;
    }
};

Java

leetcode解题: Remove Duplicates from Sorted Array (26)

发表于 2016-12-18 | 分类于刷题总结

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.

解法1：Two pointers

思路和Remove elements一样，不一样的是two pointers指向的位置不同。这题由于是sorted，那么可以用一个指针指向插入的位置，只有碰到和前面不一样的数值的时候才更新他的值。
最后由于是返回count，所以要注意是把第一个指针的数值+1.
举例：1 2 3 3 4
当1，2，3 都不一样的时候，slow的指针往前进。当碰到第二个3的时候，slow不变，当碰到4时，把4赋值给第二个3，也就是当前slow的位置。
C++

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int slow = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[i -1]) {
                nums[++slow] = nums[i];
            }
        }
        return slow + 1;
    }
};

Java

leetcode解题: Remove Element (27)

发表于 2016-12-18 | 分类于刷题总结

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

Try two pointers.
Did you use the property of “the order of elements can be changed”?
What happens when the elements to remove are rare?

解法1：Two pointers

用two pointers，back记录需要remove的起始的位置。front不停的往后扫描，当扫到不要remove的时候则前进，如果扫到需要remove的就和back指向的数值交换，back向前-1
C++

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if (nums.empty()) {
            return 0;
        }
        int front = 0, back = nums.size() - 1;
        while (front <= back) {
            if (nums[front] != val) {
                ++front;
            } else {
                int temp = nums[back];
                nums[back] = nums[front];
                nums[front] = temp;
                --back;
            }
        }
        return front;
    }
};

Java

leetcode解题: Plus One (66)

发表于 2016-12-18 | 分类于刷题总结

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

解法1：O(N)

很基本的算carry，digit的方法

C++
要注意c++ insert的用法是insert(iterator, obj)，如果是在头部插入，可以用insert(it.begin(), obj).

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        if (digits.size() == 0) {
            return digits;
        }
        int carry = 0;
        int n = digits.size();
        carry = (digits[n - 1] + 1) / 10;
        digits[n - 1] = (digits[n- 1] + 1) % 10;
        for (int i = n - 2; i >= 0; --i) {
            int temp = (digits[i] + carry) % 10;
            carry = (digits[i] + carry) / 10;
            digits[i] = temp;
        }
        if (carry > 0) {
            digits.insert(digits.begin(), carry);
        }
        return digits;
    }
};

Java

leetcode解题: Power of Four (342)

发表于 2016-12-18 | 分类于刷题总结

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example:
Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

解法1：log换底

log4(x) == int, 运用log4(x) = log10(x)/log10(4)
C++

class Solution {
public:
    bool isPowerOfFour(int num) {
        double temp = log10(num) / log10(4);
        return temp == (int) temp;
    }
};

Java

解法2：power of two + math

如果是4的次方数，那么-1之后一定能被3整除。
要注意的是&的优先级比==小，所以如果写成num & (num - 1) == 0是不对的。
C++

class Solution {
public:
    bool isPowerOfFour(int num) {
      return num > 0 && !(num & (num - 1)) && (num - 1) % 3 == 0;
    }
};

leetcode解题: Reorder List (143)

发表于 2016-12-18 | 分类于刷题总结

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

解法1：Hashmap + two pointers O(N) Time with O(N) space

用一个hashmap记录每一个node的位置，map的key是位置的坐标。然后用双指针重新把list按顺序连接起来。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == NULL) {
            return;
        }
        unordered_map<int, ListNode*> map;
        int count = 0;
        while (head != NULL) {
            ListNode* cur = head;
            head = head->next;
            cur->next = NULL;
            map.insert({count, cur});
            count++;
        }
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        for (int i = 0, j = count - 1; i <= j; ++i, --j) {
            if (i == j) {
                tail->next = map[i];
                tail = tail->next;
            } else {
                tail->next = map[i];
                tail = tail->next;
                tail->next = map[j];
                tail = tail->next;
            }
        }
        ListNode* res = dummy->next;
        head = res;
    }
};

Java

解法2： findMiddle + Reverse O(N) Time + O(1) Space

本题也可以用linkedlist的常用算法解决。
第一步可以先找出list的中点，如果是偶数个如：1->2->3-4, 找出的是2，如果是奇数个：1->2->3->4->5, 找出的是3。
第二步：找出以后对后半部分进行reverse操作。
第三步：将右半部份merge到左半部分
这种解法不像第一种解法需要额外的存储空间。
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return;
        }
        ListNode* preMiddle = findPreMiddle(head);
        ListNode* right = preMiddle->next;
        preMiddle->next = NULL;
        right = reverse(right);
        mergeToLeft(head, right);
    }
    ListNode* findPreMiddle(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        while (head != NULL) {
            ListNode* temp = head->next;
            head->next = prev;
            prev =head;
            head = temp;
        }
        return prev;
    }
    void mergeToLeft(ListNode* left, ListNode* right) {
        ListNode* curLeft;
        ListNode* curRight;
        while (left && right) {
            curLeft = left;
            left = left->next;
            curRight = right;
            right = right->next;
            curLeft->next = curRight;
            curRight->next = left;
        }
    }
};

Java

lang: java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        // Merge + reverse
        ListNode middle = findMiddle(head);
        ListNode right = middle.next;
        middle.next = null; // break at the middle
        right = reverse(right);
        mergeToLeft(head, right);
        return;        
    }
    private ListNode findMiddle(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;        
    }
    private void mergeToLeft(ListNode left, ListNode right) {
        while (left != null && right != null) {
            ListNode leftNext = left.next;
            ListNode rightNext = right.next;
            left.next = right;
            right.next = leftNext;
            left = leftNext;
            right = rightNext;
        }
    }
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}