2020-03-06

an hour read (About 13106 words) 0 visits

剑指offer题解(C++)

剑指offer各题目的C++解法

剑指offer 1 二维数组查找
剑指offer 2 替换空格
剑指offer 3 从尾到头打印链表
剑指offer 4 重建二叉树
剑指offer 5 用两个栈实现队列
剑指offer 6 旋转数组的最小值
剑指offer 7 斐波那契数列
剑指offer 8 跳台阶
剑指offer 9 变态跳台阶
剑指offer 10 矩形覆盖
剑指offer 11 二进制中1的个数**
剑指offer 12 求base的exponent次方
剑指offer 13 调整数组奇偶顺序
剑指offer 14 链表倒数第k个结点
剑指offer 15 反转链表
剑指offer 16 合并两个排序的链表
剑指offer 17 树的子结构
剑指offer 18 二叉树的镜像
剑指offer 19 顺时针打印矩阵
剑指offer 20 包含Min函数的栈
剑指offer 21 栈的压入、弹出序列
剑指offer 22 从上往下打印二叉树
剑指offer 23 二叉搜索树的后序遍历序列
剑指offer 24 二叉树中和为某一值的所有路径
剑指offer 25 复杂链表的复制
剑指offer 26 二叉搜索树转双端链表**
剑指offer 27 字符串的排列
剑指offer 28 数组中出现超过一半的数
剑指offer 29 最小的k个数**
剑指offer 30 连续子数组最大和
剑指offer 31 整数中1的个数
剑指offer 32 把数组排成最小的数**
剑指offer 33 丑数
剑指offer 34 第一次出现的字符
剑指offer 35 数组中的逆序对**
剑指offer 36 两个链表的第一个公共结点
剑指offer 37 数组在排序数组出现的次数
剑指offer 38 二叉树深度
剑指offer 39 判断平衡二叉树
剑指offer 40 数组中只出现一次的数字
剑指offer 41 和为S的连续正数序列
剑指offer 42 和为S的两个数
剑指offer 43 左旋转字符串
剑指offer 44 翻转单词顺序列
剑指offer 45 扑克牌顺子
剑指offer 46 孩子们的游戏（圆圈里最后剩下的数）
剑指offer 47 求1+2+…+n
剑指offer 48 不用加减乘除做加法
剑指offer 49 把字符串转换为整数
剑指offer 50 数组中重复的数字
剑指offer 51 构建乘积数组
剑指offer 52 正则表达式匹配
剑指offer 53 表示数值的字符串
剑指offer 54 字符流中第一个不重复的字符
剑指offer 55 链表中环的入口节点
剑指offer 56 删除链表中重复的节点
剑指offer 57 二叉树的下一个节点
剑指offer 58 对称的二叉树
剑指offer 59 之字形打印二叉树
剑指offer 60 把二叉树打印成多行（层序遍历）
剑指offer 61 序列化二叉树
剑指offer 62 二叉搜索树的第k个结点
剑指offer 63 数据流中的中位数
剑指offer 64 滑动窗口的最大值
剑指offer 65 矩阵中的路径
剑指offer 66 机器人的动作范围
剑指offer 67 剪绳子

剑指offer 1 二维数组查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

// 左下往右上查找，快速定位地图经纬度 O(n+m)
bool Find(int target, vector<vector<int> > array) {
    int rows = array.size(), cols = array[0].size();
    int row=rows-1,col=0;
    while(row>=0 && col<cols){
            if(array[row][col]==target) return true;
            else if(array[row][col]>target) row--;
            else col++;
    }
    return false;
}

// 二分法 O(nlogm) O(n+m)
bool Find(int target, vector<vector<int> > array) {
    if(array.size()==0) return false;
        int nrows = array.size(), ncols= array[0].size();
        for(int i=0;i<nrows;i++){
            int low=0;
            int high=ncols-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(target>array[i][mid])
                    low=mid+1;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    return true;
            }
        }
        return false;
    }

剑指offer 2 替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

// O(n)
void replaceSpace(char *str,int length) {
    int count=0;
    for(int i=0;i<length;i++){
        if(str[i]==' ')
            count++;
    }
    for(int i=length-1;i>=0;i--){
        if(str[i]!=' '){
            str[i+2*count]=str[i]; //非空格在新数组的位置 
            //0 1 2 3 4 5 6 7 8  
            //0 # 3 # 4     
            //0 % 2 0 3 % 2 0 4
        }
        else{
            count--;
            str[i+2*count]='%';
            str[i+2*count+1]='2';
            str[i+2*count+2]='0';
        }
    }
}

剑指offer 3 从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

//递归
vector<int> printListFromTailToHead(ListNode* head) {
    vector<int> res;
    if(head!=NULL){
        if(head->next!=NULL){
            res = printListFromTailToHead(head->next);
        }
        res.push_back(head->val);
    }
    return res;
}
//栈
vector<int> printListFromTailToHead(ListNode* head) {
    vector<int> res;
    stack<int> sta;
    while(head!=NULL){
        sta.push(head->val);
        head=head->next;
    }
    while(!sta.empty()){
        res.push_back(sta.top());
        sta.pop();
    }
    return res;
}
// **链表原地反转**
vector<int> printListFromTailToHead(struct ListNode* head) {
    vector<int> vec;
    ListNode *buf=head;
    ListNode *pre=buf;
    if(head==NULL)
        return vec;
    while(head->next!=NULL){
        buf=head->next;
        head->next=buf->next;
        buf->next=pre;
        pre=buf;
    }
    while(buf){
        vec.push_back(buf->val);
        buf=buf->next;
    }
    return vec;
}

剑指offer 4 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    TreeNode* root = helper(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
    return root;
}
TreeNode* helper(vector<int> pre, int startpre, int endpre, vector<int> vin, int startvin, int endvin){
    if(startpre>endpre||startvin>endvin)
        return NULL;
    TreeNode* root=new TreeNode(pre[startpre]);
    for(int i=startvin;i<=endvin;i++){
        if(vin[i]==pre[startpre]){
            root->left = helper(pre, startpre+1, startpre+i-startvin, vin, startvin, i-1);
            root->right = helper(pre, startpre+i-startvin+1, endpre, vin, i+1, endvin);
            break;
        }
    }
    return root;
}

剑指offer 5 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

stack<int> stack1;
stack<int> stack2;
void push(int node) {
    stack1.push(node);
}
//栈1不空，全部压入栈2，栈2的top则可以输出；
//然后把栈2再压回栈1
int pop() {
    while(!stack1.empty()){
        int a = stack1.top();
        stack1.pop();
        stack2.push(a);
    }
    int res = stack2.top();
    stack2.pop();
    while(!stack2.empty()){
        stack1.push(stack2.top());
        stack2.pop();
    }
    return res;
}

//如果栈2不空，栈2的top即为输出，否则把栈1全部压入栈2
int pop() {
    if(stack2.empty()){
        while(!stack1.empty()){
            int a = stack1.top();
            stack1.pop();
            stack2.push(a);
        }
    }
    int res = stack2.top();
    stack2.pop();
    return res;
}

剑指offer 6 旋转数组的最小值

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

//O(N)
int minNumberInRotateArray(int[] array) {
  if (array.length == 0)
      return 0;
  for (int i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1])
          return array[i + 1];
  }
  return array[0];
}

// O(logn) 二分法
int minNumberInRotateArray(vector<int> rotateArray) {
    if(rotateArray.size()==0) return 0;
    int low=0, high=rotateArray.size()-1;
    while(low<high){
        int mid=(low+high)/2;
        if(rotateArray[mid]>rotateArray[high]) low=mid+1;
        else if(rotateArray[mid]==rotateArray[high]) high--;
        else high=mid;
    }
    return rotateArray[high];
}

剑指offer 7 斐波那契数列

//斐波那契数列
0 1 2 3 4 ...
0 1 1 2 3 ...
//递归
int Fibonacci(int n) {
    if(n==0) return 0;
    if(n==1) return 1;
    return Fibonacci(n-1)+Fibonacci(n-2);
}
//循环 时间复杂度O(N) 空间复杂度O(1)
int Fibonacci(int n) {
    if(n==0) return 0;
    if(n==1) return 1;
    int pre=0, now=1;
    while(n>1){
        int tmp = pre+now;
        pre = now;
        now = tmp;
        n--;
    }
    return now;
}
//动态规划 时间复杂度O(N) 空间复杂度O(N)
int Fibonacci(int n) {
    if(n==0) return 0;
    if(n==1) return 1;
    vector<int> dp(n+1,0);
    dp[0]=0;
    dp[1]=1;
    for(int i=2;i<=n;++i){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[n];
}

剑指offer 8 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

//斐波那契数列 DP O(N)
int jumpFloor(int number) {
    if(number<2) return number;
    int pre=1, now=2;
    for(int i=3;i<=number;i++){
        int tmp = pre+now;
        pre = now;
        now=tmp;
    }
    return now;
}

剑指offer 9 变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

int jumpFloorII(int number) {
    if(number==0) return 0;
    int res=1;
    while(number-->1){
        res*=2;
    }
    return res;
}
//移位 左移一位*2，左移n-1位即 2^(n-1)
int res = 1<<(number-1)

剑指offer 10 矩形覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，有多少种方法？

1 2	//还是斐波那契数列 f(n) = f(n-1) + f(n-2)， (n > 2)。

更一般的结论，如果用1*m的方块覆盖m*n区域，递推关系式为f(n) = f(n-1) + f(n-m)，(n > m)。

// 循环
int rectCover(int number) {
    if(number<=2) return number;
    int pre=1, now=2;
    for(int i=3;i<=number;++i){
        int tmp=pre+now;
        pre=now;
        now=tmp;
    }
    return now;
}
// 递归
public class Solution {
    public int RectCover(int target) {
        if (target < 1) {
            return 0;
        } else if (target == 1 || target == 2) {
            return target;
        } else {
            return RectCover(target-1) + RectCover(target-2);
        }
    }
}
// dp
int rectCover(int number) {
    if ( number < 1 ) return 0;
    int g = 1, f = 2;
    while ( --number ) {
        f = f + g;
        g = f - g;
    }
    return g;
}

剑指offer 11 二进制中1的个数**

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

// 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
int NumberOf1(int n) {
    int count = 0;
    while (n != 0) {
        ++count;
        n = (n - 1) & n;
    }
    return count;
 }

剑指offer 12 求base的exponent次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

// 简单快速幂
double Power(double base, int exponent) {
    long long p = abs((long long)exponent);
    double r = 1.0;
    while(p){
        if(p & 1) r *= base;
        base *= base;
        p >>= 1;
    }
    return exponent < 0 ? 1/ r : r;
}

第一种方法：使用递归，时间复杂度O(logn)
当n为偶数，a^n =（a^n/2）*（a^n/2）

当n为奇数，a^n = a ^ [( n - 1) / 2] a ^ [(n-1)/2] a

举例：

2^11 = 2^1 2^2 2^8

2^1011 = 2^0001 2^0010 2^1000

第二种方法：累乘，时间复杂度为O(n)

剑指offer 13 调整数组奇偶顺序

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

// O(2n) O(n) 
void reOrderArray(vector<int> &array) {
  if(array.size()==0) return;
  vector<int> res(array.size(),0);
  int s=0,e=array.size()-1;
  for(int i=0;i<array.size();++i){
    if(array[i]%2==1){
      res[s++]=array[i];
    }
  }
  for(int i=array.size()-1;i>=0;--i){
    if(array[i]%2==0){
      res[e--]=array[i];
    }
  }
  array=res;
}

// O(n*n) O(1) 插排想法
void reOrderArray1(vector<int> &array){
  if(array.size()<=1) return;
  for(int i=0;i<array.size();i++){
    if(array[i]%2==1){
      int tmp=array[i];
      int j=i-1;
      while(j>=0 && array[j]%2==0){
        array[j+1]=array[j];
        j--;
      }
      array[j+1]  =tmp;
    }
  }
}

// 开辟2个数组分别存奇数和偶数 O(n) O(2n)

剑指offer 14 链表倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

// 遍历再数 O(2n-k)
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    if(k<=0) return NULL;
    int cnt=0, start=0;
    ListNode* root=pListHead;
    while(pListHead!=NULL){
        pListHead=pListHead->next;
        cnt++;
    }
    if(k>cnt) return NULL;
    while(start!=cnt-k){
        root=root->next;
        start++;
    }
    return root;
}

// 遍历再数 O(n)
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    if(k<=0 || pListHead==NULL) return NULL;
    ListNode *fast=pListHead;
    ListNode *slow=pListHead;
    while(k-->0){
		if(fast==nullptr) return nullptr;
        fast=fast->next;
    }
	while(fast!=NULL){
		fast=fast->next;
		slow=slow->next;
	}
	return slow;
}

// 递归
ListNode* FindKthToTail2(ListNode* pListHead, unsigned int k) {
	if(pListHead==NULL) return NULL;
	ListNode* node=FindKthToTail(pListHead->next,k);
	if(node!=NULL) return node;
	cnt++;
	if(cnt==k) return pListHead;
	else return NULL;
}

剑指offer 15 反转链表

输入一个链表，反转链表后，输出新链表的表头。

public ListNode ReverseList(ListNode head) {
    if(head==null)
        return null;
    //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
    ListNode pre = null;
    ListNode next = null;
    //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
    //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
    //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
    //所以需要用到pre和next两个节点
    //1->2->3->4->5
    //1<-2<-3 4->5
    while(head!=null){
        //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
        //如此就可以做到反转链表的效果
        //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
        next = head.next;
        //保存完next，就可以让head从指向next变成指向pre了，代码如下
        head.next = pre;
        //head指向pre后，就继续依次反转下一个节点
        //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
        pre = head;
        head = next;
    }
    //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
    //直接输出pre就是我们想要得到的反转后的链表
    return pre;
}

剑指offer 16 合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

//递归
ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
  if(pHead1==NULL) return pHead2;
  if(pHead2==nullptr) return pHead1;
      if(pHead1->val>pHead2->val) {
    pHead2->next=Merge(pHead1, pHead2->next);
    return pHead2;
  }
  if(pHead1->val<pHead2->val) {
    pHead1->next=Merge(pHead1->next, pHead2);
    return pHead1;
  }
}
// 循环
if(list1 == null) return list2;
if(list2 == null) return list1;
ListNode mergeHead = null;
ListNode current = null;
while(list1!=null && list2!=null){
    if(list1.val <= list2.val){
        if(mergeHead == null){
           mergeHead = current = list1;
        }else{
           current.next = list1;
           current = current.next;
        }
        list1 = list1.next;
    }else{
        if(mergeHead == null){
           mergeHead = current = list2;
        }else{
           current.next = list2;
           current = current.next;
        }
        list2 = list2.next;
    }
}
if(list1 == null) current.next = list2;
else current.next = list1;
return mergeHead;

剑指offer 17 树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
    bool result=false;
    if(pRoot1!=NULL && pRoot2!=NULL){
        if(pRoot1->val==pRoot2->val) result=Tree1HaveTree2(pRoot1, pRoot2);
        if(!result) {
            result=Tree1HaveTree2(pRoot1->left, pRoot2) || Tree1HaveTree2(pRoot1->right, pRoot2);
        }
    }
    return result;
}
bool Tree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2){
    if(pRoot2==NULL) return true;
    if(pRoot1==NULL) return false;
    if(pRoot1->val!=pRoot2->val) return false;
    return Tree1HaveTree2(pRoot1->left, pRoot2->left) && Tree1HaveTree2(pRoot1->right,pRoot2->right);
}

剑指offer 18 二叉树的镜像

void Mirror(TreeNode *pRoot) {
    if (pRoot==NULL) return;
    else {
        TreeNode *tmp=pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
}

剑指offer 19 顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

vector<int> printMatrix(vector<vector<int> > matrix) {
    int row = matrix.size();
    int col = matrix[0].size();
    vector<int> res;
        
    // 输入的二维数组非法，返回空的数组
    if (row == 0 || col == 0)  return res;
        
    // 定义四个关键变量，表示左上和右下的打印范围
    int left = 0, top = 0, right = col - 1, bottom = row - 1;
    while (left <= right && top <= bottom)
    {
        // left to right
        for (int i = left; i <= right; ++i)  res.push_back(matrix[top][i]);
        // top to bottom
        for (int i = top + 1; i <= bottom; ++i)  res.push_back(matrix[i][right]);
        // right to left
        if (top != bottom)
        for (int i = right - 1; i >= left; --i)  res.push_back(matrix[bottom][i]);
        // bottom to top
        if (left != right)
        for (int i = bottom - 1; i > top; --i)  res.push_back(matrix[i][left]);
        left++,top++,right--,bottom--;
    }
    return res;
}

剑指offer 20 包含Min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

stack<int> stack1, stack2;
void push(int value) {
    stack1.push(value);
    if(stack2.empty()) stack2.push(value);
    else{
        if(value<stack2.top()) stack2.push(value);
    }
}
void pop() {
    if(stack1.top()==stack2.top()) stack2.pop();
    stack1.pop();
}
int top() {
    return stack1.top();
}
int min() {
    return stack2.top();
}

剑指offer 21 栈的压入、弹出序列

//输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

bool IsPopOrder(vector<int> pushV,vector<int> popV) {
      if(pushV.empty()||popV.empty()) return false;
  stack<int> Stack;
  int popIndex=0;
  for(int i=0;i<pushV.size();++i){
    Stack.push(pushV[i]);
    while(!Stack.empty() && Stack.top()==popV[popIndex]){
      Stack.pop();
      popIndex++;
    }
  }
  return Stack.empty();
 }

剑指offer 22 从上往下打印二叉树

//双端队列
vector<int> PrintFromTopToBottom(TreeNode* root) {
	vector<int> res;
	if(root==NULL) return NULL;
	deque<TreeNode*> d;
	d.push_back(root);
	while(!d.empty()){
		root=d.front();
		if(root!=NULL){
			res.push_back(root->val);
			d.push_back(root->left);
			d.push_back(root->right);
		}
		d.pop_front();
	}
	return res;
}
//队列
vector<int> PrintFromTopToBottom(TreeNode* root) {
    vector<int> res;
    if(root==NULL)
        return res;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        res.push_back(q.front()->val);
        if(q.front()->left!=NULL)
            q.push(q.front()->left);
        if(q.front()->right!=NULL)
            q.push(q.front()->right);
        q.pop();
    }
    return res;
}

剑指offer 23 二叉搜索树的后序遍历序列

//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
//如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

bool VerifySquenceOfBST(vector<int> sequence) {
  if (sequence.empty()) {
      return false;
  }
  return helper(sequence, 0, sequence.size() - 1);
}

bool helper(vector<int> &sequence, int first, int last) { // first和last表示树序列的开始和结束的位置
  if(first >= last){
      return true;
  }
  int curIdx = first;
  int rootVal = sequence[last]; //后序遍历，根节点一定在最后，找到根节点后，就可以将树分为左右两棵子树，其中左子树中的元素都小于根节点，右子树中的元素都大于根节点
  while(curIdx < last && sequence[curIdx] < rootVal){
      ++curIdx;
  }
  int midIdx = curIdx; // 到curIdx的值大于根节点时，我们认为开始进入到右子树部分，用一个midIdx记录下当前的右子树开始的位置
  while (curIdx < last){
      if(sequence[curIdx] < rootVal){
          return false;
      }
      ++curIdx;
  }
  return helper(sequence, first, midIdx - 1) && helper(sequence, midIdx, last - 1); // 再分别对左子树和右子树做同样的操作
}

剑指offer 24 二叉树中和为某一值的所有路径

//输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
//路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
//(注意: 在返回值的list中，数组长度大的数组靠前)

vector<vector<int>> res;
vector<int> path;
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
	if(root==NULL || expectNumber<=0) return res;
	findHelper(root, expectNumber); 
	return res;
}
void findHelper(TreeNode* root, int sum){
	if(root==NULL) return;
	path.push_back(root->val);
	if(root->left==NULL && root->right==NULL && root->val==sum){
		res.push_back(path);
	}
	else{
		if(root->left!=NULL){
			findHelper(root->left, sum-root->val);
		}
		if(root->right!=NULL){
			findHelper(root->right, sum-root->val);
		}
	}
	path.pop_back();
}

剑指offer 25 复杂链表的复制

//输入一个复杂链表（每个节点中有节点值，以及两个指针，
//一个指向下一个节点，另一个特殊指针指向任意一个节点），
//返回结果为复制后复杂链表的head。
//（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

struct RandomListNode {
	int label;
	struct RandomListNode *next, *random;
	RandomListNode(int x) :
		label(x), next(NULL), random(NULL) {
	}
};
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead){
    	if(pHead==NULL) return NULL;
    	RandomListNode* currentNode=pHead;
    	//复制每个结点，将其插入结点后面
    	while(currentNode!=NULL){
    		RandomListNode* cloneNode = new RandomListNode(currentNode->label);
    		RandomListNode* nextNode = currentNode->next;
    		currentNode->next=cloneNode;
    		cloneNode->next=nextNode;
    		currentNode=nextNode;
    	}
    	currentNode=pHead;
    	//复制老结点的随机指针给新结点
    	while(currentNode!=NULL){
    		currentNode->next->random = currentNode->random==NULL?NULL:currentNode->random->next;
    		currentNode=currentNode->next->next;
    	}
    	//拆分链表
    	currentNode=pHead;
    	RandomListNode* pCloneHead=pHead->next;
    	while(currentNode!=NULL){
    		RandomListNode* cloneNode=currentNode->next;
    		currentNode->next=cloneNode->next;
    		cloneNode->next=cloneNode->next==NULL?NULL:cloneNode->next->next;
    		currentNode=currentNode->next;
    	}
    	return pCloneHead;
    }
};

剑指offer 26 二叉搜索树转双端链表**

//题目描述
//输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
//要求不能创建任何新的结点，只能调整树中结点指针的指向。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
TreeNode* Convert(TreeNode* pRootOfTree){
if(pRootOfTree==NULL) return NULL;
	TreeNode* pre=NULL;
	convertHelper(pRootOfTree, pre);
	TreeNode* res=pRootOfTree;
	while(res->left){
		res=res->left;
	}
	return res;
}
void convertHelper(TreeNode* cur, TreeNode*& pre){
	if(cur==NULL) return;
	convertHelper(cur->left, pre);
	cur->left=pre;
	if(pre) pre->right=cur;
	pre=cur;
	convertHelper(cur->right, pre);
}

剑指offer 27 字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

/**
     * 1、递归算法
     *
     * 解析：http://www.cnblogs.com/cxjchen/p/3932949.html  (感谢该文作者！)
     *
     * 对于无重复值的情况
     *
     * 固定第一个字符，递归取得首位后面的各种字符串组合；
     * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。
     *
     * 假如有重复值呢？
     * *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
     * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
     * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
     * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。
     *
     * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
     * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
     *
     *
     * @param str
     * @return
     */
vector<string> Permutation(string str) {
        vector<string> res;
        if(str.empty()) return res;
        permutationHelper(str, res, 0, str.size()-1);
        sort(res.begin(),res.end());
        return res;
    }
void permutationHelper(string str, vector<string> &res, int start, int end){
    if(start==end) {
        res.push_back(str);
    }
    for(int i=start;i<=end;i++){   //从str的头到尾都换一次
        if(is_swap(str, start, i)){
            swap(str, start, i);
            permutationHelper(str, res, start+1, end);
            swap(str, start, i);
        }
    }
}
bool is_swap(string str, int l, int r){
    bool flag=true;
    for(int i=l;i<r;i++){  //l==r则跳过循环，比如aa可以加入res
        if(str[i]==str[r]){
            flag=false;
            break;
        }
    }
    return flag;
}
void swap(string &str, int l, int r){
    char tmp=str[l];
    str[l]=str[r];
    str[r]=tmp;
}

void swap(char* str,int a,int b)
{
    char tmp = str[a];
    str[a] = str[b];
    str[b] = tmp;
}
/**
     * 2、字典序排列算法
     *
     * 可参考解析： http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html  （感谢作者）
     *
     * 一个全排列可看做一个字符串，字符串可有前缀、后缀。
     * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。
     * 这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
     *
     * [例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的987654321，
     * 从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。
     *
     * 【例】 如何得到346987521的下一个
     * 1，从尾部往前找第一个P(i-1) < P(i)的位置
     * 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
     * 最终找到6是第一个变小的数字，记录下6的位置i-1
     *
     * 2，从i位置往后找到最后一个大于6的数
     * 3 4 6 -> 9 -> 8 -> 7 5 2 1
     * 最终找到7的位置，记录位置为m
     *
     * 3，交换位置i-1和m的值
     * 3 4 7 9 8 6 5 2 1
     * 4，倒序i位置后的所有数据
     * 3 4 7 1 2 5 6 8 9
     * 则347125689为346987521的下一个排列
     *
     * @param str
     * @return
     */
 
public ArrayList<String> Permutation2(String str){
        ArrayList<String> list = new ArrayList<String>();
        if(str==null || str.length()==0){
            return list;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        list.add(String.valueOf(chars));
        int len = chars.length;
        while(true){
            int lIndex = len-1;
            int rIndex;
            while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){
                lIndex--;
            }
            if(lIndex == 0)
                break;
            rIndex = lIndex;
            while(rIndex<len && chars[rIndex]>chars[lIndex-1]){
                rIndex++;
            }
            swap(chars,lIndex-1,rIndex-1);
            reverse(chars,lIndex);
 
            list.add(String.valueOf(chars));
        }
        return list;
}
 
private void reverse(char[] chars,int k){
    if(chars==null || chars.length<=k)
        return;
    int len = chars.length;
    for(int i=0;i<(len-k)/2;i++){
        int m = k+i;
        int n = len-1-i;
        if(m<=n){
            swap(chars,m,n);
        }
    }
}

剑指offer 28 数组中出现超过一半的数

//数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

// O(n) 空间O(n) 不追求元素排序，不用map或者hashmap
int MoreThanHalfNum_Solution2(vector<int> numbers) {
	int n = numbers.size();
	//map 记录出现次数
	unordered_map<int, int> m;
	int count;
	for (int i = 0; i < n; i++) {
		count = ++m[numbers[i]];
		if (count > n/2) return numbers[i];
	}
	return 0;
}
// O(n) O(1)
int MoreThanHalfNum_Solution1(vector<int> numbers) {
	if(numbers.empty()) return 0;
	int n = numbers.size(), num=numbers[0],count=1;
	for (int i = 1; i < n; i++) {
		if(numbers[i]==num) count++;
		else count--;
		if(count==0){
			num=numbers[i];
			count=1;
		}
	}
	count=0;
	for(int i=0;i<n;i++){
		if(numbers[i]==num) count++;
	}
	return (count>n/2)?num:0;
}
//快排思想 O(n)?O(logn)?
int MoreThanHalfNum_Solution(vector<int> numbers) {
	if(numbers.empty()) return 0;
	int n = numbers.size(), mid=n/2,count=1;
	int start=0,end=n-1;
	int k=partition(numbers, 0, n-1);
	while(k!=mid){
		if(k>mid){
			end=k-1;
			k=partition(numbers, start, end);
		}
		else{
			start=k+1;
			k=partition(numbers, start, end);
		}
	}
	int num=numbers[mid];
	count=0;
	for(int i=0;i<n;i++){
		if(numbers[i]==num) count++;
	}
	return (count>n/2)?num:0;
}
int partition(vector<int> &numbers, int s, int e){
	int pivot=numbers[s];
	int leftmark=s+1, rightmark=e;
	bool done=false;
	while(!done){
		while(leftmark<=rightmark && pivot>=numbers[leftmark]) leftmark++;
		while(leftmark<=rightmark && pivot<=numbers[rightmark]) rightmark--;
		if(leftmark>rightmark) done=true;
		else{
			swap(numbers, leftmark, rightmark);
		}
	}
	swap(numbers, s, rightmark);
	return rightmark;
}
void swap(vector<int> &v, int s, int e){
	int tmp=v[s];
	v[s]=v[e];
	v[e]=tmp;
}

//拓展：输出数组中两个数量超过1/3的数 //投票法，讲道理partition应该也行1/3,2/3的位置
vector<int> MoreThanOneThirdNum_Solution(vector<int> numbers) {
    vector<int> res;
    if(numbers.empty()) return res;
    int num1=0, num2=0, cnt1=0, cnt2=0, len = numbers.size();
    for(int i=0;i<len;i++){
        if(numbers[i]==num1) cnt1++;
        else if (numbers[i]==num2) cnt2++;
        else if (cnt1==0) num1=numbers[i], cnt1=1;
        else if (cnt2==0) num2=numbers[i], cnt2=1;
        else cnt1--, cnt2--;
    }
    cnt1=0, cnt2=0;
    for(int i=0;i<len;i++){
        if(numbers[i]==num1) cnt1++;
        if(numbers[i]==num2) cnt2++;
    }
    if(cnt1>len/3) res.push_back(num1);
    if(cnt2>len/3) res.push_back(num2);
    return res;
}

剑指offer 29 最小的k个数**

//输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。partition O(n)-O(n^2）?牛客超时？

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
	vector<int> res;
	if(input.empty() || k>input.size()) return res;
	int len=input.size(), pos, s=0, e=len-1;
	pos=par(input, 0, len-1);
	while (pos!=k){
		if (pos>k) e=pos-1,pos=par(input, s, e);
		else s=pos+1,pos=par(input, s, e);
	}
	for(int i=0;i<k;i++){
		res.push_back(input[i]);
	}
	sort(res.begin(),res.end());
	return res;
}
int par(vector<int> &arr, int s, int e){
	int pivot=arr[s];
	int l=s+1, r=e;
	bool done=false;
	while(!done){
		while(l<=r && arr[l]<=pivot) 
			l++;
		while(l<=r && arr[r]>=pivot) 
			r--;
		if(l>r) done=true;
		else swap(arr, l, r); 
	}
	swap(arr, s, r);
	return r;
}

//最大堆，待写

剑指offer 30 连续子数组最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

//DP O(n) O(1)
int FindGreatestSumOfSubArray(vector<int> array) {
	if(array.empty()) return 0;
	int len=array.size();
	int res=array[0], pre=array[0];
	for(int i=1;i<len;i++){
		pre=max(array[i], pre+array[i]);
		if(res<pre) res=pre;
	}
	return res;
}

剑指offer 31 整数中1的个数

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

int NumberOf1Between1AndN_Solution(int n){
    if(n<0) return 0;
    int count=0;
    for(int i=1;i<=n;i*=10){
        int k=i*10;
        count+=(n/k)*i+min(max(n%k-i+1, 0), i);
    }
    return count;
}

剑指offer 32 把数组排成最小的数**

//输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

class Solution {
public:
	static bool cmp(int a, int b){
		string A="";
		string B="";
		A += to_string(a);
		A += to_string(b);
		B += to_string(b);
		B += to_string(a);
		return A<B;
	}
	string PrintMinNumber(vector<int> numbers) {
		string res="";
		if(numbers.empty()) return res;
		sort(numbers.begin(), numbers.end(), cmp);
		for(int i=0;i<numbers.size();i++){
			res+=to_string(numbers[i]);
		}
		return res;
    }
};

剑指offer 33 丑数

//把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

class Solution {
public:
	int GetUglyNumber_Solution(int index) {
		if(index<1) return 0;
		vector<int> ugly(index, 1);
		int pointer2=0, pointer3=0, pointer5=0;
		for(int i=1;i<index;i++){
			ugly[i] = findmin(ugly[pointer2]*2, ugly[pointer3]*3, ugly[pointer5]*5);
			if(ugly[pointer2]*2==ugly[i]) pointer2++;
			if(ugly[pointer3]*3==ugly[i]) pointer3++;
			if(ugly[pointer5]*5==ugly[i]) pointer5++;
		}
		return ugly[index-1];
    }
int findmin(int a, int b, int c){
		int tmp = a>b?b:a;
		int tmp2 = tmp>c?c:tmp;
		return tmp2;
	}
};

剑指offer 34 第一次出现的字符

//在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

int FirstNotRepeatingChar(string str) {
  int res=-1;
  if(str.empty()) return res;
  int len=str.size();
  unordered_map<char, int> mp;
  for(int i=0;i<len;i++){
    mp[str[i]]++;
    // cout<<mp[str[i]]<<endl;
  }
  for(int i=0;i<len;i++){
    cout<<mp[str[i]]<<endl;
    if(mp[str[i]]==1){
       res=i;break;
    }
  }
  return res;
}

剑指offer 35 数组中的逆序对**

//在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007。例子：输入 1,2,3,4,5,6,7,0 输出 7

//暴力求解 O(N*N)
int InversePairs2(vector<int> data) {
    int res=0;
    if(data.empty()) return res;
    int len=data.size();
    for(int i=len-1;i>=0;i--){
        for(int j=i-1;j>=0;j--){
            if(data[j]>data[i]) res++;
        }
    }
    return res;
}
//归并排序 O(nlogn)
int InversePairs(vector<int> data) {
	int res=0;
	if(data.empty()) return res;
	int len=data.size();
	vector<int> cp(len, 0);
	for(int i=0;i<len;i++){
		cp[i]=data[i];
	}
	res = mergeCount(data, cp, 0, len-1);
	return res;
}
int mergeCount(vector<int> &arr, vector<int> &cp, int s, int e){
	if(s==e) return 0;
	int mid=(s+e)>>1;
	int leftCount=mergeCount(arr, cp, s, mid)%1000000007;
	int rightCount=mergeCount(arr, cp, mid+1, e)%1000000007;
	int count=0,i=mid,j=e,locCopy=e;
	while(i>=s && j>mid){
		if(arr[i]>arr[j]){
			count += j-mid;
			cp[locCopy--] = arr[i--];
			if(count>=1000000007) count%=1000000007;
		}
		else{
			cp[locCopy--] = arr[j--];
		}
	}
	for(;i>=s;i--){
		cp[locCopy--]=arr[i];
	}
	for(;j>mid;j--){
		cp[locCopy--]=arr[j];
	}
	for(int ss=s;ss<=e;ss++){
		arr[ss]=cp[ss];
	}
	return (leftCount+rightCount+count)%1000000007;
}

剑指offer 36 两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。

// 若有公共结点，让最长的链表先走len1-len2步，再一起走，必会相交
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
    if(pHead1==NULL || pHead2==NULL) return NULL;
	int len1 = findLinkedListLength(pHead1);
	int len2 = findLinkedListLength(pHead2);
	if(len1>len2){
		pHead1=walkK(pHead1, len1-len2);
	}
	else{
		pHead2 = walkK(pHead2, len2-len1);
	}
	while(pHead1!=NULL && pHead2!=NULL){
		if(pHead1==pHead2) return pHead1;
		pHead1=pHead1->next;
		pHead2=pHead2->next;
	}
	return NULL;
}
int findLinkedListLength(ListNode* pHead){
	int res=0;
	while(pHead!=NULL){
		pHead = pHead->next;
		res++;
	}
	return res;
}
ListNode* walkK(ListNode* pHead, int k){
	while(k--){
		pHead=pHead->next;
	}
	return pHead;
}

剑指offer 37 数组在排序数组出现的次数

//统计一个数字在排序数组中出现的次数。

// O(n) O(1)
int GetNumberOfK1(vector<int> data ,int k) {
      if(data.empty()) return 0;
  int res=0;
  for(int i=0;i<data.size();i++){
    if(data[i]==k) res++;
  }
  return res;
  }
// O(logn) O(1)
int GetNumberOfK(vector<int> data ,int k) {
      if(data.empty()) return 0;
  int start=0, end=data.size()-1, res=0;
  while(start<=end){
    int mid=(start+end)>>1;
    if(data[mid]>k){
      end=mid-1;
    }
    else if(data[mid]<k) {
      start=mid+1;
    }
    else {
      int l=mid, r=mid;
      res++;
      while(data[--l]==k) res++;
      while(data[++r]==k) res++;
      cout<<res<<endl;
      break;
    }
  }
  return res;
}

剑指offer 38 二叉树深度

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

//递归
int TreeDepth(TreeNode* pRoot) {
  if(pRoot==NULL) return 0;
  return max(TreeDepth(pRoot->left), TreeDepth(pRoot->right))+1;
}
//非递归
int TreeDepthNotLoop(TreeNode* pRoot) {
  int res=0;
  if(pRoot==NULL) return res;
  queue<TreeNode *> q;
  q.push(pRoot);
  while(!q.empty()) {
    int size=q.size();
    res++;
    for(int i=0;i<size;i++){
        TreeNode* top=q.front();
        q.pop();
        if(top->left) q.push(top->left);
        if(top->right) q.push(top->right);
    }
  }
  return res; }

剑指offer 39 判断平衡二叉树

//输入一棵二叉树，判断该二叉树是否是平衡二叉树。如果二叉树的每个节点的左子树和右子树的深度不大于1，它就是平衡二叉树。

bool IsBalanced_Solution(TreeNode* pRoot){
  return pos_travel(pRoot)!=-1;
  }
int pos_travel(TreeNode* pRoot){
  if(pRoot==NULL) return 0;
  int left=pos_travel(pRoot->left);
  if(left==-1) return -1;
  int right=pos_travel(pRoot->right);
  if(right==-1) return -1;
  return abs(left-right)>1?-1:1+max(left, right);
}

剑指offer 40 数组中只出现一次的数字

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

//input vector<int> arr={1,4,4,5,5,7};
void FindNumsAppearOnce(vector <int> data, int* num1, int *num2) {
    if(data.empty()) return;
    int len=data.size();
    unordered_map <int, int> mp;
    for(int i=0;i<len;i++){
        mp[data[i]]++;
    }
    vector<int> res;
    for(int i=0;i<len;i++){
        if(mp[data[i]]==1){
            res.push_back(data[i]);
        }
    }
    *num1 = res[0];
    *num2 = res[1];
}

public static int find1From2(int[] a){
    int len = a.length, res = 0;
    for(int i = 0; i < len; i++){
        res = res ^ a[i];
    }
    return res;
}

剑指offer 41 和为S的连续正数序列

//输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

vector<vector<int> > FindContinuousSequence(int sum) {
    vector<vector<int> > vOut;
    vector<int> vIn;
    if(sum==1) {
        vIn.push_back(1);
        vOut.push_back(vIn);
        return vOut;
    }
    int left=1, right=2;
    while(left<right){
        int k=(left+right)*(right-left+1)/2;
        if(sum==k) {
            vector<int> vTmp;
            for(int i=left;i<=right;i++){
                vTmp.push_back(i);
            }
            vOut.push_back(vTmp);
            right++;
        }
        else if(sum>k) {
            right++;
        }
        else {
            left++;
        }
    }
    return vOut;
}
//
vector<vector<int> > FindContinuousSequence(int sum) {
  vector<vector<int>> res;
  if(sum<=2) return res;
  int up=sqrt(2*sum);
  for(int i=up;i>=2;i--){
    int n = sum/i;
    if(i%2==1 && sum%i==0){
      vector<int> tmp;
      for(int j=n-(i-1)/2;j<=n+(i-1)/2;j++){
        tmp.push_back(j);
      }
      res.push_back(tmp);
    }
    if(i%2==0 && sum%i*2==i){
      vector<int> tmp;
      for(int j=n-(i-2)/2;j<=n+(i-2)/2+1;j++){
        tmp.push_back(j);
      }
      res.push_back(tmp);
    }
  }
  return res;
}

剑指offer 42 和为S的两个数

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

vector<int> FindNumbersWithSum(vector<int> array,int sum) {
  vector<int> res;
  if(array.empty()) return res;
  int low=0, high=array.size()-1, Min=INT32_MAX;
  while(low<high){
    cout<<low<<" "<<high<<endl;
    int add = array[low]+array[high], product= array[low]*array[high];
    if(sum==add) {
      if(product<Min){
        Min = product;
        while(!res.empty()){
          res.clear();
        }
        res.push_back(array[low]);
        res.push_back(array[high]);
      }
      low++;high--;
    }
    else if (sum<add){
      high--;
    }
    else{
      low++;
    }
    }
  return res;
}

剑指offer 43 左旋转字符串

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

string LeftRotateStringCircle(string str, int n) {
	if (str.empty()) return "";
	deque<char> q;
	for (int i=0;i<str.size();i++){
		q.push_back(str[i]);
	}
	while(n!=0) {
		char tmp = q.front();
		q.pop_front();
		q.push_back(tmp);
		n--;
	}
	string res="";
	for (int i=0;i<q.size();i++){
		res = res+q[i];
	}
	return res;
}
string LeftRotateString(string str, int n) {
	if (str.empty()) return "";
	n = n % str.size();
	reverse(str.begin(), str.end());
	reverse(str.begin(), str.begin()+str.size()-n);
	reverse(str.begin()+str.size()-n, str.end());
	return str;
}
//自写reverse函数
void reverse1(string& str, int s, int e){
    while (s < e) {
        char temp = str[s];
        str[s] = str[e];
        str[e] = temp;
        s++;
        e--;
    }
}

剑指offer 44 翻转单词顺序列

// “student. a am I”->“I am a student.”

string ReverseSentence1(string str) {
	string res = "";
	if(str.empty()) return res;
	vector <string> s;
	int index=0;
	string tmp="";
	while(index < str.size()){
		if (str[index]==' ') {
			s.push_back(tmp);
			tmp="";
		}
		else{
			tmp+=str[index];
		}
		if(index==str.size()-1) s.push_back(tmp);
		index++;
	}
	for (int i=s.size()-1;i>=0;i--) {
		res += s[i];
		if(i!=0) res += ' ';
	}
return res;
}
string ReverseSentence(string str) {
	std::reverse(str.begin(),str.end());
	int front=0;
	int back=0;
	int size = str.size();
	while(front<size){
	    while(front<size&&str[front]==' ')++front; //跳过空格，找第一个非空字母位置
	    back = front;
	    while(back<size&&str[back]!=' ')++back; //找单词最后一个字符的位置
	    std::reverse(str.begin()+front, str.begin()+back); //反转
	    front = back;
	}
	return str;
}

剑指offer 45 扑克牌顺子

//一组数字，判断是否顺子。0为任意数，如果牌能组成顺子就输出true，否则就输出false。

// O(n)
bool IsContinuous( vector<int> numbers ) {
    if(numbers.empty()) return false;
    vector<int> arr(14, 0);
    arr[0]=-5;
    int Min=14, Max=-1;
    for (int i=0;i<numbers.size();i++){
        arr[numbers[i]]++;
        if(numbers[i]==0) continue;
        if(arr[numbers[i]]>1) return false;
        if (numbers[i]<Min) {
            Min = numbers[i];
        }
        if (numbers[i]>Max) {
            Max = numbers[i];
        }
    }
    if(Max-Min>4) return false;
    return true;
}
// O(nlogn)
bool IsContinuous( vector<int> numbers ) {
    sort(numbers.begin(), numbers.end());
    int cnt0 = 0, cntNeed = 0;
    for(int i = 0; i < 5; i++) {
        if(numbers[i] == 0) {
            ++cnt0;
        } else if(i + 1 < 5 ) {
            if(numbers[i + 1] == numbers[i]) return false;
            cntNeed += numbers[i + 1] - numbers[i] - 1;
        }
    }
    if(cntNeed > cnt0) return false;
    return true;
}

剑指offer 46 孩子们的游戏（圆圈里最后剩下的数）

//约瑟夫圆环。一个数m,编号为0开始报数，m-1的出列，下一个继续从0开始，直至最后一个。

int LastRemaining_Solution(int n, int m) {
  if(n==0 || m<=0) return -1;
  if (n==1) return 0;
  vector<int> v;
  for (int i=0;i<n;i++) {
    v.push_back(i);
  }
  int p = 0;
  while(v.size()>1) {
    n = v.size();
    p = (p+m) % n - 1;
    if (p == -1) p = n-1;
    v.erase(v.begin()+p);
  }
  return v[0];
  }
//公式dp
  int LastRemaining_Solution1(unsigned int n, unsigned int m)
  {

      if(n <= 0 && m <= 0) return -1; //蛋疼的特殊条件
      int t = 0;
      for(int i = 2; i <= n; i++)
          t = (t + m) % i;
      return t;
  }
//模拟循环链表
int LastRemaining_Solution2(int n, int m)//n为人数
{
  if(n<1||m<1)
      return -1;
  list<int> numbers;
  for(int i=0;i<n;i++)
      numbers.push_back(i);
  list<int>::iterator current=numbers.begin();
  while(numbers.size()>1)
  {
      for(int i=1;i<m;i++)//走m-1步到达第m个数处
      {
          ++current;
          if(current==numbers.end())
              current=numbers.begin();
      }

      list<int>::iterator next=++current;
      if(next==numbers.end())
          next=numbers.begin();
      --current;
      numbers.erase(current);
      current=next;
  }
  return *current;//对迭代器取值，等价于对指针取值
}

剑指offer 47 求1+2+…+n

//求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

int Sum_Solution(int n) {
  if (n<=0) return 0;
  if (n==1) return 1;
  return Sum_Solution(n-1)+n;
 }
int Sum_Solution(int n) {
    int ans = n;
//逻辑与有个短路特点，前面为假，后面不计算。
    ans && (ans += Sum_Solution(n - 1));
    return ans;
}

剑指offer 48 不用加减乘除做加法

//求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。用三步走的方式计算二进制值相加：5-101，7-111,第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101 & 111) \<\< 1。第三步重复上述两步，各位相加 0 1 0 \^ 1 0 1 0 = 1 0 0 0，进位值为100 = (010 \& 1010)\<\< 1。继续重复上述两步：1000\^100 = 1100，进位值为0，跳出循环，1100为最终结果。

int Add(int num1, int num2) {
    while(num2!=0){
        int tmp = num1^num2;
        num2 = (num1&num2)<<1;
        num1=tmp;
    }
    return num1;
}

剑指offer 49 把字符串转换为整数

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0。

int StrToInt(string str) {
    if(str.empty()) return 0;
    int res=0, symbol=1;
    if(str[0]=='+') {
        str[0]='0';
    }
    else if(str[0]=='-') {
        symbol=-1;
        str[0] = '0';
    }
    for(int i=0;i<str.size();i++) {
        if(str[i]<'0' || str[i]>'9') {
            res = 0;
            break;
        }
        res = res*10 + str[i]-'0';
    }
    return symbol*res;
}

剑指offer 50 数组中重复的数字

// 在一个长度为n的数组里的所有数字都在0到n-1的范围内.数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

// Parameters:
//        numbers:     an array of integers
//        length:      the length of array numbers
//        duplication: (Output) the duplicated number in the array number
bool duplicate1(int numbers[], int length, int* duplication) {
	bool res=false;
	if(length==0) return res;
	unordered_map<int, int> mp;
	for(int i=0;i<length;i++) {
		if (mp.count(numbers[i])==0) {
			mp[numbers[i]] ++;
		}
		else {
			*duplication = numbers[i];
			res = true;
			break;
		}
	}
	return res;
}

//思路二：剑指offer中解法：因为数组中数字都在0~n - 1，所以若无重复数字排好序则数字i将出现在下标i的位置。
//解法：从头到尾扫描这个数组，当扫描到下标为i的数字m时，先比较这个数字是否等于i，是则扫描下一个数字，否则
//将该数字与下标为m的数字进行比较，若相等，则找到一个重复的数字，否则将两个数字交换，并继续对该位置
//（下标i）重复上面比较过程。

bool duplicate(int numbers[], int length, int* duplication) {
	bool res = false;
	if (length == 0) return res;
	int i = 0;
	while(i<length) {
		if (numbers[i] == i) {
			i++;
			continue;
		}
		if (numbers[numbers[i]] == numbers[i]) {
			res = true;
			*duplication = numbers[i];
			break;
		}
		else {
			int tmp = numbers[i];
			numbers[i] = numbers[tmp];
			numbers[tmp] = tmp;
		}
	}
	return res;
}

剑指offer 51 构建乘积数组

给定一个数组A[0, 1, …, n - 1], 请构建一个数组B[0, 1, …, n - 1],其中B中的元素B[i] = A[0] A[1] … A[i - 1] A[i + 1] … A[n - 1]。不能使用除法。

// recurrent O(n\*n)
vector<int> multiplyN2(const vector<int>& A) {
  vector<int> B;
  if (A.empty()) return B;
  for (int i = 0; i < A.size(); i++) {
    B.push_back(ABhelper(A, A.size()-1, i));
  }
  return B;
}
int ABhelper(vector<int> A, int n, int k) {
  if (n == k && n == 0) return 1;
  if (n == k && n > 0) return ABhelper(A, n - 1, k);
  if (n == 0) return A[0];
  return ABhelper(A, n - 1, k) * A[n];
}
// 上下三角求解合并
//链接：https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46?f=discussion
vector<int> multiply(const vector<int>& A) {
  vector<int> B;
  if (A.empty()) return B;
  int len = A.size();
  // cal up triangle
  B.push_back(1);
  for (int i = 1; i < len; i++) {
    B.push_back(B[i - 1] * A[i - 1]);
  }
  // cal down triangle
  int down =1;
  for (int i = len - 2; i >= 0; i--) {
    down *= A[i + 1];
    B[i] *= down;
  }
  return B;
}

剑指offer 52 正则表达式匹配

//请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

bool match(char* str, char* pattern){
    if (str == NULL || pattern == NULL)  return false;
    int strIndex = 0, patternIndex = 0;
    return matchHelper(str, pattern);
}
bool matchHelper(char* str, char* pattern) {
    // str到尾，pattern到尾，匹配成功
    // 注意下指针和string字符串判断是否为空的区别
    if (*str == '\0' && *pattern == '\0') return true;
    // pattern为空，str不空，匹配必定失败
    if (*pattern == '\0' && *str != '\0') return false;

    // 如果pattern下一个字符不为'*'
    if (*(pattern + 1) != '*') {
        // 匹配成功情况：
        // 1. 当前str字符==当前pattern字符
        // 2. pattern为'.'且当前str不为空
        if (*pattern == *str || (*pattern == '.' && *str != '\0')){
            return matchHelper(str+1, pattern+1);
        }
        else return false;
    }

    // 如果pattern下一个字符为'*'
    else {
        // 继续匹配的情况：
        // 1. 当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，跳过这个‘*’符号；
        // 2. 当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符不变。
        if (*pattern == *str || (*pattern == '.' && *str != '\0')) {
            return matchHelper(str+1,pattern) || matchHelper(str, pattern+2);
        }
        else return matchHelper(str, pattern+2);
    }
}

剑指offer 53 表示数值的字符串

// 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

bool isNumeric(char* string)
{
    if (string == nullptr) return false;
    // 标记符号、小数点、e是否出现过
    bool sign = false, decimal = false, hasE = false;
    for (int i = 0; i < strlen(string); i++) {
        if (string[i] == '+' || string[i] == '-') {
            // 第二次出现+-符号，必须紧接在e之后
            if (sign && string[i-1] != 'e' && string[i-1] != 'E') return false;
            // 第一次出现+-符号，且不是在字符串开头，也必须紧接在e之后
            if (!sign && i>0 && string[i-1] != 'e' && string[i-1] != 'E') return false;
        }
        else if (string[i] == 'e' || string[i] == 'E') {
            // e后面一定要接数字 || 不能同时存在两个e
            if (i == strlen(string) - 1 || hasE) return false;
            hasE = true;
        }
        else if (string[i] == '.') {
            // e后面不能接小数点，小数点不能出现两次
            if (hasE || decimal) return false;
            decimal = true;
        }
        else if (string[i] < '0' || string[i] > '9') return false;
    }
    return true;
}

剑指offer 54 字符流中第一个不重复的字符

// 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。如果当前字符流没有存在出现一次的字符，返回#字符。

string s;
char hash[256] = {0};
//Insert one char from stringstream
void Insert(char ch)
{
        s += ch;
        hash[ch]++;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
    for (int i = 0; i < s.size(); i++) {
        if (hash[s[i]] == 1) {
            return s[i];
        }
    }
    return '#';
}

剑指offer 55 链表中环的入口节点

// 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

ListNode* EntryNodeOfLoop(ListNode* pHead)
{
    if (pHead == nullptr) return nullptr;
    ListNode* fast = pHead;
    ListNode* slow = pHead;
    ListNode* meetingNode = nullptr;
    while (fast->next && slow) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            meetingNode = fast;
            break;
        }
    }
    if (meetingNode) {
        ListNode* p1 = meetingNode;
        ListNode* p2 = pHead;
        while (p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
    return nullptr;
}

剑指offer 56 删除链表中重复的节点

// 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

ListNode* deleteDuplication(ListNode* pHead)
{
    if (pHead == nullptr) return nullptr;
    ListNode *root = pHead, *pre;
    while (root != nullptr) {
        if (root->next->val != root->val) {
            pre = root;
            root = root->next;
        }
        else {
            while (root->next && root->next->val == root->val) {
                root = root->next;
            }
            if (root->next) {
                pre->next = root->next;
                root = root->next;
            }
            else {
                pre->next = nullptr;
                return pHead;
            }
        }
    }
    return pHead;
}

剑指offer 57 二叉树的下一个节点

// 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
    if (pNode == nullptr) return pNode;
    while (pNode->right) {
        pNode = pNode->left;
    }
}

剑指offer 58 对称的二叉树

// 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

bool isSymmetrical(TreeNode* pRoot)
{
    if (pRoot == nullptr) return true;
    return isSymmetricalHelper(pRoot->left, pRoot->right);
}
bool isSymmetricalHelper(TreeNode* p1, TreeNode* p2) {
    if (p1 && p2 == nullptr) return false;
    else if (p2 && p1 == nullptr) return false;
    else if (p1 == nullptr && p2 == nullptr) return true;
    if (p1->val == p2->val) {
        return isSymmetricalHelper(p1->left, p2->right) && isSymmetricalHelper(p2->left, p1->right);
    }
    else return false;
}

剑指offer 59 之字形打印二叉树

// 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

vector<vector<int> > PrintZ(TreeNode* pRoot) {
    vector<vector<int> > res;
    if (pRoot == nullptr) return res;
    vector<TreeNode*> d;
    d.push_back(pRoot);
    vector<int> init;
    init.push_back(pRoot->val);
    res.push_back(init);
    int layer = 1;
    while (!d.empty()) {
        layer++;
        vector<TreeNode*> tmp;
        for (int i = 0; i < d.size(); i++) {
            if (d[i]->left) tmp.push_back(d[i]->left);
            if (d[i]->right) tmp.push_back(d[i]->right);
        }
        vector<int> tmpInt;
        for (int i = 0; i < tmp.size(); i++) {
            tmpInt.push_back(tmp[i]->val);
        }
        if (layer % 2 == 1 && !tmpInt.empty()) {
            res.push_back(tmpInt);
        }
        else if (layer % 2 == 0 && !tmpInt.empty()) {
            reverse(tmpInt.begin(), tmpInt.end());
            res.push_back(tmpInt);
        }
        d = tmp;
    }
    return res;
}

剑指offer 60 把二叉树打印成多行（层序遍历）

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

vector<vector<int> > Print(TreeNode* pRoot) {
    vector<vector<int> > vec;
    if(pRoot == NULL) return vec;

    queue<TreeNode*> q;
    q.push(pRoot);

    while(!q.empty())
    {
        int lo = 0, hi = q.size();
        vector<int> c;
        while(lo++ < hi)
        {
            TreeNode *t = q.front();
            q.pop();
            c.push_back(t->val);
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
        }
        vec.push_back(c);
    }
    return vec;
}

剑指offer 61 序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

typedef TreeNode node;
typedef TreeNode* pnode;
typedef int* pint;
class Solution {
    vector<int> buf;
    void dfs(pnode p){
        if(!p) buf.push_back(0x23333);
        else{
            buf.push_back(p -> val);
            dfs(p -> left);
            dfs(p -> right);
        }
    }
    pnode dfs2(pint& p){
        if(*p == 0x23333){
            ++p;
            return NULL;
        }
        pnode res = new node(*p);
        ++p;
        res -> left = dfs2(p);
        res -> right = dfs2(p);
        return res;
    }
public:
    char* Serialize(TreeNode *p) {
        buf.clear();
        dfs(p);
        int *res = new int[buf.size()];
        for(unsigned int i = 0; i < buf.size(); ++i) res[i] = buf[i];
        return (char*)res;
    }
    TreeNode* Deserialize(char *str) {
        int *p = (int*)str;
        return dfs2(p);
    }
};

剑指offer 62 二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如,(5，3，7，2，4，6，8)中，按结点数值大小顺序第三小结点的值为4。

// 递归
int cnt = 0;
TreeNode* KthNode(TreeNode* pRoot, int k)
{
    if (pRoot) {
        TreeNode* node = KthNode(pRoot->left, k);
        if (node) return node;
        cnt++;
        if (cnt == k) return pRoot;
        node = KthNode(pRoot->right, k);
        if (node) return node;
    }
    return nullptr;
}
// 非递归 中序遍历
TreeNode* KthNode(TreeNode* pRoot, int k)
{
    if (pRoot == nullptr || k < 1) return nullptr;
    stack<TreeNode*> S;
    int cnt = 0;
    TreeNode* node = pRoot;
    while (!S.empty() || node) {
        while (node) {
            S.push(node);
            node = node->left;
        }
        node = S.top();
        S.pop();
        cnt++;
        if (cnt == k) return node;
        node = node->right;
    }
    return nullptr;
}

剑指offer 63 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

// 法1：大顶堆+小顶堆 
// 法2：AVL 平衡二叉搜索树
// 法3：排序
vector<int> dataStream;
void Insert(int num)
{
    dataStream.push_back(num);
    sort(dataStream.begin(), dataStream.end());
}

double GetMedian()
{ 
    int sz = dataStream.size();
    double res;
    if (sz % 2 == 0) {
        res = (double) (dataStream[sz/2] + dataStream[sz/2-1]) / 2;
    }
    else {
        res = (double) dataStream[sz/2];
    }
    return res;
}

剑指offer 64 滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}。

// 暴力法 O(n * size)
int FindMaxVal(vector<int> num, int st, int ed) {
    int MaxVal = num[st];
    for (int i = st; i <= ed; i++) {
        if (num[i] > MaxVal) MaxVal = num[i];
    }
    return MaxVal;
}
vector<int> maxInWindows1(const vector<int>& num, unsigned int size)
{
    vector<int> res;
    if (num.size() == 0 || size < 1) return res;
    for (int i = 0; i <= num.size()-size; i++) {
        int tmp = FindMaxVal(num, i, i+size-1);
        res.push_back(tmp);
    }
    return res;
}
// 双端队列 O(n)
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
    vector<int> res;
    if (num.size() == 0 || size < 1) return res;
    deque<int> d;
    for (int i = 0; i < num.size(); ++i) {
        // 从后面依次弹出队列汇总比当前num值小的元素，同时保证队首元素为当前窗口最大值下标
        while (d.size() && num[d.back()] <= num[i]) {
            d.pop_back();
        }
        // 当当前窗口移出队首元素所在的位置，即队首元素坐标对应的num不在窗口中，需要弹出
        if (d.size() && i-d.front()+1 > size) {
            d.pop_front();
        }
        d.push_back(i);
        // 当滑动窗口首地址i大于等于size时才开始写入窗口最大值
        if (i >= size - 1) {
            res.push_back(num[d.front()]);
        }
    }
    return res;
}

剑指offer 65 矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

bool dfs(char* matrix, int i, int j, int rows, int cols, char* str, vector<vector<bool> > path) {
    if (*str == '\0') return true;
    if (matrix[i * cols + j] != str[0]) return false;

    bool hasPath = false;
    if (j >= 0 && i >=0 && i < rows && j < cols && !path[i][j]
        && matrix[i * cols + j] == str[0]) {
            path[i][j] = true;
            hasPath = dfs(matrix, i-1, j, rows, cols, str+1, path)
                    || dfs(matrix, i+1, j, rows, cols, str+1, path)
                    || dfs(matrix, i, j-1, rows, cols, str+1, path)
                    || dfs(matrix, i, j+1, rows, cols, str+1, path);
            if (!hasPath) path[i][j] = false;
        }
    return hasPath;
}

bool hasPath(char* matrix, int rows, int cols, char* str)
{
    if (matrix == nullptr || str == nullptr) return false;
    vector<vector<bool> > path(rows, vector<bool>(cols, false));
    bool res = false;
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            if (matrix[row * cols + col] == str[0]) {
                res = dfs(matrix, row, col, rows, cols, str, path);
            }
            if (res) return res;
        }
    }
    return res;
}

剑指offer 66 机器人的动作范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

int movingCount(int threshold, int rows, int cols)
{
    bool* flag=new bool[rows*cols];
    for(int i=0;i<rows*cols;i++)
        flag[i]=false;
    int count=moving(threshold,rows,cols,0,0,flag);//从（0,0）坐标开始访问;
    delete[] flag;
    return count;
}
//计算最大移动位置
int moving(int threshold,int rows,int cols,int i,int j,bool* flag) {
    int count=0;
    if(check(threshold,rows,cols,i,j,flag)) {
        flag[i*cols+j]=true;
        //标记访问过，这个标志flag不需要回溯，因为只要被访问过即可。
       //因为如果能访问，访问过会加1.不能访问，也会标记下访问过。
        count=1+moving(threshold,rows,cols,i-1,j,flag) + moving(threshold,rows,cols,i,j-1,flag)
               +moving(threshold,rows,cols,i+1,j,flag) + moving(threshold,rows,cols,i,j+1,flag);
    }
    return count;
}
//检查当前位置是否可以访问
bool check(int threshold,int rows,int cols,int i,int j,bool* flag) {
    if(i>=0 && i<rows && j>=0 && j<cols
        && getSum(i)+getSum(j)<=threshold
        && flag[i*cols+j]==false)
       return true;
    return false;
}
//计算位置的数值
int getSum(int number) {
    int sum=0;
    while(number>0) {
        sum+=number%10;
        number/=10;
    }
    return sum;
}

剑指offer 67 剪绳子

给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

/* 首先判断k[0]到k[m]可能有哪些数字，实际上只可能是2或者3。
 * 5<2*3,6<3*3,比6更大的数字我们就更不用考虑了，肯定要继续分。
 * 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2*2*2<3*3，那么题目就简单了。
 * 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。
 * 由于题目规定m>1，所以2只能是1*1，3只能是2*1，这两个特殊情况直接返回就行了。 */
long long n_max_3(long long n) {
    if (n == 2) return 1;
    if (n == 3) return 2;
    long long x = n % 3;
    long long y = n / 3;
    if (x == 0) {
        return pow(3, y);
    } else if (x == 1) {
        return 2 * 2 * (long long) pow(3, y - 1);
    } else {
        return 2 * (long long) pow(3, y);
    }
}

# Algorithm, C++