力扣1-10

1、两数之和

题目：

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

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

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

示例 1：

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

示例 2：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• \(2 <= nums.length <= 10^3\)
• \(-10^9 <= nums[i] <= 10^9\)
• \(-10^9 <= target <= 10^9\)
• 只会存在一个有效答案

思路：

• 1、暴力求解、两重循环、时间复杂度\(O(n^2)\)
• 2、哈希表存储、查询除了当前这个数的前一个数、即\(target - nums[i]\)、不存在就把数插入、存在就把下标返回。时间复杂度\(O(n)\)。

代码：

解法1：

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

解法2：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 无序哈希表
        unordered_map<int, int> heap;
        for(int i = 0 ; i < nums.size(); i ++ )
        {   
            // 定义num[i]前面那个数
            int r = target - nums[i];
            // 如果存在、返回下标
            if(heap.count(r)) return {heap[r], i}; 
            // 否则将此数的下标存入map中
            heap[nums[i]] = i ;
        }
        return {};
    }
};

2、两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

思路：

• 低位到高位、逐位相加、和大于10，保留个位，同时进1.
• 高位有进位的话、最前面补1

技巧：

// 添加一个虚拟头结点
ListNode *head = new ListNode(-1);

代码：

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 创建虚拟头节点、并用cur指向
        auto dumpy = new ListNode(-1), cur = dumpy;
        int t = 0;
        while(l1 || l2 || t)
        {
            // 把值先加上
            if(l1) t += l1->val, l1=l1->next;
            if(l2) t += l2->val, l2=l2->next;
            // 倒着放
            cur = cur->next = new ListNode(t%10);
            // 去位
            t /= 10;
        }
        // 返回生成的节点
        return dumpy->next;
    }
};

3、无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:

示例3：

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

提示：

• \(0 \leq s.length \leq 5 * 10 ^ 4\)
• \(s\) 由英文字母、数字、符号和空格组成

思路：

https://www.acwing.com/solution/content/49/

代码：

class Solution {
    public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int res = 0;
        for(int i = 0, j = 0 ; i < s.size(); i ++ )
        {
            // 将元素放入map中
            hash[s[i]]++;
            // 如果元素重复了
            while(hash[s[i]] > 1)
            {
                // 剔除这个元素
                hash[s[j]] --;
                // j 移动一格
                j ++ ;
            }
            // 更新最大值
            res = max(res, i - j + 1);
        }
        return res;
    }
};

4、填坑

5、最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

示例 3：

输入：s = "a"
输出："a"

示例 4：

输入：s = "ac"
输出："a"

提示：

• \(1 \leq s.length \leq 1000\)
• s 仅由数字和英文字母（大写和/或小写）组成

思路：

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i = 0 ; i < s.size() ; i ++ )
        {
            int l = i - 1, r = i + 1;	// 奇数
            while(l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++ ;
            if(res.size() < r - l - 1 ) res = s.substr(l + 1, r - l - 1);

            l = i, r = i + 1;		// 偶数
            while(l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++ ;
            if(res.size() < r - l - 1 ) res = s.substr(l + 1, r - l - 1);
        }
    return res;       
    }
};

6、Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、‘,‘ 和 ‘.‘ 组成
• 1 <= numRows <= 1000

思路：

https://www.acwing.com/solution/content/75/

时间复杂度\(O(n)\)

class Solution {
public:
    string convert(string s, int n) {
        string res;
        if(n == 1) return s;
        for(int i = 0 ; i < n ; i ++ )
        {
            // 第一行和最后一行的情况
            if(i == 0 || i == n - 1){
                for(int j = i ; j < s.size() ; j += 2 * n - 2)
                    res += s[j];
            } else {
                // 中间行的情况
                for(int j = i, k = 2 * n - 2 - i ; j < s.size() || k < s.size() ; j += 2 * n - 2, k += 2 * n - 2)
                {
                    // j在前、k在后
                    if(j < s.size()) res += s[j];   
                    if(k < s.size()) res += s[k];
                }
            }
        }
        return res;
    }
};

7、整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [?231, 231 ? 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

提示：

\(-2^{31} \leq x \leq 2^{31} - 1\)

思路：

借助关键代码、容易得到反转后的数字、规定不能用long long存储、需要判定边界问题

r = r * 10 + x % 10;	// 不断地将r的个位让出来	

注：

• INT_MAX、INT_MIN 均为C++中整数最大值和最小值
• C++中的取余->正数取余还是正数、负数取余还是负数。
• 时间复杂度\(O(logn)\)

代码

class Solution {
public:
    int reverse(int x) {
        int r = 0;
        while(x)
        {
            // 判断边界
            if(r > 0 && r > (INT_MAX - x % 10) / 10) return 0;
            if(r < 0 && r < (INT_MIN - x % 10) / 10) return 0;
            // 让出r的个位
            r = r * 10 + x % 10;
            x /= 10;
        }
        return r;
    }
};

8、填坑

9、回文数

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

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

示例 4：

输入：x = -101
输出：false

提示：

\(-2^{31} \leq x \leq 2^{31} - 1\)

思路：

• LeetCode第七题整数反转思路做、本题无long long限制
• 转换成字符串，s.regin()，s.rend()分别是转置后字符串的头和尾

// 反转做法
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return 0;
        int flag = x;
        long long r = 0;	// 防溢出
        while(x)
        {
            r = r * 10 + x % 10;
            x /= 10;
        }
        return r == flag;
    }
};

// 字符串做法
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return 0;
        string s = to_string(x);
        return s == string(s.rbegin(), s.rend());
    }
};

10、填坑

力扣1-10

原文：https://www.cnblogs.com/xiaofrank/p/14732704.html