删除链表中重复的结点

我的：

//方法1：
  ListNode* deleteDuplication(ListNode* pHead)
    {
       ListNode* rHead=new ListNode(0);
         ListNode* rtemp=rHead;
        ListNode* temp=pHead;
        if(pHead==NULL||pHead->next==NULL) return pHead;
        int value = NULL;
        while(temp->next!=NULL){
            if(temp->val == temp->next->val){
                value = temp->val;
            }else{
                if(value==NULL||temp->val != value){
                   rtemp->next = temp;
                   rtemp = rtemp->next;
                }
            }
              temp = temp->next;
        }
        if(temp->val!=value){
             rtemp->next = temp;
            rtemp = rtemp->next;
        }
        rtemp->next = NULL;
        return rHead->next;
    }
//方法2：递归
 ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead==NULL)
            return NULL;
        if (pHead!=NULL && pHead->next==NULL)
            return pHead;
                 
        ListNode* current;
         
        if ( pHead->next->val==pHead->val){
            current=pHead->next->next; 
            while (current != NULL && current->val==pHead->val)
                current=current->next;
            return deleteDuplication(current);                      
        }
         
        else {
            current=pHead->next;
            pHead->next=deleteDuplication(current);
            return pHead;
        }     
    }
//方法3：非递归的代码：
1. 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况
2.设置 pre ，last 指针， pre指针指向当前确定不重复的那个节点，而last指针相当于工作指针，一直往后面搜索。

if (pHead==null || pHead.next==null){return pHead;}
ListNode Head = new ListNode(0);
Head.next = pHead;
ListNode pre  = Head;
ListNode last = Head.next;
while (last!=null){
    if(last.next!=null && last.val == last.next.val){
        // 找到最后的一个相同节点
        while (last.next!=null && last.val == last.next.val){
            last = last.next;
        }
        pre.next = last.next;
        last = last.next;
    }else{
        pre = pre.next;
        last = last.next;
    }
}
return Head.next;

//方法4：
 ListNode* deleteDuplication(ListNode* pHead)
    {
          if(pHead==NULL||pHead->next==NULL) return pHead;
          else
          {
              //新建一个节点，防止头结点要被删除
              ListNode* newHead=new ListNode(-1);
              newHead->next=pHead;
              ListNode* pre=newHead;
              ListNode* p=pHead;
              ListNode* next=NULL;
              while(p!=NULL && p->next!=NULL)
              {
                  next=p->next;
                  if(p->val==next->val)//如果当前节点的值和下一个节点的值相等
                  {
                      while(next!=NULL && next->val==p->val)//向后重复查找
                          next=next->next;
                    pre->next=next;//指针赋值，就相当于删除
                    p=next;
                  }
                  else//如果当前节点和下一个节点值不等，则向后移动一位
                  {
                      pre=p;
                      p=p->next;
                  }
              }
           return newHead->next;//返回头结点的下一个节点
               
          }
    }

剑指：方法3,4一样

二叉树的下一个结点

我的：

//方法1：
int flag = false;
    TreeLinkNode* result=NULL;
   void zhong(TreeLinkNode* root, TreeLinkNode* pNode){
        if(root==NULL) return;
        if(root->left!=NULL) zhong(root->left,pNode);
        if(flag){
            result = root;
            flag = false;
            return ;
        }
        if(root == pNode){
            flag = true;
        }
        if(root->right!=NULL) zhong(root->right,pNode);
   }
   TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        TreeLinkNode* root = pNode;
        while(root->next!=NULL){
            root = root->next;
        }
        zhong(root,pNode);
        return result;
    }
//方法2：

//分析二叉树的下一个节点，一共有以下情况：
//1.二叉树为空，则返回空；
//2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
//3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。
classSolution{
 public:
     TreeLinkNode* GetNext(TreeLinkNode* pNode)
     {
         if (pNode == NULL)
             returnNULL;
         if (pNode->right != NULL)
         {
             pNode = pNode->right;
             while (pNode->left != NULL)
                 pNode = pNode->left;
             returnpNode;
         }
         while (pNode->next != NULL)
         {
             TreeLinkNode *proot = pNode->next;
             if (proot->left == pNode)
                 returnproot;
             pNode = pNode->next;
         }
         returnNULL;
     }
 };

PS：方法2：
思路：首先知道中序遍历的规则是：左根右，然后作图

image

结合图，我们可发现分成两大类：1、有右子树的，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G） 2、没有右子树的，也可以分成两类，a)是父节点左孩子（eg：N，I，L），那么父节点就是下一个节点； b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。

剑指：方法2

对称的二叉树

我的：

//方法1：
 bool judge(TreeNode* lRoot, TreeNode* rRoot){
        if(lRoot==NULL&&rRoot==NULL) return true;
         if(lRoot==NULL&&rRoot!=NULL) return false;
        if(lRoot!=NULL&&rRoot==NULL) return false;
        if(lRoot->val != rRoot->val) return false;
        return judge(lRoot->left,rRoot->right)&&judge(lRoot->right,rRoot->left);
    }
   bool isSymmetrical(TreeNode* pRoot)
    {
        if(pRoot==NULL) return true;
        return judge(pRoot->left,pRoot->right);
    }

//方法2：
代码很简单，关键还是知道怎么样才能判断一个
二叉树是否对称，只要采用前序、中序、后序、层次遍历等任何一种遍历方法，分为先左后右和先
右后左两种方法，只要两次结果相等就说明这棵树是一颗对称二叉树。
迭代版本
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==NULL) return true;
        queue<TreeNode*> q1,q2;
        TreeNode *left,*right;
        q1.push(root->left);
        q2.push(root->right);
        while(!q1.empty() and !q2.empty())
        {
            left = q1.front();
            q1.pop();
            right = q2.front();
            q2.pop();
            //两边都是空
            if(NULL==left && NULL==right)
                continue;
            //只有一边是空
            if(NULL==left||NULL==right)
                return false;
             if (left->val != right->val)
                return false;
            q1.push(left->left);
            q1.push(left->right);
            q2.push(right->right);
            q2.push(right->left);
        }
         
        return true;
         
    }
};
//方法3：
/*
      * DFS使用stack来保存成对的节点

     * 1.出栈的时候也是成对成对的 ， 

                1.若都为空，继续； 

                2.一个为空，返回false; 

                3.不为空，比较当前值，值不等，返回false； 
     * 2.确定入栈顺序，每次入栈都是成对成对的，如left.left， right.right ;left.rigth,right.left
      */
boolean isSymmetricalDFS(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        Stack<TreeNode> s = new Stack<>();
        s.push(pRoot.left);
        s.push(pRoot.right);
        while(!s.empty()) {
            TreeNode right = s.pop();//成对取出
            TreeNode left = s.pop();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //成对插入
            s.push(left.left);
            s.push(right.right);
            s.push(left.right);
            s.push(right.left);
        }
        return true;
    }
  /*
      * BFS使用Queue来保存成对的节点，代码和上面极其相似

     * 1.出队的时候也是成对成对的  


               1.若都为空，继续； 

                2.一个为空，返回false; 

                3.不为空，比较当前值，值不等，返回false； 
     * 2.确定入队顺序，每次入队都是成对成对的，如left.left， right.right ;left.rigth,right.left
      */
boolean isSymmetricalBFS(TreeNode pRoot)
    {
        if(pRoot == null) return true;
        Queue<TreeNode> s = new LinkedList<>();
        s.offer(pRoot.left);
        s.offer(pRoot.right);
        while(!s.isEmpty()) {
            TreeNode right = s.poll();//成对取出
            TreeNode left = s.poll();
            if(left == null && right == null) continue;
            if(left == null || right == null) return false;
            if(left.val != right.val) return false;
            //成对插入
            s.offer(left.left);
            s.offer(right.right);
            s.offer(left.right);
            s.offer(right.left);
        }
        return true;
    }

剑指：方法1

按之字形顺序打印二叉树

我的：

//方法1：先遍历后打印
  vector<vector<int> > Print(TreeNode* pRoot) {
          vector<vector<int> > result;
         if(pRoot==NULL) return result;
         queue<TreeNode*> nodes;
         nodes.push(pRoot);
         bool flag = true;
         while(!nodes.empty()){
            vector<int> temp;
            int le = nodes.size();
            for(int i = 0;i<le;i++){
                TreeNode* node = nodes.front();
                nodes.pop();
                temp.push_back(node->val);
                if(node->left!=NULL) nodes.push(node->left);
                if(node->right!=NULL) nodes.push(node->right);
            }
            result.push_back(temp);
         }
         for(int i = 0;i<result.size();i++){
            if(i%2==1) reverse(result[i].begin(),result[i].end());
         }
         return result;
    }
//方法2：stack来保存逆序
  vector<vector<int> > Print(TreeNode* pRoot) {
         bool flag = true;
         queue<TreeNode> le;
          vector<vector<int> > result;
        if(pRoot==NULL) return result;
         le.push(*pRoot);
         while(!le.empty()){
            vector<int> r;
            stack<int> ri;
            for(int i =0,n=le.size();i<n;i++){
               TreeNode temp = le.front();
                if(flag){
                    r.push_back(temp.val);
                }else{
                    ri.push(temp.val);
                }
                le.pop();
                if(temp.left!=NULL) le.push(*temp.left);
                if(temp.right!=NULL) le.push(*temp.right);
            }
            while(!ri.empty()){
                TreeNode temp = ri.top();
                r.push_back(temp.val);
                ri.pop();
            }
            result.push_back(r);
            flag = !flag;
         }
        return result;
    }
//方法3：
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        int layer = 1;
        //s1存奇数层节点
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        s1.push(pRoot);
        //s2存偶数层节点
        Stack<TreeNode> s2 = new Stack<TreeNode>();
         
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
         
        while (!s1.empty() || !s2.empty()) {
            if (layer%2 != 0) { 
                ArrayList<Integer> temp = new ArrayList<Integer>(); 
                while (!s1.empty()) {
                    TreeNode node = s1.pop();
                    if(node != null) {
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s2.push(node.left);
                        s2.push(node.right);
                    }
                }
                if (!temp.isEmpty()) {
                    list.add(temp);
                    layer++;
                    System.out.println();
                }
            } else {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                while (!s2.empty()) {
                    TreeNode node = s2.pop();
                    if(node != null) {
                        temp.add(node.val);
                        System.out.print(node.val + " ");
                        s1.push(node.right);
                        s1.push(node.left);
                    }
                }
                if (!temp.isEmpty()) {
                    list.add(temp);
                    layer++;
                    System.out.println();
                }
            }
        }
        return list;
    }

剑指：方法3

把二叉树打印成多行

我的：

vector<vector<int> > Print(TreeNode* pRoot) {
         vector<vector<int> > result;
         if(pRoot==NULL) return result;
         queue<TreeNode*> nodes;
         nodes.push(pRoot);
         while(!nodes.empty()){
            vector<int> temp;
            int le = nodes.size();
            for(int i = 0;i<le;i++){
                TreeNode* node = nodes.front();
                nodes.pop();
                temp.push_back(node->val);
                if(node->left!=NULL) nodes.push(node->left);
                if(node->right!=NULL) nodes.push(node->right);
            }
            result.push_back(temp);
         }
         return result;
    }
//方法2：递归BFS
//用递归做的
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        depth(pRoot, 1, list);
        return list;
    }
     
    private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
        if(root == null) return;
        if(depth > list.size()) 
            list.add(new ArrayList<Integer>());
        list.get(depth -1).add(root.val);
         
        depth(root.left, depth + 1, list);
        depth(root.right, depth + 1, list);
    }
}

剑指：一样

序列化二叉树

我的：不会

//方法1：

string result="";
       void xian(TreeNode *root){
           if(root==NULL) result=result+"#!";
           else{
                char temp = root->val+'0';
                result=result+to_string(root->val)+'!';
                xian(root->left);
                xian(root->right);
           }
       }
       char* Serialize(TreeNode *root) {
             if(root==NULL) return NULL;
             xian(root);
                char *ret = new char[result.length() + 1];
            int i;
            for(i = 0; i < result.length(); i++){
                ret[i] = result[i];
            }
            ret[i] = '\0';
            return ret;           
// strcpy(ret, result.c_str());
        }
    TreeNode* Deserialize(char *&str) {
        if(str == NULL) return NULL;
        TreeNode* node = NULL;
        if(*str!='#'){
           int temp = 0;
           while(*str!='!'){
                temp = 10*temp+int(*str-'0');
               str++;
           }
            str++;
           node = new TreeNode(temp);
           node->left = Deserialize(str);
           node->right = Deserialize(str);
        }else str+=2;
        return node;
    }

PS：
序列化二叉树：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串。需要注意的是，序列化二叉树的过程中，如果遇到空节点，需要以某种符号（这里用#）表示。以下图二叉树为例，序列化二叉树时，需要将空节点也存入字符串中。
反序列化二叉树：根据某种遍历顺序得到的序列化字符串，重构二叉树。
剑指：
一样

二叉搜索树的第k个结点

我的：

//方法1：
 int flag=0;
       TreeNode* result = NULL;
       void zhong(TreeNode *root, int k ){
           if(root!=NULL);
           {
                if(root->left!=NULL)zhong(root->left, k);
                if(++flag==k){
                    result = root;
                }
                if(root->right!=NULL)zhong(root->right,k);
           }
       }
    TreeNode* KthNode(TreeNode* pRoot, int k)
    {
        if(pRoot== NULL) return NULL;
        zhong(pRoot,k);
        return result;
    }

PS：中序遍历，非递归

   void zhong(TreeNode *root){
        stack<TreeNode*> temp;
        while (root != NULL || ! temp.empty()) {
            while (root != NULL) {
                temp.push(root);
                root = root->left;
            }
            root = temp.top();
            temp.pop();
           cout<<root->val<<endl;
            root = root->right;
        }
       }

剑指：递归中序

数据流中的中位数

我的：

//方法1：
priority_queue<int, vector<int>, less<int> > large;
   priority_queue<int, vector<int>, greater<int> > small;
   int count = 0;
    void Insert(int num)
    {
        count++;
        large.push(num);
        int lsize = large.size();
        int ssize = small.size();
        if(lsize-ssize>1){
            int temp = large.top();
            large.pop();
            small.push(temp);
        }
       if(!large.empty()&&!small.empty()&&large.top()>small.top()){
             int temp = large.top();
               large.pop();
            int temp2 = small.top();
              small.pop();
                large.push(temp2);
                small.push(temp);
        }
    }
    double GetMedian()
    {
        if(!large.empty()){
             if(count%2==0){
                return (large.top()+small.top())/2.0;
            }else return large.top();
        }
        return NULL;
    }

//方法2：

剑指：一样

class Solution {
private:
        vector<int> min;
        vector<int> max;
public:
        void Insert(int num)
        {
           if(((min.size()+max.size())&1)==0)//偶数时 ，放入最小堆 
           {
              if(max.size()>0 && num<max[0])
              {
                // push_heap (_First, _Last),要先在容器中加入数据，再调用push_heap ()
                 max.push_back(num);//先将元素压入容器
                 push_heap(max.begin(),max.end(),less<int>());//调整最大堆 
                 num=max[0];//取出最大堆的最大值 
                 //pop_heap(_First, _Last)，要先调用pop_heap()再在容器中删除数据
                 pop_heap(max.begin(),max.end(),less<int>());//删除最大堆的最大值 
                 max.pop_back(); //在容器中删除 
              }
              min.push_back(num);//压入最小堆 
              push_heap(min.begin(),min.end(),greater<int>());//调整最小堆 
           }
           else//奇数时候，放入最大堆
           {
              if(min.size()>0 && num>min[0])
              {
                // push_heap (_First, _Last),要先在容器中加入数据，再调用push_heap ()
                 min.push_back(num);//先压入最小堆 
                 push_heap(min.begin(),min.end(),greater<int>());//调整最小堆 
                 num=min[0];//得到最小堆的最小值（堆顶） 
                 //pop_heap(_First, _Last)，要先调用pop_heap()再在容器中删除数据
                 pop_heap(min.begin(),min.end(),greater<int>());//删除最小堆的最大值 
                 min.pop_back(); //在容器中删除 
              }
              max.push_back(num);//压入数字 
              push_heap(max.begin(),max.end(),less<int>());//调整最大堆 
           }    
        }
        /*获取中位数*/      
        double GetMedian()
        {
            int si敏感词.size()+max.size();
            if(size<=0) //没有元素，抛出异常 
                return 0;//throw exception("No numbers are available");
            if((size&1)==0)//偶数时，去平均 
                return ((double)(max[0]+min[0])/2);
            else//奇数，去最小堆，因为最小堆数据保持和最大堆一样多，或者比最大堆多1个 
                return min[0];
        }
};

滑动窗口的最大值

我的：

 vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        int le = num.size();
        int flag = -1;
        int ma = INT_MIN;
         vector<int> result;
           if(size==0) return result;
        for(int i = 0;i<le-size+1;i++){
            if(flag<i){
                flag = i;
                ma = num[i];
                for(int j = i+1;j<i+size;j++){
                    if(num[j]>ma){
                        flag = j;
                        ma = num[j];
                    }
                }
            }else{
                if(num[i+size-1]>num[flag]){
                     flag = i+size-1;
                     ma = num[flag];
                }
            }
            result.push_back(ma);
        }
        return result;

    }
//方法2：双端队列
//引用马客（Mark）的解题思路，马客没加注释，我用自己的理解加下注释，希望对你们有用，
//如有错误，见谅，我会及时修改。
//deque s中存储的是num的下标
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> res;
        deque<int> s;
        for(unsigned int i=0;i<num.size();++i){
            while(s.size() && num[s.back()]<=num[i])//从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标
                s.pop_back();
            while(s.size() && i-s.front()+1>size)//当当前窗口移出队首元素所在的位置，即队首元素坐标对应的num不在窗口中，需要弹出
                s.pop_front();
            s.push_back(i);//把每次滑动的num下标加入队列
            if(size&&i+1>=size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
                res.push_back(num[s.front()]);
        }
        return res;
    }
//方法3：双端
 //时间复杂度o（n），空间复杂度为o（n）
    /*思路就是采用双端队列，队列中的头节点保存的数据比后面的要大。
      比如当前假如的数据比队尾的数字大，说明当前这个数字最起码在从现在起到后面的过程中可能是最大值
      ，而之前队尾的数字不可能最大了，所以要删除队尾元素。
      此外，还要判断队头的元素是否超过size长度，由于存储的是下标，所以可以计算得到；
      特别说明，我们在双端队列中保存的数字是传入的向量的下标；
    */
    vector<int> maxInWindows(const vector<int>& num, unsigned int size)
    {
        vector<int> vec;
        if(num.size()<=0 || num.size()<size ||size<=0) return vec;//处理特殊情况
        deque<int> dq;
        //处理前size个数据，因为这个时候不需要输出最大值；
        for(unsigned int i=0;i<size;i++)
        {
 //假如当前的元素比队列队尾的元素大，说明之前加入的这些元素不可能是最大值了。因为当前的这个数字比之前加入队列的更晚
            while(!dq.empty()&&num[i]>=num[dq.back()])
                dq.pop_back();//弹出比当前小的元素下标
            dq.push_back(i);//队尾压入当前下标
        }
        //处理size往后的元素，这时候需要输出滑动窗口的最大值
        for(unsigned int i=size;i<num.size();i++)
        {
            vec.push_back(num[dq.front()]);
            while(!dq.empty()&&num[i]>=num[dq.back()])
                dq.pop_back();
            if(!dq.empty() && dq.front()<=(int)(i-size))//判断队头的下标是否超出size大小，如果超过，要删除队头元素
                dq.pop_front();//删除队头元素
            dq.push_back(i);//将当前下标压入队尾，因为可能在未来是最大值
        }
        vec.push_back(num[dq.front()]);//最后还要压入一次
        return vec;
    }

剑指：方法2，下标，每次加入尾部，删除小于尾部的，头判断是不是过期

矩阵中的路径

我的：

//方法1：回溯
bool judge(char* matrix, int nrows, int ncols, int rows, int cols,char* str, vector<int>& flag){
        if(*str=='\0') return true;
        if(nrows<0||nrows>(rows-1)||ncols<0||ncols>(cols-1)||flag[nrows*cols+ncols]==1) return false;
        if(matrix[nrows*cols+ncols] == *str){
            flag[nrows*cols+ncols]=1;
            bool result =
            judge(matrix, nrows-1,ncols,rows,cols,str+1,flag)||
            judge(matrix, nrows+1,ncols,rows,cols,str+1,flag)||
            judge(matrix, nrows,ncols-1,rows,cols,str+1,flag)||
            judge(matrix, nrows,ncols+1,rows,cols,str+1,flag);
            flag[nrows*cols+ncols]=0;
            return result;
        }else return false;
    }
  bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(*str=='\0'||*matrix=='\0') return false;
           vector<int> flag(rows*cols, 0);
        int count = 0 ;
        while(*(matrix+count)!='\0'){
            if(*str == *(matrix+count)){
                if(judge(matrix, count/cols,count%cols,rows,cols,str,flag))
                    return true;
            }
            count++;
        }
        return false;
    }
//方法2：

PS：几种初始化，和传入形式，达到修改原值：

int flag[] = new int[matrix.length];  int [] flag
 bool *isOk=new bool[rows*cols]();  bool *isOk,
 vector<bool> used(strlen(matrix),false);  vector<bool>& used
bool *flag=new bool[rows*cols];  bool* flag
 bool *flag=new bool[rows*cols];
        memset(flag,0,rows*cols);
bool* flag

还是没搞明白为什么状态要改回来，不然永久置1了？为什么我测试还是没问题。。。。我的测试有问题：
用例:
"ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS",5,8,"SGGFIECVAASABCEHJIGQEM"

可以看出有无恢复的区别

剑指：

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str) {
        bool res = 0;
        bool *flag=new bool[rows*cols];
        memset(flag,0,rows*cols);
        for (int i = 0;i<rows;++i) {
            for (int j = 0;j<cols;++j) {
                //bool *flag = (bool *)calloc(rows*cols, 1);
                res = dfs(matrix, rows, cols, i, j, flag, str);//1
                if (res == true)
                    return res;
            }
        }
        delete[] flag;
        return res;
    }
    bool dfs(char* matrix, int rows, int cols, int i, int j, bool* flag, char* str) {
        if (*str == '\0')
            return true;
        if(i<0||i>=rows||j<0||j>=cols)
            return false;
        if (*(flag+i*cols + j) == 1 || (*(flag+i*cols + j) == 0 && *(matrix + i*cols + j) != *str)) 
            return false;
        else {
            *(flag+i*cols + j) = 1;
            bool res=dfs(matrix, rows, cols, i, j - 1, flag, str + 1)//左
                ||dfs(matrix, rows, cols, i, j + 1, flag, str+1)//右
                ||dfs(matrix, rows, cols, i - 1, j, flag, str+1)//上
                ||dfs(matrix, rows, cols, i + 1, j, flag, str+1);//下
            if(res==0)
                *(flag+i*cols + j)=0;//这样从1处开始进入的DFS即使没找到路径，但是flag最后全部置为0
            return res;
        }
    }

机器人的运动范围

我的：

//方法1：
  int mysum(int x, int y){
      int sum = 0;
      while(x!=0){
        sum=sum+x%10;
        x=x/10;
      }
      while(y!=0){
        sum=sum+y%10;
        y=y/10;
      }
      return sum;
    }
    void judge(int nrows, int ncols, int rows, int cols,int& count, int k,  vector<int>& flag){
        if(nrows<0||nrows>(rows-1)||ncols<0||ncols>(cols-1)||flag[nrows*cols+ncols]==1||mysum(nrows, ncols)>k) return ;
        count++;
        flag[nrows*cols+ncols]=1;
        judge(nrows,ncols+1,rows,cols,count,k,flag);
        judge(nrows,ncols-1,rows,cols,count,k,flag);
        judge(nrows+1,ncols,rows,cols,count,k,flag);
        judge(nrows-1,ncols,rows,cols,count,k,flag);
    }
     int movingCount(int threshold, int rows, int cols)
    {
        if(threshold<0||rows<0||cols<0) return 0;
        int count = 0;
        vector<int> flag(rows*cols,0);
        judge(0, 0, rows, cols,count, threshold, flag);
        return count;
    }
//方法2：

剑指：

   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二刷2