题意 输出边长为n的从外到内顺时针螺旋矩阵 限制: 边长不大于20 方法 模拟实现 考虑从1开始写,那么如果考虑书写的方向,则有4个方向, 右下左上. 注意到当一个方向不可再书写时,切换到下一个方向即可 以题目中样例数据 n=3为例 值 i j 方向 操作 1 0 0 右 右侧还可以写,继续向右 2 0 1 右 右侧还可以写,继续向右 3 0 2 右->下 右侧超出边界,切换到向下 4 1 2 下 下侧还可以写,继续向下 5 2 2 下->左 下侧超出边界,切换到向左 6 2 1 左 左侧还可一写,继续向左 7 2 0 左->上 左侧超出...

题意 正值数组中,求最短的连续区间,使其区间上值的和大于等于给定值. 限制: 数组长度不大于10510^5105 数组中值不大于10410^4104 方法 二分法 首先,因为数组元素全为正,那么长度为i的所有区间的和的最大值,一定小于长度为i+1的区间和的最大值. 因此,随着区间长度上升,其区间和最大值单调递增 对于有单调性的,想到二分法 通过二分区间长度,检查最大值是否大于给定的target 以题目样例数据[1,2,4,4,1,1,1],9 为例,l,r,m均表示区间长度,其中m为l,r的平均数 - l r m 操作 初始化 1 7 - 检测一个值都小于9,所有值的和大于等于...

题意 把压缩过的字符串还原, 压缩过的通过次数[字符串]来表示 范围: 输出长度不会超过50 方法 每次枚举展开 按照题意,我们可以从内到外进行解码. 那第一个出现的右侧括号所包含的内容,就是最内层的. 这样每次解码一块内容更新整个字符串.直到字符串被完全解码为止,就是要求的答案 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ ...

题意 给定一个包含加减括号的表达式，计算表达式的值 限制： 表达式长度不大于100000，计算过程保证在int内，只包含 数字 加减乘除 和 括号，保证表达式正确 方法 递归同时计算 考虑表达式，其实是由数值 运算符 数值 运算符 数值 运算符构成的 其中第一个数值可能是负号开始，可以通过判断起始字符进行处理 所有数值 可能是括号表达式，可以通过判断前括号进行处理 当我们处理掉括号和负数以后。 我们可以用栈来完成表达式计算。 以400+5为例 初始化为空 数值栈 符号栈 [] [] 首先我们读入400 那么数值栈中压入 数值栈 符号栈 [400] [] ...

题意 字符串A最少需要多少次, 插入/删除/修改 能变成字符串B 限制,两个字符串长度均不超过500500500 方法 递推+状态 设计状态 dp[i][j] 表示,地一个字符串的前i个最少操作dp[i][j]次能变成第二个字符串前j 那么有状态转移 A[i]=B[j]时,对应位置字符相等,直接匹配,dp[i][j] = dp[i-1][j-1] A[i]!=B[j]时,可以采取修改,删除和插入三种方法,dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1 以样例数据"nowcoder","new"为例 - "" n o w c o d...

题意 求数组的所有排列中,恰好在当前数组排列的下一个的数组 限制: 数组长度不大于1000 方法 性质分析 如果一个数组恰好是另一个数组排列的下一个,那么首先两个数组不等,其次它们有公共前缀,在公共前缀后新数组比原数组大, 新数组剩余部分从小到大排列 正确性证明: 因为是下一个,所以不相等.存在一位下一个更大 因为满足前缀相等,后一位更大的中,最小的是剩余部分从小到大排列的, 因此这样的最小的就是排列的下一个 以题目样例[1,2,3]为例 固定位 更大位 顺序位 最终结果 "" [2] [1,3] [2,1,3] [1] [3] [2] [1,3,2] [1,2] 不存在...

题意 给定一个二叉树，返回他的后序遍历的序列。 范围: 节点数不大于100 方法 递归遍历树 按题意所说,通过递归遍历树来获得其后续遍历 每次先遍历左子树,再右子树,最后根 以题目样例为例 递归层级 左子树 根 右子树 数组 0 null 1 {2,3} {} 1 {3} 2 null {} 2 null 3 null {} 1 {3} 2 null {3} 0 null 1 {2,3} {3,2} - - - - {3,2,1} 代码 /** * struct TreeNode { * int val; * struct TreeNode *le...

题意 给定字符串,和最多可以先删除的字符数量,再对它进行连续字符的压缩,求压缩后字符串的最短长度 限制: 原字符串长度不大于100 方法 dfs(TLE) 题目拆解为两部分 字符串删除 压缩字符串 对于字符串删除字符的部分,采用深度搜索的方式, 每层记录,当前遍历的字符串位置,还可以删除的字符串个数,和删除后的字符串的部分 对于压缩字符串的部分,采取遍历和计数的方式来计算压缩后的字符串长度 以题目样例"aabcccccaaa"为例 下标 上个字符 累计个数 总长度 - 0 0 0 0 a 1 0 1 a 2 0 2 b 1 2(和a不同,统计a) 3 c 1 ...

题意 给定字符串能否由给定字典中的单词拼接而成. 限制: 字符串长度不大于500 字典单词数不大于1000,每个单词长度不大于20 方法 dfs 通过递归,每次匹配字典里所有单词,一旦匹配成功, 从匹配成功的下标递归搜索下一个位置,如果完全匹配了则返回匹配成功. 代码 class Solution { public: bool dfs(const string & s,int idx,vector<string> & dic){ // 递归 字符串 下标 字典 if(idx == s.length())return true; // 完成匹配 ...

题意 n个人参与被投票，统计每人被投次数，与无效票数量 限制：参与人不大于100，投票总数不大于100 方法 基于STL实现 把题目要求文字内容直接翻译成代码 为了保持输出顺序，所以使用vector来记录输入顺序 为了判断是否出现过，使用set来记录参与人 为了统计每人被投次数，使用map来记录人到被投票的数量关系 因为我们不需要按名字排序，所以上述set和map可以换为hash版本的 代码 #include<bits/stdc++.h> using namespace std; int main(){ int n; while(~scanf("%d",&amp...

题意 一个数组分成两组 5的倍数在一组 是3的倍数 且 不是5的倍数 在另一组 剩余数字自由分组 是否能让分成的两组数字的和相等 限制：数组长度不大于50，数值绝对值不大于500 方法 动态规划 先不考虑限制，分成两组和相等，也就是两组数字和的差为0,即是第一组的和 - 第二组的和 = 0 再看限制，不妨设，5的倍数在第一组，3的倍数 且 不是5的倍数在第二组 那么 第一组的和 - 第二组的和 = 0 变为 (5的倍数的和) - (3的倍数 且 不是5的倍数 的和) + (第一组剩余的和) - (第二组剩余的和) = 0 这里如果把和展开，实际上就是第一组的值全部 在表达式中是加法，第...

题意 找字符串中最大长度的所有数字串，输出它们和最大长度 限制：字符串长度不大于200 方法 遍历 对字符串进行一次遍历，同时记录字符串起始位置，和最大长度。 以样例数据abcd12345ed125ss123058789为例 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 a b c d 1 2 3 4 5 e d 1 2 5 s s 1 2 3 0 5 8 7 8 9 每当我们遇到非数字时把数字起始坐标设为当前坐标+1 而每次是数字时，进行最大值更新判断，和记录最大值对应的坐标 当前遍...

题意 沿n 乘 m的棋盘边界从左上角，只能向右或向下走到右下角的方案数 限制：n和m均不超过8 方法 递推 既然只能向右或者向下走，反过来说明一个位置要么从上方来，要么从左方来。切因为上一个点不同，所以这两个方向来的各不相同 定义dp[i][j]dp[i][j]dp[i][j] 表示从左上角走到第iii行,第jjj列的方案数 那么它上方的格子的方案数为dp[i−1][j]dp[i-1][j]dp[i−1][j]，它左方的格子的方案数为dp[i][j−1]dp[i][j-1]dp[i][j−1] 有递推表达式 dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp...

题意 判断给定ip是否合法 方法 内置库 对于这种大量场景地方都会用到的函数，如果是在面向用户生产代码中，尽可能的不要自己实现，而是使用很多人用过有保障的库函数 inet_pton这个函数在成功时返回1，失败时返回0，所以我们直接调用它即可 代码 #include<bits/stdc++.h> #include<arpa/inet.h> using namespace std; int main(){ string s; while(getline(cin,s)){ struct sockaddr_in sa; print...