不包含本位置值的累乘数组

一、题目

给定一个整形数组 arr，返回不包含本位置值的累乘数组

例如：

1
2

arr = [2, 3, 1, 4]
返回 [12, 8, 24, 6]，即除自己外，其他位置上的累乘

二、思路

可以使用除法，即求出数组中所有数的乘积，然后结果数组中每一位上的数值即为：总乘积 / 当前位置元素。不过这种方法要注意数组中包含 0 的情况。

不重复打印排序数组中相加和为给定值的二元组和三元组

一、题目

给定排序数组 arr 和整数 K，不重复打印 arr 中所有相加和为 k 的不降序二元组

1
2
3

例如，arr = [-8, -4, -3, 0, 1, 2, 4, 5, 8, 9], k = 10 打印结果为
1 9
2 8

题目二：给定排序数组 arr 和整数 k，不重复打印 arr 中所有相加和为 k 的不降序三元组

二、思路

对于要打印二元组，比较简单。因为是排序数组，我们维护两个指针，一个指针 left 指向数组最左边，一个指针 right 指向数组最右边。循环条件是 left < right，在循环中，我们求得 arr[left] + arr[right] 为 sum，如果 sum 等于 k，则保存这个二元组。如果 sum 小于 k，因此我们需要一个更大一点的数，则将 left++。如果 sum 大于 k，我们需要一个小一点的数，则将 right--。还要注意题目要不不重复打印，因此我们判断的时候一定要注意当 sum 等于 k 时，判断 left 和 left-1 是否相等，相等就直接跳过。

一、题目

给定一个字符串 str，如果可以在 str 的任意位置添加字符，请返回在添加字符最少的情况下，让 str 整体都是回文字符串的一种结果

1
2

str="ABA"，str 本身就是回文串，不需要添加字符，所以返回 “ABA”
str="AB"，可以在 ‘A’ 之前添加 ‘B’，使 str 整体都是回文串，故可以返回 “BAB”。可以在 ‘B’ 之后添加 ‘A’，使 str 整体都是回文串，故也可以返回 “ABA”。总之，只要添加的字符串最少，只返回其中一种结果即可

leetcode 题目：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

二、分析

使用动态规划的方式，如果 str 的长度为 N，因此动态规划表是一个 N*N 的矩阵。dp[i][j] 值的含义代表子串 str[i...j] 最少添加几个字符可以使 str[i...j] 整体都是回文串。那么。如果求 dp[i][j] 的值，有如下三种情况：

机器人到达指定位置方法数

一、题目

假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种

牛客网：https://www.nowcoder.com/questionTerminal/54679e44604f44d48d1bcadb1fe6eb61

二、思路+代码

1. 暴力递归

这类题目最简单、最容易想到的的方法是暴力递归。N 个位置，现在在 M 位置，走 K 步，到达 P 位置。那么

• 当没有步数可以走时，也就是 rest 为 0 时，如果当前位置 cur 在 P 位置，那就返回 1，表示这条路可以通过

最长递增子序列

一、题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

例子：

1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

矩阵的最小路径和

一、题目

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

leetcode：https://leetcode.cn/problems/minimum-path-sum/

类似题目，不同路径：https://leetcode.cn/problems/unique-paths/

二、思路

典型的动态规划类题目，最终要走到右下角，这个矩阵长为 m，宽为 n。右下角为 [m-1, n-1] 位置，每一次只能走一步，那就要不是 [m-2, n-1] 走过来的，要不就是 [m-1, n-2] 走过来的，所以 [m-1, n-1] 的值应该为 std::min(arr[m-2, n-1], arr[m-1, n-2]) + 1。因此我们每一步需要选择最小的路径来走就好了。

跳跃游戏

一、题目

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。题目保证可以跳到结尾

leetcode题目

能否跳到最后一个下标：https://leetcode.cn/problems/jump-game/

一、题目

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

Leetcode：https://leetcode.cn/problems/coin-change-ii/description/

一、URL反转

给你一个url，反转。

如 https://www.baidu.com/dev-ops/question，反转后结果为 https://question/ops-dev/com.baidu.www

二、分析

此题目是按照 / 来反转的，而且要排除掉 https://。所以我们先对 www.baidu.com/dev-ops/question 这部分全部反转，然后在每隔 / 作为一个分隔，进行反转即可

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

class Solution {
public:
    void reserve_str(std::string& url) {
        int left = 0, right = url.size()-1;
        int count = 0;
        while (count != 2) {
            if (url[left] == '/') {
                count++;
            }
            left++;
        }
        int pos = left;
        // 先全部反转
        while (left < right) {
            std::swap(url[left++], url[right--]);
        }
        left = pos;
        for (int i = left; i < url.size(); i++) {
            if (url[i] == '/' || i == url.size()-1) {
                right = i == url.size()-1 ? i : i-1;
                while (left < right) {
                    std::swap(url[left++], url[right--]);
                }
                left = i+1;
            }
        }
    }
};

一、题目

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

1
2
3
4

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

Leetcode：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string

二、分析

其实就是 std::string.find() 的功能，我们使用 KMP 算法来求解。