CongYang_96

剑指Offer题解

小知识(2) 读书笔记(1) 题解(6)

/ 注册

全部文章 / 剑指Offer题解（共45篇）

丑数

1.题目把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。如，输入7，返回82.思路方法一：个人感觉思路对的，可是牛客说我时间复杂度过大,但是代码比较直观所谓一个数m是...

2020-12-19

1 588

栈的压入、弹出序列

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

2020-12-17

0 568

合并两个排序的链表

1.题目输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。如，输入：{1,3,5},{2,4,6}；输出：{1,2,3,4,5,6}2.思路：方法一：迭代版本牛客官方思路初始化：定义cur指向新链表的头结点操作：如果l1指向的结点值小于等于l2指向的...

2020-12-12

0 408

反转链表

1.题目输入一个链表，反转链表后，输出新链表的表头。如，输入123，输出32.思路题目所给的是单链表，想了一下反转后的样子：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，......，第二个指向第一个，第一个指向null;知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。...

2020-12-11

0 428

链表中倒数第K个节点

1.题目输入一个链表，输出该链表中倒数第k个结点。如，输入：1,{1,2,3,4,5}；返回：{5}2.思路方法一：我首先想到的是存入hashmap，然后直接对应键值来取值，由于是倒数的，所以要有长度记录从0开始储存，记录长度为len，则找倒数第k个就是(len-k)个时间复杂度：O(n),空间复杂...

2020-12-10

0 479

调整数组位置使奇数位于偶数前面

1.题目输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。2.思路：方法一：新开数组空间换时间的解法, a.从头遍历数组,如果是奇数从头部放入到新数组中, b.从尾...

2020-12-09

0 513

数值的整数次方

1.题目给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。（保证base和exponent不同时为0 —）如，输入2，3；返回8.00000 2.思路方法一：直接调用Math类的pow方法 public class Solution { ...

2020-12-07

0 510

从头到尾打印链表

1.题目输入一个链表，按链表从尾到头的顺序返回一个ArrayList。如，输入：{67,0,24,58}；输出：[58,24,0,67]2.思路：方法一：这种反向输出很容易想到了栈 import java.util.ArrayList; import java.util.*; public clas...

2020-12-04

0 512

序列化二叉树

1.题目请实现两个函数，分别用来序列化和反序列化二叉树：二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空...

2020-12-02

0 449

按之字形顺序打印二叉树

1.题目：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。2.思路：方法一：与题目《把二叉树打印成多行》，《从上往下打印二叉树》类似，都是树的广度优先遍历(BFS),或者说是层序遍历；只不过这道题增...

2020-11-25

1 545