maomao666
maomao666
全部文章
分类
题解(21)
归档
标签
去牛客网
登录
/
注册
maomao666的博客
全部文章
(共20篇)
题解 | #字符串的排列#
穷举,排列 排列之后,字符串有些是一样的,所有要有重操作 import java.util.ArrayList; public class Solution { //穷举 ArrayList<String> res; String path; int[] used; public Arr...
Java
模拟
递归
2022-03-31
0
196
题解 | #按之字形顺序打印二叉树#
O(N), O(N) 同层序遍历的方法,但是不同的是顺序交替,只能通过别的容器辅助完成,这里选栈,如果继续选择队列,从右到左时,不能辅助完成。通过mark变量标记遍历顺序 代码中,对于二叉树中的每个节点,都会进栈出栈,进队列出队列,所以4N时间,空间即为2N.满足时间和空间复杂度 import ja...
Java
队列
栈
二叉树
数学
2022-03-31
1
197
题解 | #二叉搜索树的第k个节点#
用迭代法中序遍历得到升序数组,然后索引得到,此时空间复杂度为O(N2) 但是同样采用中序遍历,不需要得到最后的升序数组,只需要一个变量记录第几个数,等到等于k时,即返回,此时空间复杂度可以提升到O(N) O(N),O(N) public class Solution { /** * 代码中的类名、...
Java
数学
二叉搜索树
排序树
深度优先搜索
栈
2022-03-30
1
231
题解 | #顺时针打印矩阵#
O(N),此题中N代表二维数组中的元素个数 似乎只有模拟,就顺时针打印,循环不变量很重要,确保左闭右开,左闭右闭也行,反正每次循环保持一致 此题中最后要处理不够循环一周的情况,三种情况,1,剩一个,2剩一行,3剩一列,但是情况1包含在情况2和3中。用loop来标记循环周数的情况,且此题没有说明一定是...
Java
数组
数学
模拟
设计
2022-03-30
1
208
题解 | #旋转数组的最小数字#
O(N), 双指针 由于数组升序,左右指针指向首尾 左右指针相加大于sum,则右指针左移,小于sum,左指针右移使得相加等于sum 剪枝操作表示此次循环left和right指向的数值和上次循环相等,没有计算的必要,直接continue,当然也可以不用,但是这种操作可以去重(很重要),此题不要求去重,...
Java
数组
双指针
数学
2022-03-29
1
213
题解 | #剪绳子#
O(N2), O(N), dp 这里特别需要注意dp[i]的概念是指,绳子长度为i, 分为至少两段,得到的最大乘积 若dp[i] = dp[j] * (i - j) ,指的是分成至少三段,所以缺少分为两段的情况,即dp[i] = j * (i - j) public class Solution {...
Java
贪心
动态规划
数学
2022-03-27
1
234
题解 | #二维数组中的查找#
O(logN * M) 每一个数组用二分查找,然后结合得到 数组查找用二分,左右指针分别指向首末元素,且左闭右闭(循环不变量很重要) public class Solution { public boolean Find(int target, int [][] array) { boole...
Java
数组
二分查找
双指针
2022-03-25
1
308
题解 | #把数字翻译成字符串#
O(N), O(N) dp 可以优化空间复杂度为O(1), 先可以考虑问题中不含有0的情况例如1223 1223的个数 = 122的个数 + 12的个数*(23 <= 26 ? 1 : 0); 新建dp, dp[i]表示以nums[i]结尾的字符串的译码结果的个数; 所以可以得到递推公式dp...
Java
动态规划
2022-03-19
2
235
题解 | #连续子数组的最大和(二)#
O(N), O(N),dp 建立一个3*N的dp数组, dp[i][0]表示以array[i]为末尾的连续数组的最大和 dp[i][1]表示与其对应的左边索引 dp[i][1]表示与其对应的右边索引,左闭右闭 先找到最大值,然后遍历dp,找到最大值中的最长数组。 import java.util.*...
Java
动态规划
贪心
双指针
2022-03-18
1
213
题解 | #放苹果#
// dp[i][j]表示将i+1个苹果放在j+1个盘子中的不同分法 // 一共分为三种情况,i,j // 第一种,当苹果数i小于盘子数j,一定有一个盘子没放苹果,所以等价于(i, j-1); // 第二种,当苹果数i等于盘子数j,将盘子放满只有一种情况,即每个都为1,然后加上盘子不放满的情况,所以...
Java
动态规划
2022-03-11
1
205
首页
上一页
1
2
下一页
末页