剑指Offer之Java算法习题精讲数组与二叉树

/**

  * Definition for a binary tree node.

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode() {}

  *     TreeNode(int val) { this.val = val; }

  *     TreeNode(int val, TreeNode left, TreeNode right) {

  *         this.val = val;

  *         this.left = left;

  *         this.right = right;

  *     }

  * }

  */

class Solution {

     public TreeNode sortedArrayToBST( int [] nums) {

         return method(nums, 0 ,nums.length- 1 );

     }

     public TreeNode method( int [] nums, int lf, int rg){

         if (lf>rg){

             return null ;

         }

         int mid = lf+(rg-lf)/ 2 ;

         TreeNode root = new TreeNode(nums[mid]);

         root.left = method(nums,lf,mid- 1 );

         root.right = method(nums,mid+ 1 ,rg);

         return root;       

     }

}

class Solution {

     public boolean containsDuplicate( int [] nums) {

        HashSet<Integer> set = new HashSet<Integer>();

        for ( int i = 0 ;i<nums.length;i++){

            if (!set.add(nums[i])){

                return true ;

            }

            set.add(nums[i]);

        }

        return false ;

     }

}

class Solution {

     public boolean containsNearbyDuplicate( int [] nums, int k) {

         Map<Integer, Integer> map = new HashMap<Integer, Integer>();

         int length = nums.length;

         for ( int i = 0 ; i < length; i++) {

             int num = nums[i];

             if (map.containsKey(num) && i - map.get(num) <= k) {

                 return true ;

             }

             map.put(num, i);

         }

         return false ;

     }

}