方龙的博客


  • 首页

  • 归档

  • 分类

  • 标签

  • 关于

  • 搜索
close

SwordPointToOffer(45): 圆圈中最后剩下的数字

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目0,1,…,n-1折n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 分析方法一 环形链表模拟圆圈的经典解法。 创建一个总共有 n 个结点的环形链表,然后每次在这个链表中删除第 m 个结点。时间复杂度$O(nm)$,空间复杂度$O(n)$。 ...
阅读全文 »

SwordPointToOffer(44): 扑克牌的顺子

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10位数字本身,A为1,J为11,Q为12,K为13,大小王看成任意数字(百搭牌)。 分析我们可以把 5 张牌看成由 5 个数字组成的数组。大、小王是特殊的数字,我们不妨把它们都定义为 0,这样就能和其他扑克牌区分开来了。 ...
阅读全文 »

SwordPointToOffer(43): n个骰子的点数

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目把n个骰子仍在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值的概率。 分析方法一 基于递归求解,时间效率不够高,有很多重复的计算。 先把 n 个骰子分为两堆:第一堆只有一个,另一个有 n-1 个。单独的那一个有可能出现从 1 到 6 的点数。我们需要计算从 1 到 6 的 ...
阅读全文 »

SwordPointToOffer(42): 翻转单词顺序 VS 左旋转字符串(补充)

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目字符串的左旋转操作时把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。 例如输入字符串“abcdefg”和数字2,该函数将返回左旋转2位得到的结果“cdefgab”。 分析以”abcdefg”为例,我们可以把它分为两部分。由于想把它的前两个字符移到后面,我们就 ...
阅读全文 »

SwordPointToOffer(42): 翻转单词顺序 VS 左旋转字符串

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。 例如输入字符串“I am a student.”,则输出“student. a am I”。 分析通过两次翻转实现。 第一步翻转句子中所有的字符。比如翻转“I am a student. ” ...
阅读全文 »

SwordPointToOffer(41): 和为s的两个数字VS和为s的连续整数序列(补充)

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目输入一个正数s,打印出所有和为s的连续正数序列(至少含有两个数)。 例如输入15,由于 1+2+3+4+5 = 4+5+6 = 7+8 = 15,所以输出3个连续序列。 分析考虑用两个数 small 和 big 分别表示序列的最小值和最大值。首先把 small 初始化为 1,big 初始化为 2 ...
阅读全文 »

SwordPointToOffer(41): 和为s的两个数字VS和为s的连续整数序列

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,输出乘积最小的一对。 例如:输入数组 {1,2,4,7,11,15} 和数字 15,会输出4和11。 分析我们先在数组中选择两个数字 (比如第一个和最后一个),如果它们的和等于输入的 s,我们 ...
阅读全文 »

SwordPointToOffer(40): 数组中只出现一次的数字

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字,要求时间复杂度是$O(n)$,空间复杂度是$O(1)$。 例如:输入数组 {2,4,3,6,3,2,5,5},会输出4和6。 分析这两个题目都在强调一个(或两个)数字只出现一次,其他的出现两次。这有什么意 ...
阅读全文 »

SwordPointToOffer(39): 二叉树的深度(补充)

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 分析方法一前一篇涉及到如何求二叉树的深度,借用这个可以递归实现平衡判断。 该方法不足之处在于需要重复遍历节点多次。 方法二用后序遍历的方式遍历二叉树的每一个节点,在遍 ...
阅读全文 »

SwordPointToOffer(39): 二叉树的深度

发表于 2017-02-07   |   分类于 SwordPointToOffer
题目输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成一条路径,最长路径的长度为树的深度。 分析递归的思想,取左子树和右子树最大的深度加1即为根的深度。 实现12345678910111213141516171819202122public class Tree ...
阅读全文 »
1…101112…26
方龙

方龙

梦想还是要有的,万一实现了呢

257 日志
33 分类
161 标签
GitHub
© 2016 - 2018 方龙
由 Hexo 强力驱动
主题 - NexT.Mist