Java面试剑指offer系列七_编程设计

31.求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

public class Solution { 
    public int NumberOf1Between1AndN_Solution(int n) { 
        int number  = 0; 
         
        for(int i = 1; i <= n; i++){ 
            String str = String.valueOf(i); 
            char [] chars=str.toCharArray(); 
            for(int j = 0; j < chars.length; j++){ 
                if(chars[j] == '1') 
                    number++; 
            } 
        } 
        return number; 
    } 
}

32.输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

import java.util.ArrayList; 
 
public class Solution { 
    public String PrintMinNumber(int [] numbers) { 
        int len = numbers.length; 
        String str; 
         
        if(len == 0 || numbers == null) 
            return ""; 
         
        //这里相当于是把数组按”大小“排序，只是这里的排序方式不是平时的排序 
        for(int i = 0; i < len; i++){ 
            for(int j = i; j < len; j++){ 
                String m = String.valueOf(numbers[i]); 
                String n = String.valueOf(numbers[j]); 
                 
                if(Integer.parseInt(m+n) >= Integer.parseInt(n+m)){ 
                    int temp = numbers[j]; 
                    numbers[j] = numbers[i]; 
                    numbers[i] = temp; 
                } 
            } 
        } 
        str = String.valueOf(numbers[0]); 
        for(int i = 1; i < len; i++){ 
            str = str + String.valueOf(numbers[i]); 
        } 
         
        return str; 
    } 
}

33.把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

public class Solution { 
    public int GetUglyNumber_Solution(int index) { 
        if(index <=0 ) { return 0 ; } 
  
        int[] uglyNumbers = new int[index] ; 
        uglyNumbers[0] = 1 ; 
        int nextUglyIndex = 1 ; 
        int p2 = 0 ; 
        int p3 = 0 ; 
        int p5 = 0 ; 
        while(nextUglyIndex <= index-1) { 
            uglyNumbers[nextUglyIndex] = min(uglyNumbers[p2]*2, uglyNumbers[p3]*3, uglyNumbers[p5]*5) ; 
            while(uglyNumbers[p2]*2 <= uglyNumbers[nextUglyIndex]) {  
                p2++ ;  
            } 
            while(uglyNumbers[p3]*3 <= uglyNumbers[nextUglyIndex]) {  
                p3++ ;  
            } 
            while(uglyNumbers[p5]*5 <= uglyNumbers[nextUglyIndex]) {  
                p5++ ;  
            } 
            nextUglyIndex++ ; 
        } 
  
        return uglyNumbers[index-1] ; 
    } 
  
    public int min(int a, int b, int c) { 
        int temp = (a < b) ? a : b ; 
        return temp < c ? temp : c ; 
    } 
 
}

34.找出字符串中第一个只出现一次字符的位置。

import java.util.HashMap; 
 
public class Solution { 
    public int FirstNotRepeatingChar(String str)  
    { 
         
        HashMap<Character,Integer> map=new HashMap<Character,Integer>(); 
        for(int i=0;i<str.length();i++) 
        { 
            char c=str.charAt(i); 
            if(map.containsKey(c)) 
            { 
                int time=map.get(c); 
                time++; 
                map.put(c,time); 
                  
            } 
            else 
            { 
                map.put(c,1); 
            } 
        } 
       for(int i=0;i<str.length();i++) 
       { 
           char c=str.charAt(i); 
          if(map.get(c)==1) 
           return i; 
       } 
       return -1; 
    } 
}

35.在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007。

　　这一题使用的是归并排序。

public class Solution { 
    public int InversePairs(int [] array) { 
        if(array==null||array.length<=0){ 
            return 0; 
        } 
        int[] copy = new int[array.length]; 
        long count = recInversePairs(array,copy,0,array.length-1); 
          
        int result = (int)(count%1000000007); 
        return result; 
    } 
    public long recInversePairs(int[] array,int[] copy,int start,int end){ 
        if(start==end){ 
            copy[start] = array[start]; 
            return 0; 
        } 
        int mid = (start+end)/2; 
        long left = recInversePairs(array,copy,start,mid); 
        long right = recInversePairs(array,copy,mid+1,end); 
        long count = countInversePairs(array,copy,start,mid,end); 
        return count+left+right; 
    } 
    public long countInversePairs(int[] array,int[] copy,int start,int mid,int end){ 
          
        int left = mid; 
        int right = end; 
        for(int i=start;i<=end;i++){ 
            array[i] = copy[i]; 
        } 
        int index = end; 
        long count = 0; 
        while(left>=start&&right>=mid+1){ 
            if(array[left]>array[right]){ 
                copy[index--] = array[left--]; 
                count += right - mid; 
            }else{ 
                copy[index--] = array[right--]; 
            } 
        } 
         while(left>=start){ 
                copy[index--] = array[left--]; 
            } 
            while(right>=mid+1){ 
                copy[index--] = array[right--]; 
            } 
         return count; 
    } 
}

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