内容简介：题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。所谓一个数m是另一个数n的因子，是指n能被m整除，也就是
丑数
题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路
所谓一个数m是另一个数n的因子，是指n能被m整除，也就是 n%m == 0 。根据丑数的定义，丑数只能被2、3、5整除，也就是说，如果一个数能被2整除，就连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就连续除以5。如果最后得到的是1，那么这个数就是丑数，否则就不是。
那么实际上我们可以写出一个函数来判断一个数是不是丑数：
private boolean isUglyNumber(int number){
while(number % 2 == 0){
number /= 2;
}
while(number % 3 == 0){
number /= 3;
}
while(number % 5 == 0){
number /= 5;
}
return number == 1;
}
然后题目让我们输出从小到大的第N个丑数，这很简单，我们只要对从小到大每个数做一次判断，判断其是否是丑数，如果是，那么统计丑数的次数加1，这样到第N个数就是我们需要的结果了。
那么显然你能看出来，这种方法虽然可行，但是效率上来说是十分低下的，因为里面有太多的冗余，那么我们能不能想出更好的办法呢？
答案是显然的，由于丑数只包含质因子2、3、5，那么丑数跟丑数相乘的结果肯定是丑数，即一个丑数 P=2^x * 3 ^ y * 5 ^ z ，我们可以从2、3、5出发，作为基准数。然后再乘以基准数，就得到4、6、10，6、9、15，10、15、25九个丑数，但是这种乘出来的结果有重复，并且结果是无序的，那么我们只需要处理这个问题就可以。
这个问题的处理需要思考一下，实际上1、2、3、4、5、6都是丑数，首先可以想到利用 HashSet 去重解决问题，但是结果是无序的，这就需要我们重新想办法。
其实每次我们只用比较3个数：用于乘2的最小的数、用于乘3的最小的数，用于乘5的最小的数。也就是比较(2x , 3y, 5z) ，x>=y>=z的，那么最终就可以依次按照顺序排列了。
代码实现
第一种解题思路：暴力解法
//判断每个数是不是丑数,效率非常低
public int GetUglyNumber_Solution(int index) {
if(index <= 0){
return 0;
}
if(index < 7) return index;
int number = 0;
int uglyFound = 0;
while(uglyFound < index){
number++;
if(isUglyNumber(number)){
uglyFound++;
}
}
return number;
}
private boolean isUglyNumber(int number){
while(number % 2 == 0){
number /= 2;
}
while(number % 3 == 0){
number /= 3;
}
while(number % 5 == 0){
number /= 5;
}
return number == 1;
}
第二种解法：时间复杂度O(n)
public int GetUglyNumber_Solution(int n) {
if (n <= 0) return 0;
ArrayList<Integer> list = new ArrayList<>();
//第一个丑数是1
list.add(1);
//以2 3 5 作为基准数
int i2 = 0, i3 = 0, i5 = 0;
while (list.size() < n)
{
int m2 = list.get(i2) * 2;
int m3 = list.get(i3) * 3;
int m5 = list.get(i5) * 5;
int min = Math.min(m2, Math.min(m3, m5));
list.add(min);
if (min == m2) i2++;
if (min == m3) i3++;
if (min == m5) i5++;
}
return list.get(list.size() - 1);
}
第一次只出现一次的字符
题目描述：在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）
解题思路
这个题目比较简单，可以使用Map存储结构解决问题，键为字符，值为字符出现的次数，最终输出第一个值为1的键就行，那么由于有顺序，所以需要使用 LinkedHashMap 结构进行存储。
代码实现
public int FirstNotRepeatingChar(String str) {
if(str == null){
return -1;
}
char[] cs = str.toCharArray();
Map<Character,Integer> map = new LinkedHashMap<>();
for(int i = 0 ; i < cs.length; i++){
if(!map.containsKey(cs[i])){
map.put(cs[i],1);
}else{
int val = map.get(cs[i]);
map.put(cs[i],val+1);
}
}
for(Map.Entry<Character,Integer> entry : map.entrySet()){
if(entry.getValue() == 1){
return str.indexOf(entry.getKey());
}
}
return -1;
}
数组中的逆序对
题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
解题思路
这个题目有点难度，最终实现是归并 排序 的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i，参考剑指offer书上解析。
代码实现
public int InversePairs(int [] array) {
if(array==null||array.length==0)
{
return 0;
}
int[] copy = new int[array.length];
for(int i=0;i<array.length;i++)
{
copy[i] = array[i];
}
int count = InversePairsCore(array,copy,0,array.length-1);//数值过大求余
return count;
}
private int InversePairsCore(int[] array,int[] copy,int low,int high) {
if(low==high)
{
return 0;
}
int mid = (low+high)>>1;
int leftCount = InversePairsCore(array,copy,low,mid)%1000000007;
int rightCount = InversePairsCore(array,copy,mid+1,high)%1000000007;
int count = 0;
int i=mid;
int j=high;
int locCopy = high;
while(i>=low&&j>mid)
{
if(array[i]>array[j])
{
count += j-mid;
copy[locCopy--] = array[i--];
if(count>=1000000007)//数值过大求余
{
count%=1000000007;
}
}
else
{
copy[locCopy--] = array[j--];
}
}
for(;i>=low;i--)
{
copy[locCopy--]=array[i];
}
for(;j>mid;j--)
{
copy[locCopy--]=array[j];
}
for(int s=low;s<=high;s++)
{
array[s] = copy[s];
}
return (leftCount+rightCount+count)%1000000007;
}
两个链表的第一个公共节点
题目描述：输入两个单向链表，找出它们的第一个公共结点。
解题思路
首先我们需要知道具有公共节点的链表有什么特性。
可以看到，这两个单向链表从公共节点开始，后面的节点都是相同的。
很多人第一反应是暴力解法，就是第一个链表上顺序遍历每个节点，每遍历一个节点，就在第二个链表上顺序遍历每个节点。这样的找法的时间复杂度是O(mn)，其中链表的长度分别为m、n。
那么显然需要换一种思路了，这种两个链表的题目，其实很多时候都用的双指针解法思路，即一个指针先走多少步，达到某个条件的时候另外一个指针就开始遍历，这样只用遍历一次链表就可以完成，这是常用的解决办法，当然也适用于本题。我们可以先遍历获取两个链表的长度，然后再根据长的链表进行遍历，先让第一个指针走长度差步，然后第二个节点开始走，当两个节点走到第一个相同节点就是第一个公共节点。
代码实现
解法一：双指针
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode current1 = pHead1;// 链表1
ListNode current2 = pHead2;// 链表2
if (pHead1 == null || pHead2 == null)
return null;
int length1 = getLength(current1);
int length2 = getLength(current2);
// 两链表的长度差
// 如果链表1的长度大于链表2的长度
if (length1 >= length2) {
int len = length1 - length2;
// 先遍历链表1，遍历的长度就是两链表的长度差
while (len > 0) {
current1 = current1.next;
len--;
}
}
// 如果链表2的长度大于链表1的长度
else if (length1 < length2) {
int len = length2 - length1;
// 先遍历链表1，遍历的长度就是两链表的长度差
while (len > 0) {
current2 = current2.next;
len--;
}
}
//开始齐头并进，直到找到第一个公共结点
while (current1 != current2) {
current1 = current1.next;
current2 = current2.next;
}
return current1;
}
// 求指定链表的长度
public static int getLength(ListNode pHead) {
int length = 0;
ListNode current = pHead;
while (current != null) {
length++;
current = current.next;
}
return length;
}
解法二：同样思路，使用HashMap实现
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode current1 = pHead1;
ListNode current2 = pHead2;
HashMap<ListNode, Integer> hashMap = new HashMap<>();
while (current1 != null) {
hashMap.put(current1, null);
current1 = current1.next;
}
while (current2 != null) {
if (hashMap.containsKey(current2))
return current2;
current2 = current2.next;
}
return null;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
算法艺术与信息学竞赛
刘汝佳 / 清华大学出版社 / 2004-1 / 45.00元
《算法艺术与信息学竞赛》较为系统和全面地介绍了算法学最基本的知识。这些知识和技巧既是高等院校“算法与数据结构”课程的主要内容，也是国际青少年信息学奥林匹克（IOI）竞赛和ACM/ICPC国际大学生程序设计竞赛中所需要的。书中分析了相当数量的问题。 本书共3章。第1章介绍算法与数据结构；第2章介绍数学知识和方法；第3章介绍计算机几何。全书内容丰富，分析透彻，启发性强，既适合读者自学，也适合于课......一起来看看 《算法艺术与信息学竞赛》 这本书的介绍吧!
