初学小白C/C++语言知识难点题目总结(代码演示)

一、给定一个字符串,返回它的最长回文子串。如果存在多个答案,返回任意一个即可。字符串长度 ≤≤ 1000。

算法:(暴力枚举)O(n2)O(n2)

由于字符串长度小于1000,因此我们可以用 O(n2)O(n2) 的算法枚举所有可能的情况。

首先枚举回文串的中心 ii,然后分两种情况向两边扩展边界,直到遇到不同字符为止:

  • 回文串长度是奇数,则依次判断 s[i−k]==s[i+k],k=1,2,3,…s[i−k]==s[i+k],k=1,2,3,…
  • 回文串长度是偶数,则依次判断 s[i−k]==s[i+k−1],k=1,2,3,…s[i−k]==s[i+k−1],k=1,2,3…

如果遇到不同字符,则我们就找到了以 ii 为中心的回文串边界。

时间复杂度分析:一共两重循环,所以时间复杂度是 O(n2)O(n2)。

C++代码演示:

class Solution {
public:
    string longestPalindrome(string s) {
        int res = 0;
        string str;
        for (int i = 0; i < s.size(); i ++ )
        {
            for (int j = 0; i - j >= 0 && i + j < s.size(); j ++ )
                if (s[i - j] == s[i + j])
                {
                    if (j * 2 + 1 > res)
                    {
                        res = j * 2 + 1;
                        str = s.substr(i - j, j * 2 + 1);
                    }
                }
                else break;

            for (int j = i, k = i + 1; j >= 0 && k < s.size(); j -- , k ++ )
                if (s[j] == s[k])
                {
                    if (k - j + 1 > res) 
                    {
                        res = k - j + 1;
                        str = s.substr(j, k - j + 1);
                    }
                }
                else break;
        }
        return str;
    }
};

二、给定一个整型数组,要求返回两个数的下标,使得两数之和等于给定的目标值,要求同一个下标不能使用两次,数据保证有且仅有一组解。

算法:(暴力枚举) O(n2)O(n2)

暴力枚举方法很简单:两重循环枚举下标 i,ji,j,然后判断 nums[i]+nums[j]nums[i]+nums[j] 是否等于 targettarget。

时间复杂度:由于有两重循环,所以复杂度是 O(n2)O(n2)。

C++代码演示:

class Solution {
public:
    vector twoSum(vector& nums, int target)
    {
        vector res;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    res = vector({j, i});
                    break;
                }
            }
            if (res.size() > 0) break;
        }
        return res;
    }
};

三、给你两个非空链表,分别表示两个非负整数。表示方法:链表中的每个节点,分别表示整数中的一位数字,顺序从低位至高位。例如:2 -> 4 -> 3 表示342. 请计算两个整数的和,并返回成链表的形式。数据保证两个整数均不包含前导0(除了0之外),例如:不会出现0023。

算法:(模拟人工加法) O(n)O(n)

这是道模拟题,模拟我们小时候列竖式做加法的过程:

  • 从最低位至最高位,逐位相加,如果和大于等于10,则保留个位数字,同时向前一位进1.
  • 如果最高位有进位,则需在最前面补1.

做有关链表的题目,有个常用技巧:添加一个虚拟头结点:ListNode *head = new ListNode(-1);,可以简化边界情况的判断。

C++代码演示:

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) 
    {
        ListNode *res = new ListNode(-1);   //添加虚拟头结点,简化边界情况的判断
        ListNode *cur = res;
        int carry = 0;  //表示进位
        while (l1 || l2) 
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(1); //如果最高位有进位,则需在最前面补1.
        return res->next;   //返回真正的头结点
    }
};

四、给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。

算法:(两重枚举,集合判重) O(n2)O(n2)

使用 C++ 中的集合 unordered_set。

  1. 首先对 nums 进行从小到大排序。
  2. 两重循环枚举 nums 数组,第一重循环仅枚举不重复的数字。
  3. 第二重循环需要用两个集合 hash 和 vis 记录某个数字是否存在,在循环体重我们做两件事:
  • 判断 -nums[st] − nums[i] 是否在 hash 集合中;若存在,则可以记录进答案;并且需要向 vis 集合添加数字-nums[st] - nums[i]。若不存在,则向 hash 集合中添加数字 nums[i]。
  • 做完上一步后需要判断 vis 集合中是否存在数字 -nums[st] - nums[i](显然如果1中刚刚添加过一定是存在的);若存在,则删除 hash 集合中数字 -nums[st] - nums[i]。

注意:使用 vis 集合的目的是防止 -nums[st] - nums[i] 和 nums[i] 数对被重复计算入答案。

时间复杂度:排序时间复杂度是 O(nlogn)O(nlogn),枚举的时间复杂的是 O(n2)O(n2),每次需要用集合操作平均 O(1)O(1),所以总时间复杂度为 O(n2)O(n2),但常数较大。

C++代码演示:

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> res;
        unordered_set hash, vis;
        sort(nums.begin(), nums.end());

        for (int st = 0; st < nums.size(); st++) {
            while (st != 0 && nums[st] == nums[st - 1])
                st++;
            hash.clear();
            vis.clear();
            for (int i = st + 1; i < nums.size(); i++) {
                auto got = hash.find(-nums[st] - nums[i]);
                if (got == hash.end())
                    hash.insert(nums[i]);
                else {
                    res.push_back({nums[st], nums[i], -nums[st] - nums[i]});
                    vis.insert(-nums[st] - nums[i]);
                }
                if (vis.find(-nums[st] - nums[i]) != vis.end())
                    hash.erase(-nums[st] - nums[i]);
            }
        }
        return res;
    }
};

五、实现 atoi 函数,将以字符串(string)形式表示的整数,转换成整型(int)。

aoti 函数需要满足的条件:

  1. 忽略所有行首空格,找到第一个非空格字符,可以是 ‘+/−+/−’ 表示是正数或者负数,紧随其后找到最长的一串连续数字,将其解析成一个整数;
  2. 整数后可能有任意非数字字符,请将其忽略;
  3. 从前往后遍历时,如果第一段连续数字为空,则返回0;
  4. 如果整数大于INT_MAX,请返回int_MAX;如果整数小于INT_MIN,请返回INT_MIN;

算法:(模拟) O(n)O(n)

这道题的难点在于边界情况非常多,需要仔细考虑。

做这道题目时,推荐先写一个傻瓜版,然后提交,再根据Wrong Case去逐步添加针对各种情况的处理。

时间复杂度分析:假设字符串长度是 nn,每个字符最多遍历一次,所以总时间复杂度是 O(n)O(n)。

C++代码演示:

class Solution {
public:
    int strToInt(string str) {
        int res = 0;
        int neg = 0;
        int i = 0;
        while (i < str.size() && str[i] == ' ') i++;
        if (str[i] == '-') neg = -1;
        if (str[i] == '+' || str[i] == '-') ++i;
        for (; i < str.size(); ++i)
        {
            if (str[i] < '0' || str[i] > '9') break;
            else 
            {
                int x = str[i] - '0';
                if (neg == -1) 
                {
                    x = -x;
                    if ((INT_MIN - x) / 10 <= res)
                    {
                        res *= 10;
                        res += x;
                    }
                    else return INT_MIN;
                }
                else 
                {
                    if ((INT_MAX - x) / 10 >= res)
                    {
                        res *= 10;
                        res += x;
                    }
                    else return INT_MAX;
                }
            }
        }
        return res;
    }
};

6、给出两个排好序的单向链表,返回合并排序后新的单向链表。

链表结点的数据结构:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

算法:(线性合并) O(n)O(n)

  1. 新建头部的保护结点 dummy,设置 cur 指针指向 dummy。
  2. 若当前 l1l1 指针指向的结点的值 val 比 l2l2 指针指向的结点的值 val 小,则令 cur 的 next 指针指向 l1l1,且 l1l1 后移;否则指向 l2l2,且 l2l2 后移。
  3. 然后 cur 指针按照上一部设置好的位置后移。
  4. 循环以上步骤直到 l1l1 或 l2l2 为空。
  5. 将剩余的 l1l1 或 l2l2 接到 cur 指针后边。

时间复杂度:两个链表各遍历一次,所以时间复杂度为 O(n)O(n)。

C++代码演示:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            }
            else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }

        cur -> next = (l1 != NULL ? l1 : l2);
        return dummy -> next;
    }
};

资料免费领取
首先恭喜您,能够认真的阅读到这里,如果对部分理解不太明白,建议先将文章收藏起来,然后对不清楚的知识点进行查阅,然后在进行阅读,相应你会有更深的认知。如果您喜欢这篇文章,就点个赞或者【关注我】吧!!

你可能感兴趣的