235 Lowest Common Ancestor of a Binary Search Tree

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).”

思路: 用树的遍历方法来寻找,则LCA必然存在于1. p跟q中的一个 2. p,q所在的左右子树中.
复杂度: time O(n), space O(1)

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;
        if (p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else {
            return left == null ? right : left;
        }
    }
}

270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.

Note:
Given target value is a floating point.
You are guaranteed to have only one unique value in the BST that is closest to the target.

思路:用的pre-order travseral来做的,需要用一个global mindiff来找到target跟节点的最小差值,然后把此节点赋给closet.

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closet = root.val;
        double mindiff = Double.MAX_VALUE;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while(!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                double diff = Math.abs(target - current.val);
                if (diff < mindiff) {
                    mindiff = diff;
                    closet = current.val;
                }
                current = current.left;
            } else {
                current = stack.pop();
                current = current.right;
            }
        }

        return closet;
    }
}

二分, 递归

public class Solution {
    public int closestValue(TreeNode root, double target) {
        int closet = root.val;
        while(root != null) {
            // 更新到离目标节点的最近值
            closet = Math.abs(closet - target) > Math.abs(root.val - target) ? root.val : closet;
            root = target < root.val ? root.left : root.right; // 二分,找所在节点
        }
        return closet;
    }
}

Reference: https://segmentfault.com/a/1190000003797291

170. Two Sum III – Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

思路: 题目不难,用个hashmap来解,注意可能会出现重复数字. hashMap中村数字跟出现的次数,
复杂度: 插入O(n), 查找O(1)

public class TwoSum {
    HashMap<Integer, Integer> map;

    public TwoSum (){
        map = new HashMap<>();
    }

    // Add the number to an internal data structure.
    public void add(int number) {
        if (map.containsKey(number)) {
            map.put(number, map.get(number) + 1);
        } else {
            map.put(number, 1);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (int key: map.keySet()) {
            int target = value - key;
            if (key == target && map.get(target) > 1) {
                return true;
            } else if (key != target && map.containsKey(target)) {
                return true;
            }
        }
        return false;
    }
}

438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:

Input:
s: “abab” p: “ab”

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.

思路: 这个题目是求给定的pattern的anagram,在给定的字符串中出现的位置; 需要借助两个数组, 一个是给定的pattern数组,用来存pattern中各个字符的出现次数。 另一个长度等同于pattern的滑动窗口,当前window下的各个字符的出现次数。当window遍历给定的字符s的时候,做一下几件事情: 1. window中前一个坐标对应的字符的次数-1; window中新加进来的字符的次数+1. 然后比较当前window下的anagram跟pattern 是否相同。

复杂度: 比较anagram O(1), 遍历O(n).

public class Solution {
    public List&lt;Integer&gt; findAnagrams(String s, String p) {
        List&lt;Integer&gt; res = new ArrayList&lt;&gt;();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return res;
        if (s.length() &lt; p.length()) return res;
        int[] pattern = new int[26];
        int[] window = new int[26];
        int pLen = p.length();

        for (int i = 0; i &lt; pLen; i++) {
            int pIdx = p.charAt(i) - 'a';
            int sIdx = s.charAt(i) - 'a';
            pattern[pIdx]++;
            window[sIdx]++;
        }
        if (isAnagram(window, pattern)) res.add(0);
        for (int i = pLen; i &lt; s.length(); i++) {
            int preIdx = i - pLen;
            window[s.charAt(preIdx) - 'a']--;
            window[s.charAt(i) - 'a']++;
            if (isAnagram(window, pattern)) res.add(i - pLen + 1);
        }
        return res;
    }
    public boolean isAnagram(int[] window, int[] pattern) {
        for (int i = 0; i &lt; pattern.length; i++) {
            if(window[i] != pattern[i]) return false;
        }
        return true;
    }
}

20. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

思路: 建是否括号匹配, 可以用stack来做.
1. 遍历给定的字符串,针对每个字符char, 当char等于'(‘,”{“,'[‘的时候,把char压入stack.
2. 当char等于’)’,’}’,’]’的时候,把stack栈顶元素pop出来,跟char比较看是否是一对。这里要注意几个情况的判断: 1. stack.isEmpty(), 为空的话,返回false. 2. sc == ‘)’ && stack.pop() != ‘(‘, 返回false.同理其他的几个括号.
3.最后还要判断下最后stack是否为空. 不为空,返回false。

public class Solution {
    public boolean isValid(String s) {
        if (s == null || s.length() == 0) return true;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            Character sc = s.charAt(i);
            if (s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '[') {
                stack.push(sc);
            }
            if (s.charAt(i) == ')' || s.charAt(i) == '}' || s.charAt(i) == ']') {
                if (stack.isEmpty()) return false;
                if (sc == ')' && stack.pop() != '(') return false;
                if (sc == '}' && stack.pop() != '{') return false;
                if (sc == ']' && stack.pop() != '[') return false;
            }
        }
        return stack.isEmpty();

    }
}

LeetCode Bit题目汇总整理

136. Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
思路:利用异或的性质,相同位异或为0,不同异或为1.

public class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
            res = res ^ nums[i];
        }
        return res;
    }
}

371. Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.
思路:位运算加法。
1.先检查edge case,如果有一个给定为0,就返回另一个的值.
2. 对于输入的a,b 如果不考虑进位的话,做加法求和等同于a XOR b, 例如1+0=1,1+1=0;1+0=1.
3. 对于进位运算,当相加两数都为1才进位,进位可以表示为carry = (a and b) << 1. 进位,就左移1位。
4. 最后 a + b可以表示为: (a XOR b) + (a AND b) << 1, 由于可能产生进位,所以要递归调用处理进位。

public class Solution {
    public int getSum(int a, int b) {
        if (b == 0) return a;
        int sum = a ^ b;
        int carry = (a & b) << 1;
        return getSum(sum, carry);
    }
}

231. Power of Two
Given an integer, write a function to determine if it is a power of two.
思路: 2次幂的特征就是数字中只有一个1. k次幂就是相当于向左移动了k位, 那么这个数N-1后,第k位变为0,从第k-1位到最后一位都是1. 那么N & (N-1) == 0。 我们可以用这个性质来判断这个数是否是2的次幂.
思路2:我们还可以连续对2做除法,直到判断最后是否为1.

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

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 0) return false;
        if (n == 1) return true;
        while( n % 2 == 0) {
            n = n / 2;
            if (n == 1){
                return true;
            }
        }
        return false;
    }
}

231. Power of Four
Given an integer (signed 32 bits), write a function to check whether it is a power of 4.
思路: 直接方法就是不停的跟4整除, 看最后是否为1.
bit方法,4次方就是1向左移动两位,4次幂中1只出现在奇数位,也就是二进制数从右边起开始,1,3,5,…奇数位都为1. 其16进制表示为0x55555555, 那么如果(num & 0x55555555! != 0,肯定不是4次幂,这里我们先去除不是2次幂的,然后去除不是4次幂的。

public class Solution {
    public boolean isPowerOfFour(int num) {
       if (num <= 0) return false;
       return ((num&(num-1)) == 0) && ((num & 0x55555555) != 0 );
    }
}

191. Number of 1 Bits
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,就累加,然后整个数字右移1位(注意要用无符号右移>>>). 直到最后为0,循环停止。

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

190. Reverse Bits
Reverse bits of a given 32 bits unsigned integer.

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

思路: 32位无符号二进制翻转,大概思路就是对于给定数,从低位i开始,翻转后就是我们把i对应的数字放到31-i位上面。 大概分几步:1. 将翻转的数n跟1做&运算,取最低位的数. 2.将这个数左移到31-i位置上面. 3. 将翻转的结果放到result变量 4. n 无符号右移1位,取下一个数

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int reverse = 0;
        for (int i = 0; i < 32; i++) {
            int tmp = n & 1;
            int reverseTmp = tmp << (31 - i);
            reverse = reverse | reverseTmp;
            n = n >>> 1;
        }
        return reverse;
    }
}

169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
思路: 投票算法,用一个count表示出现次数,candidate表示这个众数,如果candidate跟当前数相同,则count加1,否则count减一。如果count为0情况,那么candidate就选当前数。最后返回的candidate就为众数。

public class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int ret = 0;
        for (int num : nums) {
            if (count == 0) {
                ret = num;
            } 
            if (ret == num) {
                count++;
            } else {
                count--;
            }
        }
        return ret;
    }
}

389. Find the Difference
Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

思路: 利用XOR性质,把s中所有字符代表的char数值XOR,跟t中所有字符代表的char数值XOR, 那么结果就是不同的那个字母的char值。

public class Solution {
    public char findTheDifference(String s, String t) {
        char res = 0;
        for (int i = 0; i < s.length(); i++) {
            res = (char)(res ^ s.charAt(i));
        }
        for (int j = 0; j < t.length(); j++) {
            res = (char)(res ^ t.charAt(j));
        }
        return res;
    }
}

405. Convert a Number to Hexadecimal
Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.
思路: 十进制转十六进制。 可以借鉴十进制转二进制方法,对2做mod,求得的余数反向输出。 这里我们可以将输入数字的每4个bit作为一个单位进行转换。

public class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        while( num != 0) {
            sb.append(hex[num & 15]);
            num = num >>> 4;
        } 
        sb.reverse();
        return sb.toString();
    }
}

404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

3

/ \
9 20
/ \
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

思路: 求所有左叶子节点的和,我们需要判断该节点是否是叶子节点,如果是就加和。判断left leaf的要求就是: parent.left = cur&&cur.left==null&&cur.right==null; 这里我们可以用in-order traversal的方法去记录parent,在cur入栈之前先判断parent.left!=null, 则parent=cur; 等到pop的时候,我们就去查left node的条件就可以加入sum。

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int sum = 0;
        TreeNode cur = root;
        TreeNode parent = root;
        Stack<TreeNode> stack = new Stack<>();
        while(cur!= null || !stack.isEmpty()) {
            if (cur != null) {
                if (cur.left != null){
                     parent = cur;
                }
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (parent.left == cur && cur.left == null && cur.right == null) {
                    sum += cur.val;
                }
                cur = cur.right;
            }
        }
        return sum;
    }
}