单词拆分(二) 题目描述 给定一个字符串 s 和一个字符串数组 dic ，在字符串 s 的任意位置添加任意多个空格后得到的字符串集合是给定字符串数组 dic 的子集（即拆分后的字符串集合中的所有字符串都在 dic 数组中），你可以以任意顺序 返回所有这些可能的拆分方案。 方法一：递归的方法 解题思路 对于本题，采用递归的方法进行求解，首先从头部匹配一个单词，然后从该单词的结尾在进行匹配找到另一个单词，最后输出能够完全匹配的结果。  解题代码 class Solution { public: // 原字符串，搜索起始下标，字典，结果数组，当前拼接字符串 void dfs(string &...

给数组加一 题目描述 给定一个用数组表示的数字，即数组中每个数表示一个数位上的数，例如 [1,2,3]，表示 123 ，请问给这个数字加一后得到的结果（结果同样以数组的形式返回）。 注意：数组中不可能出现负数，且保证数组的首位即数字的首位不可能是 0 。 方法一：直接法 解题思路 对数组进行逆序遍历，模拟加一操作，此时需要一个辅助数组来存储结果。  解题代码 class Solution { public: vector<int> plusOne(vector<int>& nums) { vector<int> res; int flag=1;//进...

长度为K的重复字符子串 题目描述 给你一个由小写字母组成的长度为n的字符串 S ，找出所有长度为 k 且包含重复字符的子串，请你返回全部满足要求的子串的数目。 方法一：枚举法 解题思路 对于本题目的求解，使用枚举法，对每个位置进行枚举，判断是否出现了重复字符，如果出现了则计数加1，直到最后得到答案。  解题代码 class Solution { public: int numKLenSubstrRepeats(string s, int k) { int ans = 0; for(int i = 0;i + k <= s.length();i++) { // 枚举起始位置 vector&...

打家劫舍(三) 题目描述 你是一个经验丰富的小偷，经过上次在街边和湖边得手后你准备挑战一次自己，你发现了一个结构如二叉树的小区，小区内每个房间都存有一定现金，你观察到除了小区入口的房间以外每个房间都有且仅有一个父房间和至多两个子房间。 问，给定一个二叉树结构的小区，如之前两次行动一样，你无法在不触动警报的情况下同时偷窃两个相邻的房间，在不触动警报的情况下最多的偷窃金额。 方法一：递归法 解题思路 对于本题目的求解，使用递归搜索的方法进行，对于每次选择的位置，如果选定当前位置，那么下一层递归的值不可选，如果不选择当前位置，那么下层递归的值可选。在递归过程中记录最大值，最后输出即可。 解题代码 c...

打家劫舍(二) 题目描述 你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。 给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。 方法一：递归法 解题思路 对于本题目的求解，使用递归搜索的方法进行，对于每次选择的位置，如果选定当前位置，那么下次递归可从当前位置往后移动2个开始，如果不选择当前位置，那么下次递归可从当前位置往后...

打家劫舍(一) 题目描述 你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。 给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。 方法一：递归法 解题思路 对于本题目的求解，使用递归搜索的方法进行，对于每次选择的位置，如果选定当前位置，那么下次递归可从当前位置往后移动2个开始，如果不选择当前位置，那么下次递归可从当前位置往后移动1个开始。在递归过程中记录最大值，最后输出即可。 解题代码 class ...

最大值 题目描述 有一个只由字符'1'到'9'组成的长度为 n 的字符串 s ，现在可以截取其中一段长度为 k 的子串并且将该子串当作十进制的正整数，如对于子串"123"，其对应的十进制数字就是123 。 如果想让这个正整数尽可能的大的话，问该正整数最大能是多少。 函数传入一个长度为 n 的字符串 s 和一个正整数k，请你返回答案。 方法一：枚举法 解题思路 对于本题目的求解，直接对每个位置进行枚举，并在枚举过程中记录最大值的起始位置，最后得到结果。  解题代码 class Solution { public: int maxValue(string s, int k) { int i0 = ...

填充数组 题目描述 牛妹给了牛牛一个长度为 n的下标从0开始的正整型数组a ，粗心的牛牛不小心把其中的一些数字删除了。 假如aia_{i}ai​被删除了，则aia_{i}ai​=0。对于所有被删除的数字，牛牛必须选择一个正整数填充上。现在牛牛想知道有多少种填充方案使得： a0≤a1≤...≤an−1a_{0} \leq a_{1} \leq...\leq a_{n-1}a0​≤a1​≤...≤an−1​且对于所有的0≤i≤n−10 \leq i \leq n-10≤i≤n−1满足1≤ai≤k1 \leq a_{i} \leq k1≤ai​≤k。 函数传入一个下标从0开始的数组 a和一个正整数k...

二进制取反 题目描述 有一个二进制字符串num，可以选择该串中的任意一段区间进行取反(可以进行一次或不进行)，取反指将0变为1，将1变为0。那么取反之后的num可能的最大的字典序是多少呢。如有num=1000，将区间[num_{2},...,num_{4} ]取反变为1111是字典序最大的。 方法一：贪心方法 解题思路 对于本题目的求解，利用贪心的思想，遇到第一段连续的0区间，将其变为1，即可得到最大的字典序。  解题代码 class Solution { public: string maxLexicographical(string num) { int len=num.length();...

直方图内最大矩形 题目描述 给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少? 1.每个直方图宽度都为1 2.直方图都是相邻的 3.如果不能形成矩形，返回0即可 4.保证返回的结果不会超过2^31-1 方法一：暴力解法 解题思路 对于本题目的求解，直接遍历每一个直方图，将其高度作为矩形的高度，然后分别向前、向后延申，得到可能的矩形的最大长度，然后计算每个矩形的面积，最后取最大值即可。  解题代码 import java.util.*; public class Solution { public int la...

最长公共子序列(一) 题目描述 给定两个字符串 s1 和 s2，长度为m和n 。求两个字符串最长公共子序列的长度。 所谓子序列，指一个字符串删掉部分字符（也可以不删）形成的字符串。例如：字符串 "arcaea" 的子序列有 "ara" 、 "rcaa" 等。但 "car" 、 "aaae" 则不是它的子序列。 所谓 s1 和 s2 的最长公共子序列，即一个最长的字符串，它既是 s1 的子序列，也是 s2 的子序列。 方法一：动态规划方法 解题思路 对于本题目的求解，利用动态规划，dp[i][j]表示s1长度为i，s2长度为j时的最长公共子序列的长度。我们将dp数组初始化为0，然后两层循环遍历s...

最长上升子序列(二) 题目描述 给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。 所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。 方法一：动态规划方法 解题思路 对于本题目的求解，利用动态规划，dp[i]表示以下标i结尾的最长上升子序列的长度。首先初始化，dp[i]=1，因为以任意下标结尾的子序列长度大于等于1。然后遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变。有...

最长上升子序列(一) 题目描述 给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。 所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。 方法一：动态规划方法 解题思路 对于本题目的求解，利用动态规划，dp[i]表示以下标i结尾的最长上升子序列的长度。首先初始化，dp[i]=1，因为以任意下标结尾的子序列长度大于等于1。然后遍历数组中所有的数，再遍历当前数之前的所有数，只要前面某个数小于当前数，则要么长度在之前基础上加1，要么保持不变。因...

字符串通配符 题目描述 在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。 要求： 实现如下2个通配符： ∗*∗：匹配0个或以上的字符 （注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同） ？：匹配1个字符 方法一：动态规划方法 解题思路 对于本题目的求解，利用动态规划，dp[i][j]表示pattern前i个字符和字符串str前j个字符的匹配情况。如果匹配，dp[i][j] = 1，如果不匹配，dp[i][j] = 0。dp[0][0] = 0，首先遍历一遍动态数组，假设pattern第i个字符为c1，str数组第j个字...