简单模块

1、两数之和

简单题,用unordered_map<int,int> um;key为值,value为数组下标

遍历一遍,看um中是否有和为target的另一半,并且另一半的数组下标不能相同

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> um;
        for(int i =0;i<nums.size();i++){
            um[nums[i]]=i;
        }
        for(int i=0;i<nums.size();i++){  
            int k =target-nums[i];
            if(um.count(k) && um[k]!=i){  //WA一次,没考虑um[k]!=i
                res.push_back(i);
                res.push_back(um[k]);
                break;
            }
        }
        return res;
    }
};

20、有效的括号

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i =0;i<s.length();i++){
            if(s[i]=='('){
                st.push(')');
            }else if(s[i]=='['){
                st.push(']');
            }else if(s[i]=='{'){
                st.push('}');
            }else{
                if(st.size()&&s[i]==st.top()){  //WA一次,没考虑st.size()
                    st.pop();
                    continue;
                }else{
                    return false;
                }
            }
        }
        if(st.size()) return false;
        else return true;
    }
};

21、合并2个有序链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//思路一:迭代
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode * dummy = new ListNode(0); //创建哑结点
        ListNode * p = dummy; //新链表的工作指针
        //如果两个都不为空
        while(list1!=NULL&&list2!=NULL){
            //先把list1中小的元素放到新链表中
            if(list1->val<=list2->val){
                p->next = list1;
                list1=list1->next;
                p=p->next;
            }
            else{
                p->next = list2;
                list2=list2->next;
                p=p->next;
            }
        }
        //如果list1空了,list2不空
        if(list2!=NULL){
            //把list2剩下部分放进去
            p->next =list2;
        }
        //如果list2空了,list1不空
        if(list1!=NULL){
            //把list1剩下部分放进去
            p->next = list1;
        }
        return dummy->next;
    }
};

53、最大子数组和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:   
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        int dp[len];
        int res = -10005;
        dp[0]=nums[0];
        for(int i =1;i<len;i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
        }
        for(int i =0;i<len;i++){
            res=max(res,dp[i]);
        }
        return res;
    }
};

70、爬楼梯

递归超时了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int get(int n){
        if(n==1) return 1;
        else if(n==2) return 2;
        else return get(n-1)+get(n-2);
    }
    int climbStairs(int n) {
        return get(n);
    }
};

改用dp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int dp[48];
    int climbStairs(int n) {
        dp[1]=1;
        dp[2]=2;
        for(int i =3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

94、二叉树的中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> res;
    void dfs(TreeNode* root){
        if(root->left) dfs(root->left);
        res.push_back(root->val);
        if(root->right) dfs(root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==nullptr) return res;
        dfs(root);
        return res;
    }
};

101、对称二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isSame(TreeNode* l,TreeNode* r){
        if(!l&&!r) return true;
        if(!l&&r||l&&!r) return false;
        if(l->val==r->val){
            return isSame(l->left,r->right)&&isSame(l->right,r->left);
        }
        return false;
        
    }
    bool isSymmetric(TreeNode* root) {
        if(!root->left&&!root->right) return true;
        if(root->left&&root->right) return isSame(root->left,root->right);
        return false;
    }
};

104、二叉树的最大深度

dfs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int dfs(TreeNode* root){
        if(!root) return 0;
        int l = 1+dfs(root->left);
        int r = 1+dfs(root->right);
        return max(l,r);
    }
    int maxDepth(TreeNode* root) {       
        return dfs(root);
    }
};

bfs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxDepth(TreeNode* root) { 
        int res = 0;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            int len = q.size();
            res++;
            for(int i =0;i<len;i++){
                auto t = q.front();
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
        return res;
    }
};

121、买卖股票的最佳时机

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int res =0;
        int dp[n]; //dp[i]表示前i个元素中的最小元素
        dp[0]=prices[0];
        for(int i =1;i<n;i++){
            dp[i]=min(prices[i],dp[i-1]);  
        }
        for(int i =0;i<n;i++){
            res=max(res,prices[i]-dp[i]);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
//空间优化版本
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int min = prices[0], max = 0;
        for(int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return max;
    }
}

136、只出现一次的数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        for(int i =0;i<nums.size();i++){
            res^=nums[i];  //2个相同的数异或为0,0异或任意一个数等于这个数
        }
        return res;
    }
};

141、环形链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *one =head;
        ListNode *two = head;       
        while(two!=NULL&&two->next!=NULL){                       
            one=one->next;two=two->next->next;     
            if(one==two) return true;       
        }
        return false;
    }
};

key:一快一慢 总会想见

155、最小栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
        if (st.size() == 0) {
            st.push({x, x});
        } else {
            st.push({x, min(x, st.top().second)});
        }
    }
    
    void pop() {
        st.pop();
    }
    
    int top() {
        return st.top().first;
    }
    
    int getMin() {
        return st.top().second;
    }
private:
    stack<pair<int, int>> st;
};

key:妙用pair

160、相交链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL) return NULL;
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA != curB) {
            curA = curA == NULL ? headB : curA->next;
            curB = curB == NULL ? headA : curB->next;
        }
        return curA;
    }
};

key:我走过你来时的路

169、多数元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int m = nums[0];
        int count =1;
        for(int i =1;i<nums.size();i++){
            if(nums[i]==m) count++;
            else count--;
            if(count==0){
                 m=nums[i];
                 count =1;
            }
        }
        return m;
    }
};

key:摩尔投票法

有一个对摩尔投票法非常形象的比喻:多方混战。

首先要知道,在任何数组中,出现次数大于该数组长度1/3的值最多只有两个。

我们把这道题比作一场多方混战,战斗结果一定只有最多两个阵营幸存,其他阵营被歼灭。数组中的数字即代表某士兵所在的阵营。

我们维护两个潜在幸存阵营A和B。我们遍历数组,如果遇到了属于A或者属于B的士兵,则把士兵加入A或B队伍中,该队伍人数加一。继续遍历。

如果遇到了一个士兵既不属于A阵营,也不属于B阵营,这时有两种情况:

情况一:A阵营和B阵营都还有活着的士兵,那么进行一次厮杀,参与厮杀的三个士兵全部阵亡:A阵营的一个士兵阵亡,B阵营的一个士兵阵亡,这个不知道从哪个阵营来的士兵也阵亡。继续遍历。

情况二:A阵营或B阵营已经没有士兵了。没有士兵的阵营暂时从地球上消失了。那么把当前遍历到的新士兵算作新的潜在幸存阵营,这个新阵营只有他一个人。继续遍历。

大战结束,最后A和B阵营就是初始人数最多的阵营。判断一下A,B的人数是否超过所有人数的三分之一就行了。

229、求众数2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ans;
        int element1 = 0;
        int element2 = 0;
        int vote1 = 0;
        int vote2 = 0;
        for(auto num:nums){
            if(vote1>0&&num==element1){
                vote1++;
            }else if(vote2>0&&num==element2){
                vote2++;
            }else if(vote1==0){
                vote1++;
                element1=num;
            }else if(vote2==0){
                vote2++;
                element2=num;
            }else{
                vote1--;
                vote2--;
            }
        }
        int cnt1 = 0;
        int cnt2 = 0;
        for (auto & num : nums) {
            if (vote1 > 0 && num == element1) {
                cnt1++;
            }
            if (vote2 > 0 && num == element2) {
                cnt2++;
            }
        }
        // 检测元素出现的次数是否满足要求
        if (vote1 > 0 && cnt1 > nums.size() / 3) {
            ans.push_back(element1);
        }
        if (vote2 > 0 && cnt2 > nums.size() / 3) {
            ans.push_back(element2);
        }

        return ans;

    }
};

206、反转链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* t = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};

226、翻转二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return nullptr;
        TreeNode* t =root->left;
        root->left=root->right;
        root->right=t;
        if(root->left){
            invertTree(root->left);
        }
        if(root->right){
            invertTree(root->right);
        }
        return root;
    }
};

234、回文链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> st;
        ListNode* p = head;
        while(p){
            st.push(p->val);
            p=p->next;
        }
        while(head){
            if(head->val!=st.top()) return false;
            head=head->next;
            st.pop();
        }
        return true;
    }
};

283、移动零

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len = nums.size();
        int j=0;
        for(int i=0;i<len;i++){
            if(nums[i]!=0){
                nums[j]=nums[i];
                j++;
            }
        }
        for(;j<len;j++){
            nums[j]=0;
        }    
    }
};

338、比特位计数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> res(n+1);
        for(int i =0;i<=n;i++){
            int cnt = 0;
            int j =i;
            while(j){
                if(j&1) cnt++;
                j=j>>1;
            }
            res[i]=cnt;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public int[] CountBits(int n) {
        //x = x&(x-1),清除最低位的1
        int[] bits = new int[n+1];
        for(int i=1;i<=n;i++)
        {
            bits[i] = bits[i&(i-1)]+1;
        }
        return bits;
    }
}

key:x = x & (x-1)

448、找到所有数组中消失的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        set<int> st;
        for(int i =0;i<nums.size();i++){
            st.insert(nums[i]);
        }
        for(int i =1;i<=nums.size();i++){
            if(!st.count(i)){
                res.push_back(i);
            }
        }
        return res;
    }
};

461、汉明距离

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int hammingDistance(int x, int y) {
        int res=0;
        while(x||y){
            res+= (x&1)^(y&1);
            x=x>>1;
            y=y>>1;
        }
        return res;
    }
};

543、二叉树的直径

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int res = 0;
    int dfs(TreeNode* root){
        if(!root) return 0;
        int l = 1+dfs(root->left);
        int r = 1+dfs(root->right);
        res = max(res,l+r-2);
        return max(l,r);
    }
    int diameterOfBinaryTree(TreeNode* root) {        
        dfs(root);
        return res;
    }
};

617、合并二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr){return root2;}
        if(root2==nullptr){return root1;}
        root2->val=root2->val+root1->val;
        root2->left=mergeTrees(root1->left,root2->left);
        root2->right=mergeTrees(root1->right,root2->right);
        return root2;
    }
};

中等模块

2、两数相加

3、无重复字符串的最长子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        if(n==0) return 0;
        int left=0;
        int len = 0;
        int res = 0;
        unordered_map<char,int> st;
        for(int i =0;i<n;i++){
            if(!st.count(s[i])){
                len++;
                st[s[i]]=i;
            }else{
                left=st[s[i]]>=left?st[s[i]]+1:left;  //注意
                len = i-left+1;
                st[s[i]]=i;
            }
            res=max(res,len);
        }
        return res;
    }
};

5、最长回文子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        int maxLen = 0;
        int maxLeft = 0;
        int len = 1;
        for(int i =0;i<n;i++){
            int l = i-1;
            int r = i+1;
            while(l>=0&&s[l]==s[i]){
                len++;
                l--;                
            }
            while(r<n&&s[r]==s[i]){
                len++;
                r++;                
            }
            while(l>=0&&r<n&&s[l]==s[r]){
                len=len+2;
                l--;
                r++;                
            }
            if(len>maxLen){
                maxLen=len;
                maxLeft=l;
            }
            len = 1;
        }
        return s.substr(maxLeft+1,maxLen);
    }
};

11、盛最多水的容器

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxArea(vector<int>& height) {
        int r = height.size()-1;
        int res = 0;
        int l = 0;
        int sum =0;
        while(l<r){
            int shorter = min(height[l],height[r]);
            int len = r-l;
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
            sum=shorter*len;
            res=max(res,sum);
        }
        return res;
    }
};

15、三数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        if(nums.size()<3) return ans;
        sort(nums.begin(), nums.end());
        if(nums[0]>0) return ans;
        int i = 0;
        while(i<nums.size()){
            if(nums[i]>0) break;        // 1楼网友指正,将这个if语句放这里提前终止循环
            int left = i+1, right = nums.size()-1;
            while(left< right){
                if(nums[i] + nums[left] +nums[right]>0)
                    right--;
                else if(nums[i] + nums[left] +nums[right]<0)
                    left++;
                else{
                    ans.push_back({nums[i], nums[left], nums[right]});
                    // 相同的left和right不应该再次出现,因此跳过
                    while(left<right&&nums[left]==nums[left+1])
                        left++;
                    while(left<right&&nums[right] == nums[right-1])
                        right--;
                    left++;
                    right--;
                }
            }
            // 避免nums[i]作为第一个数重复出现
            while(i+1<nums.size()&&nums[i] == nums[i+1])
                i++;
            i++;
        }
        return ans;
    }
};

16、最接近的三数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int res = 1e7;
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int i =0;
        while(i<n){
            int l = i+1;
            int r = n-1;
            while(l<r){
                int sum=nums[i]+nums[l]+nums[r];
                if(sum<target){
                    l++;
                    if(abs(res-target)>abs(sum-target)){
                        res=sum;
                    }
                }else if(sum>target){
                    r--;
                    if(abs(res-target)>abs(sum-target)){
                        res=sum;
                    }
                } 
                else{
                    return target;
                }              
            }
            i++;
        }
        return res;
    }
};

17、电话号码的字母组合

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
 //1. 用map记录每个数字按键对应的所有字母
    unordered_map<char, string> m = {
        {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
        {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };
    //2. 存储最终结果和临时结果的变量
    vector<string> ans;
    string current;
    string cp;
    int n;
    void dfs(int len,char c){
        if(current.length()==n){
            ans.push_back(current);            
            return;
        }
        for(int i =0;i<m[c].length();i++){
            current+=m[c][i];
            dfs(len+1,cp[len+1]);
            current.pop_back(); 
        }    
    }
    vector<string> letterCombinations(string digits) {
        cp = digits;
        n = digits.length();
        if(n==0) return ans;
        dfs(0,digits[0]);
        return ans;
    }
};

19、删除链表的倒数第N个结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* start = head;
        ListNode* end = head;
        while(n--){
            end = end -> next;
        }
        if(end == nullptr) return head->next;
        while(end -> next != nullptr){
            end = end -> next;
            start = start -> next;
        }
        start -> next = start -> next -> next;
        return head;
    }
};

22、括号生成

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    vector<string> res;
    string cur="";
    void dfs(int l,int r){
        if(l==0&&r==0){
            res.push_back(cur);
            return;
        }
        if(l>0){
            cur+='(';
            dfs(l-1,r);
            cur.pop_back();
        }
        if(r>l){
            cur+=')';
            dfs(l,r-1);
            cur.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        dfs(n,n);
        return res;
    }
};


class Solution {
public:
    int m;    
    vector<string> res;
    string cur="";
    void dfs(int l,int r){
        if(l==r&&l+r==2*m){
            res.push_back(cur);
            return;
        }
        if(l<=m){
            cur+='(';
            dfs(l+1,r);
            cur.pop_back();
        }
        if(l>r){
            cur+=')';
            dfs(l,r+1);
            cur.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        m = n;
        dfs(0,0);
        return res;
    }
};

31、下一个排列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(),nums.end());
    }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int i,j;
        bool flag=false;
        for(int k=n-1;k>=1;k--){
            if(nums[k]>nums[k-1]){
                i = k-1;
                j = k;
                flag=true;
                break;
            }
        }
        if(flag){
            for(int k = n-1;k>=i;k--){
                if(nums[k]>nums[i]){
                    swap(nums[k],nums[i]);
                    sort(nums.begin()+j,nums.end());
                    break;
                }
            }
        }
        else sort(nums.begin(),nums.end());
    }
};

33. 搜索旋转排序数组

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0,r=nums.size()-1;
        if(target==nums[l]) return l;
        if(target==nums[r]) return r;
        if(target<nums[l]&&target>nums[r]) return -1;
        if(target>nums[l]){
            while(l<r){
                int mid = (l+r) >> 1;
                if(target==nums[mid]) return mid;
                else if(target<nums[mid]||nums[mid]<nums[0]) r=mid;
                else l=mid+1;
            }
            return -1;
        }
        l = 0;
        r=nums.size()-1;
        if(target<nums[r]){
            while(l<r){
                int mid = (l+r) >> 1;               
                if(target==nums[mid]) return mid;
                else if(nums[mid]>nums[nums.size()-1]||nums[mid]<target) l=mid+1;
                else r=mid;
            }
            return -1;
        }
        return -1;
    }
};