二叉树的前序遍历 题意 输出一个二叉树的前序遍历 方法 递归 分析 前序遍历，即使根先于左右节点访问 因此返回的内容是 [根，左子树的前序遍历，右子树的前序遍历] 因此设计函数，接受一个树的节点，返回当前节点为根的前序遍历的结果 每次递归左右子树完成拼接 这样，对根调用这个函数就是要求的结果 样例 以样例数据为例 代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), righ...

字符串的全部子序列 题意 给一个字符串，求它的字符串的全部子序列 方法 递归生成所有序列并排序去重 分析 子序列不能改变字符的顺序，但是可以不连续 于是实际上相当于字符串中选取部分字符，然后保持原有的顺序拼接而成 考虑递归每一个深度分别选择当前位置字符和不选择当前位置字符, 并向下递归 这样就能得到所有的子序列 但题目要求重复的子序列只出现一次，考虑使用排序去重 代码 class Solution { public: void dfs(string s,int idx,string curs,vector<string> & arr){ if(idx...

给单链表加一 题意 给一个用链表表示的数字，对它加1，并返回加法后的链表 方法 递归 分析 真实的加一操作仅仅发生在末位 剩下的位上如果数字要变，都是因为进位 因此分成两部分 递归找到最低位加一 如果当前值等于10，则进位到它的父节点 因此，递归过程传递当前节点和它的父节点 对于根部需要特殊处理，也就是 根节点的父节点是NULL 如果根节点+1后为10，还需要额外增加节点 代码 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr)...

二进制求和 题意 以字符串形式给两个二进制数字，求它们的二进制表示下的和 方法 python3内置高精度库 分析 注意到数字长度很大，因此普通的int/long等是无法满足，需要高精度 而python3的自带高精度，考虑使用python3内置的高精度 代码 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param A string字符串 # @param B string字符串 # @return string字符串 # class Solution: def binaryAdd(self , A: str, B: str) -&...

两两交换链表的节点 题意 给一个链表，两个两个的实际的交换节点 方法 每两个一处理 分析 既然是两两交换，那么当我们把前两个处理完以后，后面剩余的部分可以递归用同样的方法处理 所以每次把第二个作为新的根，指向第一个节点 而第一个节点指向 递归后面的节点 代码 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、...

岛屿的最大面积 题意 给一个0/1的二维数组，问四连通的最大的1的块数 方法 广搜 分析 如果我们从一个为1的块开始，向它相邻的搜索 以此反复，搜索完所有相邻的为1的块 那么这个数量就是一个四连通的块数，其中最大值就是要求的答案 为了避免重复搜索，利用辅助数组记录一个块是否被搜索过即可 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param grid int整型vector<vector<>> * ...

判断是不是二叉搜索树 题意 给定一个树，判断它是不是二叉搜索树 方法 转化成数组再比较 分析 一个树，是二叉搜索树，则它的中序遍历是递增数组 因此考虑通过先得到它的中序遍历，再判断数组内容是否有序 代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ class Solution { public: void df...

最长公共子数组 题意 给定两个子数组，求最长公共子数组的长度 方法 循环对比(TLE) 分析 公共子数组的性质是连续的一段 换句话说，从A的某个位置i开始，从B的某个位置j开始，长度为len的一段相等 那么问题可以变为，先分别选取起始位置，再进行比较，并记录最大的相等长度 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A int整型vector * @param B int整型vector * @re...

单词拆分(二) 题意 给定一个字典，和一个字符串，把字符串拆分成字典的子集 方法 递归搜索 分析 因为要拆分成字典的子集 所以，字符串的开头一定匹配某个单词 如果我们枚举找到一个单词，也就从这个单词的结尾知道了下一个拆分的位置 对于下一个拆分的位置，操作和初始单词的操作相同，都是从头部开始匹配 所以，整体步骤为 从头部匹配 一个单词 从单词结尾递归进入第一步 这样如果完全匹配，则输出拆分的结果 样例 以样例数据 "nowcoder",["now","coder","no","wcoder"] 为例 代码 class Solution { public: // 原字符串，搜索起始...

给数组加一 题意 给定一个数组表示的数字，对这个数字加1，同样返回数组表示的数字 方法 python内置高精度 分析 直接把数字数组转换成数字，然后数字+1，最后把数字转换回数组 代码 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型一维数组 # class Solution: def plusOne(self , nums: List[int]) -> List[int]: v = 0 for d in nums: ...

长度为 K 的重复字符子串 题意 给定一个字符串，问其中长度为k，且包含重复字符的字符串个数 方法 枚举起始位置 分析 我们对枚举每个位置作为起始位置 判断是否出现了重复字符，如果出现了则计数+1 则最后的计数总和就是要求的答案 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param k int整型 * @return int整型 */ int num...

打家劫舍(三) 题意 给定一个数字二叉树，不能选相邻的两个节点，问选的数的最大的和是多大 方法 深搜(TLE) 分析 我们递归搜索，每次递归时传递当前位置是否可选 如果不选这个位置，那么下一层递归的点都是可选 如果可选且选定这个位置，那么下一层递归的值都不可选 在递归过程中记录选择的和 最后输出和中的最大值 代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nu...

打家劫舍(二) 题意 给定一个数字数组，它们构成环，不能选相邻的两个数，问选的数的最大的和是多大 方法 深搜(TLE) 分析 我们递归搜索，每次有可选的起始位置。 如果选定这个位置，那么下一层递归，则可选位置从当前位置+2开始 如果不选这个位置，那么下一层递归，可选位置从当前位置+1开始 在递归过程中记录选择的和 最后输出和中的最大值 这样的问题在于，没有处理首个位置和末尾的位置相邻的情况 考虑对第一个位置单独处理，分别讨论选和不选 如果第一个位置选了，那么最后一个位置不选，第二个位置不能选 如果第一个位置不选，那么从第二个位置开始操作 代码 class Solution { public...

打家劫舍(一) 题意 给定一个数字数组，不能选相邻的两个数，问选出的数的最大的和是多大 方法 深搜(TLE) 分析 我们递归搜索，每次有可选的起始位置。 如果选定这个位置，那么下一层递归，则可选位置从当前位置+2开始 如果不选这个位置，那么下一层递归，可选位置从当前位置+1开始 在递归过程中记录选择的和 最后输出和中的最大值即可 代码 class Solution { public: // 数组，可选的起始位置，总和 int dfs(vector<int>& nums,int idx,int sum = 0){ if(idx >= nu...