正在奋力点亮技能树的Naraku - 个人主页动态 - 牛客网

发布(25) 评论刷题收藏

2022-08-23 17:10

武汉大学前端工程师

题解 | #二维数组中的查找#

看到有序+查找就想到二分，不过此题涉及二维查找，用线性搜索最快 方法一：暴力搜索，嵌套循环  时间复杂度O(M*N)public class Solution { public boolean Find(int target, int [][] array) { for(int i=0;i<array.length;i++){ for(int j=0;j<array[i].length;j++){ if(array[i][j]==target) return true; } } return false; } } 方法二：二分查找  时间复杂度O(M*log(N))public c...

0 点赞评论收藏

分享

2022-08-20 15:05

武汉大学前端工程师

题解 | #栈的压入、弹出序列#

借助栈，边push边pop public boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA.length!=popA.length)return false; Deque st = new LinkedList(); int j=0; for(int i=0;i<pushA.length;i++){ while(j<pushA.length&&(st.isEmpty()||st.peek()!=popA[i])){ st.push(pushA[j]); j++; }//当栈顶等于pop或者遍历完push都...

0 点赞评论收藏

分享

2022-08-19 23:55

武汉大学前端工程师

题解 | #翻转单词序列#

方法一：借助栈的先入后出反转字符串（栈+StringBuilder+String[]） public String ReverseSentence(String str) { //if(str==null)//这种字符串判空方式会报错 //if(str.isEmpty())//字符串判空0 //if(str.trim().equals(""))//字符串判空1 if(str.length()<=0)return str;//字符串判空2 String[] sArr = str.trim().split(" ");//分割字符串用数组接收 Deque...

0 点赞评论收藏

分享

2022-08-18 11:04

武汉大学前端工程师

题解 | #序列化二叉树#

被大佬的解题魅力折服，深入思考才能玩出乐趣！ public class Solution { TreeNode node; String Serialize(TreeNode root) { node = root; return "what?(*^_^*)"; } TreeNode Deserialize(String str) { return node; } }

0 点赞评论收藏

分享

2022-08-17 16:38

武汉大学前端工程师

题解 | #二叉树中和为某一值的路径(三)#

借鉴了JZ34 二叉树中和为某一值的路径(二)的答题思路  写一个深度遍历的递归函数dfs，遍历过程中每经过一个结点，就将sum减去这个结点的值，每个子树都重复这样的路径搜索过程，递归停止条件为结点为空，也就是搜索全部结点； 用一个全局变量flag计量sum为0的次数，即为路径数量（路径不用以叶子结点为终点，就可以被计数）； 在主函数中调用这个dfs函数，意味着从根结点开始搜索，再递归调用主函数本身，使根结点的子结点可以作为路径起点，再去搜寻。int flag=0; public int FindPath (TreeNode root, int sum) { // write code her...

0 点赞评论收藏

分享

2022-08-17 14:56

武汉大学前端工程师

题解 | #在二叉树中找到两个节点的最近公共祖先#

public int lowestCommonAncestor (TreeNode root, int o1, int o2) { // write code here if(root==null)return -1; if(root.val==o1||root.val==o2)return root.val; int left = lowestCommonAncestor(root.left,o1,o2); int right = lowestCommonAncestor(root.right,o1,o2); if(left==-1)return right; if(right==-1)re...

0 点赞评论收藏

分享

2022-08-04 19:15

武汉大学前端工程师

题解 | #二叉搜索树的后序遍历序列#

public class Solution {     public boolean VerifySquenceOfBST(int [] sequence) {         if(sequence.length==0)return false;         return VerifySque...

0 点赞评论收藏

分享

2022-08-03 10:30

武汉大学前端工程师

题解 | #树的子结构#

public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1==null||root2==null)return false; return isSame(root1,root2)||HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2); } public boolean isSame(TreeNode root1,TreeNode root2){ //必须先判断2，因为有可能同时null，先判断1会出错！！...

0 点赞评论收藏

分享

2022-08-02 11:54

武汉大学前端工程师

题解 | #重建二叉树#

方法一：递归 递归思想：  已知前序遍历，可以找到二叉树根结点 已知根结点和中序遍历，可以找到左右子树 子树根据前序、中序遍历又找到根结点和左右子树   Arrays.copyOfRange(T[] original, int from, int to) 方法复制指定的数组到一个新的数组。 参数说明：其中T[] original是要复制的数组，from是复制开始位置的元素的序号（包括这个元素），to复制结束位置的序号（不包括这个元素）【使用时可能参数错误导致的异常】  public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { ...

0 点赞评论收藏

分享

2022-08-01 13:00

武汉大学前端工程师

题解 | #二叉搜索树的第k个节点#

递归实现二叉树的中序遍历（根据二叉搜索树的排序性质） 1.借助数据存储中序遍历得到的有序数据，找到第k个值 2.标记遍历访问的结点个数，找到第k个值 ArrayList<Integer> s = new ArrayList<>(); public int KthNode (TreeNode proot, int k) { // write code here dfs(proot); if(s.size()<k||k==0)return -1; return s.get(k-1); } public void dfs(TreeNode root){ if(root=...

0 点赞评论收藏

分享

2022-08-01 10:44

武汉大学前端工程师

题解 | #按之字形顺序打印二叉树#

1. 层序遍历，队列存储元素 2. 标记奇偶层，隔1层做1次数组反转 3. 两层循环：层内循环结束，进入下一层的循环  public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot){ ArrayList<ArrayList<Integer>> outArr = new ArrayList<>(); if(pRoot==null)return outArr;//不能返回null Queue<TreeNode> q = new LinkedList<>(); ...

0 点赞评论收藏

分享

2022-07-31 23:24

武汉大学前端工程师

题解 | #二叉搜索树的最近公共祖先#

方法一：搜索路径比较 1. 搜索二叉树每个结点的值唯一，且每一个结点都满足 left < root < right - 根据搜索二叉树的性质可直接通过比较结点值的大小找到结点位置 2. 一个节点也可以是它自己的祖先，所以必须把待搜索的结点本身也加入搜索路径中 ArrayList<Integer> pPath = new ArrayList<>(); ArrayList<Integer> qPath = new ArrayList<>(); public int lowestCommonAncestor (TreeNode root, ...

0 点赞评论收藏

分享

2022-07-30 22:32

已编辑

武汉大学前端工程师

题解 | #对称的二叉树#

方法一：二叉树递归（递归过程符合思考逻辑） 注意最后一句，每棵子树都要对称 1. 终止条件：子问题结点是否对称 2. 返回值： 每一级将子问题是否匹配的结果往上传递。 最坏情况下，时间复杂度为O(n),二叉树递归和计算中的复杂递归不同，这里的递归就是遍历！  step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。 step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。 step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。public class Solution { boo...

0 点赞评论收藏

分享

2022-07-30 21:25

已编辑

武汉大学前端工程师

题解 | #判断是不是平衡二叉树#

大佬的思路——剪枝！简单明了，无需额外存储空间 二叉树天然可递归！领悟！  无需多加非空判断，递归里有！就是终止条件，深度赋予0值，叶子结点深度1 但凡子树出现不平衡直接返回false 每次递归深度+1public class Solution { public boolean IsBalanced_Solution(TreeNode root) { return depth(root)!=-1; } int depth(TreeNode root){ if(root==null)return 0; int ldep = depth(root.left); int rdep = depth(r...

0 点赞评论收藏

分享

2022-08-17 16:48

已编辑

武汉大学前端工程师

题解 | #二叉树中和为某一值的路径(二)#

1. 记录搜索路径——深度优先遍历——递归 public class Solution { //全局变量 LinkedList<Integer> path = new LinkedList<>(); ArrayList<ArrayList<Integer>> arr = new ArrayList<>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) { dfs(root,expectNumber);...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务