CongYang_96

剑指Offer题解

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

/ 注册

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

重建二叉树

1.题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。2.思路：根据中序遍历和前序遍历可以确定二叉树，具体过...

2020-11-05

1 500

平衡二叉树

1.题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。（在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树）2.思路：判断一个数是否为平衡二叉树。平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1，同样左子树是平衡二叉树，右子树为平衡二叉树。方法一：自上而下的遍历 publi...

2020-11-04

0 573

二进制中1的个数

1.题目：输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。2.思路：方法一：暴力法1、先将数字转换成二进制字符串2、用String.split()函数存入一个数组中3、遍历数组跟1比较，同时计数4、输出计数值 public class Solution { public...

2020-10-29

0 508

二叉树的深度

1.题目：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。2.思路：方法一：递归写法构思：传入某节点，调用该方法，返回的应该是以传入节点为根节点的树的深度，而树的深度，肯定和左右子树深度有关，所以进入这个方法后，就包含了左右子树...

2020-10-26

0 500

矩形覆盖

1.题目：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？比如n=3时，23的矩形块有3种覆盖方法：2.思路涂掉最后一级矩形的时候，是用什么方式完成的？ n = 1 的时候只能横着覆盖，一种 n = 2 的...

2020-10-14

0 444

数组中重复的数字

1.题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。2.思路：方法一：哈希+...

2020-10-14

0 601

和为S的两个数字

1.题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。对应每个测试案例，输出两个数，小的先输出。2.思路：这道题关键在于递增与乘积最小。首先，递增表示数字没有重复，并且是从左往右增大；其次，乘积最小，不难证明两个数字...

2020-10-12

0 607

数组中只出现一次的数字

1.题目：给定一个数组，数组中只有2个数字出现了一次，其余都出现了2次，找出这2个数字。2.思路：方法一：哈希法：暴力解法，直接存储每个数出现的次数，与《数组中出现次数超过一半的数字》的解法类似时间复杂度：O(n)空间复杂度：O(n)//num1,num2分别为长度为1的数组。传出参数//将num1...

2020-10-12

0 540

数组中出现次数超过一半的数字

1 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。2.思路：方法一：排序的方法先给数组排序，那么有超过数组长度一半的众数一定在...

2020-10-10

0 555

跳台阶

1.题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。2.思路：此题与变态跳台阶不同，它每次只能跳1级，或者2级，而变态跳台阶是可以跳n阶方法一：递归时间复杂度O(n^2) public class Solution { ...

2020-09-30

0 533