Skip to main content
 首页 » 编程设计

Java面试剑指offer系列六

2022年07月19日26JustinYoung

26.输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

/** 
public class TreeNode { 
    int val = 0; 
    TreeNode left = null; 
    TreeNode right = null; 
 
    public TreeNode(int val) { 
        this.val = val; 
 
    } 
 
} 
*/ 
public class Solution { 
    public TreeNode Convert(TreeNode pRootOfTree) { 
        if(pRootOfTree == null) 
            return null; 
        if(pRootOfTree.left == null && pRootOfTree.right == null) 
            return pRootOfTree; 
         
        //使用递归求出根节点的前一个节点 
        TreeNode pre = Convert(pRootOfTree.left); 
        TreeNode temp = pre; 
         
        //循环求出左子树最右边的节点 
        while(temp != null && temp.right != null){ 
            temp = temp.right; 
        } 
         
        if(pre != null){ 
            temp.right = pRootOfTree; 
            pRootOfTree.left = temp; 
        } 
         
        TreeNode last = Convert(pRootOfTree.right);        
         
        if(last != null){ 
            pRootOfTree.right = last; 
            last.left = pRootOfTree; 
        } 
         
        return pre != null ? pre : pRootOfTree; 
    } 
}

27.输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。 

  输入描述:
  输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
import java.util.ArrayList; 
import java.util.Collections; 
public class Solution { 
    public ArrayList<String> Permutation(String str) 
    { 
        ArrayList<String> res=new ArrayList<String>(); 
        if(str.length()==0||str==null) 
            return res; 
        int n= str.length(); 
        helper(res,0,str.toCharArray()); 
        Collections.sort(res); 
        return res; 
          
    } 
    public void helper( ArrayList<String> res,int index,char []s) 
    { 
        if(index==s.length-1) 
            res.add(new String(s)); 
        for(int i=index;i<s.length;i++) 
        { 
            if(i==index||s[index]!=s[i]) 
            { 
                swap(s,index,i); 
                helper(res,index+1,s); 
                swap(s,index,i); 
            } 
        } 
          
    } 
      
    public void swap(char[]t,int i,int j) 
     { 
        char c=t[i]; 
        t[i]=t[j]; 
        t[j]=c; 
    } 
} 

28.数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

import java.util.HashMap; 
import java.util.Map; 
 
public class Solution { 
    public int MoreThanHalfNum_Solution(int [] array) { 
        int len = array.length; 
         
        if(len == 0) 
            return 0; 
        if(len == 1) 
            return array[0]; 
         
        Map<Integer,Integer> map = new HashMap<Integer, Integer>(); 
         
        int key; 
        int value = 1; 
         
        for(int i = 0; i < len; i++){ 
            key = array[i]; 
            if(map.containsKey(key)){ 
                value = map.get(key)+1; 
                if(value > len/2) 
                    return key; 
                map.put(key,value); 
            }else{ 
                map.put(key,value); 
            } 
        } 
         
        return 0; 
    } 
}

29.输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

import java.util.ArrayList; 
 
public class Solution { 
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k){ 
        ArrayList<Integer> list = new ArrayList<Integer>(); 
        int len = input.length; 
         
        if(k > len) 
            return list; 
         
        //使用的是冒泡排序,但是没有全排序,以为题目要求是最小的k个数,所以最外层循环只有k次 
        for(int i = 0; i < k; i++){ 
            for(int j = 0; j < len-1-i; j++){ 
                if(input[j] < input[j+1]){ 
                    int temp = input[j]; 
                    input[j] = input[j+1]; 
                    input[j+1] = temp; 
                } 
            } 
            list.add(input[len-i-1]); 
        } 
         
        return list; 
    } 
}

30.HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?

public class Solution { 
    public int FindGreatestSumOfSubArray(int[] array) { 
        if(array.length == 0) 
            return 0; 
        int max = 0, sum = 0; 
         
        for(int i = 0; i < array.length; i++){ 
            sum = sum + array[i]; 
             
            if(sum < array[i])//如果sum小于当前元素,这样就说明前面元素的和为负数,这样就从当前开始 
                sum = array[i]; 
             
            if(i == 0){//这里是是为了解决数组开始的数都是负数的情况 
                max = sum; 
            }else if(sum > max){//这里用来比较max的sum的大小,要是sum大于max,就把sum的值赋值给max 
                max = sum; 
            } 
        } 
         
        return max;     
    } 
}

本文参考链接:https://www.cnblogs.com/wgl1995/p/5797950.html