随笔档案

实现一棵多叉树

这棵树可以有任意多颗子树 0-n

    1
 2  3  4
5 6 7  8

输入建立二叉树，输入的格式是每个节点的具体数据和拥有的孩子数目

例如上面的树是这样建成的：
1 3
2 2
5 0
6 0
3 1
7 0
4 1
8 0

 

 

一个规划性问题

12个工厂分布在一条东西向高速公路的两侧，工厂距离公路最西端的距离分别是0、4、5、10、12、18、27、30、31、38、39、47.在这12个工厂中选取3个原料供应厂，使得剩余工厂到最近的原料供应厂距离之和最短，问应该选哪三个厂 ？
这是阿里云实习的笔试题

这个类似于电梯调度算法，电梯调度是一个点，这里是三个点。
最直观的做法是枚举所有的情况，P(12, 3)。
其实也就是这样。三个 for 循环，但是这就是一种暴力的解法。

 

面试题分析小结-3

33 O(1) 删除单链表中的节点

常规的方法是从 head 遍历到待删除节点 p 的上一个节点 q
q->next = p->next;
delete p;
遍历到 p 的时间复杂度是 O(N)

既然知道了 p ，则就可以 O(1) 得到下一个节点 t ，将 t 的值拷贝到 p 所指的节点，然后删除 t 即可。
t = p->next;
p->data = t->data;
p->next = t->next;
delete t;
这样时间复杂度是 O(1)

要考虑 p 是不是最后一个节点，但是最终不会影响 O(1) 的时间复杂度

void delete(node* p, node* head)
{
 if (p == 0 || head == 0)
 {
  return;
 }
 if (p->next != 0)
 {
  node* t = p->next;
  p->data = t->data;
  p->next = t->next;
  delete t;
  t = 0;
 }
 else
 {
  node * t = head;
  while (t->next != p)
  {
   t = t->next;
  }
  t->next = 0;
  delete p;
  p = 0;
 }
}

http://www.cppblog.com/jake1036/archive/2011/05/21/146879.html

34 找出数组中唯一出现一次的两个数
如果一个数组中其他数都是出现偶数次，只有一个数出现奇数次，则可以直接对这个数组中的所有元素进行异或运算，最终的结果即是这个出现奇数次的数。
异或运算的特性。

这里是有两个数出现了一次，其他数都出现了两次。
对整个数组进行异或运算，所得到的结果即是这两个数的异或值 a ^ b = c

考虑 c
考虑 c 的某位为 1 的那位，比如考虑最低的那个为 1 的位
根据这个位，把原数组分成两部门，即该位为 1 的集合和为 0 的集合，a 和 b 必然被分开，然后对这两个集合分别做异或运算，即可得到相应的 a 和 b 。

异或运算的特性：
a ^ (全 0) = a
a ^ (全 1) = ~a
a ^ a = 0
偶数个 a 异或 = 0
奇数个 a 异或 = a

http://www.cppblog.com/jake1036/archive/2011/05/21/146881.html

35 找出两个链表的第一个共同节点
这个题目也可以简化为判断两个单链表是否交叉
1.
最直观的解法是两个循环，直接检测，O(M * N)
2.
对每个节点的地址哈希 O(M + N)
3.
遍历两个链表，取得长度，然后再次遍历，先遍历长的那个链表，提前走 t 步，然后共同向后走，检测第一次两个节点地址是否一样，如果一样，则是那个共同节点。O(M + N)
4.
交叉的链表是 Y 型的，将其中一个链表 a 连到另一个链表 b 尾部，从 a 的 head 遍历，如果再次回到了 a 的 head 即可判定 a 和 b 是交叉的。如果想找到交叉节点，则同时从 a 的 head 和 b 的 head 遍历，直到 a 的 head 和 b 的 head 遇到一起时，这时 a 的 head 也就是 b 的 head 即是指向的那个公共节点。

http://www.cppblog.com/jake1036/archive/2011/05/22/146909.html

36 在字符串中删除指定的字符
给定两个字符串，删除第一个字符串中在第二个字符串出现的字符
例如：
"abcefgh", "abcef"
得到：
"gh"

先对第二个字符串，做 hash 记录要删除的字符
然后遍历第一个字符串，根据 hash 表，判断当前字符是否是要删除的那个字符
对第一个字符串的处理，可以利用一个指针和一个已删除的字符数目记录
也可以利用两个指针，分别记录当前遍历的字符和删除后的字符串记录

http://www.cppblog.com/jake1036/archive/2011/05/22/146944.html
http://baike.baidu.com/view/15482.htm
http://zh.wikipedia.org/wiki/ASCII
http://zh.wikipedia.org/wiki/File:ASCII_Code_Chart-Quick_ref_card.jpg

boost 中的 noncopyable

// boost
class noncopyable
{
protected:
 noncopyable() {}
 ~noncopyable() {}
private:
 noncopyable(const noncopyable&);
 const noncopyable& operator = (const noncopyable&);
};

class test : public noncopyable
{
};

int main()
{
 test a, b;
 // test b(a);
 // c = a;
}

这是通过继承的方式来实现的 noncopy

也可以通过组合的方式

class noncopyable
{
public:
 noncopyable() {}
 ~noncopyable() {}
private:
 noncopyable(const noncopyable&);
 const noncopyable& operator = (const noncopyable&);
}

class test
{
private:
 noncopyable noncopyable_;
};

int main()
{
 test a, c;
 // test b(a);
 // c = a;
}

http://www.cppblog.com/luke/archive/2009/03/13/76411.html
http://ebenzhang.blogbus.com/tag/noncopyable/
http://hi.baidu.com/jrckkyy/blog/item/e6b241de1645735f95ee37de.html
http://hi.baidu.com/jrckkyy/home
http://blog.csdn.net/alai04/article/details/577798
http://www.boost.org/doc/libs/1_47_0/boost/noncopyable.hpp

 

不能被继承的类、不能被拷贝的类、只能定义一个对象的类

不能被继承的类
将构造函数和析构函数定义为私有的，这样派生类在构造基类子对象时就不能调用基类私有的构造函数。
class T
{
private:
 T() {}
 ~T() {}
public:
 static T* create()
 {
  return new T();
 }
 static T* release(T*& p)
 {
  delete p;
  p = 0;
 }
};
见构造函数和析构函数声明为 private ，也限制了本身的对象创建。利用静态成员函数来创建创建和释放对象。
这种方式只能在堆上创建对象。
如果还想在栈上创建对象，利用友元机制，声明友元类，可以调用友元类的 private 构造函数和析构函数，但是友元关系不能被继承。其中一个友元类 virtual 继承自含有 private 构造函数和析构函数的被友元类。

不能拷贝的类
拷贝意味着拷贝构造函数和复制运算符，将拷贝构造函数和赋值运算符声明为 protected 的，并且不需要实现。
class T
{
protected:
 T(const T& rhs);
 T& operator = (const T& rhs);
};

只能声明一个对象的类
即是单例模式
将构造函数声明为 private 以防在栈上随意定义对象
定义一个 static 的本类型指针，只是指向唯一的一个对象
定义一个 static 成员函数，用于获得指向唯一的那个对象的指针

class T
{
private:
 T() {}
 ~T() {}
 static T* pt;
public:
 static T* getInstance()
 {
  if (pt == 0)
  {
   pt = new T();
  }
  return pt;
 }
};

T* T::pt = 0;

http://www.cppblog.com/jake1036/archive/2011/05/21/146870.html
http://blog.csdn.net/xkyx_cn/article/details/2245038
http://www.cublog.cn/u3/112083/showart_2237163.html
http://blog.csdn.net/ericming200409/article/details/5975874
http://blog.csdn.net/wulibin136/article/details/6347215
http://www.cppblog.com/unixfy/archive/2011/04/29/145340.html

31 随机生成只输出一次的 1-100 的 100 个元素

随机生成下标，将这个下标生成的值与 end 交换，然后 --end
继续在 0-end 范围内随机生成下标，然后将这个下标与 end 对应的元素交换，--end
直到生成完 100 个元素

http://www.cppblog.com/jake1036/archive/2011/05/20/146818.html

31 倒序输出链表中的元素
采用递归的策略
void print(node* p)
{
 if (p != 0)
 {
  print(p->next);
  cout << p->item << ' ';
 }
}

扩展：在函数体内不声明变量，求字符串的长度
int length(const char* s)
{
 if (*s != '\0')
 {
  return 1 + length(++s);
 }
 else
 {
  return 0;
 }
}

#include <iostream>
using namespace std;

int length(const char* s)
{
 if (*s != '\0')
 {
  return length(++s) + 1;
 }
 else
 {
  return 0;
 }
}

int main()
{
 char s[100];
 while (cin >> s)
 {
  cout << length(s) << endl;
  cout << strlen(s) << endl;
 }
}

http://www.cppblog.com/jake1036/archive/2011/05/21/146869.html

 

几个面试题的小分析

面试题 100 - 20 最长公共子串
求两个字符串的最长公共子串，不需要连续
根据当前的两个字符 a[i] b[j]
m[i][j]
= max(m[i - 1][j], m[i][j - 1], m[i - 1][j - 1] + k)
if (a[i] = b[j]) k = 1
else k = 0

m[LenA][LenB]

记录路径，根据 max 去哪个值，记录 m 矩阵的走势，是向右、向下还是向右下
求路径的时候，利用辅助矩阵 t[][] 记录的走势状态，递归求出具体的最长公共子串。

面试题 100 - 30 异常安全的复制
一般函数指针成员的类对象，对 operator = 进行重载
在重载的函数体内，有可能造成重新分配内存失败，造成了异常，原来的内存空间已经被释放掉了，无法恢复之前的状态。例如：
T& T::operator = (const T& rhs)
{
 if (this != &rhs)
 {
  delete [] pdata;
  pdata = new Type[];
  copy(...);
 }
 return *this;
}

这种情况下，可能 new 失败造成异常，但是 pdate 指向的内存已经被释放。

为了异常安全
采用临时多一份的策略
第一种方法是，使用一个临时指针，给这个指针分配块内存，然后删除原来的内存，将这个临时指针赋值给本对象中的指针成员。
T& T::operator = (const T& rhs)
{
 if (this != &rhs)
 {
  Type * temp = new Type[];
  copy(...);
  delete [] pdata;
  pdata = temp;
 }
 return *this;
}

第二种方法也是用临时多一份的策略，使用一个临时本类型的对象，利用拷贝构造函数，然后交换临时对象与本对象。
T& T::operator = (const T& rhs)
{
 if (this != &rhs)
 {
  T temp(rhs);
  swap(*this, temp);
 }
 return *this;
}

这里交换的是 *this 和 temp 的指针的值，而不是指针成员指向的内存内容，也就是说是做的对象的位交换。
这种有了一个临时对象，可以不用做自赋值的检测。即便是自赋值，也不会造成原数据的丢失。可以写成：
T& T::operator = (const T& rhs)
{
 T temp(rhs);
 swap(*this, temp);
 return *this;
}

上面的第一种做法，也可以不做自赋值检测。

最上面的非异常安全的做法是
1
0
1
当 0 过后，可能在产生 1 的时候异常，就无法恢复了。
临时多一份的策略是
1
2
1
即便在产生 2 的过程中发生了异常，仍然有一个，所以是异常安全的。
两个发生异常的阶段分别是
0->1
1->2
关键要看异常前的情况，如果异常前就保证有效，则即使发生了异常也没有问题，即是异常安全的。

http://www.cppblog.com/jake1036/archive/2011/05/20/146689.html
http://www.cppblog.com/jake1036/archive/2011/05/20/146816.html

使数组中的奇数位于偶数之前

从数组两端遍历，检测当前元素的奇偶性，条件允许时交换，直到两个索引交叉。

http://www.cppblog.com/jake1036/archive/2011/05/20/146798.html

求给定值的连续序列

例如给定值是 15
则有：
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15

求解
设定一个区间 [left, right]
计算 left 到 right 之间的所有和 sum
若 sum 小于给定值 n 则 right 右移
若 sum 大于给定值 n 则 left 右移
若 sum 等于给定值 n 则 left 右移

[left, right] 的初始是 [1, 1]

另一个问题
求解一个集合中两个元素之和等于给定值
先对这个集合进行排序，然后从两端遍历，若和大于给定值则右边的标记左移，若和小于给定值则左边的值右移。

http://www.cppblog.com/jake1036/archive/2011/05/19/146745.html

判断栈的 push 和 pop 序列是否正确

有两个队列分别是 push 队列和 pop 队列
判断其入栈出栈序列是否正确

利用一个辅助栈 tmp
扫描 pop 队列
对 pop 队列的首元素进行检测，首先检测 tmp 栈顶元素是否与 pop 队首元素一样，如果一样则将则将 tmp 栈顶元素删除。
如果不一样，则遍历整个 push 队列，将不一样的压入到 tmp 中，直到遇到一样的。
http://www.cppblog.com/jake1036/archive/2011/05/19/146731.html