剑桥offer(41~50)

首页 > 代码库 > 剑桥offer(41~50)

2024-08-21 23:41:22 226人阅读

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;
        
    }
};

View Code

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);
        
    }
};

View Code

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;
        
    }
};

View Code

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;
    }
};

View Code

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;
    }
};

View Code

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;
    }
};

View Code

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;
    }
};

View Code

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 ‘#‘;
    }

};

View Code

49.题目描述

一个链表中包含环，请找出该链表的环的入口结点。

/*
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;   
    }
};

View Code

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;
 
    }

};

View Code

剑桥offer(41~50)

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 剑桥offer(41~50)