LeetCode Top100 Liked Questions

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i]<0?-nums[i]:nums[i];
            if(nums[x-1]>0){
                nums[x-1]= -nums[x-1];
            }
        }
        List<Integer> re = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){
                re.add(i+1);
            }
        }
        return re;
    }

461.Hamming Distance　　

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.Given two integers x and y, calculate the Hamming distance.

Note:0 ≤ x, y < 2³¹.

Example:

Input: x = 1, y = 4

Output: 2

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

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

public int hammingDistance(int x, int y) {//位运算
        int n = x^y;
        int re = 0;
        //计算整数二进制中1的个数
        while(0!=n){
            n=n&(n-1);
            re++;
        }
        return re;
    }

538.Convert BST to Greater Tree

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   
           2     13

Output: The root of a Greater Tree like this:
             18
            /   
          20     13

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {//树
        if(null!=root){
            TreeNode right = convertBST(root.right);
            root.val+=sum;
            sum = root.val;
            TreeNode left = convertBST(root.left);
        }
        return root;
    }
}

543.Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

class Solution {
    int re;
    public int diameterOfBinaryTree(TreeNode root) {//树的深度 递归
        re =0;
        maxDepth(root);
        return re;
    }
    public int maxDepth(TreeNode root) {
        if(null==root){
            return 0;
        }
        int ld=maxDepth(root.left);
        int lr = maxDepth(root.right);
        int d = ld>lr?(ld+1):(lr+1);
        re =re>(ld+lr)?re:(ld+lr);
        return d;
    }
}

617.Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         /                        /                             
        3   2                     1   3                        
       /                                                    
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / 
	   4   5
	  /     
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {//树 递归
        if(null==t1&&null==t2){
            return null;
        }
        if(null==t1){
            return t2;
        }
        if(null==t2){
            return t1;
        }
        TreeNode left=mergeTrees(t1.left,t2.left);
        TreeNode right = mergeTrees(t1.right,t2.right);
        TreeNode node = new TreeNode(t1.val+t2.val);
        node.left=left;
        node.right=right;
        return node;
    }

简洁写法

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        if (t2 == null)
            return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }

非递归方法

public class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null)
            return t2;
        Stack < TreeNode[] > stack = new Stack < > ();
        stack.push(new TreeNode[] {t1, t2});
        while (!stack.isEmpty()) {
            TreeNode[] t = stack.pop();
            if (t[0] == null || t[1] == null) {
                continue;
            }
            t[0].val += t[1].val;
            if (t[0].left == null) {
                t[0].left = t[1].left;
            } else {
                stack.push(new TreeNode[] {t[0].left, t[1].left});
            }
            if (t[0].right == null) {
                t[0].right = t[1].right;
            } else {
                stack.push(new TreeNode[] {t[0].right, t[1].right});
            }
        }
        return t1;
    }
}

771. Jewels and Stones

　　https://www.cnblogs.com/zhacai/p/10429670.html easy　　

7.Reverse Integer　　

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

public int reverse(int x) {
       String str= String.valueOf(x);
        StringBuffer strb;
        int re=0;
        if('-'==str.charAt(0)){
            strb = new StringBuffer(str.substring(1,str.length())).reverse();
            strb.insert(0,"-");
        }
        else {
            strb= new StringBuffer(str).reverse();
        }
        try{
            re =Integer.valueOf(strb.toString());
        }catch (Exception e){

        }
        return re;
    }

使用数学方法的优解

public int reverse(int x) {
       int re = 0;
        while(0!=x){
            int temp = re * 10 + x % 10;
            if(temp / 10 != re)//如果整数不溢出显然相等
                return 0;
            re = temp;
            x /= 10;
        }
        return re;
    }