剑指Offer-week1

给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

数据范围

1≤n≤1000

抽屉原理加分支，将数组划分为左右两边重复元素一定在么某一侧，如果说某一侧中区间内的数大于区间长度r-l+1说明重复元素在该侧，二分求解即可。

special judge：

class Solution {
public:
    int duplicateInArray(vector& nums) {
          int n=nums.size();
          int l=1,r=n;
          while(l>1;
              int s=0;
              for(auto x:nums) s+=(x>=l&&x<=mid);
              if(s>mid-l+1) r=mid;
              else l=mid+1;
              }
              return l;
    }
};

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

数据范围

二维数组中元素个数范围 [0,1000]

副对角线上的元素同一行随校表增大而增大，同一列随下标增大而减小根据这个性质能在O（n+m）时间复杂度下求出target 是否存在。

return true or false

class Solution {
public:
    bool searchArray(vector> array, int target) {
         if(array.empty()||array[0].empty()) return false;
         int i=0,j=array[0].size()-1;
         while(i=0){
             int x=array[i][j];
             if(x==target) return true;
             else if(x>target) j--;
             else i++;
         }
         return false;
    }
};

给你一个字符串用“%20”替换当中的空格。

class Solution {
public:
    string replaceSpaces(string &str) {
         string res;
         for(int i=0;i<(int )str.size();i++){
             if(str[i]==' '){
                 res+="%20";
             }else res+=str[i];
         }
         return res;
    }
};

给你一个链表，按照从尾到头的顺序返回结点的值，返回的结果用一个数组来存储。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector printListReversingly(ListNode* head) {
           vectorres;
           while(head) {
               res.push_back(head->val);
               head=head->next;
           }
           return  vector(res.rbegin(),res.rend());
   }
};

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

//前序遍历是 根->左儿子->右儿子，中序遍历是左儿子- >根->右儿子；

注意:

• 二叉树中每个节点的值都互不相同；
• 输入的前序遍历和中序遍历一定合法；

数据范围

树中节点数量范围 [0,100]。

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7