Group Shifted Strings leetcode

Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:

"abc" -> "bcd" -> ... -> "xyz"

Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.

For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
Return:

[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]

这个例子有点歧义, 其实就是

abc ((b - a) + 26 )% 26 = 1, ((c - b) + 26 )% 26= 1;

bcd ((c - b) + 26 )% 26= 1, ((d - c) + 26 )% 26= 1;

所以他们是一组shifted string

["eqdf", "qcpr"]。

((‘q’ - 'e') + 26) % 26 = 12, ((‘d’ - 'q') + 26) % 26 = 13, ((‘f’ - 'd') + 26) % 26 = 2

((‘c’ - 'q') + 26) % 26 = 12, ((‘p’ - 'c') + 26) % 26 = 13, ((‘r’ - 'p') + 26) % 26 = 2

所以他们也是一组

这样用一个map, key是这些数组的集合(注意中间要有空格 否则2,2 和22就会出现相同的情况)

然后value的arraylist放入所有符合的string

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> res = new ArrayList<List<String>>();
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for (String s : strings) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                int l = (s.charAt(i) - s.charAt(0) + 26) % 26;
                sb.append(l + " ");
                
            }
            String str = sb.toString();
            if (!map.containsKey(str)) {
                List<String> tem = new ArrayList<String>();
                map.put(str, tem);
            }
            map.get(str).add(s);
        }
        for (String m : map.keySet()) {
            Collections.sort(map.get(m));
            res.add(map.get(m));
        }
        return res;
    }
}

Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.

public class Solution {
    public int strobogrammaticInRange(String low, String high) {
        int count = 0;
        ArrayList<String> res = new ArrayList<String>();
        for (int i = low.length(); i <= high.length(); i++) {
            res.addAll(helper(i, i));
        }
        for (String s : res) {
            if ((s.length() == low.length() && s.compareTo(low) < 0)|| (s.length() == high.length() && s.compareTo(high) > 0)) {
                continue;
            }
            count++;
        }
        return count;
    }
    public ArrayList<String> helper(int m, int n) {
        if (m == 0) {
            return new ArrayList(Arrays.asList(""));
        } else if (m == 1) {
            return new ArrayList(Arrays.asList("0", "1", "8"));
        }
        ArrayList<String> cur = helper(m - 2, n);
        ArrayList<String> tem = new ArrayList<String>();
        for (String s : cur) {
            if (m != n) {
                tem.add("0" + s + "0");
            }
            tem.add("1" + s + "1");
            tem.add("8" + s + "8");
            tem.add("6" + s + "9");
            tem.add("9" + s + "6");
        }
        return tem;
    }
}

Strobogrammatic Number II leetcode

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return ["11","69","88","96"].
Arrays.asList() -->返回一个包含括号内元素的arraylist
第一种方法 从中间向两边插入

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        return helper(n, n);
    }
    public List<String> helper(int m, int n) {
        if (m == 1) {
            List<String> res = Arrays.asList("0", "1", "8");
            return res;
        }
        if (m == 0) {
            List<String> res = Arrays.asList("");
            return res;
        }
        List<String> list = helper(m - 2, n);
        List<String> res = new ArrayList<String>();
        for (String s : list) {
            if (n != m) {
                res.add("0" + s + "0");
            }
            res.add("1" + s + "1");
            res.add("6" + s + "9");
            res.add("8" + s + "8");
            res.add("9" + s + "6");
        }
        return res;
    }
}

第二种方法 两边往中间插

public class Solution {
    char[] list = {'0', '1', '8', '6', '9'};
    public List<String> findStrobogrammatic(int n) {
        
        List<String> res = new ArrayList<String>();
        helper(new char[n], res, 0, n - 1);
        return res;
    }
    public void helper(char [] cur, List<String> res, int left, int right) {
        if (left > right) {
            res.add(new String(cur));
            return;
        }else if (left == right) {
            for (int i = 0; i < 3; i++) {
                cur[left] = list[i];
                res.add(new String(cur));
            }
            return;
        } else {
            int i = 0;
            if (left == 0) {
                i = 1;
            }
            for (; i < 5; i++) {
                if (i < 3) {
                    cur[left] = list[i];
                    cur[right] = list[i];
                } else if (i == 3) {
                    cur[left] = '6';
                    cur[right] = '9';
                } else {
                    cur[left] = '9';
                    cur[right] = '6';
                }
                helper(cur, res, left + 1, right - 1);
            }
        }
            
        
    }
}

Strobogrammatic Number leetcode

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers "69", "88", and "818" are all strobogrammatic.

public class Solution {
    public boolean isStrobogrammatic(String num) {
        HashMap map = new HashMap();
        map.put('1', '1');
        map.put('0', '0');
        map.put('6', '9');
        map.put('8', '8');
        map.put('9', '6');
        int left = 0;
        int right = num.length() - 1;
        while (left <= right) {
            if (!map.containsKey(num.charAt(left)) || map.get(num.charAt(left)) != num.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

Shortest Word Distance III leetcode

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

word1 and word2 may be the same and they represent two individual words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “makes”, word2 = “coding”, return 1.
Given word1 = "makes", word2 = "makes", return 3.

与Shortest Word Distance I唯一不同点就是要考虑一个word1 和Word2相等的情况, 这样的话只更新index1

public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int index1 = -1, index2 = -1;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            String s = words[i];
            if (s.equals(word1)) {
                if (word1.equals(word2)) {
                    if (index1 != -1) {
                        res = Math.min(i - index1, res);
                    }
                    index1 = i;
                } else {
                    index1 = i;
                    if (index2 != -1) {
                        res = Math.min(res, i - index2);
                    }
                }
            } else if (s.equals(word2)) {
                index2 = i;
                if (index1 != -1) {
                    res = Math.min(res, i - index1);
                }
            }
        }
        return res;
    }
}

Shortest Word Distance II leetcode

This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

public class WordDistance {
    private HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
    public WordDistance(String[] words) {
        for (int i = 0; i < words.length; i++) {
            String s = words[i];
            if (map.containsKey(s)) {
                map.get(s).add(i);
            } else {
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(i);
                map.put(s, list);
            }
        }
    }

    public int shortest(String word1, String word2) {
        ArrayList<Integer> l1 = map.get(word1);
        ArrayList<Integer> l2 = map.get(word2);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < l1.size(); i++) {
            for (int j = 0; j < l2.size(); j++) {
                res = Math.min(Math.abs(l1.get(i) - l2.get(j)), res);
            }
        }
        return res;
    }
}

Shortest Word Distance leetcode

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Given word1 = “coding”, word2 = “practice”, return 3.
Given word1 = "makes", word2 = "coding", return 1.

public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int index1 = -1, index2 = -1;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word1)) {
                index1 = i;
                if (index2 != -1) {
                    res = Math.min(res, Math.abs(index2 - index1));
                }
            } 
            if (words[i].equals(word2)) {
                index2 = i;
                if (index1 != -1) {
                    res = Math.min(res, Math.abs(index2 - index1));
                }
            }
            
        }
        return res;
    }
}

Valid Anagram leetcode

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

public class Solution {
    public boolean isAnagram(String s, String t) {
        int[] tem = new int[26];
        for (int i = 0; i < s.length(); i++) {
            tem[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            tem[t.charAt(i) - 'a']--;
        }
        for (int str : tem) {
            if (str != 0) {
                return false;
            }
        }
        return true;
    }
}

Different Ways to Add Parentheses leetcode

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

分治法,类似Unique Binary Search Trees II 每次遇到一个符号就对起左右递归

public class Solution {
    public List<Integer> diffWaysToCompute(String input) {
        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < input.length(); i++) {
            char c = input.charAt(i);
            if (c != '+' && c != '-' && c != '*') {
                continue;
            }
            List<Integer> left = diffWaysToCompute(input.substring(0, i));
            List<Integer> right = diffWaysToCompute(input.substring(i + 1));
            for (int l : left) {
                for (int r : right) {
                    if (c == '+') {
                        res.add(l + r);
                    } else if (c == '-') {
                        res.add(l - r);
                    } else {
                        res.add(l * r);
                    }
                }
            }
            
        }
        if (res.size() == 0) {
            res.add(Integer.parseInt(input));
        }
        return res;
    }
}

Search a 2D Matrix II leetcode

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length - 1;
        int n = 0;
        while (m >= 0 && n < matrix[0].length) {
            if (matrix[m][n] == target) {
                return true;
            } else if (matrix[m][n] > target) {
                m--;
            } else {
                n++;
            }
        }
        return false;
    }
}

Product of Array Except Self leetcode

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

给出一个数组nums=[a1, a2, a3, a4]。 
想在O(n)时间复杂度完成最终的数组输出，res=[a2*a3*a4, a1*a3*a4, a1*a2*a4, a2*a3*a4]。

可以构造两个数组相乘：

1. [1, a1, a1*a2, a1*a2*a3]
2. [a2*a3*a4, a3*a4, a4, 1]

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        int [] tem = new int[nums.length];
        res[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            res[i] = res[i - 1] * nums[i - 1];
        }
        tem[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            tem[i] = tem[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < nums.length; i++) {
            res[i] = res[i] * tem[i];
        }
        return res;
    }
}

Delete Node in a Linked List leetcode

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

题意:

编写一个函数删除单链表中（除末尾节点外）的一个节点，只提供待删除节点。

假如链表是1 -> 2 -> 3 -> 4 给你第3个节点，值为3，则调用你的函数后链表为1 -> 2 -> 4

public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

Lowest Common Ancestor of a Binary Tree leetcode

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p , q);
        if (left != null && right != null) {
            return root;
        } else if (right != null) {
            return right;
        } else if (left != null) {
            return left;
        } else {
            return null;
        }
    }
}

Lowest Common Ancestor of a Binary Search Tree leetcode

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
    
}

Palindrome Linked List leetcode

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

找到list的中点, 然后翻转后面的list 一一对比

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode fast = head, slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = reverse(slow.next);// 这里导入的是中点的下一个 因为这种找中点情况 偶数时候是在左中点, 奇数时候是在正中点
        while (cur != null) {////这里不能是head!=null 对于0->0这个list head后面还有一个元素0

            if (head.val != cur.val) {
                return false;
            }
            head = head.next;
            cur = cur.next;
        }
        return true;
    }
    public ListNode reverse(ListNode node) {
        ListNode dummy = new ListNode(0);
        dummy.next = node;
        ListNode next = node.next;
        while (next != null) {
            node.next = next.next;
            next.next = dummy.next;
            dummy.next = next;
            next = node.next;
        }
        return dummy.next;
    
    }
}

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

思路: http://blog.csdn.net/xudli/article/details/46798619

public class Solution {
    public int countDigitOne(int n) {
         int res = 0;
         for (long m = 1; m <= n; m*= 10) {
             long a = n / m;
             long b = n % m;
             res += (a + 8) / 10 * m;
             if (a % 10 == 1) {
                 res += b + 1;
             }
         }
         return res;
    }
}

Implement Queue using Stacks leetcode

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

//方法1 push() O(n), pop() O(1), peek() O(1)
class MyQueue {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> tem = new Stack<Integer>();
    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(x);
        } else {
            while (!stack.isEmpty()) {
                tem.push(stack.pop());
            }
            tem.push(x);
            while (!tem.isEmpty()) {
                stack.push(tem.pop());
            }
            
        }
    }
    public void pop() {
        stack.pop();
    }
    public int peek() {
        return stack.peek();
    }
    public boolean empty() {
        return stack.isEmpty();
    }
}
//方法2 push() O(1), pop() O(n), peek() O(n)
class MyQueue {
    private Stack<Integer> stack = new Stack<Integer>();
    private Stack<Integer> tem = new Stack<Integer>();
    public void push(int x) {
        stack.push(x);
    }
    public void pop() {
        int x = peek();
        tem.pop();
    }
    public int peek() {
        if (tem.isEmpty()) {
            while (!stack.isEmpty()) {
                tem.push(stack.pop());
            }
         }
         return tem.peek();
    }
    public boolean empty() {
        return stack.isEmpty() && tem.isEmpty();
    }
}

Kth Smallest Element in a BST leetcode

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

非递归方法: 类似线序遍历, 每访问到一个最小的count++, 直到count == k

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        int count = 0;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode tem = stack.pop();
                count++;
                
                if (count == k) {
                    return tem.val;
                }
                node = tem.right;
            }
        }
        return 0;
    }
}

递归方法:

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int count = count(root.left);
        if (count + 1 > k) {
            return kthSmallest(root.left, k);
        } else if (count + 1 < k) {
            return kthSmallest(root.right, k - count- 1);
        } else {
            return root.val;
        }
    }
    public int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }
}

Majority Element II leetcode

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        int n1 = 0, n2 = 0;
        int count1 = 0, count2 = 0;
        for (int s : nums) {
            if (count1 == 0) {
                n1 = s;
                count1++;
            } else if (count2 == 0 && n1 != s) {
                n2 = s;
                count2++;
            } else if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int s  : nums) {
            if (s == n1) {
                count1++;
            } else if (s == n2) {
                count2++;
            }
        }
        if (count1 > nums.length / 3) {
            res.add(n1);
        }
        if (count2 > nums.length / 3) {
            res.add(n2);
        }
        return res;
    }
}

Basic Calculator II leetcode

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

这回没有括号, sign记录符号, num记录数字, 每当遇到新的符号时候入栈数字 更新sign

public class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        Stack<Integer> stack = new Stack<Integer>();
        char sign = '+';
        int num = 0 ;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                num = num* 10 + c - '0';
            }
            if (!Character.isDigit(c) || i == s.length() - 1) {
                if (sign == '+') {
                    stack.push(num);
                } else if (sign == '-'){
                    stack.push(-num);
                } else if (sign == '*') {
                    int m = stack.pop();
                    stack.push(m * num);
                } else if (sign == '/') {
                    int m = stack.pop();
                    stack.push(m/num);
                }
                num = 0;
                sign = c;
            }
        }
        int res = 0;
        for (int i : stack) {
            res += i;
        }
        return res;
    }
}

Implement Stack using Queues leetcode

mplement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

方法1: push() O(1), pop() O(n), peek() O(n) 用两个queue 来实现, 每次pop事后都把q1前边的都推入q2中, 最后一个出列, 然后q1, q2互换, top时候同理, 只是最后一个元素也入列q2.

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        q1.offer(x);
    }

    // Removes the element on top of the stack.
    public void pop() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        q1.poll();
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
    }

    // Get the top element.
    public int top() {
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int res = q1.peek();
        q2.offer(q1.poll());
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
        return res;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}

方法2: push() O(n), pop() O(1), peek() O(1) 用两个queue 来实现, 每次push时候都入列q2, 然后再把q1的元素都一一入列q2直到q1空为止, 然后q1 q2互换. 这样q1内元素的出列顺序和stack中的顺序相同 所以pop 和 top功能就是q1的 poll() 和peek()

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Queue tem = q1;
        q1 = q2;
        q2 = tem;
    }

    // Removes the element on top of the stack.
    public void pop() {
        q1.poll();
    }

    // Get the top element.
    public int top() {
        
        return q1.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
}

Basic Calculator leetcode

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

因为只有加减法 我们只要考虑括号的问题, 如果括号前面是+号, 括号内运算并不改变, 之间做加减法并入结果中, 如果括号前面是-号, 那么括号内加法, 结果就要减去相应的数. 所以我们用sign来记录数字前面的加减号, stack内部存括号外面的加减号, 这样每次运算只需要num*sign*stack.peek()
用stack和一个sign来记录符号,遇到加号 sign为1, 遇到减号sign 为-1, 遇到左括号 计算当前的符号(sign* stack.peek()) 压入栈内, 遇到右括号 出栈, 遇到数字把数字* sign* stack.peek()加入结果中

public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(1);// 先压入一个1进栈，可以理解为有个大括号在最外面

        s = s.replace(" ", "");
        int sign = 1, res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '(') {
                stack.push(sign * stack.peek());
                sign = 1;
            } else if (c == ')') {
                stack.pop();
            } else {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i) - '0';
                    i++;
                }
                res += num * sign * stack.peek();
                i--;
            }
        }
        return res;
    }
}

Count Complete Tree Nodes leetcode

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
先找到从root出发到最左和最右的距离, 如果距离相等说明最后一行自左到右都有node 总共2^n - 1个
如果不相等, 递归的找出左右不同的敌方和个数

public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = findleft(root);
        int right = findright(root);
        if (left == right) {
            return (2<<left - 1) - 1;//减号优先等级大于<<
        } else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }
    }
    public int findleft(TreeNode root) {
        int res = 0;
        while (root != null) {
            root = root.left;
            res++;
        }
        return res;
    }
    public int findright(TreeNode root) {
        int res = 0;
        while (root != null) {
            root = root.right;
            res++;
        }
        return res;
    }
}

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int max = 0;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1; 
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        return max * max;
    }
}

Combination Sum III leetcode

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (k <= 0) {
            return res;
        }
        List<Integer> tem = new ArrayList<Integer>();
        helper(res, tem, k, n, 1, 0, 0);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> tem, int k, int n, int pos, int sum, int count) {
        if (sum == n && count == k) {
            res.add(new ArrayList<Integer>(tem));
            return;
        }

        for (int i = pos; i <= 9; i++) {
            tem.add(i);
            helper(res, tem, k, n, i + 1, sum + i, count+1);
            tem.remove(tem.size() - 1);
        }
    }
}

Kth Largest Element in an Array leetcode

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
用quick selecte的方法

//pivot为left
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, nums.length - k);
    }
    public int find (int[] nums, int i, int j, int k) {
        int left = i;
        int right = j;
        int pivot = nums[left];
        while (left < right) {//为< 不是<=
            while (left < right && nums[right] > pivot) {//必须先right--
                right--;
            }
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            
            swap(nums, left, right);
            
        }
        swap(nums,right, i);
        if (left == k) {
            return nums[k];
        } else if (left < k) {
            return find(nums, left + 1, j, k);
        } else {
            return find(nums, i, left - 1, k);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}
//pivot为right
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return find(nums, 0, nums.length - 1, nums.length - k);
    }
    public int find (int[] nums, int i, int j, int k) {
        int left = i;
        int right = j;
        int pivot = nums[right];
        while (left < right) {
            while (left < right && nums[left] < pivot) {//右pivot时候先左边 反之亦然
                left++;
            }
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            if (left < right) {//此判定可有可无, 因为不会出现left> right情况
                swap(nums, left, right);
            }
            
        }
        swap(nums,left, j);
        if (left == k) {
            return nums[k];
        } else if (left < k) {
            return find(nums, left + 1, j, k);
        } else {
            return find(nums, i, left - 1, k);
        }
    }
    public void swap(int[] nums, int i, int j) {
        int tem = nums[i];
        nums[i] = nums[j];
        nums[j] = tem;
    }
}

Priority Queue的解法

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        for (int i : nums) {
            queue.offer(i);
        }
        for (int i = 0; i < nums.length - k ; i++) {
            queue.poll();
        }
        return queue.peek();
    }
}

House Robber II leetcode

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

第一次去掉第一家保留最后一家 第二次去掉最后一家保留第一家, 计算能抢得最大值, 然后拿结果比较取最大的.

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        } else if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        //include the first one
        int[] dp = new int[nums.length];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        //include the last one
        int [] dr = new int[nums.length];
        dr[0] = 0;
        dr[1] = nums[1];
        for (int i = 2; i < nums.length; i++) {
            dr[i] = Math.max(dr[i - 1], dr[i - 2] + nums[i]);
        }
        return Math.max(dp[nums.length - 1], dr[nums.length - 1]);
    }
}

Minimum Size Subarray Sum leetcode

Given an array of n positive integers and a positive integer s, find the minimal length of a 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.

用滑动窗口的做法

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right];
            while (sum >= s) {
                sum -= nums[left];
                min = Math.min(min, right - left + 1);
                left++;
            }
            right++;
        }
        if (min == Integer.MAX_VALUE) {
            return 0;
        } else {
            return min;
        }
        
    }
}

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null && t == null) {
            return true;
        } else if (s == null || t == null) {
            return false;
        } else if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> map1 = new HashMap<Character, Character>();
        HashMap<Character, Character> map2 = new HashMap<Character, Character>();
        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            if (map1.containsKey(c1)) {
                if (map1.get(c1) != c2) {
                    return false;
                }
            }
            if (map2.containsKey(c2)) {
                if (map2.get(c2) != c1) {
                    return false;
                }
            }
            map1.put(c1, c2);
            map2.put(c2, c1);
        }
        return true;
    }
}

Count Primes leetcode

Description:

Count the number of prime numbers less than a non-negative number, n.

厄拉多塞筛法(Sieve of Eeatosthese):
从第一个质数开始 把所有他的倍数都去掉, 那么下一个没有被去掉的肯定是质数, 依次循环到sqrt(n)

public class Solution {
    public int countPrimes(int n) {
        if(n <= 2) {
            return 0;
        }
        boolean[] map = new boolean[n];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            //如果n=100, 那么只需要递加到10就可以, 之后的11* 11 > 100, 而11*(2到10)都已经在2到10时候剪去过了
            if (map[i] == false) {
                for (int j = i + i; j < n; j += i) {
                    map[j] = true;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (map[i] == false) {
                count++;
            } 
        }
        return count;
    }
}

Happy Number leetcode

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

public class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<Integer>();
        while (!set.contains(n)) {
            set.add(n);
            int newn = 0;
            while (n != 0) {
                newn += (n % 10) * (n % 10);//注意要有()
                n /= 10;
            }
            if (newn == 1) {
                return true;
            } else {
                n = newn;
            }
        }
        return false;
    }
}