1.两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

解题思路

常规暴力
$O(n^2)$ 双层循环遍历比较
return {i, j}; 返回 vector 的初始化列表，等同于返回有两个元素的 vector

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

二分查找
$O(nlogn)$ 构建带有位置信息的 data 数组，按值升序排序，循环遍历，二分查找目标值
cmp 函数设置 static 关键字排除隐式参数 this 指针
二分查找递归方程为 $T(n)=T(n/2)+1$

class Solution
{
public:
    struct sa
    {
        int value;
        int position;
    };
    vector<int> twoSum(vector<int> &nums, int target)
    {
        sa data[nums.size()];
        for (int i = 0; i < nums.size(); i++)
        {
            data[i].value = nums[i];
            data[i].position = i;
        }
        sort(data, data + nums.size(), cmp);
        for (int i = 0; i < nums.size(); i++)
        {
            int l = i + 1;
            int r = nums.size() - 1;
            int tmp = target - data[i].value;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (tmp < data[mid].value)
                {
                    r = mid - 1;
                }
                else if (tmp > data[mid].value)
                {
                    l = mid + 1;
                }
                else
                    return {data[i].position, data[mid].position};
            }
        }
        return {};
    }
    static int cmp(const sa &a, const sa &b)
    {
        return a.value < b.value;
    }
};

9.回文数

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

提示：
-231 <= x <= 231 - 1

进阶：你能不将整数转为字符串来解决这个问题吗？

解题思路

倒序数
由题，负数不是回文数；非负数计算倒序数，判断与自身是否相等
int 倒序后可能溢出，由于非负，采用 unsigned int 保存倒序数

class Solution
{
public:
    bool isPalindrome(int x)
    {
        if (x < 0)
            return false;
        unsigned int rev = 0;
        unsigned int tmp = x;
        while (tmp)
        {
            rev = rev * 10 + tmp % 10;
            tmp /= 10;
        }
        return rev == x;
    }
};

13.罗马数字转整数

题目描述

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符	数值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

示例 1:
输入: s = “III”
输出: 3
示例 2:
输入: s = “IV”
输出: 4
示例 3:
输入: s = “IX”
输出: 9
示例 4:
输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：
1 <= s.length <= 15
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考罗马数字 - Mathematics 。

解题思路

暴力匹配
设置所有可翻译最小单元的键值对，循环遍历字符串，匹配相加
substr 切割子串避免越界，末尾子串长度为1

class Solution
{
public:
    int romanToInt(string s)
    {
        map<string, int> vis = {
            {"I", 1},
            {"V", 5},
            {"X", 10},
            {"L", 50},
            {"C", 100},
            {"D", 500},
            {"M", 1000},
            {"IV", 4},
            {"IX", 9},
            {"XL", 40},
            {"XC", 90},
            {"CD", 400},
            {"CM", 900}};
        int ans = 0;
        for (int i = 0; i < s.length(); i++)
        {
            string two = s.substr(i, 2);
            string one = s.substr(i, 1);
            if (vis[two] && two.size() == 2)
            {
                ans += vis[two];
                i++;
            }
            else
            {
                ans += vis[one];
            }
        }
        return ans;
    }
};

14.最长公共前缀

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “"。

示例 1：
输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”
示例 2：
输入：strs = [“dog”,“racecar”,“car”]
输出：”"
解释：输入不存在公共前缀。

提示：
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

解题思路

纵向比较
$O(mn)$ m为最短字符串长度，n为字符串数量
依次拿首串的字符与其余各串比较，不相同时截取首串返回，若首串全部字符都与其余串相同则返回首串

class Solution
{
public:
    string longestCommonPrefix(vector<string> &strs)
    {
        for (int i = 0; i < strs[0].length(); i++)
        {
            for (int j = 1; j < strs.size(); j++)
            {
                if (strs[j][i] != strs[0][i])
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

排序比较
$O(nlogn+m)$ m为最短字符串长度，n为字符串数量
排序后只需比较头尾字符串即可

class Solution
{
public:
    string longestCommonPrefix(vector<string> &strs)
    {
        sort(strs.begin(), strs.end());
        string s1 = strs[0];
        string s2 = strs[strs.size() - 1];
        for (int i = 0; i < s1.length(); i++)
        {
            if (s1[i] != s2[i])
                return s1.substr(0, i);
        }
        return s1;
    }
};

20.有效的括号

题目描述

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([)]”
输出：false
示例 5：
输入：s = “{[]}”
输出：true

提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

解题思路

压栈匹配
$O(n)$ n为字符串长度
压栈条件：左括号
出栈条件：栈非空并且与栈顶元素匹配
字符串无效条件：不匹配

class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> vis;
        map<char, char> mvis = {{'(', ')'}, {'[', ']'}, {'{', '}'}};
        for (int i = 0; i < s.length(); i++)
        {
            if (mvis.count(s[i]))
                vis.push(s[i]);
            else if (!vis.empty() && s[i] == mvis[vis.top()])
                vis.pop();
            else
                return false;
        }
        return vis.empty();
    }
};

21.合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

解题思路

$O(m+n)$ m，n为两链表长度
结构体定义后三行为构造函数，值通过参数传递，大括号内无内容
nullptr 为 C++ 设置的空指针关键字，由于 C++ 使用 NULL 可能存在二义性，故空指针使用 nullptr 表示，NULL 定义为 0

class Solution
{
public:
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;
        ListNode *ans, *p;
        ans = new ListNode();
        p = ans;
        while (list1 && list2)
        {
            if (list1->val <= list2->val)
            {
                p->next = list1;
                list1 = list1->next;
            }
            else
            {
                p->next = list2;
                list2 = list2->next;
            }
            p = p->next;
        }
        if (list1)
            p->next = list1;
        else
            p->next = list2;
        return ans->next;
    }
};

217. 存在重复元素

题目描述

给你一个整数数组 nums 。如果任一值在数组中出现至少两次，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示：
1 <= nums.length <= 105
-109 <= nums[i] <= 109

解题思路

排序查询
$O(nlogn)$ 经过排序，相同元素位置相邻，只需比较相邻元素即可

class Solution
{
public:
    bool containsDuplicate(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] == nums[i - 1])
                return true;
        }
        return false;
    }
};

set 容器
$O(n)$ 将数组元素插入无序 set 容器后查询

class Solution
{
public:
    bool containsDuplicate(vector<int> &nums)
    {
        unordered_set<int> vis;
        for (int i = 0; i < nums.size(); i++)
        {
            if (vis.count(nums[i]))
                return true;
            vis.insert(nums[i]);
        }
        return false;
    }
};

数组去重
nums.erase(unique(nums.begin(), nums.end()), nums.end());

53. 最大子数组和

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解题思路

$O(n)$ 线性dp，递推求解dp，同时更新答案
$dp=以nums[i]结尾的最大子段和$

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int dp, ans;
        dp = ans = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            dp = max(nums[i] + dp, nums[i]);
            ans = max(ans, dp);
        }
        return ans;
    }
};

1.两数之和#

题目描述#

解题思路#

9.回文数#

题目描述#

解题思路#

13.罗马数字转整数#

题目描述#

解题思路#

14.最长公共前缀#

题目描述#

解题思路#

20.有效的括号#

题目描述#

解题思路#

21.合并两个有序链表#

题目描述#

解题思路#

217. 存在重复元素#

题目描述#

解题思路#

53. 最大子数组和#

题目描述#

解题思路#

1.两数之和

题目描述

解题思路

9.回文数

题目描述

解题思路

13.罗马数字转整数

题目描述

解题思路

14.最长公共前缀

题目描述

解题思路

20.有效的括号

题目描述

解题思路

21.合并两个有序链表

题目描述

解题思路

217. 存在重复元素

题目描述

解题思路

53. 最大子数组和

题目描述

解题思路