内容简介：题目描述：把只包含质因子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;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
An Introduction to Genetic Algorithms
Melanie Mitchell / MIT Press / 1998-2-6 / USD 45.00
Genetic algorithms have been used in science and engineering as adaptive algorithms for solving practical problems and as computational models of natural evolutionary systems. This brief, accessible i......一起来看看 《An Introduction to Genetic Algorithms》 这本书的介绍吧!
