剑指offer第六章

1.数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在数组中出现了4次，所以输出4

分析：思路1：直官思路：直接顺序扫描，O（n）

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) 
 4     {
 5         int count=0;
 6         for(int i=0;i<data.size();i++)
 7         {
 8             if(data[i]==k)
 9                 count++;
10         }
11         return count;
12 
13     }
14 };

思路2：因为是排序数组，所以想到二分查找，关键在于如何用二分查找找到第一个和最后一个k

找第一个k：先拿数组中间的数和k做比较，中间数字比k大，那么k只能出现在前半段，中间比k小，那么k只能出现在后半段，如果相等，先判断是不是第一个k如果中间数字的前一个不是k，则找到第一个k。如果前一个也是k，也就是说第一个k肯定在数组前半段，下一轮继续在前半段查找。

找最后一个k：同上

 1 class Solution {
 2     /*二分查找 找到第一个K 和 最后一个K 二者位置相减*/
 3 public:
 4     int GetNumberOfK(vector<int> data ,int k) {
 5         if(data.empty())
 6             return 0;
 7         int number = 0;
 8         int first = GetFirstIndex(data,k,0,data.size()-1);
 9         int last = GetLastIndex(data,k,0,data.size()-1);
10         if(first>-1 && last>-1)
11             number = last - first +1;
12         return number;
13         
14     }
15     int GetFirstIndex(vector<int> &data,int k,int start,int end){
16         if(start > end)
17             return -1;
18         int mid = start+(end-start)/2;
19         if(data[mid] == k){
20             if((mid == start) || (data[mid-1] != k))
21                 return mid;
22             else
23                 end = mid-1;
24         }
25         else{
26             if(data[mid] > k)
27                 end = mid - 1;
28             else
29                 start = mid + 1;
30         }
31         return GetFirstIndex(data,k,start,end);
32     }
33     int GetLastIndex(vector<int> &data,int k,int start,int end){
34         if(start > end)
35             return -1;
36         int mid = start+(end-start)/2;
37         if(data[mid]==k){
38             if((mid == end) || (data[mid+1] != k))
39                 return mid;
40             else
41                 start = mid +1;
42         }
43         else{
44             if(data[mid]>k)
45                 end = mid-1;
46             else
47                 start = mid+1;
48         }
49         return GetLastIndex(data,k,start,end);
50     }
51 };

2.二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

分析：递归

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     int TreeDepth(TreeNode* pRoot)
13     {
14         if(pRoot==NULL)
15             return 0;
16         int nLeft=TreeDepth(pRoot->left);
17         int nRight=TreeDepth(pRoot->right);
18         int depth=0;
19         if(nLeft>nRight)
20             depth=nLeft+1;
21         else
22             depth=nRight+1;
23         return depth;
24     }
25 };

3.平衡二叉树

输入一颗二叉树，判断该树是不是平衡二叉树。

如果某二叉树中任意结点的左右子树的深度相差不超过1，那么他就是一颗平衡二叉树

分析：容易想到的思路：在遍历树的每个结点的时候，调用函数TreeDepth得到他的左右子树的深度，如果每个结点的左右子树的深度相差不超过1，则就是平衡二叉树

 1 class Solution {
 2 public:
 3     bool IsBalanced_Solution(TreeNode* pRoot) 
 4     {
 5         if(pRoot==NULL)
 6             return true;
 7         int left=TreeDepth(pRoot->left);
 8         int right=TreeDepth(pRoot->right);
 9         int diff=left-right;
10         if(diff>1||diff<-1)
11             return false;
12         return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
13     }
14     int TreeDepth(TreeNode* pRoot)
15     {
16         if(pRoot==NULL)
17             return 0;
18         int nLeft=TreeDepth(pRoot->left);
19         int nRight=TreeDepth(pRoot->right);
20         int depth=0;
21         if(nLeft>nRight)
22             depth=nLeft+1;
23         else
24             depth=nRight+1;
25         return depth;
26     }
27 };

4.数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都只出现了两次，找出这两个数字

要求：时间复杂度是O（n），空间复杂度O（1）

分析：首先：位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

两个相同数字异或=0，一个数和0异或还是它本身。

当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，记为第n位，接着把原数组分成两组，分组标准是第n位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

 1 class Solution {
 2 public:
 3     void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) 
 4     {
 5         int length=data.size();
 6         if(length<2)
 7             return;
 8         if(length==2)
 9         {
10               num1[0] = data[0];
11               num2[0] = data[1];
12               return;
13         }
14       int bitResult = 0;
15         for(int i = 0; i < length; ++i)
16         {
17             bitResult ^= data[i];
18         }
19         int index = findFirst1(bitResult);
20         *num1=*num2=0;
21         for(int i = 0; i < length; ++i)
22         {
23             if(isBit1(data[i], index))
24             {
25                 *num1 ^= data[i];
26             }
27             else
28             {
29                 *num2 ^= data[i];
30             }
31         }
32     }
33     int findFirst1(int num)
34     {
35         int index=0;
36         while(((num&1)==0)&&(index<8*sizeof(int)))
37         {
38             num=num>>1;
39             ++index;
40         }
41         return index;
42     }
43     bool isBit1(int num,int index)
44     {
45         num=num>>index;
46         return (num&1);
47     }
48 };

5.和为s的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

分析：先在数组中选择两个数字，如果他们的和等于S，则找到；如果小于S，选择较小的数字后面的数字；如果大于S，选择较大数字前面的数字。因为数组已经是有序的。

 1 class Solution {
 2 public:
 3     vector<int> FindNumbersWithSum(vector<int> array,int sum)
 4     {
 5         int length=array.size();
 6         vector<int> res;
 7         int ahead=length-1;
 8         int behind=0;
 9         while(ahead>behind)
10         {
11             long long curSum=array[ahead]+array[behind];
12             if(curSum==sum)
13             {
14                 res.push_back(array[behind]);
15                 res.push_back(array[ahead]);
16                 break;
17             }
18             else if(curSum>sum)
19             {
20                 ahead--;
21             }
22             else
23             {
24                 behind++;
25             }
26         }
27         return res;
28     }
29 };

6.和为s的连续正数序列

输入一个正数S，打印出所有和为S的连续正数序列（至少含有两个数）

分析：首先考虑用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列和大于S，则去掉序列中较小的值，也就是增加small的值；如果小于S，增大big，让序列包含更多的数字，一直增加到small为（1+S）/2为止

 1 class Solution {
 2 public:
 3     vector<vector<int> > FindContinuousSequence(int sum)
 4     {
 5         vector<vector<int> > res;
 6         if(sum<3)
 7             return res;
 8         int small=1;
 9         int big=2;
10         int middle=(1+sum)/2;
11         int curSum=small+big;
12         while(small<middle&&big<sum)
13         {
14             while(curSum > sum)
15             {
16                 curSum -= small;
17                 small++;
18             }
19             if(curSum==sum)
20             {
21                 InsertRes(small,big,res);
22             }
23             big++;
24             curSum+=big;
25         }
26         return res;
27     }
28     void InsertRes(int small,int big,vector<vector<int> > &res)
29     {
30         vector<int> temp;
31         for(int i = small;i<=big;i++)
32             temp.push_back(i);
33         res.push_back(temp);
34     }
35 };

7.反转单词序列

输入一个英文句子，反转句子中单词的顺序，但单词内字符的顺序不变，标点符号和普通字母一样处理

分析：第一步翻转句子中所有字符；第二步再翻转每个单词中字符的顺序

 1 class Solution {
 2 public:
 3     string ReverseSentence(string str) 
 4     {
 5         ReverseWord(str,0,str.size()-1);//先整体翻转
 6         int start=0,end=0;
 7         int i=0;
 8         int length=str.size();
 9         while(i<length)
10         {
11             while(i<length&&str[i]==' ')//空格跳过
12             {
13                 i++;
14             }
15             start=end=i;
16             while(i<length&&str[i]!=' ')
17             {
18                 i++;
19                 end++;
20             }
21             ReverseWord(str,start,end-1);
22         }
23         return str;
24     }
25     void ReverseWord(string &str, int start, int end)
26     {
27         while(start < end)
28         {
29             swap(str[start++], str[end--]);
30         }
31     }
32 };

8.左旋转字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它

分析：三次翻转，先翻转前n个部分，再翻转后一部分，再翻转整体

 1 class Solution {
 2 public:
 3     string LeftRotateString(string str, int n)
 4     {
 5       int length = str.size();
 6         if(length<=0)
 7             return str;
 8         if(length>0&& n>0&&n<length)
 9         {
10             int firstStart = 0;
11             int firstEnd = n-1;
12             int secondStart = n;
13             int secondEnd = length-1;
14             Reverse(str,firstStart,firstEnd);
15             Reverse(str,secondStart,secondEnd);
16             Reverse(str,firstStart,secondEnd);
17         }
18     return str;
19     }
20   void Reverse(string &str, int start, int end)
21     {
22         while(start < end)
23         {
24             swap(str[start++], str[end--]);
25         }
26     }
27 };

9.扑克牌的顺子

从扑克牌中随机抽取5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以为任意数字。

分析：首先把数组排序，在统计数组中0的个数，最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续

注意：如果非零数字重复出现，则不连续

 1 class Solution {
 2 public:
 3     bool IsContinuous( vector<int> numbers ) {
 4         if(numbers.size()!=5) 
 5             return false;
 6         sort(numbers.begin(),numbers.end());
 7         int i=0;
 8         while(numbers[i]==0) 
 9             i++;
10         if(numbers[4]-numbers[i]>4) 
11             return false;
12         for(int j=i;j<4;j++){
13             if(numbers[j]==numbers[j+1]) 
14                 return false;
15         }
16         return true;
17     }
18 };

10.圆圈中最后剩下的数字

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

分析：两种解法：

解法一：经典解法，用环形链表模拟圆圈

 1 class Solution {
 2 public:
 3     int LastRemaining_Solution(int n, int m)
 4     {
 5         if(n<1||m<1)
 6             return -1;
 7         int i=0;
 8         list<int> numbers;
 9         for(i=0;i<n;++i)
10             numbers.push_back(i);
11         list<int>::iterator current=numbers.begin();//开始点
12         while(numbers.size()>1)
13         {
14             for(int i=1;i<m;++i)
15             {
16                 current++;//指针后移
17                 if(current==numbers.end())
18                     current=numbers.begin();
19             }
20             list<int>::iterator next=++current;
21             if(next==numbers.end())
22                 next=numbers.begin();
23             --current;
24             numbers.erase(current);
25             current=next;
26         }
27         return *(current);
28     }
29 };

解法二：创新解法：找到数学规律

递推公式 f[1]=0;

f[i]=(f[i-1]+m)%i; (i>1)

 1 class Solution {
 2 public:
 3     int LastRemaining_Solution(unsigned int n, unsigned int m)
 4     {
 5         if(n==0)
 6             return -1;
 7         if(n==1)
 8             return 0;
 9         else
10             return (LastRemaining_Solution(n-1,m)+m)%n;
11     }
12 };

11.求1+2+3+...+n

求1+2+3+...+n要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句

分析：解题思路：

1.需利用逻辑与的短路特性实现递归终止。

2.当n==0时，sum&&((sum+=Sum_Solution(n-1)))只执行前面的判断，为false，然后直接返回0；

3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。

1 class Solution {
2 public:
3     int Sum_Solution(int n) 
4     {
5       int sum = n;
6         sum&&((sum+=Sum_Solution(n-1)));
7       return sum;
8     }
9 };

12.不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

分析：用位运算代替二进制加法

第一步不考虑进位对每一位相加==》采用异或

接着考虑第二步进位，可以想象为是两个数先做位与运算，然后再向左移动一位

第三步把前两个步骤结果相加。第三步相加的过程依然是重复前两步，直到不产生进位为止

 1 class Solution {
 2 public:
 3     int Add(int num1, int num2)
 4     {
 5         int sum,carry;
 6         do{
 7             sum=num1^num2;
 8             carry=(num1&num2)<<1;
 9             num1=sum;
10             num2=carry;
11         }while(num2!=0);
12         return num1;
13     }
14 };