剑指offer之面试题3
#include <iostream>
using namespace std;
const int rowSize = 4;
const int colSize = 4;
int array[rowSize][colSize] = {
1, 2, 8, 9,
2, 3, 9, 12,
4, 7, 10, 13,
6, 8, 11, 15
};
struct Position
{
int xPos;
int yPos;
};
bool searchArray(int array[][colSize], int destValue, Position &postion)
{
if (array == NULL)
return false;
for (int i = 0; i < rowSize; i++)
{
if (array[i] == NULL)
return false;
}
bool flag = false;
for (int row = 0, col = colSize - 1; row < rowSize && col >= 0;)
{
if (array[row][col] > destValue)
{
col--;
}
else if (array[row][col] < destValue)
{
row++;
}
else
{
postion.xPos = row + 1;
postion.yPos = col + 1;
flag = true;
break;
}
}
return flag;
}
void print(int array[][colSize])
{
for (int i = 0; i < rowSize; i++)
{
for (int j = 0; j < colSize; j++)
{
cout << array[i][j] << " ";
}
cout << endl;
}
}
void main()
{
print(array);
Position position;
for (int i = 1; i <= 16; i++)
{
bool flag = searchArray(array, i, position);
if (flag == true)
cout << "find " << i << " at: " << "(" << position.xPos << ", " << position.yPos << ")" << endl;
else
cout << "can't find " << i << endl;
}
}
面试题4：替换空格
#include <iostream>
using namespace std;
void replace(char *source, const char *str = "%20")
{
if (source == NULL || str == NULL)
return;
const int length = strlen(source);
int count = 0;
for (int i = 0; i < length; i++)
{
if (source[i] == ' ')
count++;
}
if (count == 0)
return;
const int strLen = strlen(str);
if (strLen == 0)
{
cout << "本题不考虑这个情形" << endl;
return;
}
const int destLength = length + (strLen - 1) * count;
source[destLength] = '\0';
int destPos = destLength - 1;
for (int i = length - 1; i >= 0; i--)
{
if (source[i] == ' ')
{
for (int j = strLen - 1; j >= 0; j--)
{
source[destPos--] = str[j];
}
}
else
{
source[destPos--] = source[i];
}
}
}
void main()
{
const int size = 100;
char source[size] = " We are happy ";
replace(source);
cout << "after replace: " << endl;
cout << "source: " << source << endl;
}
面试题5：从尾到头打印链表
#include <iostream>
#include <stack>
using namespace std;
struct Node
{
Node(int i = 0, Node *next = NULL) : next(next), data(i) {}
Node *next;
int data;
};
void printLink(Node *head, bool flag, const char *str = "recurse")
{
if (head == NULL)
return;
static bool myFlag = false;
if (!myFlag)
{
cout << str << endl;
myFlag = true;
}
printLink(head->next, flag, str);
cout << head->data << " ";
}
void printLink(Node *head, const char *str = "iterator")
{
if (head == NULL)
return;
static bool myFlag = false;
if (!myFlag)
{
cout << str << endl;
myFlag = true;
}
stack<Node *> snode;
while (head != NULL)
{
snode.push(head);
head = head->next;
}
while (!snode.empty())
{
Node *node = snode.top();
cout << node->data << " ";
snode.pop();
}
}
Node *construct()
{
Node *head = NULL;
Node *pHead = head;
for (int i = 1; i <= 10; i++)
{
Node *node = new Node(i);
if (head == NULL)
{
head = node;
pHead = head;
}
else
{
pHead->next = node;
pHead = pHead->next;
}
}
return head;
}
void main()
{
Node *head = construct();
printLink(head, true);
cout << endl;
printLink(head);
}
面试题6：重建二叉树
#include <iostream>
#include <vector>
using namespace std;
struct Node
{
Node(int i = 0, Node *left = NULL, Node *right = NULL) : m_pLeft(left), m_pRight(right), data(i) {}
Node *m_pLeft;
Node *m_pRight;
char data;
};
const char *preOrder = "12473568";
const char *inOrder = "47215386";
const int len = strlen(preOrder);
Node *constructTree(const char *preOrder, const char *inOrder, int inLen)
{
if (preOrder == NULL || inOrder == NULL || inLen == 0)
return NULL;
Node *node = new Node(*preOrder);
int pos = 0;
while (inOrder[pos] != *preOrder)
pos++;
if (pos == inLen)
{
cerr << "wrong input" << endl;
return NULL;
}
node->m_pLeft = constructTree(preOrder + 1, inOrder, pos);
node->m_pRight = constructTree(preOrder + pos + 1, inOrder + pos + 1, inLen - pos - 1);
return node;
}
void printLevel(Node *root)
{
if (root == NULL)
return;
vector<Node *> nvec;
nvec.push_back(root);
int start = 0;
int end = 1;
int pos = end;
while (start != end)
{
Node *node = nvec[start];
cout << node->data << " ";
start++;
if (node->m_pLeft)
{
nvec.push_back(node->m_pLeft);
end++;
}
if (node->m_pRight)
{
nvec.push_back(node->m_pRight);
end++;
}
if (start == pos)
{
pos = end;
cout << endl;
}
}
}
void PreOrder(Node *root)
{
if (root)
{
cout << root->data << " ";
PreOrder(root->m_pLeft);
PreOrder(root->m_pRight);
}
}
void InOrder(Node *root)
{
if (root)
{
InOrder(root->m_pLeft);
cout << root->data << " ";
InOrder(root->m_pRight);
}
}
void main()
{
Node *root = constructTree(preOrder, inOrder, strlen(inOrder));
if (root == NULL)
{
cerr << "construct failed" << endl;
}
else
{
printLevel(root);
PreOrder(root);
cout << endl;
InOrder(root);
}
}
面试题7：用两个栈来实现队列
#include <iostream>
#include <stack>
using namespace std;
class MyQueue
{
public:
void add(int i)
{
istack2.push(i);
}
void del()
{
if (istack1.empty())
{
if (istack2.empty())
{
cout << "empty queue" << endl;
return;
}
while (!istack2.empty())
{
int data = istack2.top();
istack1.push(data);
istack2.pop();
}
}
istack1.pop();
}
int front()
{
if (istack1.empty())
{
if (istack2.empty())
{
cout << "empty queue" << endl;
return -1;
}
while (!istack2.empty())
{
int data = istack2.top();
istack1.push(data);
istack2.pop();
}
}
return istack1.top();
}
bool empty()
{
if (istack1.empty() && istack2.empty())
return true;
else
return false;
}
private:
stack<int> istack1;
stack<int> istack2;
};
void main()
{
MyQueue myQueue;
for (int i = 1; i <= 5; i++)
{
myQueue.add(i);
}
while (!myQueue.empty())
{
cout << myQueue.front() << endl;
myQueue.del();
}
}
面试题8：求旋转数组的最小值
#include <iostream>
using namespace std;
const int array[] = {7, 8, 9, 10, 1, 2, 3, 4, 5, 6};
const int size = sizeof array / sizeof *array;
int findMinValue(const int *array, int left, int right)
{
if (array == NULL || left < 0 || left > right || right < 0)
return -1;
if (left == right)
return array[left];
int mid = left + (right - left) / 2;
if (mid == left)
return min(array[left], array[right]);
int minValue;
while (left != right - 1)
{
mid = left + (right - left) / 2;
if (array[left] == array[mid] && array[mid] == array[right])
{
minValue = array[left];
for (int i = left + 1; i <= right; i++)
{
if (array[i] < minValue)
minValue = array[i];
}
return minValue;
}
if (array[mid] < array[right])
right = mid;
else if (array[mid] > array[left])
left = mid;
}
minValue = min(array[left], array[right]);
return minValue;
}
void main()
{
int value = findMinValue(array, 0, size - 1);
cout << "value: " << value << endl;
}
#include <iostream>
using namespace std;
int array[] = {1};
const int size = sizeof array / sizeof *array;
int getMinNumber(int *array, int size)
{
if (array == NULL || size <= 0)
return -1;
int leftIndex = 0;
int rightIndex = size - 1;
while (leftIndex != rightIndex - 1)
{
int mid = (rightIndex - leftIndex) / 2 + leftIndex;
if (array[leftIndex] == array[mid] && array[mid] == array[rightIndex])
{
int minValue = array[leftIndex];
for (int i = leftIndex + 1; i <= rightIndex; i++)
{
if (array[i] < minValue)
minValue = array[i];
}
return minValue;
}
if (array[leftIndex] < array[rightIndex])
{
return array[leftIndex];
}
if (array[mid] > array[leftIndex])
leftIndex = mid;
else
rightIndex = mid;
}
return array[rightIndex];
}
void main()
{
int ret = getMinNumber(array, size);
cout << "ret = " << ret << endl;
}
面试题9：斐波那契数列
三种方法：递归、循环和log(N)级解
题目简单，不写
面试题10：求十进制中1的个数
int getNumberOne1(int number)
{
int count = 0;
while (number)
{
count++;
number = number & (number - 1);
}
return count;
}
int getNumberOne2(int number)
{
int count = 0;
while (number)
{
if (number & 0x01)
count++;
number = number >> 1;
}
return count;
}
int getNumberOne3(long long int n)
{
int count = 0;
unsigned int flag = 1;
while (flag)
{
if (n & flag)
count++;
flag = flag << 1;
}
return count;
}
书中给出3种解法，解法2存在负数时变死循环
关于负数的二进制说明：
比如-1的二进制，首先是1, 00000000 00000000 00000000 00000001，补码：11111111 11111111 11111111 11111110，然后+1，得11111111 11111111 11111111 11111111，共计32个1
关于解法3，很奇怪的地方是居然能退出循环。。。不可思议！！！如果直接flag = flag << 32，flag的值却是1。。。oh, no!!! %>_<%
面试题11：数值的整数次方
#include <iostream>
using namespace std;
bool equalZero(double number)
{
if (number < 0.000001 && number > -0.000001)
return true;
else
return false;
}
double _myPow(double base, int exp)
{
if (exp == 0)
return 1;
if (exp == 1)
return base;
double result = _myPow(base, exp >> 1);
result *= result;
if (exp & 0x01)
result *= base;
return result;
}
double _myPow2(double base, int exp)
{
if (exp == 0)
return 1;
double result = 1;
while (exp)
{
if (exp & 0x01)
result *= base;
base *= base;
exp = exp >> 1;
}
return result;
}
double myPow(double base, int exp)
{
if (equalZero(base))
return 0;
if (exp == 0)
return 1;
bool flag = false;
if (exp < 0)
{
flag = true;
exp = -exp;
}
double result = _myPow2(base, exp);
if (flag)
{
result = 1 / result;
}
return result;
}
void main()
{
double base = -2.0;
int exp = -5;
double result = myPow(base, exp);
cout << "result: " << result << endl;
}
面试题12：打印1到最大的N位数
#include <iostream>
using namespace std;
const int size = 10;
char array[size];
void printNumber(int number)
{
int i;
for (i = 0; i < number; i++)
{
if (array[i] != '0')
break;
}
if (i == number)
return;
for (int j = i; j < number; j++)
{
cout << array[j];
}
cout << endl;
}
void printNumber2(int number)
{
int i;
for (i = 1; i <= number; i++)
{
if (array[i] != '0')
break;
}
if (i == number + 1)
return;
for (int j = i; j <= number; j++)
{
cout << array[j];
}
cout << endl;
}
void recursePrint(int number, int index)
{
if (index == number)
{
printNumber(number);
return;
}
for (int i = 0; i < 10; i++)
{
array[index] = i + '0';
recursePrint(number, index + 1);
}
}
void iteratorPrint(int number)
{
array[number + 1] = '\0';
bool flag = false;
while (true)
{
if (array[0] == '1')
break;
for (int i = number; i >= 0; i--)
{
if (i == number)
{
if (array[i] == '9')
{
array[i] = '0';
flag = true;
}
else
{
array[i]++;
break;
}
}
else
{
if (flag)
{
if (array[i] == '9')
{
array[i] = '0';
flag = true;
}
else
{
array[i]++;
flag = false;
break;
}
}
}
}
printNumber2(number);
}
}
void main()
{
memset(array, '0', size);
iteratorPrint(3);
}
面试题13：在O(1)时间删除链表结点
#include <iostream>
using namespace std;
struct Node
{
Node(int i = 0, Node *p = NULL) : data(i), next(p) {}
Node *next;
int data;
};
Node *construct(Node *&pNode)
{
Node *head = NULL;
Node *pHead = head;
for (int i = 1; i <= 10; i++)
{
Node *node = new Node(i);
if (i == 10)
pNode = node;
if (head == NULL)
{
head = node;
pHead = head;
}
else
{
pHead->next = node;
pHead = pHead->next;
}
}
return head;
}
void deleteNode(Node *&head, Node *destNode)
{
if (head == NULL || destNode == NULL)
return;
if (head == destNode)
{
head = head->next;
delete destNode;
return;
}
if (destNode->next == NULL)
{
Node *pHead = head;
while (pHead->next != destNode)
pHead = pHead->next;
pHead->next = NULL;
delete destNode;
return;
}
else
{
Node *destNodeNext = destNode->next;
destNode->data = destNodeNext->data;
destNode->next = destNodeNext->next;
delete destNodeNext;
}
}
void printLink(Node *head)
{
if (head == NULL)
return;
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
}
void main()
{
Node *pNode = NULL;
Node *head = construct(pNode);
cout << "before delete: " << endl;
printLink(head);
deleteNode(head, pNode);
cout << endl << "after delete: " << endl;
printLink(head);
}
面试题14：调整数组顺序使奇数位于偶数前面
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int size = sizeof array / sizeof *array;
void tranverse(int *array, int size)
{
if (array == NULL || size <= 0)
return;
int i = 0;
int j = size - 1;
while(true)
{
while (array[i] & 0x01)
i++;
while (!(array[j] & 0x01))
j--;
if (i > j)
break;
swap(array[i], array[j]);
}
}
void main()
{
tranverse(array, size);
copy(array, array + size, ostream_iterator<int>(cout, " "));
}
面试题15：链表中倒数第k个结点
本题注意点：1
1. 关于k的取值范围的判定
2. 如果链表长度恰好等于k时的处理
#include <iostream>
using namespace std;
struct Node
{
Node(int i = 0, Node *p = NULL) : data(i), next(p) {}
Node *next;
int data;
};
Node *construct(Node *pNode)
{
Node *head = NULL;
Node *pHead = head;
for (int i = 1; i <= 10; i++)
{
Node *node = new Node(i);
if (i == 10)
pNode = node;
if (head == NULL)
{
head = node;
pHead = head;
}
else
{
pHead->next = node;
pHead = pHead->next;
}
}
return head;
}
Node* findLastKNode(Node *head, int k)
{
if (head == NULL || k <= 0)
return NULL;
Node *fastNode = head;
Node *slowNode = head;
while (fastNode != NULL && k != 0)
{
fastNode = fastNode->next;
k--;
}
if (fastNode == NULL && k != 0)
{
cout << "k is too big" << endl;
return NULL;
}
while (fastNode != NULL)
{
fastNode = fastNode->next;
slowNode = slowNode->next;
}
return slowNode;
}
void printLink(Node *head)
{
if (head == NULL)
return;
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
}
void main()
{
Node *head = construct(NULL);
for (int i = 1; i <= 10; i++)
{
Node *node = findLastKNode(head, i);
if (node)
cout << "last " << i << " node: " << node->data << endl;
}
}
面试题16：反转链表
#include <iostream>
using namespace std;
struct Node
{
Node(int i = 0, Node *p = NULL) : data(i), next(p) {}
Node *next;
int data;
};
Node *construct(Node *pNode)
{
Node *head = NULL;
Node *pHead = head;
for (int i = 1; i <= 10; i++)
{
Node *node = new Node(i);
if (i == 10)
pNode = node;
if (head == NULL)
{
head = node;
pHead = head;
}
else
{
pHead->next = node;
pHead = pHead->next;
}
}
return head;
}
Node *recursiveReverse(Node *head, Node *&newHead)
{
if (head ->next == NULL)
return head;
Node *node = recursiveReverse(head->next, newHead);
if (newHead == NULL)
{
newHead = node;
node->next = head;
node = head;
node->next = NULL;
}
else
{
node->next = head;
node = head;
node->next = NULL;
}
return node;
}
Node *reverseLink(Node *head)
{
if (head == NULL || head->next == NULL)
return head;
Node *pHead = head;
Node *pHeadNext = head->next;
Node dump;
while (pHeadNext != NULL)
{
head->next = dump.next;
dump.next = head;
head = pHeadNext;
pHeadNext = pHeadNext->next;
}
head->next = dump.next;
dump.next = head;
head = pHeadNext;
return dump.next;
}
Node* reverse(Node *head)
{
if(head == NULL) {
cout << "link is null" << endl;
return NULL;
}
Node *newHead = NULL, *pHeadNext = head;
while(pHeadNext) {
head = pHeadNext;
pHeadNext = pHeadNext->next;
head->next = newHead;
newHead = head;
}
return newHead;
}
void printLink(Node *head)
{
if (head == NULL)
return;
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
}
void main()
{
Node *head = construct(NULL);
Node *pHead = NULL;
recursiveReverse(head, pHead);
printLink(pHead);
Node *newHead = reverseLink(pHead);
cout << endl;
printLink(newHead);
cout << endl;
Node *newHead2 = reverse(newHead);
printLink(newHead2);
}
递归算法：
Node* recursiveReverse(Node *PreNode, Node *CurrentNode)
{
Node* resultNode;
if(CurrentNode == NULL)
return NULL;
if(CurrentNode->next == NULL)
{
CurrentNode->next = PreNode;
resultNode = CurrentNode;
}
else
{
resultNode = recursiveReverse(CurrentNode, CurrentNode->next);
CurrentNode->next = PreNode;
}
PreNode->next = NULL;
return resultNode;
}
╮(╯▽╰)╭一天才做了这几道，哭啊。。。伤心。。。
面试题17：合并两个排序链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
链表1: 1 3 5 7
链表2: 2 4 6 8
#include <iostream>
using namespace std;
struct Node
{
Node(int i = 0, Node *pNext = NULL) : data(i), next(pNext) {}
int data;
Node *next;
};
Node *construct()
{
Node *node4 = new Node(7);
Node *node3 = new Node(5, node4);
Node *node2 = new Node(3, node3);
Node *node1 = new Node(1, node2);
return node1;
}
Node* construct2()
{
Node *node4 = new Node(8);
Node *node3 = new Node(6, node4);
Node *node2 = new Node(4, node3);
Node *node1 = new Node(2, node2);
return node1;
}
Node* mergeLink(Node *head1, Node *head2)
{
if (head1 == NULL || head2 == NULL)
return NULL;
Node *pHead1 = head1;
Node *pHead2 = head2;
Node *head = NULL;
Node *pHead = head;
while (pHead1 != NULL && pHead2 != NULL)
{
if (head == NULL)
{
if (pHead1->data < pHead2->data)
{
head = pHead1;
pHead1 = pHead1->next;
pHead = head;
}
else
{
head = pHead2;
pHead2 = pHead2->next;
pHead = head;
}
}
else
{
if (pHead1->data < pHead2->data)
{
pHead->next = pHead1;
pHead1 = pHead1->next;
pHead = pHead->next;
}
else
{
pHead->next = pHead2;
pHead2 = pHead2->next;
pHead = pHead->next;
}
}
}
if (pHead1 == NULL)
pHead->next = pHead2;
else
pHead->next = pHead1;
return head;
}
void printLink(Node *head)
{
if (head == NULL)
return;
Node *pHead = head;
while (pHead != NULL)
{
cout << pHead->data << " ";
pHead = pHead->next;
}
return;
}
void main()
{
Node *head1 = construct();
Node *head2 = construct2();
cout << "two LINK: " << endl;
printLink(head1);
cout << endl;
printLink(head2);
cout << endl;
Node *newHead = mergeLink(head1, head2);
cout << "after merge: " << endl;
printLink(newHead);
}
这道题目很弱，但是书上给出的解法很NB
Node *recursiveMergeLink(Node *head1, Node *head2)
{
if (head1 == NULL)
return head2;
else if (head2 == NULL)
return head1;
Node *head;
if (head1->data < head2->data)
{
head = head1;
head->next = recursiveMergeLink(head1->next, head2);
}
else
{
head = head2;
head->next = recursiveMergeLink(head1, head2->next);
}
return head;
}
面试题18：树的子结构
题目：输入两颗二叉树A和B，判断B是不是A的子结构。
8
8 7
9 2
4 7
8
9 2
#include <iostream>
using namespace std;
struct Node
{
Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft), right(pRight) {}
int data;
Node *left;
Node *right;
};
Node* construct()
{
Node *node7 = new Node(7);
Node *node6 = new Node(4);
Node *node5 = new Node(2, node6, node7);
Node *node4 = new Node(9);
Node *node3 = new Node(7);
Node *node2 = new Node(8, node4, node5);
Node *node1 = new Node(8, node2, node3);
return node1;
}
Node* construct2()
{
Node *node3 = new Node(2);
Node *node2 = new Node(9);
Node *node1 = new Node(8);
return node1;
}
bool hasSubTree(Node *root1, Node *root2)
{
if (root2 == NULL)
return true;
if (root1 == NULL)
return false;
if (root1->data != root2->data)
return false;
else
return hasSubTree(root1->left, root2->left) && hasSubTree(root1->right, root2->right);
}
bool isSubTree(Node *root1, Node *root2)
{
if (root1 == NULL || root2 == NULL)
return false;
bool flag = false;
flag = hasSubTree(root1, root2);
bool leftFlag = false;
bool rightFlag = false;
if (root1->left)
leftFlag = isSubTree(root1->left, root2);
if (root1->right)
rightFlag = isSubTree(root1->right, root2);
return flag || leftFlag || rightFlag;
}
void main()
{
Node *root1 = construct();
Node *root2 = construct2();
bool result = isSubTree(root1, root2);
if (result == true)
cout << "has subtree" << endl;
else
cout << "no sub tree" << endl;
}
递归的方法很简单，那么关于迭代的方法呢。。。
#include <iostream>
#include <stack>
using namespace std;
struct Node
{
Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft), right(pRight) {}
int data;
Node *left;
Node *right;
};
Node* construct()
{
Node *node7 = new Node(7);
Node *node6 = new Node(4);
Node *node5 = new Node(2, node6, node7);
Node *node4 = new Node(9);
Node *node3 = new Node(7);
Node *node2 = new Node(8, node4, node5);
Node *node1 = new Node(8, node2, node3);
return node1;
}
Node* construct2()
{
Node *node3 = new Node(2);
Node *node2 = new Node(9);
Node *node1 = new Node(8, node2, node3);
return node1;
}
bool checkSubTree(Node *root1, Node *root2)
{
if (root1 == NULL || root2 == NULL)
return false;
stack<Node *> nstack1;
stack<Node *> nstack2;
bool result = true;
while (!nstack2.empty() || root2 != NULL)
{
if (root2 != NULL)
{
if (root1->data == root2->data)
{
nstack1.push(root1);
nstack2.push(root2);
root1 = root1->left;
root2 = root2->left;
}
else
{
result = false;
break;
}
}
else
{
root1 = nstack1.top();
root2 = nstack2.top();
nstack1.pop();
nstack2.pop();
root1 = root1->right;
root2 = root2->right;
}
}
return result;
}
bool isSubTree(Node *root1, Node *root2)
{
if (root1 == NULL || root2 == NULL)
return false;
stack<Node*> nstack;
bool result = false;
while (!nstack.empty() || root1 != NULL)
{
if (root1 != NULL)
{
if (checkSubTree(root1, root2) == true)
{
result = true;
break;
}
nstack.push(root1);
root1 = root1->left;
}
else
{
root1 = nstack.top();
nstack.pop();
root1 = root1->right;
}
}
return result;
}
void main()
{
Node *root1 = construct();
Node *root2 = construct2();
if (isSubTree(root1, root2) == true)
cout << "is subtree" << endl;
else
cout << "not a subtree" << endl;
}
面试题19：二叉树的镜像
题目：请完成一个函数，输入一棵二叉树，该函数输出它的镜像
8
6 10
5 7 9 11
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft), right(pRight) {}
int data;
Node *left;
Node *right;
};
Node* construct()
{
//Node *node7 = new Node(11);
Node *node6 = new Node(9);
Node *node5 = new Node(7);
Node *node4 = new Node(5);
Node *node3 = new Node(10, node6);
Node *node2 = new Node(6, node4, node5);
Node *node1 = new Node(8, node2, node3);
return node1;
}
void printLevel(Node *root)
{
if (root == NULL)
return;
queue<Node *> qnode;
qnode.push(root);
int count = 1;
int start = 0;
int tempCount = 0;
while (!qnode.empty())
{
tempCount = 0;
while (start != count)
{
Node *top = qnode.front();
if (top != NULL)
{
if (top->left)
{
qnode.push(top->left);
tempCount++;
}
else if (top->left == NULL && top->right != NULL)
{
qnode.push(NULL);
tempCount++;
}
if (top->right)
{
qnode.push(top->right);
tempCount++;
}
else if (top->left != NULL && top->right == NULL)
{
qnode.push(NULL);
tempCount++;
}
}
start++;
if (top != NULL)
cout << top->data;
else
cout << " ";
qnode.pop();
}
count = tempCount;
start = 0;
cout << endl;
}
}
Node* swapTree(Node *root)
{
if (root == NULL)
return root;
swap(root->left, root->right);
swapTree(root->left);
swapTree(root->right);
return root;
}
void main()
{
Node *root = construct();
printLevel(root);
Node* root2 = swapTree(root);
printLevel(root2);
}
面试题20：顺时针打印矩阵
输入矩阵如下：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
输出：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
#include <iostream>
using namespace std;
const int size = 4;
int array[4][4] =
{
1, 2, 3, 4,
12, 13, 14, 5,
11, 16, 15, 6,
10, 9, 8, 7
};
void print(int (*array)[size])
{
for (int i = 0; i < (size + 1) / 2; i++)
{
for (int j = i; j < size - i; j++)
cout << array[i][j] << " ";
for (int j = i + 1; j < size - i; j++)
cout << array[j][size - i - 1] << " ";
for (int j = size - i - 2; j >= i; j--)
cout << array[size - i - 1][j] << " ";
for (int j = size - i - 2; j >= i + 1; j--)
cout << array[j][i] << " ";
}
}
void main()
{
print(array);
}
递归解法：
#include <iostream>
using namespace std;
const int size = 16;
int array[size] =
{
1, 2, 3, 4,
12, 13, 14, 5,
11, 16, 15, 6,
10, 9, 8, 7
};
void print(int *array, int rows, int cols, int index)
{
if (array == NULL || rows < 0 || cols < 0 || index >= min(rows >> 1, cols >> 1))
return;
for (int i = index; i < cols - index; i++)
cout << array[index * rows + i] << " ";
for (int i = index + 1; i < rows - index; i++)
cout << array[i * rows + cols - index - 1] << " ";
for (int i = cols - index - 2; i >= index; i--)
cout << array[(rows - index - 1) * rows + i] << " ";
for (int i = rows - index - 2; i > index; i--)
cout << array[i * rows + index] << " ";
print(array, rows, cols, index + 1);
}
void main()
{
print(array, 4, 4, 0);
}
面试题21：包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数，在该栈中，调用min，push及pop的时间复杂度都是O(1)
本题目一定要注意，保存的是最小元素的index，而不是最小元素，因为stack里面保存的不一定是int型，有可能是类
#include <iostream>
using namespace std;
class MyStack
{
public:
MyStack(int i = -1, int j = -1) : currentIndex(i), currentIndexMin(j) {}
void push(int item)
{
if (currentIndex == size - 1)
{
cerr << "over flow" << endl;
return;
}
data[++currentIndex] = item;
if (currentIndexMin == -1)
minIndex[++currentIndexMin] = currentIndex;
else if (item < data[minIndex[currentIndexMin]])
{
minIndex[++currentIndexMin] = currentIndex;
}
}
void pop()
{
if (currentIndex == -1)
{
cerr << "under flow" << endl;
return;
}
if (currentIndex == minIndex[currentIndexMin])
{
currentIndexMin--;
}
currentIndex--;
}
int min()
{
if (currentIndexMin == -1)
{
cerr << "under flow" << endl;
return -1;
}
return data[minIndex[currentIndexMin]];
}
private:
static const int size = 100;
int data[size];
int currentIndex;
int currentIndexMin;
int minIndex[size];
};
void main()
{
MyStack myStack;
myStack.push(3);
myStack.push(5);
myStack.push(1);
myStack.push(2);
myStack.push(4);
cout << myStack.min() << endl;
myStack.pop();
cout << myStack.min() << endl;
myStack.pop();
cout << myStack.min() << endl;
myStack.pop();
cout << myStack.min() << endl;
myStack.pop();
cout << myStack.min() << endl;
myStack.pop();
}
面试题22：栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该栈序列对应的一个弹出序列，但是4、3、5、1、2就不可能是该压栈序列的弹出序列。
#include <iostream>
#include <stack>
using namespace std;
int source[] = {1, 2, 3, 4, 5};
int dest[] = {4, 3, 2, 1, 5};
const int size = sizeof source / sizeof *source;
bool isPopSequence(int *source, int sizeSource, int *dest, int sizeDest)
{
if (source == NULL || dest == NULL || sizeSource != sizeDest)
return false;
stack<int> istack;
int indexDest = 0;
int indexSource = 0;
bool flag = false;
while (indexSource != sizeSource && indexDest != sizeDest)
{
istack.push(source[indexSource]);
indexSource++;
while (!istack.empty() && istack.top() == dest[indexDest])
{
istack.pop();
indexDest++;
}
}
if (indexSource == sizeSource && indexDest == sizeDest)
flag = true;
return flag;
}
void main()
{
bool result = isPopSequence(source, size, dest, size);
if (result)
cout << "pos sequence" << endl;
else
cout << "not a pop sequence" << endl;
}
面试题23：从上往下打印二叉树
题目：从上往下打印二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
8
6 10
5 7 9 11
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft), right(pRight){}
int data;
Node *left;
Node *right;
};
void printLevel(Node *root)
{
if (root == NULL)
return;
queue<Node *> qnodes;
qnodes.push(root);
int indexFast = 1;
int indexSlow = 1;
int index = 0;
while (!qnodes.empty())
{
Node *node = qnodes.front();
qnodes.pop();
if (node->left)
{
indexFast++;
qnodes.push(node->left);
}
if (node->right)
{
indexFast++;
qnodes.push(node->right);
}
index++;
cout << node->data << " ";
if (index == indexSlow)
{
indexSlow = indexFast;
cout << endl;
}
}
}
Node *construct()
{
Node *node7 = new Node(11);
Node *node6 = new Node(9);
Node *node5 = new Node(7);
Node *node4 = new Node(5);
Node *node3 = new Node(10, node6, node7);
Node *node2 = new Node(6, node4, node5);
Node *node1 = new Node(8, node2, node3);
return node1;
}
void main()
{
Node *root = construct();
printLevel(root);
}
面试题24：二叉搜索树的后序遍历序列
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果，如果是返回true，否则返回false，假设输入数组的任意两个数字都互不相同。
比如{5， 7， 6， 9， 11， 10， 8} 则返回true
{7， 4， 6， 5}返回false
#include <iostream>
using namespace std;
//int array[] = {5, 7, 6, 9, 11, 10, 8};
//int array[] = {6, 8, 7, 5};
int array[] = {3, 5};
const int size = sizeof array / sizeof *array;
bool _isPostOrder(int *array, int start, int end)
{
if (start > end)
return false;
if (start == end)
return true;
int index = end - 1;
while (index >= 0 && array[index] > array[end])
index--;
if (index == -1 || index == end - 1)
return _isPostOrder(array, start, end - 1);
else
return _isPostOrder(array, start, index) && _isPostOrder(array, index + 1, end - 1);
}
bool isPostOrder(int *array, int size)
{
if (array == NULL || size <= 0)
return false;
return _isPostOrder(array, 0, size - 1);
}
void main()
{
bool result = isPostOrder(array, size);
if (result)
cout << "post order" << endl;
else
cout << "not post order" << endl;
}
UT：
1. 空指针
2. 含有一个元素 {1}
3. 只有左子树 {2, 4, 3, 5} {1, 2, 3, 4}
4. 只有右子树 {6, 8, 7, 5} {4, 3, 2, 1}
5. 左右子树均有
面试题25：二叉树中和为某一值的路径
题目：输入一棵二叉树和一个整数，打印二叉树中结点值的和为输入整数的所有路径，从树的根节点开始往下一直到叶结点所经过的结点形成一条路径。
10
5 12
4 7
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
struct Node
{
Node(int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft), right(pRight) {}
int data;
Node *left;
Node *right;
};
Node* construct()
{
Node *node5 = new Node(-1);
Node *node4 = new Node(4);
Node *node3 = new Node(12);
Node *node2 = new Node(13, node4, node5);
Node *node1 = new Node(10, node2, node3);
return node1;
}
void printSum(Node *root, int sum, vector<Node *> nvec)
{
if (root == NULL)
return;
nvec.push_back(root);
if (root ->left == NULL && root->right == NULL)
{
if (sum == root->data)
{
for (vector<Node *>::iterator iter = nvec.begin(); iter != nvec.end(); ++iter)
cout << (*iter)->data << " ";
cout << endl;
}
nvec.pop_back();
return;
}
printSum(root->left, sum - root->data, nvec);
printSum(root->right, sum - root->data, nvec);
nvec.pop_back();
}
void main()
{
Node *root = construct();
vector<Node *> nvec;
printSum(root, 22, nvec);
}
面试题26：复杂链表的复制
#include <iostream>
using namespace std;
struct Node
{
Node(int i = 0, Node *nextNode = NULL, Node *nextRandNode = NULL) : data(i), next(nextNode), randNext(nextRandNode) {}
int data;
Node *next;
Node *randNext;
};
Node *construct()
{
Node *node5 = new Node(5);
Node *node4 = new Node(4, node5);
Node *node3 = new Node(3, node4);
Node *node2 = new Node(2, node3);
Node *node1 = new Node(1, node2);
node5->randNext = node1;
node4->randNext = node2;
node2->randNext = node5;
node1->randNext = node3;
return node1;
}
Node* copyLinkStepOne(Node *head)
{
if (head == NULL)
return head;
Node *pHead = head;
while (pHead != NULL)
{
Node *cloneNode = new Node(pHead->data);
cloneNode->next = pHead->next;
pHead->next = cloneNode;
pHead = cloneNode->next;
}
return head;
}
Node *copyLinkStepTwo(Node *head)
{
if (head == NULL)
return head;
Node *pHead = head;
Node *pCloneHead = pHead->next;
while (pHead != NULL)
{
pCloneHead->randNext = pHead->randNext;
pHead = pCloneHead->next;
if (pHead != NULL)
pCloneHead = pHead->next;
}
return head;
}
Node *copyLinkStepThree(Node *head)
{
if (head == NULL)
return head;
Node *pHead = head;
Node *cloneHead = pHead->next;
Node *pCloneHead = cloneHead;
while (pHead != NULL)
{
pHead->next = pCloneHead->next;
pHead = pCloneHead->next;
if (pHead != NULL)
{
pCloneHead->next = pHead->next;
pCloneHead = pCloneHead->next;
}
else
{
pCloneHead->next = NULL;
}
}
return cloneHead;
}
void printLink(Node *head)
{
if (head == NULL)
return;
cout << head->data << '\t';
if (head->randNext != NULL)
cout << head->randNext->data << endl;
else
cout << endl;
printLink(head->next);
}
void printLink2(Node *head)
{
if (head == NULL)
return;
Node *pHead = head;
while (pHead != NULL)
{
cout << pHead->data << '\t';
if (pHead->randNext != NULL)
cout << pHead->randNext->data << endl;
else
cout << endl;
pHead = pHead->next;
}
}
void main()
{
Node *head = construct();
cout << "source link: " << endl;
printLink(head);
Node *tempCloneHead = copyLinkStepOne(head);
tempCloneHead = copyLinkStepTwo(tempCloneHead);
Node *cloneHead = copyLinkStepThree(tempCloneHead);
cout << "After Copy!!!: Source Link" << endl;
printLink(head);
cout << "After Copy!!!: Clone Link" << endl;
printLink(cloneHead);
}
UT:
1. NULL指针
2. 只有1个node
3. 普通链表
4. 正常的复杂链表
面试题27：二叉搜索树与双向链表
题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表，要求不能创建任何新的结点，只能调整树中结点指针的指向。
10
6 14
4 8 12 16
输出：4 6 8 10 12 14 16
#include <iostream>
#include <stack>
using namespace std;
struct Node
{
Node(int i = 0, Node *nextNode = NULL, Node *nextRandNode = NULL) : data(i), left(nextNode), right(nextRandNode) {}
int data;
Node *left;
Node *right;
};
Node *construct()
{
Node *node7 = new Node(16);
Node *node6 = new Node(12);
Node *node5 = new Node(8);
Node *node4 = new Node(4);
Node *node3 = new Node(14, node6, node7);
Node *node2 = new Node(6, node4, node5);
Node *node1 = new Node(10, node2, node3);
return node1;
}
Node* convert2LinkRecursive(Node *root)
{
if (root == NULL)
return root;
static Node *head = NULL;
static Node *pHead = head;
convert2LinkRecursive(root->left);
if (head == NULL)
{
head = root;
pHead = head;
}
else
{
pHead->right = root;
root->left = pHead;
pHead = root;
}
convert2LinkRecursive(root->right);
return head;
}
Node* convert2LinkIterator(Node *root)
{
if (root == NULL)
return root;
Node *head = NULL;
Node *pHead = head;
stack<Node *> snode;
while (root != NULL || !snode.empty())
{
while (root != NULL)
{
snode.push(root);
root = root->left;
}
root = snode.top();
if (head == NULL)
{
head = root;
pHead = head;
}
else
{
pHead->right = root;
root->left = pHead;
pHead = root;
}
root = root->right;
snode.pop();
}
return head;
}
void printLink(Node *head)
{
if (head == NULL)
return;
cout << head->data << " ";
printLink(head->right);
}
void printLinkLeft(Node *head)
{
if (head == NULL)
return;
Node *pHead = head;
while (pHead->right != NULL)
{
pHead = pHead->right;
}
while (pHead != head)
{
cout << pHead->data << " ";
pHead = pHead->left;
}
cout << pHead->data << endl;
}
void inorder(Node *root)
{
if (root)
{
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
void main()
{
Node *root = construct();
inorder(root);
cout << endl;
Node *head = convert2LinkIterator(root);
printLink(head);
cout << endl;
printLinkLeft(head);
}
面试题28：字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列，例如输入字符串abc，则打印出字符串a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和aba。
#include <iostream>
#include <vector>
using namespace std;
char str[] = {'a', 'b', 'c'};
const int size = sizeof str / sizeof *str;
void printCombine2(char *str, int index, int size)
{
if (str == NULL || index < 0 || size <= 0 || index > size)
return;
if (index == size)
cout << str << endl;
for (int i = index; i < size; i++)
{
swap(str[i], str[index]);
printCombine2(str, index + 1, size);
swap(str[i], str[index]);
}
}
bool isSolution(int index, int size)
{
return index == size;
}
void processSolution(char *states, int statesSize)
{
if (states == NULL || statesSize <= 0)
return;
for (int i = 0; i < statesSize; i++)
cout << states[i] << " ";
cout << endl;
}
void generateCandidates(char *str, int size, char *states, char *candidates, int *ncandidates, int index)
{
if (str == NULL || size <= 0 || states == NULL || candidates == NULL || ncandidates == NULL)
return;
*ncandidates = 0;
for (int i = 0; i < size; i++)
{
int j;
for (j = 0; j < index; j++)
{
if (str[i] == states[j])
break;
}
if (j == index)
{
candidates[*ncandidates] = str[i];
*ncandidates = *ncandidates + 1;
}
}
}
void printCombine(char *str, int size, char *states, int statesSize, int index)
{
if (str == NULL || size <= 0 || states == NULL || statesSize <= 0 || index < 0 || index > statesSize)
return;
if (isSolution(index, statesSize) == true)
{
processSolution(states, statesSize);
}
else
{
int ncandidates;
char candidates[100];
generateCandidates(str, size, states, candidates, &ncandidates, index);
for (int i = 0; i < ncandidates; i++)
{
states[index] = candidates[i];
printCombine(str, size, states, statesSize, index + 1);
}
}
}
void main()
{
char states[100];
printCombine(str, size, states, size, 0);
}
面试题29: 数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字，例如输入一个长度为9的数组{1， 2， 3， 2， 2， 2， 5， 4， 2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int array[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
const int size = sizeof array / sizeof *array;
int myPartition1(int *array, int size)
{
if (array == NULL || size <= 0)
return -1;
int pivot = array[size - 1];
int i = -1;
int j = 0;
while (j < size - 1)
{
if (array[j] < pivot)
{
i++;
swap(array[i], array[j]);
}
j++;
}
i++;
swap(array[i], array[j]);
return i;
}
int myPartition2(int *array, int left, int right)
{
if (array == NULL)
return -1;
if (left == right)
return left;
int leftIndex = left;
int rightIndex = right - 1;
int &pivot = array[right];
while (leftIndex <= rightIndex)
{
while (leftIndex < right && array[leftIndex] <= pivot)
leftIndex++;
while (rightIndex >= left && array[rightIndex] > pivot)
rightIndex--;
if (leftIndex > rightIndex)
break;
swap(array[leftIndex], array[rightIndex]);
}
swap(array[leftIndex], pivot);
return leftIndex;
}
int partitionIndex(int *array, int size, int k)
{
if (array == NULL || size <= 0 || k <= 0 || k > size)
return -1;
k = k - 1;
int pos = -1;
int left = 0;
int right = size - 1;
while (true)
{
pos = myPartition2(array, left, right);
if (pos < k)
left = pos + 1;
else if (pos > k)
right = pos - 1;
else
break;
}
return array[pos];
}
void main()
{
int result = partitionIndex(array, size, (size + 1) >> 1);
cout << "mid value = " << result << endl;
for (int i = 1; i <= size; i++)
{
int result = partitionIndex(array, size , i);
cout << "result = " << result << endl;
}
}
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int array[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
const int size = sizeof array / sizeof *array;
int findMoreThanHalf(int *array, int size)
{
if (array == NULL || size <= 0)
return -1;
int candidate = array[0];
int count = 1;
for (int i = 1; i < size; i++)
{
if (count == 0)
{
candidate = array[i];
count = 1;
continue;
}
if (candidate == array[i])
count++;
else
count--;
}
return candidate;
}
void main()
{
int result = findMoreThanHalf(array, size);
cout << "result = " << result << endl;
}
面试题30：最小的K个数
题目：输入n个整数，找出其中最小的K个数，例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4
思路1：利用partition来求解，代码同上
思路2：利用最大堆来求解
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
void keepHeap(int *array, int position, int size)
{
if (array == NULL || size <= 0)
return;
int start = position;
int maxPos = start;
while (start < size / 2)
{
int leftChild = 2 * start + 1;
int rightChild = 2 * start + 2;
maxPos = start;
if (leftChild < size)
{
if (array[start] < array[leftChild])
maxPos = leftChild;
}
if (rightChild < size)
{
if (array[maxPos] < array[rightChild])
maxPos = rightChild;
}
if (maxPos != start)
{
swap(array[start], array[maxPos]);
start = maxPos;
}
else
break;
}
}
void buildMaxHeap(int *array, int size)
{
if (array == NULL || size <= 0)
return;
for (int i = (size - 1) / 2; i >= 0; i--)
keepHeap(array, i, size);
}
void getKMin(int *data, int size, int *array, int k)
{
if (data == NULL || size <= 0 || array == NULL || k <= 0)
return;
if (k >= size)
{
for (int i = 0; i < size; i++)
array[i] = data[i];
copy(array, array + size, ostream_iterator<int>(cout, " "));
return;
}
else
{
for (int i = 0; i < k; i++)
array[i] = data[i];
}
buildMaxHeap(array, k);
for (int i = k; i < size; i++)
{
if (data[i] < array[0])
{
array[0] = data[i];
keepHeap(array, 0, k);
}
}
copy(array, array + k, ostream_iterator<int>(cout, " "));
}
void main()
{
const int k = 5;
int array[k];
int data[] = {5, 4, 1, 9, 8, 7, 6, 2, 3};
const int size = sizeof data / sizeof *data;
getKMin(data, size, array, k);
}
UT：
1. k的取值问题，如果k为负数、0、正数(比size小，和size一样大，比size大)
2. 数组data的值选取
思路3：利用计数排序的思想来求解
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
const int maxNumber = 20;
void getKMin(int *data, int size, int *array, int k)
{
if (data == NULL || size <= 0 || array == NULL || k <= 0)
return;
if (k >= size)
{
for (int i = 0; i < size; i++)
array[i] = data[i];
copy(array, array + size, ostream_iterator<int>(cout, " "));
return;
}
int count[maxNumber];
for (int i = 0; i < maxNumber; i++)
count[i] = 0;
for (int i = 0; i < size; i++)
{
count[data[i]]++;
}
int index = 0;
for (int i = 0; i < maxNumber; i++)
{
for (int j = 0; j < count[i]; j++)
{
array[index] = i;
index++;
if (index == k)
goto here;
}
}
here:
copy(array, array + k, ostream_iterator<int>(cout, " "));
}
void main()
{
const int k = 5;
int array[k];
int data[] = {5, 4, 1, 9, 8, 7, 6, 2, 3};
const int size = sizeof data / sizeof *data;
getKMin(data, size, array, 5);
}
面试题31：连续子数组的最大和
题目：输入一个整形数组，数组里有正数也有负数，数组中一个或连续的多个整数组成一个子数组，求所有子数组和的最大值，要求时间复杂度为O(N)
#include <iostream>
using namespace std;
int array[] = {-2, 5, 3, -6, 4, -8, 6};
const int size = sizeof array / sizeof *array;
bool gStatus = false;
int getMaxSum(int *array, int size)
{
if (array == NULL || size <= 0)
{
gStatus = true;
return -1;
}
int maxSum = -65535;
int tempSum = 0;
for (int i = 0; i < size; i++)
{
tempSum += array[i];
if (tempSum > maxSum)
maxSum = tempSum;
if (tempSum < 0)
tempSum = 0;
}
return maxSum;
}
int getMaxSum2(int *array, int size)
{
if (array == NULL || size <= 0)
{
gStatus = true;
return -1;
}
int maxInclude = array[0];
int maxExclude = array[0];
for (int i = 1; i < size; i++)
{
maxExclude = max(maxInclude, maxExclude);
maxInclude = max(array[i] + maxInclude, array[i]);
}
return max(maxInclude, maxExclude);
}
void main()
{
int result = getMaxSum2(array, size);
cout << "result = " << result << endl;
}
面试题32：从1到n正数中1出现的次数
题目：输入一个正数n，求从1到n这n个整数的十进制表示中1出现的次数，例如输入12，从1到12这些整数中包含1的数字有1，10,11和12，1共出现了5次。
#include <iostream>
using namespace std;
int getOneNumber(int number)
{
int count = 0;
int currentNumber;
int preNumber;
int posNumber;
int position = 1;
while (number / position)
{
currentNumber = (number / position) % 10;
preNumber = number / (position * 10);
posNumber = number % position;
switch (currentNumber)
{
case 0:
count += preNumber * position;
break;
case 1:
count += preNumber * position + posNumber + 1;
break;
default:
count += (preNumber + 1) * position;
break;
}
position *= 10;
}
return count;
}
void main()
{
int number = getOneNumber(123);
cout << "number = " << number << endl;
}
话说书上的递归解我就想不出来。。。
#include <iostream>
using namespace std;
const char *input = "123";
int myExp(int base, int exp)
{
int result = 1;
for (int i = 0; i < exp; i++)
result *= base;
return result;
}
int getOneNumber(const char *input)
{
if (input == NULL || *input < '0' || *input > '9' || *input == '\0')
return 0;
int length = strlen(input);
int currentNumber = input[0] - '0';
if (length == 1)
{
if (currentNumber == 0)
return 0;
else
return 1;
}
int currentCount;
int otherCount;
if (currentNumber == 1)
{
currentCount = atoi(input + 1) + 1;
}
else
{
currentCount = myExp(10, length - 1);
}
otherCount = currentNumber * (length - 1) * myExp(10, length - 2);
return currentCount + otherCount + getOneNumber(input + 1);
}
void main()
{
int result = getOneNumber(input);
cout << "result = " << result << endl;
}
面试题33：把数组排成最小的数
题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接处的所有数字钟最小的一个。例如输入数组{3，32，321}，则打印出这3个数字能排成的最小数字321323
#include <iostream>
#include <iterator>
#include <algorithm>
#include <sstream>
#include <string>
using namespace std;
int compare(const char *lhs, const char *rhs, char *lhsCatRhs, char *rhsCatLhs)
{
if (lhs == NULL || rhs == NULL)
return false;
int lenLhs = strlen(lhs);
int lenRhs = strlen(rhs);
strncpy(lhsCatRhs, lhs, lenLhs);
strncpy(lhsCatRhs + lenLhs, rhs, lenRhs);
lhsCatRhs[lenLhs + lenRhs] = 0;
strncpy(rhsCatLhs, rhs, lenRhs);
strncpy(rhsCatLhs + lenRhs, lhs, lenLhs);
rhsCatLhs[lenLhs + lenRhs] = 0;
return strcmp(lhsCatRhs, rhsCatLhs);
}
string myItoa(int number)
{
stringstream ss;
ss.str("");
ss << number;
string str = ss.str();
return str.c_str();
}
int partition(int *array, int left, int right, char *lhsCatRhs, char *rhsCatLhs)
{
if (array == NULL)
return -1;
int leftIndex = left;
int& pivot = array[right];
int rightIndex = right - 1;
while (leftIndex < right)
{
while (leftIndex < right && compare(myItoa(array[leftIndex]).c_str(), myItoa(pivot).c_str(), lhsCatRhs, rhsCatLhs) <= 0)
leftIndex++;
while (rightIndex >= 0 && compare(myItoa(array[rightIndex]).c_str(), myItoa(pivot).c_str(), lhsCatRhs, rhsCatLhs) > 0)
rightIndex--;
if (leftIndex > rightIndex)
break;
swap(array[leftIndex], array[rightIndex]);
}
swap(array[leftIndex], pivot);
return leftIndex;
}
void fastSort(int *array, int start, int end, char *lhsCatRhs, char *rhsCatLhs)
{
if (array == NULL || start >= end)
return;
int pos = partition(array, start, end, lhsCatRhs, rhsCatLhs);
fastSort(array, start, pos - 1, lhsCatRhs, rhsCatLhs);
fastSort(array, pos + 1, end, lhsCatRhs, rhsCatLhs);
}
void getMinNumber(int *array, int size, int maxDigits)
{
if (array == NULL || size <= 0)
return;
char *lhsCatRhs = new char[maxDigits + 1];
char *rhsCatLhs = new char[maxDigits + 1];
fastSort(array, 0, size - 1, lhsCatRhs, rhsCatLhs);
copy(array, array + size, ostream_iterator<int>(cout, " "));
cout << endl;
delete []lhsCatRhs;
delete []rhsCatLhs;
}
void main()
{
const int size = 3;
int array[size] = {3, 32, 321};
const int maxDigits = 10;
getMinNumber(array, size, maxDigits);
}
面试题34：丑数
题目：我们把只包含因子2、3和5的数称作丑数，求按从小到大的顺序的第1500个丑数。
#include <iostream>
using namespace std;
long long int findUglyNumber(int count)
{
long long int *pUglyNumbers = new long long int[count];
*pUglyNumbers = 1;
long long int *pUglyNumbersTwo = pUglyNumbers;
long long int *pUglyNumbersThree = pUglyNumbers;
long long int *pUglyNumbersFive = pUglyNumbers;
int i = 1;
while (i < count)
{
pUglyNumbers[i] = min(min(*pUglyNumbersTwo * 2, *pUglyNumbersThree * 3), *pUglyNumbersFive * 5);
while (*pUglyNumbersTwo * 2 <= pUglyNumbers[i])
pUglyNumbersTwo++;
while (*pUglyNumbersThree * 3 <= pUglyNumbers[i])
pUglyNumbersThree++;
while (*pUglyNumbersFive * 5 <= pUglyNumbers[i])
pUglyNumbersFive++;
++i;
}
long long int ugly = pUglyNumbers[count - 1];
delete[] pUglyNumbers;
return ugly;
}
void main()
{
long long int result = findUglyNumber(4);
cout << "result = " << result << endl;
}
面试题35：第一个只出现一次的字符
题目：在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出b
#include <iostream>
using namespace std;
char findFirstChar(const char *str)
{
if (str == NULL)
return '\0';
char result = '\0';
const int length = strlen(str);
const int size = 256;
int hashBuff[size];
for (int i = 0; i < size; i++)
hashBuff[i] = 0;
for (int i = 0; i < length; i++)
{
hashBuff[str[i]]++;
}
for (int i = 0; i <size; i++)
{
if (hashBuff[str[i]] == 1)
{
result = str[i];
break;
}
}
return result;
}
void main()
{
const char *str = "abaccdeff";
char result = findFirstChar(str);
cout << "result = " << result << endl;
}
面试题36：数组中的逆序对
题目：在数组中的两个数字如果前面一个数字大于后面的数字，则两个数字组成一个逆序对，输入一个数组，求出这个数组中的逆序对总数
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
const int size = 4;
int tempArray[size];
int findReversePair(int *array, int leftIndex, int rightIndex)
{
if (array == NULL)
return -1;
if (leftIndex == rightIndex)
return 0;
int midIndex = (leftIndex + rightIndex) >> 1;
int count = 0;
int leftCount = findReversePair(array, leftIndex, midIndex);
int rightCount = findReversePair(array, midIndex + 1, rightIndex);
for (int i = leftIndex; i <= midIndex; i++)
tempArray[i] = array[i];
for (int i = midIndex + 1; i <= rightIndex; i++)
tempArray[i] = array[i];
int i = leftIndex;
int j = midIndex + 1;
int k = leftIndex;
while (i <= midIndex && j <= rightIndex)
{
if (tempArray[i] > tempArray[j])
{
array[k] = tempArray[j];
count += midIndex - i + 1;
j++;
k++;
}
else
{
array[k] = tempArray[i];
i++;
k++;
}
}
if (i == midIndex + 1)
{
for (int m = j; m <= rightIndex; m++)
array[k++] = tempArray[m];
}
else if (j == rightIndex + 1)
{
for (int m = i; m <= midIndex; m++)
array[k++] = tempArray[m];
}
return count + leftCount + rightCount;
}
void main()
{
int array[] = {7, 5, 6, 4};
int result = findReversePair(array, 0, size - 1);
cout << "result = " << result << endl;
copy(array, array + size, ostream_iterator<int>(cout, " "));
}
面试题37：两个链表的第一个公共结点
题目：输入连个链表，找出它们的第一个公共结点。
1 2 3
6 7
4 5
#include <iostream>
using namespace std;
struct Node
{
Node(int i = 0, Node *pLeft = NULL) : data(i), next(pLeft) {}
int data;
Node *next;
};
void constructLink(Node *&head1, Node *&head2)
{
Node *node7 = new Node(7);
Node *node6 = new Node(6, node7);
Node *node5 = new Node(5, node6);
Node *node4 = new Node(4, node5);
Node *node3 = new Node(3, node6);
Node *node2 = new Node(2, node3);
Node *node1 = new Node(1,node2);
head1 = node1;
head2 = node4;
}
Node *findFirstCommonNode(Node *head1, Node *head2)
{
if (head1 == NULL || head2 == NULL)
return NULL;
int head1Len = 0;
int head2Len = 0;
Node *pHead1 = head1;
Node *pHead2 = head2;
while (pHead1 != NULL)
{
head1Len++;
pHead1 = pHead1->next;
}
while (pHead2 != NULL)
{
head2Len++;
pHead2 = pHead2->next;
}
pHead1 = head1;
pHead2 = head2;
if (head1Len > head2Len)
{
int dist = head1Len - head2Len;
while (dist)
{
pHead1 = pHead1->next;
dist--;
}
}
if (head1Len < head2Len)
{
int dist = head2Len - head1Len;
while (dist)
{
pHead2 = pHead2->next;
dist--;
}
}
while (pHead1 != NULL && pHead2 != NULL && pHead1 != pHead2)
{
pHead1 = pHead1->next;
pHead2 = pHead2->next;
}
return pHead1;
}
void main()
{
Node *head1;
Node *head2;
constructLink(head1, head2);
Node *commonNode = findFirstCommonNode(head1, head2);
cout << "common node: " << commonNode->data << endl;
}
面试题38：数字在排序数组中出现的次数
题目：统计一个数字在排序数组中出现的次数，例如输入排序数组{1， 2， 3， 3， 3， 3， 4， 5}和数字3，由于3在这个数组中出现4次，所有输出4
#include <iostream>
using namespace std;
int array[] = {3, 3, 3, 3, 3, 3, 3, 5};
const int size = sizeof array /sizeof *array;
int binarySearchLeftIndex(int *array, int size, int value)
{
if (array == NULL || size <= 0)
return -1;
int leftIndex = 0;
int rightIndex = size - 1;
while (leftIndex != rightIndex)
{
int midIndex = (leftIndex + rightIndex) >> 1;
if (array[midIndex] < value)
leftIndex = midIndex + 1;
else
rightIndex = midIndex;
}
if (array[leftIndex] == value)
return leftIndex;
else
return -1;
}
int binarySearchRightIndex(int *array, int size, int value)
{
if (array == NULL || size <= 0)
return -1;
int leftIndex = 0;
int rightIndex = size - 1;
while (leftIndex != rightIndex)
{
int midIndex = (leftIndex + rightIndex + 1) >> 1;
if (array[midIndex] > value)
rightIndex = midIndex - 1;
else
leftIndex = midIndex;
}
if (array[leftIndex] == value)
return leftIndex;
else
return -1;
}
void main()
{
int indexLeft = binarySearchLeftIndex(array, size, 3);
int indexRight = binarySearchRightIndex(array, size, 3);
int count;
if (indexLeft > -1 && indexRight > -1)
count = indexRight - indexLeft + 1;
else
count = 0;
cout << "count = " << count << endl;
}
面试题39：二叉树的深度
题目一：输入一棵二叉树的根节点，求该树的深度。从根节点到叶结点依次经历过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为数的深度。
题目二：输入一棵二叉树的根节点，判断该树是不是平衡二叉树，如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
1
2 3
4 5 6
7
#include <iostream>using namespace std;
struct Node
{
Node (int i = 0, Node *pLeft = NULL, Node *pRight = NULL) : data(i), left(pLeft), right(pRight) {}
int data;
Node *left;
Node *right;
};int getBinaryTreeDepth(Node *root)
{
if (root == NULL)
return 0;int leftDepth = getBinaryTreeDepth(root->left);
int rightDepth = getBinaryTreeDepth(root->right);return max(leftDepth, rightDepth) + 1;
}Node *construct()
{
Node *node7 = new Node(7);
Node *node6 = new Node(6);
Node *node5 = new Node(5, node7);
Node *node4 = new Node(4);
Node *node3 = new Node(3, NULL, node6);
Node *node2 = new Node(2, node4, node5);
Node *node1 = new Node(1, node2, node3);return node1;
}void main()
{
Node *root = construct();
int depth =