赋值运算需要注意的地方
对于重载的“=”函数,考察知识点如下:
把返回值的类型声明为该类型的引用;
把传入的参数的类型声明为常量引用;
释放自身已有的内存;
判断传入的参数和当前的实例(*this)是不是同一个实例。
于是有重载的=函数:
1 | class CMyString { |
如果我们在new char的时候发现内存不足,那么程序就会崩溃。于是我们有如下的代码:
1 | CMyString& CMyString::operator =(const CMyString &str) { |
这种情况下,如果内存不足,我们还没有修改原来的实例,也就保证了异常安全性。
这一道题考察对C++基础语法的理解,包括运算符参数、常量引用等等;还有内存泄漏;对高级程序员还要考察对异常安全性的理解。
二维数组的查找
对于已经排序的二维数组中数字的查找:从右上角开始查找。
1 | bool find(int** matrix, int rows, int columns, int number) { |
测试用例:二维数组包含了要查找的数字;没有包含要查找的数字;输入空指针。
数组扫描
例题:替换空格,将字符串中的空格替换为”%20”
解题思路:从后往前扫描。预先分配足够大的内存空间,两个指针分别从后往前扫描,一个指向原始字符串,另一个指向替换之后的字符串。参考代码如下。
1 | /* length为字符数组string的总容量,该容量足够大以容纳转换后的字符数组*/ |
注意,以下的情况必须通过测试:
1.输入的字符串包括的多个空格
2.输入的字符串没有空格
3.输入的字符串为NULL
注意,string的内存空间必须足够大。
合并两个数组的时候,如果从前往后复制需要移动元素多次,我们不妨考虑从后往前复制,以减少移动元素的次数。
链表考察
1 | struct ListNode { |
插入节点:
1 | Status addToTail(ListNode* &pHead, int Value) { |
删除节点:
1 | void removeNode(ListNode** pHead, int value) { |
重建二叉树
1 | struxt BTNode { |
由于先序遍历序列的第一个元素就是根节点的值,而在中序遍历序列中,位于这个值左边的元素都在左子树上,位于这个值右边的元素都在右子树上,这样就确定了根节点的元素,以及左右子树分别有哪些元素。递归的处理这两个序列,我们就可以重建出一颗二叉树。
1 | BTNode* Construct(int* preOrder, int* inOrder, int length) { |
快速排序
在数组中选择一个数字,将所有比这个数字小的数移动到整个数组的左边,大的数移动到数组的右边。递归的对数组的左右两边进行同样的处理。
1 | int Partition(int* data, int length, int start, int end) { |
旋转数组
旋转数组,如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转。输入一个旋转后的数组,输出数组的最小值,在$O(1)$的时间复杂度内实现。
用类似二分法的超照实现,比如在旋转数组{3, 4, 5, 1, 2}中,首先查找位于中间的元素,得到5,5>3,于是5位于第一个递增的子数组中,那么最小元素位于5后面的部分,即{1, 2};然后对这个子数组采取同样的查找操作,得到元素1,’’’ 1 >= 1 && 1 <= 2 ‘’’,于是最小元素位于{1, 2}的左边部分,即{1};最后不需要再查找了,因为{1}只包含一个元素,这个元素就是我们要找的最小元素。
基于以上的思路,我们可以写出如下的代码:
1 | /* 顺序查找*/ |
Fibonacci数列
基于动态规划的解法:
1 |
|
也可以基于如下公式:
$$
\begin{matrix}
f(n) & f(n-1) \
f(n-1) & f(n-2)
\end{matrix}
=
\begin{matrix}
1 & 1 \
1 & 0
\end{matrix}
^{n-1}
$$
求二进制中1的个数
依次判断证书最右边一位是不是1,然后右移。这样做有一个问题,如果输入一个负数,就会引起死循环。
1 | int numberOfOne(int n) { |
为了避免出现死循环,我们可以做左移运算:
1 | int numberOfOne(int n) { |
如果一个整数减去1,那么最右边的一个1会变成0.如果在这个1的右边有0存在,它们都会变成1;而这个1左边的所有的1保持不变。比如,1100 - 1 = 1011。这个时候,再对做减法得到的结果1011和原来的数1100做“与”运算,得到了1000,也就是说,我们“处理掉”了位于最右边的一个1.基于这样的思路,可以写出如下的代码。
1 | int numberOfOne(int n) { |
类似的,我们可以统计一个整数中1的个数,来判断它是不是2的整数次方;如果只有一位是1,那么它是2的整数次方,因而可以用0 == (n - 1) & n
来判断。