首页 > 代码库 > 剑桥offer(41~50)
剑桥offer(41~50)
41.题目描述
求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。
class Solution { public: int Sum_Solution(int n) { char a[n][n+1]; return sizeof(a)>>1; } };
42.题目描述
写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。
class Solution { public: int Add(int num1, int num2) { if(num1 == 0) return num2; if(num2 == 0){ return num1; } return Add(num1^num2,(num1&num2)<<1); } };
43.题目描述
将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
class Solution { public: int StrToInt(string str) { if(str.length()==0){ return 0; } int symbol = 0; int val = 0; if(str[0]==‘+‘){ symbol=1; }else if(str[0]==‘-‘){ symbol=-1; }else if(str[0]-‘0‘>=0 && str[0]-‘0‘<10){ val = str[0]-‘0‘; symbol=1; } for(int i=1;i<str.length();i++){ if(str[i]-‘0‘>10 || str[i]-‘0‘<0){ return 0; } val = val*10 + str[i]-‘0‘; } return val*symbol; } };
44.题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3。
class Solution { public: // Parameters: // numbers: an array of integers // length: the length of array numbers // duplication: (Output) the duplicated number in the array number // Return value: true if the input is valid, and there are some duplications in the array number // otherwise false bool duplicate(int numbers[], int length, int* duplication) { map<int,int>a; for(int i=0;i<length;i++){ a[numbers[i]]++; } for(auto it=a.begin();it!=a.end();it++){ if(it->second>1){ *duplication = it->first; return true; } } return false; } };
45.题目描述
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
思路:
利用两个辅助数组,
第一个数组L依次保存A数组从
0
-length-
1
的乘积,
第二个数组h依次保存从length-
1
到
0
的乘积,
然后每一个要求的B[i]=L[i-
1
]*H[i+
1
].
//B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1] //从左到右算 B[i]=A[0]*A[1]*...*A[i-1] //从右到左算B[i]*=A[i+1]*...*A[n-1] class Solution { public: vector<int> multiply(const vector<int>& A) { int n=A.size(); vector<int> b(n); int ret=1; for(int i=0;i<n;ret*=A[i++]){ b[i]=ret; } ret=1; for(int i=n-1;i>=0;ret*=A[i--]){ b[i]*=ret; } return b; } };
46.题目描述
请实现一个函数用来匹配包括‘.‘和‘*‘的正则表达式。模式中的字符‘.‘表示任意一个字符,而‘*‘表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配
class Solution { public: bool match(char* str, char* pattern) { if (*str == ‘\0‘ && *pattern == ‘\0‘) return true; if (*(pattern + 1) == ‘*‘) { // 如果已经到结尾了,把后面的*都匹配掉 if (*str == ‘\0‘) return match(str, pattern + 2); if ((*pattern == *str || *pattern == ‘.‘)) { // 尝试匹配一个,模式串往后移动 // 尝试匹配一个,模式串不往后移 // 一个都不匹配,模式串往后移动 // 3种当中有一种成功就可以了 return match(str + 1, pattern + 2) || match(str + 1, pattern) || match(str, pattern + 2); } else { // 因为是*所以不匹配也没事,直接跳到下一个 return match(str, pattern + 2); } } else if (*str == ‘\0‘) // 如果没有*了,但是模式串还没匹配完,那么失败 return false; else if (*pattern == ‘.‘ || *pattern == *str) // .或者模式串字符本来就匹配 { return match(str + 1, pattern + 1); } return false; } };
47.题目描述
请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
class Solution { public: bool isNumeric(char* str) { // 标记符号、小数点、e是否出现过 bool sign = false, decimal = false, hasE = false; for (int i = 0; i < strlen(str); i++) { if (str[i] == ‘e‘ || str[i] == ‘E‘) { if (i == strlen(str)-1) return false; // e后面一定要接数字 if (hasE) return false; // 不能同时存在两个e hasE = true; } else if (str[i] == ‘+‘ || str[i] == ‘-‘) { // 第二次出现+-符号,则必须紧接在e之后 if (sign && str[i-1] != ‘e‘ && str[i-1] != ‘E‘) return false; // 第一次出现+-符号,且不是在字符串开头,则也必须紧接在e之后 if (!sign && i > 0 && str[i-1] != ‘e‘ && str[i-1] != ‘E‘) return false; sign = true; } else if (str[i] == ‘.‘) { // e后面不能接小数点,小数点不能出现两次 if (hasE || decimal) return false; decimal = true; } else if (str[i] < ‘0‘ || str[i] > ‘9‘) // 不合法字符 return false; } return true; } };
48.题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
class Solution { public: //Insert one char from stringstream string str; void Insert(char ch) { str += ch; } //return the first appearence once char in current stringstream char FirstAppearingOnce() { vector<char> a; map<char, int>b; for (int i = 0; i<str.size() ; i++){ a.push_back(str[i]); b[str[i]]++; } for (int i = 0; i<a.size();i++){ if (b[a[i]]>1){ continue; } else if (b[a[i]] == 1){ return a[i]; } } return ‘#‘; } };
49.题目描述
一个链表中包含环,请找出该链表的环的入口结点。
View Code
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { //if(pHead == NULL)return NULL; ListNode* p = pHead; map<ListNode*,int>a; while(p){ if(++a[p] == 2) { break; } p = p->next; } return p; } };
50.题目描述
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* deleteDuplication(ListNode* pHead) { if (pHead == NULL || pHead->next == NULL) return pHead; /*---------先为链表创建一个头结点---------*/ int firstNumber = pHead->val; //假设我的头结点数值为-1 int myFirst = -1; //万一链表的头结点也为-1,那么我就改成-2 if (myFirst == firstNumber) { myFirst = -2; } ListNode *head = new ListNode(myFirst); head->next = NULL; head->next = pHead; ListNode *p = head; ListNode *q = head->next; while (q) { while (q->next && (q->next->val == q->val)) { q = q->next; } if (p->next != q) { q = q->next; p->next = q; } else { p = q; q = q->next; } } //返回的时候,注意去掉头结点(自己创建的辅助节点) return head->next; } };
剑桥offer(41~50)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。