一、题目

给定一个字符串 str，返回 str 中最长回文子串的长度

1
2

str="123", 其中的最长回文子串为 "1"、"2" 或者 "3"，所以返回 1
str="abc1234321ab"，其中的最长回文子串为 "1234321",所以返回 7

Leetcode：https://leetcode.cn/problems/longest-palindromic-substring/

二、分析

大名鼎鼎的 manacher 算法，就是用于此种类型的题目

把字符串转换成整数

一、题目

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

判断两个字符串是否互为变形词

一、题目

给定两个字符串 str1 和 str2，如果 str1 和 str2 中出现的字符种类一样且每种字符出现的次数也一样，那么 str1 和 str2 互为变形词。请实现函数判断两个字符串是否互为变形词

比如：

1
2

str1 = "123", str2 = "231" 返回 true
str1 = "123", str2 = "2331" 返回 false

二、思路

这道题目简单，首先判断两个字符串长度是否相等，如果不等，直接返回 false。然后用一个 map，key 为字符，value 为出现的次数，先遍历 str1，然后遇到 key，就给 value 自增。接下来，遍历 str2，遇到 key 就给 value 减减。

一、题目

1. 给定一个字符串 str，判断是不是整体有效的括号字符串。比如：

1
2

str="(()())" 返回 true
str="()(" 返回 false

一、题目

有一个字符串s，仅有数字组成，现在将字符串的删除n个字符，使得剩下的字符组成的数字最小，不能打乱字符的顺序。

1
2
3
4
5
6

输入样例：
1221 2
324682385 3
输出样例：
11
242385

二、分析

贪心算法求解。最优解是删除出现的第一个左边 大于 右边的数，因为删除之后高位减小；每次删除一个数，一共删除 n 次，留下的数总是当前最优解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    std::string delete_n_numbers(std::string& str, int n) {
        bool flag = false;
        int start_pos = 0;
        for (int i = 0; i < n; i++) {
            flag = false;
            for (int j = start_pos; j < str.size()-1; j++) {
                if (str[j] > str[j+1]) {
                    str.erase(j, 1);
                    flag = true;
                    start_pos = j == 0 ? 0 : j-1;
                    break;
                }
            }
            // 如果所有数都递增，删除最后 i 个数字后直接返回
            if (flag == false) {
                str.erase(str.end()-i, str.end());
                break;
            }
        }
        return str;
    }
};

替换字符串中连续出现的指定字符串

一、题目

给定三个字符串 str、from 和 to，把 str 中所有 from 的子串全部替换成 to 字符串，对连续出现 from 的部分要求只替换成一个 to 字符串，返回最终的结果字符串

举例：

1

str="abcabc123abcabc456abcabc" from="abc" to="X" 返回 "X123X456X"

二、思路

有很多思路，这里提供一种思路。先将字符串中出现 from 的地方全部赋值为 0，使用一个变量 match 为 from 的下标标识。遍历 str 字符串。同时比较 from 字符串，如果 str[i] 和 from[i] 相等，那就让 match 继续自增。直到到达 from 的最后位置，仍然相等的话，就将 str 这些位置替换为 0，长度为 from 的长度。如果在出现 str[i] 和 from[i] 不相等，那就让 match 为 0，继续遍历 str。

一、题目

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

leetcode：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

二、分析

滑动窗口的思路，来一个滑动窗口，记录他的最左边和最右边。再来一个 set 记录元素是否出现过，

• 滑动窗口从向右扩一位的时候，就判断下这位数是否在 set 中，如果没在，那就将其插入到滑动窗口中，然后继续向右扩

一、接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

Leetcode：https://leetcode.cn/problems/trapping-rain-water/

1
2
3

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

换钱的最小货币数

一、题目

给定数组 arr，arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数 aim 代表要找的钱数，求组成 aim 的最少货币数

举例：

1
2
3
4
5
6

arr[5, 2, 3], aim=20
4 张 5 元可以组成 20 元，其他的找钱方案都要使用更多张的货币，所以返回 4
arr[5,2,3], aim=0
不用任何货币就可以组成 0 元，返回 0
arr[3,5], aim=2
根本无法组成 2 元，钱不能找开的情况下默认返回 -1

二、思路

动态规划的思路。组成 aim 所需的最小货币数，可以展开成分别组成 0 - aim 所需的最小货币数。我们申请一个二维数组 dp。列代表 0 - aim，行代表给的钱的面值。

一、题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

1
2
3

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

Leetcode：https://leetcode.cn/problems/WhsWhI/

Leetcode：https://leetcode.cn/problems/longest-consecutive-sequence/