频道栏目
首页 > 考试 > 其他 > 正文
剑指Offer——丑数
2017-01-01 10:06:00           
收藏   我要投稿

剑指Offer——丑数

前言

参照《剑指Offer》,通过洞悉其思想并消化吸收,改为java实现,供自己以后巩固。

package cn.edu.ujn.offersword;
 
import java.util.Scanner;
 
public class C5_34_UglyNumber {
 
/**
 * @date 2016-09-16
 * @number 01
 * @author SHQ
 * 丑数
 * 题目描述
 *把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * 思路
 *空间换时间
 *根据丑数的定义,丑数应该是另一个丑数乘以2,3,或5所得(1除外)。故非丑数不在计算范围之内。额外创建一个数组,用于存放已确定的丑数。
 *通过设置3个变量,用于标记第一个大于最大丑数的位置,并将3个变量中的最小丑数作为下一个丑数。 同时避免重复计算。
 * 空间复杂度O(n);
 */
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextInt()){
int index = in.nextInt();
System.out.println(GetUglyNumber_Solution2(index));
}
}
// 超时
    private static int GetUglyNumber_Solution(int index) {
    	if(index <= 0){
    	return 0;
    	}
    	int cnt = 0;
    	int number = 1;
    	while(cnt < index){
    	if(isUgly(number)){
    	cnt++;
    	}
    	number++;
    	}
    	return number;
    }
    
    private static boolean isUgly(int num){
    	while(num % 2 == 0)
    	num /= 2;
    	while(num % 3 == 0)
    	num /= 3;
    	while(num % 5 == 0)
    	num /= 5;
    	return num == 1 ? true : false;
    
    }
    
    private static int GetUglyNumber_Solution2(int index) {
    	if(index <= 0){
    	return 0;
    	}
    	int [] arr = new int [index];
    	arr[0] = 1;
    	int index2 = 0, index3 = 0, index5 = 0, nextIndex = 1;
    	while(nextIndex < index){
    	System.out.print(arr[nextIndex-1] + " ");
    	int min = min(arr[index2]*2, arr[index3]*3, arr[index5]*5);
    	arr[nextIndex] = min;
    	while(arr[index2] * 2 <= arr[nextIndex])
    	index2++;
    	while(arr[index3] * 3 <= arr[nextIndex])
    	index3++;
    	while(arr[index5] * 5 <= arr[nextIndex])
    	index5++;
    	nextIndex++;
    	}
    	return arr[nextIndex-1];
    }
    
    private static int min(int a, int b, int c){
    	int min = (a > b) ? b : a;    
    	return min > c ? c : min;
    }
}
点击复制链接 与好友分享!回本站首页
上一篇:HDU 4952 Number Transformation(数学)——2014 Multi-University Training Contest 8
下一篇:SPOJ LCS 最长公共子串 后缀自动机&后缀树(Ukkonen)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站