Remove Linked List Elements leetcode

Remove all elements from a linked list of integers that have value val.

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode node = dummy;
        while (node.next != null) {
            if (node.next.val == val) {
                node.next = node.next.next;
            } else {
                node = node.next;
            }
        }
        return dummy.next;
    }
}

Single Number III leetcode

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

与single number1 类似 每个重复的数都出现两次, 假设不重复的数字为a, b. 用^遍历所有数组就会得到一个a^b的结果c. 我们知道在c中, 每一位1说明在这一位上a与b是不同的. 
      3 (0011) xor 
      5 (0101)= 
     6 (0110) 
我们只需要找到这1位, 然后把数组按照这一位是1还是这一位是0分为两个数组 然后分别做^遍历 就会在每个组中找到一个独立的单身狗了.

public class Solution {
    public int[] singleNumber(int[] nums) {
        int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        }
        int tem = 0;
        for (int c : nums) {
            tem ^= c;
        }
        int pre = 0;
        while (tem!= 0) {
            pre = tem;
            tem &= tem - 1;
        }
        for (int n : nums) {
            if ((n & pre) == 0) {
                res[0] ^= n;
            } else {
                res[1] ^= n;
            }
        }
        return res;
    }
}

Sliding Window Maximum leetcode

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

用deque来解决, deque里入他们的下角标, 每当入新数的时候把新数与deque的num[末尾]比较 如果num[末尾]小就把末尾扔掉, 直到num[末尾]大于等于num[新数], 这样一来deque里就是按照num的大小顺序排列的 前边的最大 后边的最小. 每次不用出列不在窗口里德数字, 我们只需要确定deque开头的数是在窗口就可以了. 因为每个数只可能被操作最多两次，一次是加入队列的时候，一次是因为有别的更大数在后面，所以被扔掉，或者因为出了窗口而被扔掉。   所以时间复杂度为O(N).

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < n; i++) {
            //如果最左侧的数不在窗口内 出列
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.pollFirst();
            }
            //如果结尾的数小于新数则出列
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            //添加入新数
            deque.offerLast(i);
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}

Reverse Bits leetcode

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++, n >>= 1) {
            res = res << 1 | (n & 1);//给res的最后一位置为(n最右一位)
        }
        return res;
    }
}

//方法2
public int reverseBits(int n) {
        int res = 0;
        int[] tem = new int[32];
        for (int i = 0; i < 32; i++) {
            tem[i] = n >> i & 1;
        }
        for (int i = 31; i >= 0; i--) {
            res += tem[i] << (31 - i);
        }
        return res;
    }

Power of Two leetcode

Given an integer, write a function to determine if it is a power of two.

public class Solution {
    public boolean isPowerOfTwo(int n) {
         if (n <= 0) {
             return false;
         }
         return (n & (n - 1)) == 0;
        
    }
}

Number of 1 Bits leetcode

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.

解法1: 把每一位都 & 1, 计算所有1的个数
解法2: 因为n & (n - 1)就可以消除掉最右边的一个1, 比如110，减去1得101，相与得100，消去了最右边的1。这样一直消除到没有, 可以计算出1得个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                count++;
            }
        }
        return count;
    }
}

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

3Sum Smaller leetcode

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

用3Sum的方法 a=num[i] + num[l] + num[r]
当a < target时候 left++, 但是注意此时对于num[i] + num[l] + num[l + 1 ---> r] 都满足<target
所以这个时候指针右移 count+ right - left;

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        } 
        Arrays.sort(nums);
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    count+= right - left;
                    left++;
                }
                if (nums[i] + nums[left] + nums[right] >= target) {
                    right--;
                }
            }
        }
        return count;
    }
}

Add Digits leetcode

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

public class Solution {
    public int addDigits(int num) {
        while (num > 9) {
            int newnum = 0;
            while (num > 0) {
                newnum += num % 10;
                num = num / 10;
            }
            num = newnum;
        }
        return num;
    }
}

public class Solution {
    public int addDigits(int num) {
        return  (num - 1) % 9 + 1;
    }
}

Binary Tree Paths leetcode

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

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

public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if (root == null) {
            return res;
        }
        String str = root.val +"";
        helper(res, root, str);
        return res;
    }
    public void helper(List<String> res, TreeNode root, String str) {
        if (root.left == null && root.right == null) {
            res.add(str);
            return;
        }
        if (root.left != null) {
            helper(res, root.left, str + "->" + root.left.val);
        }
        if (root.right != null) {
            helper(res, root.right, str +"->" + root.right.val);
        }
    }
}

Paint House leetcode

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

public class Solution {
    public int minCost(int[][] costs) {
        if(costs == null || costs.length == 0 || costs[0] == null || costs[0].length == 0) {
            return 0;
        }
        int n = costs.length;
        int[][] dp = new int[n][3];
        for (int i = 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
        }
        for (int j = 1; j < costs.length; j++) {
            dp[j][0] = costs[j][0] + Math.min(dp[j - 1][1], dp[j - 1][2]);
            dp[j][1] = costs[j][1] + Math.min(dp[j - 1][0], dp[j - 1][2]);
            dp[j][2] = costs[j][2] + Math.min(dp[j - 1][1], dp[j - 1][0]);
        }
        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));

    }
}

Verify Preorder Sequence in Binary Search Tree leetcode

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        return helper(preorder, 0, preorder.length - 1);
    }
    public boolean helper(int[] preorder, int left, int right) {
        if (left >= right) {
            return true;
        }
        int i = left + 1;
        while (i <= right && preorder[i] < preorder[left]) {
            i++;
        }
        int j = i;
        while (j <= right) {
            if (preorder[j] > preorder[left]) {
                j++;
            } else {
                return false;
            }
        }
        
        return helper(preorder, left + 1, i - 1) && helper(preorder, i, right);
        
    }
}

Factor Combinations leetcode

Numbers can be regarded as product of its factors. For example,

8 = 2 x 2 x 2;
  = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Note: 

1. Each combination's factors must be sorted ascending, for example: The factors of 2 and 6 is [2, 6], not [6, 2].
2. You may assume that n is always positive.
3. Factors should be greater than 1 and less than n.

Examples: 
input: 1
output: 

[]

input: 37
output: 

[]

input: 12
output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

input: 32
output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

用dfs方法,

public class Solution {
    public List<List<Integer>> getFactors(int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (n <= 2) {
            return res;
        }
        List<Integer> tem = new ArrayList<Integer>();
        helper(res, tem,n,2);
        return res;
    }
    public void helper(List<List<Integer>> res, List<Integer> tem, int m,int div) {
        if (m <= 1) {
            if (tem.size() > 1) {
                res.add(new ArrayList<Integer>(tem));
            }
            return;
        }
        for (int i = div; i <= m; i++) {
            if (m % i == 0) {
                tem.add(i);
                helper(res, tem,m / i, i);
                tem.remove(tem.size() - 1);
            }
            
        }
    }
}

Meeting Rooms leetcode

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        Comparator com = new Comparator() {
            public int compare(Interval i1, Interval i2) {
                return i1.start - i2.start;
            }
        };
        Arrays.sort(intervals, com);
        Interval tem = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            Interval next = intervals[i];
            if (next.start < tem.end) {
                return false;
            }
            tem = next;
        }
        return true;
    }
}

Count Univalue Subtrees leetcode

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

              5
             / \
            1   5
           / \   \
          5   5   5

return 4.

就是对一个树找子树值和root相同的个数, 对于例子中 三个叶节点5都算, 另外一个是root的右儿子 因为它left child为空 right child值跟本身相等

public class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] res = new int[1];
        if (root == null) {
            return 0;
        }
        helper(root, res);
        return res[0];
    }
    public boolean helper(TreeNode root, int[] res) {
        if (root.left == null && root.right == null) {
            res[0]++;
            return true;
        } else if (root.left == null && root.right != null) {
            if (helper(root.right, res) && root.val == root.right.val) {
                res[0]++;
                return true;
            } else {
                return false;
            }
        } else if (root.right == null && root.left != null) {
            if (helper(root.left, res) && root.left.val == root.val) {
                res[0]++;
                return true;
            } else {
                return false;
            }
        } else {
            boolean l = helper(root.left, res);//必须单独列出来因为如果root.left = false 仍要递归root.right以对res进行操作
            boolean r = helper(root.right, res);
            if (l && r && root.val == root.left.val && root.val == root.right.val) {
                res[0]++;
                return true;
            } else {
                return false;
            }
        }
    }
}

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