寂寞如雪lhd

剑指offer

docker(1) java(18) linux(3) scala学习(1) 未归档(2)

/ 注册

全部文章 / 剑指offer （共15篇）

从上往下打印出二叉树的每个节点，同层节点从左至右打印

这时候，我们可以发现，使用队列存放节点，数组存放值。先将根节点加入到队列中，然后遍历队列中的元素，遍历过程中，上来直接把第一个节点取出来，然后看其左右节点，如果有左右节点将其依次加入队列，如果没有则不用操作队列。直接把队列第一个元素取出加到数组即可。 public ArrayList<Inte...

2020-08-29

0 470

栈的压栈和出栈顺序

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的...

2020-08-29

0 937

二叉树的镜像

题目：求二叉树的镜像分析：我们可以观察上面的镜像二叉树的规则就是每个非叶节点的子节点都交换，所以我们就可以很容易得出以下的代码 public void Mirror(TreeNode root) { if(root==null) return; ...

2020-08-18

0 430

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

剑指offer上的一题，这题有很多方法，但是我们用取巧的一种。众所周知，如果链表里有环的话，我们遍历时必然会遇到重复的节点，那么我们就可以考虑用一个Set存节点，Set不能存重复的，所以在第一次Set没有存时就是环的入口。 ListNode node=pHead; Set<Li...

2020-08-17

1 634

反转链表

众所周知，在链表里有大量的指针操作，而这些指针很容易出错，所以面试的时候很多面试官喜欢出链表的题，而反转链表就是一个高频题。分析：链表前后元素的关联就是通过指针实现的，每个链表都有一个next指针指向下一个结点，末尾的节点的next域则置NULL;　　所以我们可以考虑将节点的next指向他原先...

2020-08-15

0 317

O（1）条件下实现删除链表某个元素

在链表中，我们一般删除一个元素的方法是遍历找到他，然后将其前面的next指向他下一位，然而有一种时间复杂度为O（1）的方法，下面我们分析一下，这个方法就是如果他后面有元素，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。 if(head=...

2020-08-11

0 612

二进制中1的个数

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。首先我们分析二进制中的规律，比如9用二进制转换便是1001，我们可以发现1的二进制表示为1，我们可以发现任何正数的二进制与1相与，当最后一位为0时为0，最后一位是1时为1，所以我们可以将二进制右移（向右移一位，左边添0），将每一位...

2020-08-09

0 776

剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是1...

2020-08-09

0 362

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如矩阵中包含一条字符串"bcced"的路径...

2020-08-08

0 349

青蛙跳台阶

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。分析：当只有一节台阶的时候，只有一种跳法，而当有两节台阶的时候，便有两种跳法三阶台阶的时候，我们就可以推出来，先是一节台阶的跳法，然后是两节台阶的跳法就可以得到上面的式子，这个式子便是斐波那契数列，...

2020-08-08

0 414