《剑指 offer》¶

《剑指 offer》这本书给出了 50 到面试题，涉及到字符串处理，堆栈，链表，二叉树等问题的处理。

代码鲁榜性：边界条件，特殊输入，异常处理：空指针
分析方法：画图，举例，分解
查找和排序是常考：重点掌握二分查找，快速排序，归并排序
本书完整源代码在：

数值¶

二进制中 1 的个数¶

输入一个整数，输出该数二进制中 1 出现的次数。比如 9 的二进制 10001，输出是 2

n=n&n-1

int one_appear_count(int n)

数值的整数次方¶

要求不得使用库函数。这里注意考虑指数是 0 和负数的情况

double power(double base,int exponent)

打印 1 到最大的 n 位数¶

比如 n=3，就打印 1 到 999

void print_to_max_with_length(int n)

求 1+2+...+n¶

要求不用乘除法，for/while/if/else/switch 等关键字及条件判断语句

long long sum(unsigned int n);

不用加减乘除做加法¶

求 2 个整数之和

位运算

int sum(int a,int b

丑数¶

只包含因子 2，3，5 的数叫做丑数；比如 6(2x3), 8(2x2x2) 是丑数（ugly number）

求按从小到大的顺序，第 1500 个丑数

int ugly(int n)

字符串¶

替换空格¶

如把字符串中的每个空格替换成 %20

二遍扫描

void replace_blank(char *str);

把字符串转换成整数¶

比如 "12343567754" -> 12343567754

NULL,空串,正负号,溢出

int strToInt(char str);

第一个只出现一次的字符¶

在字符串中查找第一个只出现一次的字符

哈希表：值为出现的次数 二次扫描

char find_appear_once_char(char *string)

字符串的排列¶

输入一个字符串，打印该字符串中字符的所有排列

递归，分解

void print_full_permutation(char *string)

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

a. 翻转句子中单词的顺序，但单词内字符不变。如『I am a student』 -> 『student. a am I』

先以单词为单位翻转,整个句子再次翻转

char *reverse_by_word(char *string)

b. 左旋转字符串是把字符串其那面的若干位转义到字符串的尾部。比如 "abcedfsz" 和数字 2，结果是 "cedfszab"

char *left_rotate_string(char *s,int n)

链表¶

从尾到头打印链表¶

栈

void print_reversing(LinkList *head)

两个链表的第一个公共节点¶

长的链表先走k步

LinkListNode *common_node(LinkList *head1,LinkList head2);

在 O(1) 时间删除链表节点¶

已经有一个头节点指针，还有一个指向改删除节点的指针

用下一个节点的内容覆盖当前删除节点的内容，删除下一个节点

void deleteNode(LinkList *head,LinkList *targetToDelete);

输出链表中倒数第 K 个节点¶

使用两个指针，一个先走k-1步

void print_lastK(LinkList *head);

反转链表¶

三个指针

void reverse(LinkList *head);

反转二叉树呢？

合并 2 个排序的链表¶

要求合并以后链表任然排序

递归

LinkList *merge(LinkList *one,LinkList *two);

复杂链表的复制¶

在复杂链表结构中，每个节点都有一个指向下一个节点的 m_pNext; 还有一个指向任意节点的 m_pSibling

typedef struct LinkListNode{
    int m_value;
    LinkListNode *m_pNext;
    LinkListNode *m_pSlbling;
}LinkList;

LinkList * copy(LinkList *head);

列表&数列¶

数组中出现次数超过一半的数字¶

遍历数组，下一个数字和之前保存的数字一样就+1，否则就-1

int find_more_than_half_num(int *nums ,int length)

n 个整数中最小的 K 个数¶

快速排序 最大堆

void find_least_k(int *data,int n,int *ouput,int k)

最大的 K 个数呢？

连续子数组的最大和¶

输入一个整数数组，有正有负，求所有子数组的和的最大值

分析规律 动态规划

int max_of_subarray(int *data,int length)

从 1 到 n 整数中，1 出现的次数¶

比如 12，从 1 到 12 这些整数中，包含 1 的数字有 1， 10，11，12 ，1 出现了 5 次

int one_appear_count(int n)

把数组排成最小的数¶

输入一个正整数数组,把所有数字拼起来排出一个最小数

int minSort(int *nums, int length);

菲波那切数列¶

波那切数列 fabonacci , 也叫黄金分割数列, F (0)=0, F (1)=1, F (n)= F (n - 1)+ F (n - 2) ; 即 0、1、1、2、3、5、8、13、21、34、……

long long fabonacci(unsigned n)

调整数组顺序使奇数位于偶数前面¶

调整后，所有奇数在前半部分，偶数在后半部分

两边向中间扫描

void reorder(int *data,int length)

旋转数组的最小数字¶

旋转数组是指把一个数组最开始的若干个元素搬到数组的末尾。输入一个递增排序的数组的旋转，比如 {3，4，5，1，2} 是 {1，2，3，4，5} 的一个旋转。求该数组的最小值。

int min(int *num, int length)

数组中只出现一次的数字¶

数组中除了 2 个数字之外，其他的数组都出现了 2 次，找出这两个数

异或 二进制

如果是只有 1 个数字只出现一次，我们可以通过对数组依次做异或运算。

如果我们能把原数组分成 2 个子数组，每个子数组都包含一个只出现一次的数字，问题就能解决了。我们把数组中的所有数字依次做异或操作，如果有 2 个数字不一样，结果肯定不是 0，且异或结果数字的二进制表示中至少有一位是 1（不然结果不就是 0 了）

在结果数字二进制表示中找到第一个为 1 的位的位置，标记 n
以二进制表示中第 n 位是不是 1 为标准，把原数组分成 2 个子数组

void find_two_numbers_appear_once(int *data,int length,int *ouput)

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

有一个递增排序数组，和一个数字 s，找出数组中的 2 个数，使得和等于 s。输出任意一对即可

两边向中间扫描

void print_two_numbers(int *data,int length,int sum)

数组中的逆序对¶

数组中的两个数字如果前面一个数字大于后面的数字，这两个数字组成一个逆序对。如：[7，5，6，4] 的逆序对：(7,5)(7,6)(7,4)(5,4)(6,4)

输入一个数组，求出这个数组逆序对总数。

归并排序 O(nlogn),空间O(n)

int reversePairs(int *data,int length)

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

比如 {1，2，3，3，3，3，4，5}，数字 3 出现了 4 次

使用二分查找找第一个3，和最后一个3出现的位置

int appear_count(int *nums,int length,int n);

n 个色子的点数¶

把 n 个色子丢地上，朝上一面的点数之和为 s。输入 n，打印可能的值出现的概率

void print_sum_probability(int n)

扑克牌中的顺子¶

从扑克牌从随机抽 5 张牌，判断是不是顺子。A 是 1，J~K 是 11~13，大小王可以看出任意数字。

bool is_straight(int *data,int length)

圆圈中最后剩下的数字 (约瑟夫问题)¶

约瑟夫问题: 又称为约瑟夫环, N 个人围成一圈，从第一个开始报数，第 M 个将被杀掉，最后剩下一个，其余人都将被杀掉。例如 N=6，M=5，被杀掉的顺序是：5，4，6，2，3

0,1,...,n-1 这 n 个数字排成一个圆圈，从数字 0 开始从这个圆圈里面删除第 m 个数字，求出这个圆圈里最后剩下的数字。

int last_remaining(unsigned int n,unsigned int m)

栈 & 队列¶

用两个栈实现队列¶

队列就是在尾部插入节点，头部删除节点。

实现一个能找到栈的最小元素的函数¶

最小元素用辅助栈保存

int min(Stack *stack)

栈的压入，弹出序列¶

输入 2 个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。比如：

1，2，3，4，5 是压栈序列，4，5，3，2，1 是弹栈序列，但是 4，3，5，1，2 就不是弹栈序列

bool is_pop_order(int *push,int *pop,int length)

矩阵¶

矩阵用二维数组表示

从外向里顺时针打印矩阵¶

void print_matrix_clockwise(int *matrix,int cols,int rows);

延伸：按大小顺序打印矩阵

二维数组中的查找¶

二维数组中每一行从左到右递增，每一列从上到下递增，判断数组中是否包含该整数。

bool find(int *matrix,int rows,int columns,int numbers)

二叉树¶

重建二叉树¶

输入某二叉树的前序遍历和中序遍历的结果，重建该二叉树

BinaryTree *construct(int *preorder,int inroder,int length);

树的子结构¶

考察二叉树的基本操作。输入 2 课二叉树 A 和 B，判断 B 是不是 A 的子结构。

struct BinaryTreeNode{
    int m_value;
    BinaryTreeNode *m_pleft;
    BinaryTreeNode *m_pRight;
}

        8                   
       / \                 10
      /   \                / \                      
     6     10    子结构      11  9   
    / \    / \            
   5   7  9  11

bool subTree(BinaryTreeNode *root1,BinaryTreeNode *root2);

二叉树翻转¶

        8                   8
       / \                 / \
      /   \               /   \                         
     6     10    翻转后    10     6
    / \    / \          / \   / \
   5   7  9  11        11  9 7   5

交换每个节点的左右子树

void reverse(BinaryTreeNode *root);

从上往下打印二叉树¶

辅助队列

void print_binary_level(BinaryTreeNode *root)

二叉搜索树的后续遍历序列¶

输入一个整数数组，判断该数组是不是某二叉查找树的后续遍历序列的结果。比如【 5，7，6，9，11，10，8】是下面二叉查找树的后续遍历结果：

        8               
       / \                 
      /   \                                         
     6     10    
    / \    / \         
   5   7  9  11

寻找规律

bool is_post_order(BST *root,int *data, int length);

二叉树中和为某一值的路径¶

和为 22 的路径有 2 条：10--5--7， 10--12

递归，栈

void print_path(BinaryTree *root,int n)

二叉搜索树与双向链表¶

将二叉搜索树转换成一个排序的双向链表，只调整树中节点的指针指向

递归 分解问题

BST *transform(BST *root);

二叉树的深度¶