剑指offer题解笔记:时间效率和空间效率的平衡 - Sanarous的博客

剑指offer题解笔记:时间效率和空间效率的平衡

丑数

题目描述:把只包含质因子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,那么这个数就是丑数,否则就不是。

那么实际上我们可以写出一个函数来判断一个数是不是丑数:

1
2
3
4
5
6
7
8
9
10
11
12
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的,那么最终就可以依次按照顺序排列了。

代码实现

第一种解题思路:暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//判断每个数是不是丑数,效率非常低
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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结构进行存储。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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书上解析。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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。

那么显然需要换一种思路了,这种两个链表的题目,其实很多时候都用的双指针解法思路,即一个指针先走多少步,达到某个条件的时候另外一个指针就开始遍历,这样只用遍历一次链表就可以完成,这是常用的解决办法,当然也适用于本题。我们可以先遍历获取两个链表的长度,然后再根据长的链表进行遍历,先让第一个指针走长度差步,然后第二个节点开始走,当两个节点走到第一个相同节点就是第一个公共节点。

代码实现

解法一:双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
如果这篇文章对您很有帮助,不妨
-------------    本文结束  感谢您的阅读    -------------
0%