剑指offer 66题 part6（31~36题）

本文主要是介绍剑指offer 66题 part6（31~36题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第三十一题：求1~n中所有整数里面1出现次数和

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数

class Solution {
/*
本题解法我们可以用两个数字来模拟即可懂
43147
43247
对于百位来说，是不同的，在下列程序运行的结果也不一样
因为我们找规律可以发现，百位出现1的次数，由前后两部分影响
并且如果它还是1的话，后面一部分影响的值有变换
+8的意思是：如果当前位大于1使得其进一位，方便计算
*/
public:int NumberOf1Between1AndN_Solution(int n){int a,b,cnt=0;for(int m=1;m<=n;m*=10){a=n/m;b=n%m;cnt+=(a+8)/10*m+(a%10==1?1:0)*(b+1);}return cnt;}
};

第三十二题：把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323

/*
sort中的比较函数compare要声明为静态成员函数或全局函数
因为：非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的
静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何对象实例就可以访问。
同时静态成员函数不可以调用类的非静态成员
*/
class Solution {
private:static bool cmp(int a,int b){string A=to_string(a)+to_string(b);string B=to_string(b)+to_string(a);return A<B;}
public:string PrintMinNumber(vector<int> numbers) {string ans="";sort(numbers.begin(),numbers.end(),cmp);for(int i=0;i<numbers.size();i++)ans+=to_string(numbers[i]);return ans;}
};

第三十三题：丑数

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数

题解：

设定三个指针，分别从同一个位置开始，当指针指向的下一个数字是最小的时候，对应的指针指向移动一个

class Solution {
public:int GetUglyNumber_Solution(int index) {if(index==0) return 0;vector<int>ans(index);int t2=0,t3=0,t5=0;ans[0]=1;for(int i=1;i<index;i++){ans[i]=min(2*ans[t2],min(3*ans[t3],5*ans[t5]));if(ans[i]==ans[t2]*2) t2++;if(ans[i]==ans[t3]*3) t3++;if(ans[i]==ans[t5]*5) t5++;}return ans[index-1];}
};

第三十四题：第一个只出现一次的字符

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

题解：

hash，map（红黑树）等等

class Solution {
public:int FirstNotRepeatingChar(string str) {map<char,int>mp;for(int i=0;i<str.size();i++)mp[str[i]]++;for(int i=0;i<str.size();i++)if(mp[str[i]]==1) return i;return -1;}
};

第三十五题：数组的逆序数对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

数据范围有点大，不能暴力

搞过acm的都知道可以用，线段树，树状数组，归并思想

下面代码使用归并思想：

递归到叶子节点后再返回上一级合并，这里使用一个辅助数组，但是利用了辅助数组却没有把辅助数组的内容复制回去到原数组，见代码注释即可理解

递归到叶子节点很简单，合并的时候见下图

class Solution {
private:long long deal(vector<int> &data,vector<int> &cp,int start,int end){if(start==end){cp[start]=data[start];return 0;}int len=(end-start)/2;long long left=deal(cp,data,start,start+len);//这里直接交换了数组，就不需要再把辅助数组复制回去long long right=deal(cp,data,start+len+1,end);int i=start+len,j=end;int index=end;long long cnt=0;while(i>=start&&j>=start+len+1){if(data[i]>data[j]){cp[index--]=data[i--];cnt+=j-start-len;}else cp[index--]=data[j--];}while(i>=start) cp[index--]=data[i--];while(j>=start+len+1) cp[index--]=data[j--];return (left+right+cnt)%1000000007;}
public:int InversePairs(vector<int> data) {int size=data.size();if(size<=0) return 0;vector<int> cp=data; //这里已经保证了两个数组一致long long cnt=deal(data,cp,0,size-1);return cnt%1000000007;}
};

第三十六题：两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点

题解：根据结构体可以发现，一旦有公共节点，那么两个链表的尾部就一定是相同的

所以，我们先跑一边得到链表的长度，然后再把最长的先跑相应节点使得两条链表尾部长度一样，最后再一起跑，如果相同肯定会一起到达尾部，在此过程中就可以碰到第一个相同的节点返回即可

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};*/
class Solution {
public:ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {int a=0,b=0,t;ListNode *p1=pHead1,*p2=pHead2;while(p1) p1=p1->next,a++;while(p2) p2=p2->next,b++;if(a>b){t=a-b;while(t--) pHead1=pHead1->next;t=b;}else if(b>a){t=b-a;while(t--) pHead2=pHead2->next;t=a;}else t=a;while(t&&(pHead1->val)!=(pHead2->val)){pHead1=pHead1->next;pHead2=pHead2->next;t--;}return pHead1;}
};

这篇关于剑指offer 66题 part6（31~36题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---