匿名网友
笔试题：
1 删除重复元素
给定一个已经排序的单链表，删除链表中的重复元素。
由于链表是已经排序的，也就是说，相同的元素必定相邻。这题感觉本来没什么问题，但是，同学们在讨论的时候，出现了两种不同的理解方式：
节点定义：
struct list_node {
int data;
list_node *next;
};
1.1 理解1
只删除多余的重复节点，要留下一个。例如，对于链表1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 4，输出的链表为1 -> 2 -> 3 -> 4。
list_node* remove_duplicates(list_node *head)
{
if(head == NULL || head->next == NULL) {
return head;
}
list_node *pre = head;
list_node *pnode = pre->next;
while(pnode != NULL) {
if(pre->data == pnode->data) {
pre->next = pnode->next;
delete pnode;
}
else {
pre = pnode;
}
pnode = pre->next;
}
return head;
}
1.2 理解2
将重复的节点全部删除。例如，对于链表1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 4，输出的链表为1 -> 4。
list_node* remove_duplicates(list_node *head)
{
if(head == NULL || head->next == NULL) {
return head;
}
bool is_remove = false;
list_node *pre = head;
list_node *pnode = pre->next;;
while(pnode != NULL) {
if(pre->data == pnode->data) {
is_remove = true;
pre->next = pnode->next;
delete pnode;
}
else {
if(is_remove) {
pre->data = pnode->data;
pre->next = pnode->next;
delete pnode;
is_remove = false;
}
else {
pre = pnode;
}
}
pnode = pre->next;
}
return head;
}
2 回文补全
给定一个字符串，将它补全为回文。例如，对于字符串abc，可以补全为abcdcba或者abcba，对于字符串abcb，可以补全为abcbbcba或者abcba，要求补全的回文长度最小。
基本思路：得到尾部的最长回文，然后将前面的部分反向添加到尾部即可。例如，对于字符串abc，尾部的最长回文是c，因此，将ab反向添加到尾部就变成了abcba，对于字符串abcb，尾部的最长回文是bcb，因此，将a反向添加到尾部就变成了abcba。
bool is_pal(const string &str)
{
size_t first = 0, last = str.size() - 1;
while(first < last) {
if(str[first] != str[last]) {
return false;
}
++first;
--last;
}
return true;
}
void pal(string &str)
{
string::iterator iter = str.begin();
while(iter != str.end()) {
string s(iter, str.end());
if(is_pal(s)) {
break;
}
++iter;
}
string s(str.begin(), iter);
reverse(s.begin(), s.end());
str += s;
}
面试题：
二维数组arr[m][m]表示一个棋盘，在该棋盘中设定起点arr[a][b]和终点arr[c][d]，求棋子从起点到终点的最小步数，并且棋子只能走日(如象棋中的马)。
