题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。1、思路分析从左至右的顺序打印联想到队列这种数据结构，但仍需注意入队和出队的逻辑。首先将根节点添加进队列，接着进行当队列不为空的循环，在循环里，先弹出队首元素，并将其保存在值TreeNode类型的t中，因为后续我们还需获得t的左右结点情况，将t添加进list中，并将t的左右结点依次入队，至此，一次循环的操作结束。此外，还需注意队列这种数据结构的基本操作。2、代码 import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; /** p...

题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）1、思路分析初始思路是把所有弹出序列都找出，再判断是否和popA相等，但操作过于繁琐，其实只要判断出某一个位置处的顺序不对，就直接可以返回false。这里总结下别人的代码思路。首先新建一个栈，利用for循环按照pushA的顺序入栈，每次入栈后，判断当前栈顶元素是否和popA对应位置处的元素...

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。1、思路分析将此类题归类为利用已知数据结构实现新方法，尤其注意的是，我们是可以直接调用固有方法的，并不需要我们自己去写方法的完整代码，直接调用即可。这里用到了迭代器，首先我们需要导入包，顺便回顾一下迭代器的知识。迭代器的生成：Iterator<泛型> 迭代器名称 = 容器名称.iterator();常用方法：hasNext()--是否有下一个元素，题目描述定义栈的数据结构，请在该类型中实...

题目描述输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.1、思路分析关键在于求出层数，layers=(Math.min(m,n)-1)/2+1，利用层数我们可以定位打印的元素，按照从左往右、右上至右下、从右往左、左下至左上的顺序依次打印。层数、行数决定上下边界，层数、列数决定左右边界。2、代码 import java.util.ArrayList; public class ...

题目描述操作给定的二叉树，将其变换为源二叉树的镜像。1、思路分析采用递归算法。首先判断特殊情况也即递归跳出的条件，当前root结点为空或者其左右子树均为空。接着是交换当前结点的左右结点，使用中间结点tmp进行过渡，交换完成后，进行递归调用，左右结点的调用顺序可以随意。非递归算法需要使用栈，先将根结点入栈，进行当栈不为空的循环，先弹出栈顶元素，交换该元素的左右结点，再分别将左右结点入栈。2、代码 public class Solution { public void Mirror(TreeNode root) { if(root == null) return; ...

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）1、思路分析首先要明白子结构的概念，可以理解为B是A的某一部分，但B的根节点在A的哪一部分并不确定，只要A里能包含B即可。仍然是先判断特殊情况，接着判断两者的根节点的值是否相等，即我们要开始寻找“起点”，如果相等，就判断是否是子树结构（封装在新写的isSubTree函数里，递归写法），不是子树结构，flag=false。回到上一步，如果两者的根节点不相等，递归调用HasSubTree，参数分别为root1.left&root2、root1.right&root2，即重新寻找两者的起...

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。1、思路分析解法一：非递归新建两个结点，一个用来保留头结点，一个用来移动扩充新结点。看了别人的思路后，有两点需进行优化：如果我们每次更新的是cur.next，更新完后令cur=cur.next，我们就不需要提前对head进行赋值，可以简化很多代码，也使思路更加清晰，正是cur=cur.next使得head和cur的值不再关联。而是循环时，注意条件是两个链表不同时为空，而不是任意一个链表不为空，这样可以减少很多循环的次数，循环结束后再判断是哪一个链表为空。解法二：递归更新完当前结点后，令cur.n...

题目描述输入一个链表，反转链表后，输出新链表的表头。1、思路分析为保证思路的完整性，一开始需考虑特殊情况，即链表结点为空或者只有头结点的时候，直接返回链表本身。初始思路我想用三个指针分别前一个、当前和下一个结点，其实通过移动head可以充当当前指针，因此我们再另外新建pre、next两个指针即可。再在while循环中交换三个指针指向的下一个指针位置，这与交换两个数字的思路比较像，需要预先存储即将被改变的，以免被覆盖。最后返回pre指针即可。2、代码 public class Solution { public ListNode ReverseList(ListNode head) { ...

题目描述输入一个链表，输出该链表中倒数第k个结点。1、思路分析使用左右两个指针，一开始left和right均指向头结点，left保持不变，right向右移动k-1次，外层循环控制移动次数，循环体中每次循环时判断right是否为空，如果为空，直接返回null，否则继续移动。第一次循环结束后，需要再次判断最后一次移动后right是否为空。第二次循环同时移动左右两个结点，注意，这时需要判断的是right是否是链表的最后一个结点，因此判断条件为right.null != 0，正是这里错了所以一直未提交成功，需要特别注意每次判断的目的是什么。最后返回left就好。2、代码 public class So...

题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。1、思路分析用的双指针，一开始我是让两个指针指向相邻位置，并且只循环一次，最后得到了错误的结果，分析发现，如果有一个奇数在两个连续的偶数的后面，则不能进行正常的交换，但每次循环之后，能保证最右边的偶数移到了循环的最后一个位置。因此，用了两层循环。第一层循环用来控制第二层循环的结束位置，依次保证每次循环遍历的最后一个位置为偶数，这个“窗口”不断向左扩充，最后就完成了题目完成的奇偶之间的交换。2、代码 public clas...

题目描述给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为01、思路分析最简单的办法，按照指数的定义进行循环迭代。一开始思路不完整，需要考虑指数为负的情况。同时，简单的if条件语句可以用一个语句来代替，注意这种简洁的写法。2、代码写法一： public class Solution { public double Power(double base, int exponent) { if(base == 0.0) return 0.0; if(exponen...

题目描述输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。1、思路分析自己没有思路，搬运的评论区大佬的解释。我们先来看看二进制表示形式下的整数减去1会发生什么，假设一个整数不为0，例如1100，1100-1=1011，可以看出，减去1的结果为最右边的1变为0，最右边的1后面的0（如果有）全部变为1，即从最右边的1，到最右边一位，所有位的结果变成了相反数，我们考虑按位与运算，即将原整数和减去1后的整数做按位与运算，从最右边的一个1开始，其右边所有位都会变为0，因此又会出现新的最右边的1，持续下去，该整数有多少个1，就能进行多少次这样的操作，直到原整数为0。2、代码 public c...

题目描述我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？1、思路分析动态规划的思想，当小矩形个数大于等于3时，覆盖个数可由矩形个数减少1、减少2来决定。一开始我想的是，f(n)=f(n-1)+2f(n-2)，但其实f(n-2)后面的覆盖情况有一种已经包含在了f(n-1)中，不需要乘以2。还需要注意的是，最后作为返回值的变量需要初始化，否则编译失败。2、代码 public class Solution { public int RectCover(int target) { if(target &l...

题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。1、思路分析是上一种跳台阶的变种。上一次主要是动态规划（迭代，项数确定）的思想，由于青蛙每次只能跳一步后者两步，因此当前台阶的跳法由前一级和前两级决定。而本题中，青蛙每一次可以跳的步数不再是完全一样的，而是由当前要跳的台阶数决定，因此这里没办法迭代或是用递归的思想。同时，由于每次有n种跳法，因此当前步数决定于前面每一级的跳法，即有：f(n)=f(n-1)+f(n-2)+...+f(1)f(n-1)=f(n-2)+...f(1)得:f(n)=2*f(n-1)2、代码 public...