leetCode编程题

(1)给定一个字符串和一个变量，用z型读取变量,其中rows为给定的数字，可以视为定义多少列

思路：先想象字符串安装z字排列，然后用StringBuffer一行行的读取。

public static void main(String[] args) {
        String result =convert("abcdefg",3);
        System.out.println(result);
    }

    private static String convert(String word, int rows) {
        char[] arr = word.toCharArray();
        int len = word.length();
        StringBuffer[] sb = new StringBuffer[rows];
        for(int i=0;i<rows;i++){
            sb[i] = new StringBuffer();
        }
        int j=0;
        while(j<len){ //退出条件---当所有的元素都读取完
            for(int idx=0;idx<rows&&j<len;idx++){//垂直的读取，放进相应的stringBuffer中,idx读取三个之后不符合
                sb[idx].append(arr[j++]);
            }
            for(int idy=rows-2;idy>=1&&j<len;idy--){//在斜线上只能吃到1位置，其它的为垂直的读取。
                sb[idy].append(arr[j++]);
            }
        }
        for(int i=1;i<rows;i++){ //把其它的sb.append到stringBuffer中
            sb[0].append(sb[i]);
        }
        return sb[0].toString();
    }

(2)给定一个数组 nums = [2, 7, 11, 15], target = 9,因为 nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

思路：1.可以排序之后用两个指针，大则减尾巴，小则加头
2.用一个map集合放（nums[i] , i）,通过key也即是值来查找位置

//这个题求的是返回对应值的下标，所以应该得记录下标
      public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = find(nums,target);
        System.out.println(nums[result[0]]+" "+nums[result[1]]);
        
    }

    private static int[] find(int[] nums, int target) {
        //用一个数组来记录两个数的位置
        int[] a = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                a[1] = i;
                a[0]=map.get(target-nums[i]);
            }
            //value作为key,位置作为value
            map.put(nums[i], i);
        }
        return a;
    }

(3)给定一个数组，把数组内的数排列成最小的数

思路：把AB和BA进行比较，比较大小，取小的那个

    public static void main(String[] args) {
        int[] arr = {3,32,45,312};
        MaxNumberFunction(arr);
    }

    private static void MaxNumberFunction(int[] arr) {
        String s="";  //用来装字符串
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<arr.length;i++){
            list.add(arr[i]);  
        }
        //一般都是这种写法，注意sort的写法---new匿名类重写compare方法
        Collections.sort(list,new Comparator<Integer>() {
            public int compare(Integer int1, Integer int2) {
                 String s1 = int1 + "" + int2;               
                 String s2 = int2 + "" + int1; 
                return s1.compareTo(s2);
            }
        });
        
        for(int result:list){
            s+=result;
        }
        System.out.println(s);
    }

(4) 测试一副牌是否能组成顺子，其中0可以替换任何的元素

思路：先统计0的个数，然后计算两个牌之间的间隔

    public static void main(String[] args) {
        int[] array={0,4,6,7,0};
        System.out.println(isContinuous(array));
    }
    private static boolean isContinuous(int[] arrays) {
        if(arrays==null) return false; 
        int countOfZero = 0;
        Arrays.sort(arrays);
        for(int i = 0 ;i<arrays.length;i++){
            if(arrays[i]==0){
                countOfZero++;
            }
        }
        int small=countOfZero;
        int span=0;
        for(int j=small;j<arrays.length-1;j++){
            //有对子的话则表明这牌不是顺子
            if(arrays[j+1]==arrays[j]) return false;
            span+=(arrays[j+1]-arrays[j]-1);
        }
        return span>countOfZero?false:true;
    }

(5) 输入"abcacbbb"，最长串是"abc",长度是3

输入"bbbbb"，最长串是"b",长度是1
输入"pwwkew"，最长串是"wke",长度是3

思路：用map集合统计<num[i]:i>用于获取位置，当map的key相同的时候会进行覆盖，
然后得到关键j，用于抛弃前面的序列

public static void main(String[] args) {
        String s = "ababac";
        int i =lengthOfLongestSubstring(s);
        System.out.println(i);
    }

    private static int  lengthOfLongestSubstring(String s) {
        if(s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for(int i =0,j=0;i<s.length();++i){
            if(map.containsKey(s.charAt(i))){
                //eg:ababac其中j的取值用于抛弃前面的值
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
             //在map中相同的key会进行更新
             map.put(s.charAt(i),i);
             int k =i-j+1;
             max = Math.max(max,k);
        }
         return max;
    }

(6)给出一个 string 串 s，找到里面最长的回文串。你可以假设 s 最长的长度是 1000。

思路：回文串分为两种，奇数回文和偶数回文。
1.判断最长的回文，则是一个（i,i）开始，一个是（i,i+1）开始。
2.判断一个数是不是回文串，则一个从(mid,mid）一个从(mid,mid）开始，也可用数组首尾比较法。

    //全局变量，等到输出的
    int begin;
    int maxlength;
    public static void main(String[] args) {
        test6 t6 =new test6();
        String str="abcbc";
        String solution = t6.Solution(str);
        System.out.println(solution);
    }
    public String Solution(String str){
        if(str==null) return null;
        if(str.length()<2) return str;
        for(int i=0;i<str.length()-1;i++){
            //奇数回文
            huiwen(str,i,i);
            //偶数回文
            huiwen(str,i,i+1);
        }   
        return str.substring(begin, begin + maxlength);
    }

    private void huiwen(String str, int j, int k) {
        while(j>=0&&k<str.length()&&(str.charAt(j)==str.charAt(k))){
            j--;
            k++;
        }
        //这一步其实有求MAX的意思了
        if(maxlength<k-j-1){
            begin=j+1;
            maxlength=k-j-1;
        }
    }

(7)示例1： x= 123, return 321 示例2： x= -123, return -321

思路:就是求余后除10，不停的往前移动求和

public static void main(String[] args) {
        int reverse = reverse(321);
        System.out.println(reverse);
    }
    public static int reverse(int x)
    {
        int result=0;
        while(x!=0){
         int tail = x%10;
        result = result*10+tail;
         //在中间做进一步的判断
              if((result-tail)%10 !=0) return 0;
            x/=10;
        }
        return result;
    }

(8) 判断一个数字是否是回文数

示例一： 12321 ，rev 为 123，x 为 12，x==rev/10=12，返回 true
示例一： 123321 ，rev 为 123，x 为 123，x==rev=123，返回 true

思路:跳出while时，rev定大于x了，所以是偶个数的话那个rev=x,后者rev/10等于x

    public static void main(String[] args) {
        test8  t8 = new test8();
        boolean palindrome = t8.isPalindrome(123321);
        System.out.println(palindrome);
    }
    public boolean isPalindrome(int x){
        if(x<0||(x!=0&&x%10==0)) return false;
        int rev=0;
        while(x>rev){
            rev=rev*10+x%10;
            x/=10;
        }
        //这一步是判断数组为奇数位或偶数位
        return (rev==x||rev/10==x);
    }

(8-1) 判断一个字符串是否是回文

    public static  boolean isPalindrome(String str){
        char[] arr = str.toCharArray();
        int len = arr.length-1;
        int mid= len/2;
        return huiwwen(arr,mid,mid) || huiwwen(arr,mid,mid+1);
    }
//判断一个数是回文的情况，要从中间开始搜索，如果中间都不是，那肯定就不是了。
    private  static boolean huiwwen(char[] arr, int mid, int mid2) {
        while(mid>0&&mid2<arr.length&&arr[mid]==arr[mid2]){
            mid--;
            mid2++;
        }
        if((arr.length-1) == (mid2-mid)){
            return true;
        }
        return false;
    }

(9)求能装多少水的问min(line1,line2)*|x2-x1|，也类似于牛客的柱状图求解

思路：从外面往里面缩，遇到短的就缩短

    public static void main(String[] args) {
        int[] nums={4,9,6,7,2,3,5};
        int maxArea = getMaxArea(nums);
        System.out.println(maxArea);
    }
    public static int getMaxArea(int[] height){
        int start=0;
        int end = height.length-1;
        int maxArea=0;
        while(start<end){
            maxArea = Math.max(maxArea, Math.min(height[start], height[end])*(end-start));
            if(height[start]<height[end]){
                start++;
            }else {
                end--;
            }
        }
        return maxArea;
    }

(10)给一个整数，将其转换为罗马数字。输入范围：1~3999

    private static String solution(int nums){
        int a=nums/1000;
        int b=(nums/100)%10;
        int c=(nums/10)%10;
        int d=nums%10;
        String M[] = {"", "M", "MM", "MMM"};
        String C[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        String X[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        String I[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return M[a]+C[b]+X[c]+I[d];
    }

(11)写一个函数来查找字符串数组中最长的公共前缀字符串。

思路：假设第一个为最长子串，然后与其它的字符串匹配，不匹配则缩短

    public static void main(String[] args) {
        String[] str={"abc","abcdd","abce","abcj"};
        String longestCommonPrefix = longestCommonPrefix(str);
        System.out.println(longestCommonPrefix);
    }
    public static String longestCommonPrefix(String[] str){
        String pre = str[0];  //假设str[0]位最长公共子串，这一步肯定正确的
        int i =0;
        while(i<str.length){
            //没有找到的话，即可把pre缩短
            if(str[i].indexOf(pre)!=0){
                pre=pre.substring(0, pre.length()-1);
            }
            i++;
        }
        return pre;
    }

(12)给一个排好序的数组,删除重复的数字，使得每个数字只能出现一次，并返回新的长度。

    public static void main(String[] args) {
        int[] nums={1,2,3,4,5,5,6,7,7,7,8};
        int removeNums = removeNums(nums);
        System.out.println(removeNums);
    }

    private static int removeNums(int[] nums) {
        List<Integer> list = new ArrayList<Integer>();
        for(int i=1;i<nums.length;i++) {
            if(nums[i]!=nums[i-1]) {
                list.add(nums[i]);
            }
        }
        return list.size()+1;
    }

(13) 给一个有 n 个整数的数组 S，找到 S 中的三个数，使得这三个数的和最接近传入的target(目标数)。并返回这三个数的 sum(和)。

思路：假设三个数组成i;start=i+1;end=nums.length-1;

    public static void main(String[] args) {
    int[]S = {-1, 2, 1, -4};
    int target = 3;
    int threeNumsCloset = threeNumsCloset(S,target);
    System.out.println(threeNumsCloset);
    }
    public static int threeNumsCloset(int[] nums,int target){
        if(nums.length<3) {return 0;}
        Arrays.sort(nums);
        //刚开始设置一个初始化值
        int result=nums[0]+nums[2]+nums[nums.length-1];
        int ClosetResult=0;
        for(int i=0;i<nums.length-2;i++){
            int end=nums.length-1;
            int start=i+1;
            //关键在这里，固定某个i，在start在[i--end]之间来回穿梭
            //在开始的大区间再逐步的缩小区间
            while(start<end){
            int newReuslt = nums[start]+nums[i]+nums[end];
            if(newReuslt>target){
                end--;
            }else{
                start++;
            }
            if((Math.abs(newReuslt-target)< Math.abs(result-target))){
                ClosetResult=newReuslt;
            }
        }
    }
            
        return ClosetResult;
    }

(14) 给定一个链表，从链表的末尾删除第n个节点并返回它的头。

思路：一个快指针和一个慢指针，快指针先走K,然后快慢指针一块走

    public static  ListNode removeNthFromEnd(ListNode headnode,int k){
        ListNode save= headNode;
        ListNode printNode = headNode;
        ListNode fastNode = headNode;
        for(int i=0;i<k;i++){
            fastNode= fastNode.nextNode;
        }
        while(fastNode!=null){
            fastNode =fastNode.nextNode;
            printNode =printNode.nextNode;
        }
        printNode.nextNode = printNode.nextNode.nextNode;
        return save;
    }

(15)给定一个只包含字符'（'，'）'，'{'，'}'，'['和']'的字符串，确定输入字符串是否是有效的

思路：用if elseif的形式，获取一个就在栈中加入相反的一个

    public static void main(String[] args) {
        String str = "()([])({}[][]){}()";
        
        System.out.println(isValid(str));
    }
    public static  boolean isValid(String s){
        char[] arr = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        for(char c :arr ){
            if(c=='('){
                stack.push(')');
            }
            else if(c=='{'){
                stack.push('}');
            }
            else if(c=='['){
                stack.push(']');
            }
            //假如不是({[，那么就是它的反方向，用栈，越在顶层的越浅
            else if(stack.isEmpty() || stack.pop()!=c){
                return false;
            }
        }
        return stack.isEmpty();
    }

(16) 给定 n 对圆括号，写一个函数来生成正确形式的括号的所有组合。

思路：当open<max的时候只能添加（，close < open时即添加）

    public static void main(String[] args) {
        List<String> list = generateParenthesis(3);
        for(String s :list){
            System.out.println(s);
        }
    }
    public static List<String> generateParenthesis(int n ){
        List<String> list = new ArrayList<String>();
        backtrack(list,"",0,0,n);
        return list;
    }

    private static void backtrack(List<String> list, String str, int open, int close, int n) {
        if(str.length()==n*2){
            list.add(str);
            return;
        }
        //当 open<max 时可以添加 （，并 open+1
        if(open < n)
            backtrack(list, str+"(", open+1, close, n);
        //当 close < open 时可以添加 ）,并 close+1
        if(close < open)
            backtrack(list, str+")", open, close+1, n);
    }

(17)给出 1->2->3->4 ，你应该返回的链表是 2->1->4->3。

    public ListNode swapPairs(ListNode node){
        if((node==null) || (node.next==null)) return null;
        //保留node节点的下一个节点
        ListNode head = node.next;
        //通过递归回去node的下一个节点
        node.next =  swapPairs(node.next.next);
        //把node变成第二个节点
        head.next = node;
        //返回头节点
        return head;
    }

(19)返回字符串 needle 在字符串 haystack 中最先出现的 index(序号)，如果 haystack 中不包含 needle，就返回 -1。

public static int strStr(String haystack, String needle) {
        if(needle==null) return haystack.length();
        char[] arr = haystack.toCharArray();
        char[] arr2 = needle.toCharArray();
        for(int i=0,j=0;i<arr.length-1;i++){
            //一步步的递进
            while(arr[i]==arr2[j]){
                j++;
                i++;
            //只有当j完全等于needle的大小时才符合
            if(j==arr2.length){
                return i-j;
              }
            }
         //否则把j进行清零的处理，也即是返回needle的起点
            j=0;
        }
        return -1;
    }

(20) 实现 nextPermutation 方法，这个方法把输入的数字 a 中的每个数字重新排序得到一个恰好比当前数字大的数字 b，若是此数字已经最大了，则把数字排列。

思路：从右到左遍历第一个反序，eg:1,5,2,4,3 取到了2，然后后面reverse把（i+1）即3.4进行发转

public static void main(String[] args) {
        int[] nums ={1,5,2,4,3};
        nextPermutation(nums);
    }
    public static void nextPermutation(int[] A) {
        if(A==null || A.length<1) return ;
        //15243 --取到4；12345
        //下面有A[i+1]，所以取到length-2；
        int i=A.length-2;
        //注意这种不停的递归的方法，得用while
        while(i>=0 && A[i]>=A[i+1]) i--; //这一步取到2
        if(i>=0){
            int j = A.length-1;
            //拿最后一个与取出来的2进行交换
            while(A[j]<=A[i]) j--;
            swap(A,i,j);
        }
        //若while都跳过的话，则反转数字，在上面的i--中
        //若是为顺序排列的话，则能把i减到-1；所以调换是从[0,A.length-1];
        reverse(A,i+1,A.length-1);
        for(int k :A){
            System.out.print(k+" ");
        }
    }
    
    private static void swap(int[] A, int i, int j) {
         int tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
    }
    private static void reverse(int[] a, int i, int j) {
        while(i<j){
            swap(a,i++,j--);
        }
    }

(21)假设有一个升序的数组以某个未知的支点旋转。 （例如，0 1 2 3 4 5 6 7 可以变成 4 5 6 7 0 1 2）

public void search(int[] nums,int target){
    StringBuffer sb = new StringBuffer();
    for(int i :nums ) sb.append(i);
    String value = new String (sb);
    String[] arr = {value.substring(0,target-1),value.substring(target,value.length-1)};
    StringBuffer str= new StringBuffer();
    for(String s: arrs){
                //先逐个对String进行逆排序
        str.append(reverse(s));
    }
        //对生成的字符串进行全排序
    String result = reverse(new String(str));
}
    //注意是String的调换顺序，i与arr.length-i-1之间
    public String reverse(String str){
        if(str==null) return null;
        char[] arr = str.toCharArrays();
        for(int i=0;i<(arr.length+1)/2;i++){
        //发现数组长度好与i的关系也是很关键的
            char temp = arr[i];
            arr[i] = arr[arr.length-i-1];
            arr[arr.length-i-1]=temp;
        }
        return String.valueOf(arr);
    }

(22)给定以升序排序的整数数组，找到给定目标值(target)的开始和结束位置。也即是重复数组中，找到某一个数的开始与结束的位置

    public int[] searchRange (int[] nums ,int target){
        int[] result = new int[2];
        result[0] = FindFirst(nums,target);
        result[1] = FindLast(nums,target);
        return result;
    } 
  //识别的规则为一个不停的向前方靠
    public int[] FindFirst(int[] nums , int target){
        int idx=0;
        int statrt=0;
        int end = nums.length -1;
        while(start<=end){
            int mid = (start+end)/2;
            if(nums[mid]>=target){
                end = mid-1;
            }else{
                start=mid+1;
            }
            if(nums[mid] = target ) idx=mid;
        }
    }
  //一个不停的向后方靠
        public int[] FindLast(int[] nums , int target){
        int idx=0;
        int statrt=0;
        int end = nums.length -1;
        while(start<=end){
            int mid = (start+end)/2;
            if(nums[mid]=<target){
                start=mid+1;    
            }else{
                end = mid-1;
            }
            if(nums[mid] = target ) idx=mid;
        }
    }

(23) 查找数组中的某一个数，用二分查找法

    public static int searchInsert(int[] nums, int target) {
        int start=0;
        int end = nums.length-1;
        for(int i=0;i<end;i++){
            int mid = (start+end)/2;
            if(nums[mid]==target){ return mid;}
            else if (nums[mid]<target){
                start=mid+1;
            }else {
                end=mid-1;
            }
        }
        return start;
    }

(24)判断数独板是否符合数独的规则，数独板可以是部分填充的，其中空单元填充字符'.'代替。

    public boolean isValidSudoku(char[][] board){
        Set seen = new HashSet<Charaset>();
        for(int i=0;i<9;i++){
            for(int i=0;i<9;i++){
                if(board[i][j]!="."){
                    String b ="("+board[i][j]+")";
                    //根据set集合元素不能相同
                    if(!seen.add(b+i) || !seen.add(j+b) ||!seen.add(i/3+b+j/3)){
                        return false;
                    }
                }               
            }
        }
    
    }

(25)关于数组的读法

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 比如4->5,读出来是"1个1，1个2，2个1"，提取其中的数字就是 111221 。

思路：用递归，从1（return 1）开始到目标数，然后用count（默认1）来统计arr[i]==a[i++]出现的次数

    public String countAndSay(int n ){
        if(n==1) return "1";
        String str = countAndSay(n-1)+"*";
        char[] arr = str.toCharArray();
        String s = "";
        int count=1;
        for(int i=0;i<arr.length-1;i++){
            //假如“*”是在最后比较的时候，能计算准确
            if(arr[i]==arr[i+1]){
                count++;
            }else{
                //这里用s加主要是为了变成字符串
                s=s+count+arr[i];
                count=1;
            }
            
        }
        return s;
    }

(26) 例如输入 {2,3,6,7} 求数组种那几个数能组成target=7的数组，可包含重复值。

    public List<List<Integer>> combinationSum(int[] candidates,int target){
        Arrays.sort(candidates);
        List<List<Integer>> result = new  List<List<Integer>>();
        getResult(result,new ArrayList<Integer>(),candidates,target,0);
        return result;
    }

    private static void getResult(List<List<Integer>> result, List<Integer> cur, int candidates[], int target, int start){
        if(target>0){
            for(int i=start;i<candidates.length && target>=candidates[i];i++){
                cur.add(candidates[i]);
                //重新传入i，用于不跳过自己
                getResult(result,cur,candidates,target-candidates[i],i);
                cur.remove(cur.size()-1);
            }
        }else if(target==0){
            result.add(new ArrayList<Integer>(cur));
        }
    }

(27) 给定字符串 hello world 返回第一个空格的位置

    public int lengthOfLastWord(String s){
        return s.trim().length-s.trim().lastIndexOf(" ")-1;
    }

(29)实现大数的相乘，主要用String进行乘法的判断

    public static void main(String[] args) {
        String multiply = multiply("-9967696","2");
        System.out.println(multiply);
    }   
    public static String multiply(String num1, String num2){
        if(num1.equals("0") ||num2.equals("0") ) return "0";
        boolean flag=false;
        if(num1.substring(0, 1).equals("-") && num2.substring(0, 1).equals("-") ){
            num1=num1.substring(1, num1.length());
            num2=num2.substring(1, num2.length());
            flag=true;
        }else if(num1.substring(0, 1).equals("-")) {
            num1=num1.substring(1, num1.length());
            flag=false;
        }else if(num2.substring(0, 1).equals("-")) {
            num2=num2.substring(1, num2.length());
            flag=false;
        }
        int len1 = num1.length();
        int len2 = num2.length();
        int[] produces= new int[len1+len2];
        for(int i =len1-1;i>=0;i--){
            for(int j =len2-1;j>=0;j--){
                //求出index与j和i之间的关系是关键
                int index=len1+len2-i-j-2;
                //从char变成int的关键,把最后两个数的乘积乘出来
                produces[index]+=(num1.charAt(i)-'0')*(num2.charAt(j)-'0');
                //这里产生进位到index+1
                produces[index+1]+=produces[index]/10;
                //对第一个数进行取余后写回
                produces[index]%=10;
            }
        }
        StringBuilder strbuf = new StringBuilder();
        if(!flag){
            strbuf.append("-");
        }
        //用于出除前面的0
        for(int i=produces.length-1;i>=0;i--){
            if(strbuf.length()==0 && produces[i]==0) continue;
            strbuf.append(produces[i]);
        }
        return strbuf.toString();
    }

(30)例如输入{1,2,3,6}，返回此数组的全部排列方式

      public void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums){
        if(tempList.size() == nums.length){
            list.add(new ArrayList<Integer>(tempList));
        }else{
            for(int i=0;i<nums.length;i++){
                 //如果已经有了这个元素,则跳过这次循环
                if(tempList.contain(nums[i])) continue;
                tempList.add(num[i]);
                 //下面三步一起看,用到了递归，递归缩小规模
                backtrack(list,tempList,nums);
                 //用于把整个tempList清空的，递归后会执行三次remove
                tempList.remove(tempList.size()-1);
            }
        }
      }

(31)给出一个可以包含重复数字的数字集，返回所有可能的不重复排列组合。

如：[1,1,2] 有如下的排列组合：
[1,1,2],
[1,2,1],
[2,1,1]

    public List<List<Integer>> permuteUnique(int[] nums){
         List<List<Integer>> res = new ArrayList<List<Integer>>();
         if(nums==null || nums.length==0) return res;
         boolean[] used = new boolean[nums.length];
         List<Integer> list = new ArrayList<Integer>();
          Arrays.sort(nums);
          dfs(nums,used,list,res);
          return res;
    }
    private  void dfs(int[] nums,boolean[] used,List<Integer> list,List<List<Integrt>> res){
        if(list.size()==nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i=0;i<nums;i++){
            if(used[i]) continue;
            if(i>0&&nums[i-1] == nums[i] &&!user[i-1]) continue;
            used[i]=true;
            list.add(nums[i]);
            dfs(nums,used,list,res);
            used[i] = false;
            list.remove(list.size()-1);
        }
    
    }

(32)把一个二维数组顺时针旋转90度

public void rotate(int[][] matrix){
    int[][] matrix2 = new int[matrix.length][matrix.length];
    //关键是发现二维数组与其旋转90度后数位置的关系
     for(int i=0;i<matrix.length;i++){
         for(int j=0;j<matrix.length;j++){
            matrix2[j][matrix.length-i-1] = matrix[i][j];
        }
     }
     for(int i=0;i<matrix2.length;i++){
         for(int j=0;j<matrix2.length;j++){
            matrix[i][j]=matrix2[i][j];
        }
     }
}

(33) 例如，给出： ["eat", "tea", "tan", "ate", "nat", "bat"],

["ate", "eat","tea"],
["nat","tan"],
["bat"]

思路：把字符串线排序一次，再把单个的字符串再排序一次，用一个字母作为key，其它相同的作为value；

public List<List<String>> groupAnagrams(String[] strs){
    if(strs==null || strs.length ==0 ) return new ArrayList<List<String>>();
    Map<String,List<String>> map = HashMap<String,List<String>>();
    Arrays.sort(strs);
    for(String str:strs){
        char[] arr = str.toCharArrays();
        String sb = new String(arr);
        Arrays.sort(arr);
        //如果不包含的情况，那么添加一个新的ArrayList
        if(!map.containKey(value)){map.put(value,new ArrayList<String>());}
        map.get(value).add(sb);
    }
    //map.values()是获取map中的value
    return new ArrayList<List<String>(map.values())>
}

(34) 求一个数字x的n次方

    public double myPow(int x,int n ){
        if(n==0) return 1;
        if(n<0){
            n=-n;
            x=1/x;
        }
        return x%2==0?myPow(x,n/2),myPow(x,n/2)*x;
    }

(35) 输入几个区间，然后合并区间

     class Interval{
    int start;
    int end;
    Interval() {start=0;end=0;}
    Interval(int s,int e) {start=s;end=e;}
}
public class test40 {
    public static void main(String[] args) {
        List<Interval> intervals = new ArrayList<Interval>();
        intervals.add( new Interval(1,3));
        intervals.add( new Interval(2,6));
        intervals.add( new Interval(7,9));
        intervals.add( new Interval(8,12));
        List<Interval> merger = merger(intervals);
        for(Interval inte:merger){
            System.out.println(inte.start+"  "+inte.end);
        }
        
    }
    public  static List<Interval> merger( List<Interval> intervals){
        List<Interval> result = new LinkedList<Interval>();
        if(intervals == null || intervals.size()<1){
            return result;
        }
        Collections.sort(intervals,new Comparator<Interval>() {
            //对区间的start进行排序
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start -o2.start;
            }
        });
          Interval prev = null;
          //如果前一个的end,小于后一个的start，则表明两个区间是隔断的，那么把它放进人result
          //之后把这个item作为prev，如果下个item与这个prev有合区间的话，则扩大prev中的end属性
          //这时候prev指向item也即是修改result中的end
            for (Interval item : intervals) {
                if (prev == null || prev.end < item.start) {
                    result.add(item);
                    prev = item;
                } else if (prev.end < item.end) {
                    //prev也即是item的引用传递
                    prev.end = item.end;
                }
            }
            return result;
    }
}

(36) 给出两个二叉树，写一个方法判断这两个树是否相同。

思路：两个二叉树如果结构一致，并且每个节点有相同的值，则我们认为它们相同。

    public boolean isSameTree(TreeNode node1,TreeNode node2){
        if(node1==null && node2 == null) return true;
        if(node1==null || node2==null ) return false;
        if(node1.val==node2.val){
            return isSameTree(node1.left,node2.left) &&  isSameTree(node1.right,node2.right);
        }
    }

(37) 给出 1->2->3->4->5->NULL 和 k = 2,返回 4->5->1->2->3->NULL.

    class ListNode{
        int val;
        ListNode next;
        ListNode(int value){this.val =value;}
    } 
    
    public ListNode rotateRight(ListNode head ,int k ){
        if(k==0 || head==null) return head;
        ListNode thisNode = head ;
        ListNode returnNode = new ListNode(0);
        int x=1,n=1;
        while (thisNode.next!=null)
        {
            thisNode = thisNode.next;
            x++;
        }
        thisNode.next= head;
        while (thisNode.next!=null)
        {
            if(n==(x-k%x)){
                returnNode= thisNode.next.next;
                thisNode.next.next=null 
                return returnNode;
            }
            thisNode = thisNode.next;
            n++;
        }
        return returnNode;
    }

(38) 一个机器人在 m × n 的网格中的左上角（在下面示意图中标记 'Start' 的位置）。在同一时间点中，机器人只能向下或者向右走。机器人的目标是右下角（用 'Finish' 标记的位置）

    public static void main(String[] args) {
        int m=3;
        int n=3;
        int result = uniquePaths(m,n);
        System.out.println(result);
    }
    public static int uniquePaths(int m ,int n ){
        Integer[][] map = new Integer[m][n];
        for (int i = 0; i <m; i++) {
            map[i][0]=1;
        }
        for (int j = 0; j <n; j++) {
            map[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //在这里假定map[i][j]的生成方式，然后锁定一个，用另一个区遍历
                map[i][j]=map[i-1][j]+map[i][j-1];
            }
        }
        return map[m-1][n-1];
    }

(39) 现在如果我们给栅格中加入了障碍，那会有多少种不同的路径呢？在栅格中障碍标记为 1，空格标记为 0。

    public int uniquePathsWithObstacles(int[][] obstacleGrid){
        if(obstacleGrid.length==0) return 0;
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        //因为考虑到第一行或者第一列也存在有障碍的情况，所以不能都赋值1
        //需要判断
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(obstacleGrid[i][j]==1) obstacleGrid[i][j]=0；
                else if(i==0 && j==0 ) obstacleGrid[i][j]=1；
                else if(i==0) obstacleGrid[i][j]=obstacleGrid[i][j-1]*1;
                else if(j==0) obstacleGrid[i][j]=obstacleGrid[i-1][j]*1;
                else{
                    obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
                }
            }
        }
        return obstacleGrid[rows-1][cols-1];
    }

(40)关于动态规划中的路径选择问题

   ① 到第一行的格子只有一条路，所以到达的值 = 到左边格子的值 + 本格子的数
   ② 到第一列的格子只有一条路，所以到达的值 = 到上边格子的值 + 本格子的数
   ③ 到其他格子的方式简化为 两种，从左边来 和 从上面来 ，
          所以达到的值 = min(到左边格子的值,到上边格子的值) + 本格子的数

    public int minPathSum(int[][] grid) {
           //得到行列长度
           int m = grid.length, n = grid[0].length;
           for(int i = 0; i < m; i++){
                   for(int j = 0; j < n; j++){
                       //求出第一行第一列栅格的最小值
                       if(i == 0 && j != 0) grid[i][j] += grid[i][j-1];
                       if(i != 0 && j == 0) grid[i][j] += grid[i-1][j];
                       //其他栅格的最小值
                    if (i != 0 && j != 0) grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);

                   }
              }
              //返回终点的最小值
           return grid[m-1][n-1]; 
    }

(41) 给一个用数组表示的非负整数，加一并返回。假设数组除了 0 本身不会零打头（不会有 01，007 这样的数组）。

public static void main(String[] args) {
        int[] arr = {9,9,9};
        int[] plusOne = plusOne(arr);
        for(int i :plusOne ){
            System.out.println(i);
        }
    }
    public static int[] plusOne(int[] digits){
        int n = digits.length;
        //从最后一个变量起，若为9，则变为0，执行for的第二次为进位加一
        //若为999之类的，则过了这一步之后都为0了，那么在第0位加1表示进位
        for(int i=n-1;i>=0;i--){
            if(digits[i]<9){
                digits[i]++;
                return digits;  
            }   
            digits[i]=0;
        }
        //下面情况为for循环都不符合，则直接new int[]全为0再加一位
        int[] newnumber = new int[n+1];
        newnumber[0]=1;
        return newnumber;
    }

(42) 对两个二进制的字符串进行加法

    public  static String addBinary(String a, String b){
        StringBuffer sb = new StringBuffer();
        int i=a.length-1,j=b.length-1,carry=0; //carry为进位
        while(i>0 || j>0){
            int sum = carry;
            if(j>=0) sum+=a.charAt(j)-'0';
            if(i>=0) sum+=a.charAt(i)-'0';
            sb.append(sum%2);
            carry/=2;
        }
        if(carry!=0) sb.append(carry);
        return sb.reverse().toString();
    }

(43) 写方法 int sqrt(int x),计算并返回 x 最接近的平方根

思路：求一个数r的平方大于x，然后r减少到凑出正确的值。 高中的公式：((a+b)/2)^2 > 2ab;其中a=r/2 , b =x/2r;

        public int mySqrt(int n ){
            long r=x;
            while (r*r>x)
            {
                r=(r+x/r)/2;
            }       
        }

(44)你要爬楼梯。你面对的是一个 n 步可以走上去的楼梯。

思路：你每次可以走一步或者两步，那么你有几种不同的方式可以爬上去吗？

    public int climbStairs(int n){
        if(n==0 ||n==1 ||n==2) retur n ;
        int men = new int[2];
        men[0]=1;
        men[1]=2;
        //和那个格子的道理是一样的
        for(int i=2,i<n ;i++){
            men[i]=men[i-1]+men[i-2]
        }
        return men[n-1];
    }

(45)两种思路：一种是使用队列，打印root，然后把root.left入对，再把root.right入队即可。一种就是用ArrayList<Integer>来记录树的深度

    private void levelHelper(List<List<Integer>> res, TreeNode root, int height){
        if(root==null) return;
        if(hegiht>=res.size()) res.add(new ArrayList<Integre>());
        res.get(height).add(root.val);
        levelHelper(res,root.leftNode,height+1);
        levelHelper(res,root.rightNode,height+1);
    }

(46)给一个二叉树，确认这个是不是自己的镜像（即围绕其中心对称）

private boolean isSymmetric(TreeNode leftNode, TreeNode rightNode){
    if(leftNode==null && rightNode==null) return true;
    if(leftNode==null || rightNode==null) return false;
    return leftNode.val == rightNode.val && isSymmetric(leftNode.rightNode,rightNode.leftNode)
    && isSymmetric(leftNode.leftNode,rightNode.rightNode)
    }

(47)求一颗树的深度

    public int findPath(TreeNode root){
        if(root==null) return 0;
        return 1+Math.max(findPath(root.leftNode),findPath(root.rightNode));
    }