|
183 | 183 | - 不为空,那么递归调用printListFromTailToHead方法来获取后面的节点反序生成的ArrayList,然后添加当前的节点的值,然后返回arrayList。 |
184 | 184 | - 为空,那么说明当前节点是链表尾部节点,直接创建一个ArrayList,然后添加当前节点的值,然后返回arrayList。 |
185 | 185 |
|
186 | | -```java |
187 | | -ArrayList<Integer> printListFromTailToHead(ListNode listNode) { |
188 | | - if(listNode == null) { return new ArrayList<Integer>(); } |
189 | | - ArrayList<Integer> arrayList; |
190 | | - ListNode nextNode = listNode.next; |
191 | | - if (nextNode!=null) { |
192 | | - arrayList = printListFromTailToHead(nextNode); |
193 | | - arrayList.add(listNode.val); |
194 | | - } else { |
195 | | - arrayList = new ArrayList<>(); |
196 | | - arrayList.add(listNode.val); |
197 | | - } |
198 | | - return arrayList; |
199 | | -} |
200 | | -``` |
201 | | -或者是这样写,其实原理就是先递归遍历,然后再打印,这样链表打印的顺序就是逆序的了。 |
| 186 | +其实原理就是先递归遍历,然后再打印,这样链表打印的顺序就是逆序的了。 |
202 | 187 | ```java |
203 | 188 | ArrayList<Integer> list = new ArrayList<Integer>(); |
204 | 189 | public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { |
@@ -282,8 +267,6 @@ public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { |
282 | 267 |
|
283 | 268 | 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 |
284 | 269 |
|
285 | | - |
286 | | - |
287 | 270 | ```java |
288 | 271 | int minNumberInRotateArray(int[] array) { |
289 | 272 | if (array[0]<array[array.length-1]){//当前就是一个递增的情况 |
@@ -445,9 +428,11 @@ double Power(double base ,int exponent) { |
445 | 428 |
|
446 | 429 | 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。 |
447 | 430 |
|
| 431 | +解题思路: |
| 432 | + |
448 | 433 | 如果可以使用额外的内存空间,可以对数组遍历两遍,一遍将奇数取出,存放在额外的数组中去,一遍把剩下的偶数存放到额外的数组中去。 |
449 | 434 |
|
450 | | -如果不能使用额外的内存空间,就是查找奇数,然后与前面的元素互换,一直到替换到最后一个奇数的后面,有点像是冒泡排序 |
| 435 | +如果不能使用额外的内存空间,就是查找奇数,然后与前面的元素互换,一直到替换到最后一个奇数的后面,有点像是冒泡排序。(因为不能改变相对位置,所以不能用快排) |
451 | 436 |
|
452 | 437 | 冒泡排序是其实是交换,从头开始,依次判断两个相邻的元素,将更大的元素向右交换,遍历一次后可以将当前序列最大的元素交换到最后面去,下次遍历就不用管最后一个元素。 |
453 | 438 |
|
@@ -479,14 +464,12 @@ ListNode FindKthToTail(ListNode head, int k) { |
479 | 464 | return null; |
480 | 465 | } |
481 | 466 | ListNode secondNode = head; |
482 | | - |
483 | 467 | for (int i=0 ; i < k-1 ; i++) {//向前走k-1步 |
484 | 468 | if (secondNode.next==null) {//链表长度不足k个 |
485 | 469 | return null; |
486 | 470 | } |
487 | 471 | secondNode = secondNode.next; |
488 | 472 | } |
489 | | - |
490 | 473 | ListNode firstNode = head; |
491 | 474 | while (secondNode.next != null) {//一直遍历到secondNode成为最后一个节点 |
492 | 475 | secondNode = secondNode.next; |
@@ -776,29 +759,29 @@ public int min() { |
776 | 759 | 所以可以对压入顺序A进行遍历,判断A压入的元素是否是出栈顺序B最前面的元素, |
777 | 760 |
|
778 | 761 | * 如果不是,那么说明只是把元素压入栈tempStack,现在还没有出栈 |
779 | | -* 如果是,那么现在元素可以出栈了,将元素先压入tempStack,然后对B继续向后遍历,并且与tempStack的栈顶元素进行判断,是的话就出栈,知道tempStack的元素与B中遍历到的元素不相等,那么停止出栈,继续之前的循环。 |
| 762 | +* 如果是,那么现在元素可以出栈了,将元素先压入tempStack,然后对B继续向后遍历,继续之前的循环。 |
780 | 763 |
|
781 | 764 | 循环结束后,继续对B继续向后遍历,并且与tempStack的栈顶元素进行判断,是的话就出栈,知道tempStack的元素与B中遍历到的元素不相等,那么说明B与A对应不上。 |
782 | 765 |
|
783 | 766 | ```java |
784 | | -public static boolean IsPopOrder1(int [] pushA,int [] popA) { |
785 | | - if (pushA==null||popA==null) { |
| 767 | +public static boolean IsPopOrder1(int [] pushA,int [] popB) { |
| 768 | + if (pushA==null||popB==null) { |
786 | 769 | return false; |
787 | 770 | } |
788 | 771 | Stack<Integer> stack = new Stack<>(); |
789 | 772 | int j = 0; |
790 | 773 | //先根据入栈序列,往栈中压入数据 |
791 | 774 | for (int i = 0; i < pushA.length; i++) { |
792 | 775 | //如果当前栈顶元素跟出栈序列当前遍历的元素一样,那么进行出栈处理 |
793 | | - while (stack.size()>0 && j<popA.length && popA[j] == stack.peek()) { |
| 776 | + while (stack.size()>0 && j<popA.length && popB[j] == stack.peek()) { |
794 | 777 | j++; |
795 | 778 | stack.pop(); |
796 | 779 | } |
797 | 780 | //将后面的元素压栈 |
798 | 781 | stack.push(pushA[i]); |
799 | 782 | } |
800 | 783 | //对剩余元素出栈 |
801 | | - while (stack.size()>0 && j<popA.length && popA[j] == stack.peek()) { |
| 784 | + while (stack.size()>0 && j<popA.length && popB[j] == stack.peek()) { |
802 | 785 | j++; |
803 | 786 | stack.pop(); |
804 | 787 | } |
|
0 commit comments