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;
}
}