6 面试中的各项能力

38 数字在排序数组中出现的次数¶

nowCoder

题目描述

统计⼀个数字在排序数组中出现的次数。例如输⼊排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。

解题思路

见34. Find First and Last Position of Element in Sorted Array。

39 ⼆叉树的深度¶

题目描述

输⼊⼀棵⼆叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的⼀条路径，最长路径的长度为树的深度。

解题思路

见LeetCode 104. Maximum Depth of Binary Tree

题目描述

输⼊⼀棵⼆叉树的根结点，判断该树是不是平衡⼆叉树。如果某⼆叉树中任意结点的左右⼦树的深度相差不超过 1，那么它就是⼀棵平衡⼆叉树。

解题思路

见110. Balanced Binary Tree

40 数组中只出现⼀次的数字¶

题目描述

⼀个整型数组⾥除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现⼀次的数字。要求时间复杂度是 $O(n)$ ，空间复杂度是 $O(1)$ 。

解题思路

见LeetCode 260 Single Number III。

41 和为s的两个数字VS和为s的连续正数序列¶

和为s的两个数字¶

题目描述

输⼊⼀个递增排序的数组和⼀个数字 $s$ ，在数组中查找两个数，使得它们的和正好是 $s$ 。如果有多对数字的和等于 $s$ ，输出任意⼀对即可。

解题思路

参见LeetCode 167. Two Sum II - Input array is sorted

为s的连续正数序列¶

题目描述

输⼊⼀个正数s，打印出所有和为s的连续正数序列（⾄少含有两个数）。例如输⼊15，由于1＋2＋3＋4＋5＝4＋5＋6＝7＋8＝15，所以结果打印出3个连续序列1～5、4～6和7～ 8。

解题思路

42 翻转单词顺序 VS左旋转字符串¶

翻转单词顺序¶

题目描述

输⼊⼀个英⽂句⼦，翻转句⼦中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母⼀样处理。例如输⼊字符串"I am a student. "，则输出"student. a am I"。

解题思路

左旋转字符串¶

题目描述

字符串的左旋转操作是把字符串前⾯的若⼲个字符转移到字符串的尾部。请定义⼀个函数实现字符串左旋转操作的功能。⽐如输⼊字符串"abcdefg"和数字2，该函数将返回左旋转2 位得到的结果"cdefgab"。

解题思路

43 n个骰⼦的点数¶

题目描述

把 $n$ 个骰⼦扔在地上，所有骰⼦朝上⼀⾯的点数之和为 $s$ 。输⼊ $n$ ，打印出 $s$ 的所有可能的值出现的概率。

解题思路

44 扑克牌的顺⼦¶

题目描述

从扑克牌中随机抽5张牌，判断是不是⼀个顺⼦，即这5张牌是不是连续的。2～10为数字本⾝，A为1，J为11，Q为 12，K为13，⽽⼤、⼩王可以看成任意数字。

解题思路

45 圆圈中最后剩下的数字¶

题目描述

$0,1,…,n－1$ 这 $n$ 个数字排成⼀个圆圈，从数字0开始每次从这个圆圈⾥删除第 $m$ 个数字。求出这个圆圈⾥剩下的最后⼀个数字。

解题思路

46 求1＋2＋…＋n¶

题目描述

求 $1＋2＋…＋n$ ，要求不能使⽤乘除法、for、while、 if、else、switch、case等关键字及条件判断语句（A?B:C）。

解题思路

47 不⽤加减乘除做加法¶

题目描述

写⼀个函数，求两个整数之和，要求在函数体内不得使⽤＋、－、×、÷四则运算符号。

解题思路

48 不能被继承的类¶

题目描述

⽤C++设计⼀个不能被继承的类。

解题思路

49 把字符串转换成整数¶

解题思路

50 树中两个结点的最低公共祖先¶

解题思路