剑指offer 算法 （时间空间效率的平衡）

题目描述

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

解析：根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。因此我们可以创建一个数组，里面的数字是排好序的丑数。里面的每一个丑数是前面的丑数乘以2、3或者5得到的。那关键就是确保数组里的丑数是有序的了。我们假设数组中已经有若干个丑数，排好序后存在数组中。我们把现有的最大丑数记做M。现在我们来生成下一个丑数，该丑数肯定是前面某一个丑数乘以2、3或者5的结果。我们首先考虑把已有的每个丑数乘以2。在乘以2的时候，能得到若干个结果小于或等于M的。由于我们是按照顺序生成的，小于或者等于M肯定已经在数组中了，我们不需再次考虑；我们还会得到若干个大于M的结果，但我们只需要第一个大于M的结果，因为我们希望丑数是按从小到大顺序生成的，其他更大的结果我们以后再说。我们把得到的第一个乘以2后大于M的结果，记为M2。同样我们把已有的每一个丑数乘以3和5，能得到第一个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5三个数的最小者

class Solution { public:int GetUglyNumber_Solution(int index) {if(index<=0)return 0;int numUgly=1;vector<int> ugly;ugly.push_back(1);int u2=0,u3=0,u5=0;vector<int> *ugly2=&ugly;vector<int> *ugly3=&ugly;vector<int> *ugly5=&ugly;while(numUgly<index){ugly.push_back(min((*ugly2)[u2]*2,(*ugly3)[u3]*3,(*ugly5)[u5]*5));while((*ugly2)[u2]*2 <= ugly[numUgly])u2++;while((*ugly3)[u3]*3 <= ugly[numUgly])u3++;while((*ugly5)[u5]*5 <= ugly[numUgly])u5++;numUgly++;}return ugly[index-1];}int min(int num1,int num2,int num3){num1=num1<num2?num1:num2;return num1<num3?num1:num3;} };

题目描述

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

解析：建立简单的哈希表，存每个字符出现的次数，之后遍历求出首个符合要求位置
class Solution { public:int FirstNotRepeatingChar(string str) {if(str.empty())return -1;int const num=256;//int *cnt=new int[num];//很奇怪 不知道为什么这样动态建立数组就不对？？//memset(cnt,0,256);int cnt[256]={0};int cur=0;while(str[cur] != '\0'){cnt[str[cur++]]++;}cur=0;while(str[cur] != '\0'){if(cnt[str[cur++]] == 1)return --cur;}//delete []cnt;return -1;} };
题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
解析：用一个辅助数组保存比0~8大的数的数量。遍历每个数时累加既得结果 class Solution { public:int InversePairs(vector<int> data) {//针对的数据为0~9之间vector<int> a(9,0);int cnt=0;for(int i=0;i<data.size();i++){cnt+=a[data[i]];for(int j=data[i]-1;j>=0;j--){a[j]++;}}return cnt;} };题目描述

输入两个链表，找出它们的第一个公共结点。 解析：由于两个链表有公共结点，两条链必从公共结点开始合并为一链。即从链尾开始的话两链表重合到公共结点。即去除两链表长度差开始遍历的话，当两节点相等，即为公共结点。
/* struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {} };*/ class Solution { public:int lengthList(ListNode* head){ListNode* node=head;int length=0;while(node!=NULL){length++;node=node->next;}return length;}ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {int length1=lengthList(pHead1);int length2=lengthList(pHead2);if(length1==0 || length2==0)return NULL;ListNode* longList=pHead1;ListNode* shortList=pHead2;int diflength=length2>length1?length2-length1:length1-length2;if(length1<length2){longList=pHead2;shortList=pHead1;}//长链表先走diflength步while(diflength--){longList=longList->next;}while(shortList!=NULL){if(longList ==shortList)return longList;longList=longList->next;shortList=shortList->next;}return NULL;} };

总结

以上是生活随笔为你收集整理的剑指offer 算法 （时间空间效率的平衡）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。