当前位置:   article > 正文

LeetCode-剑指Offer_剑指offer leetcode

剑指offer leetcode


包含main函数的栈

一、题目描述
LeetCode-剑指 offer30.包含main函数的栈

二、分析与代码
分析

第一个想到的思路:
1、申请两个栈S1、S2,将输入数据push到S1中。
2、当要输出S1中最小数据时,将数据从S1中pop出,并依次push到S2中,同时记录最小值。
3、之后再将数据从S2中pop出push到S1中。
以上操作后在S1中的数据顺序并未改变,并且可以正常实现功能,但是时间复杂度过高,会导致超时,具体代码如代码1

改进思路:
1、申请两个栈S1、S2,将输入数据push到S1中,并在push数据的同时在S2中记录到此数据为止S1中数据的最小值,并将最小值同步push到S2中。
2、每次pop数据时,S1、S2同时要pop。
3、输出S1中的最小值只需要输出S2的栈顶元素即可。
具体代码如代码2

具体代码

代码1:

class MinStack {
public:
    stack <int> Stack;
    stack <int> Stack2;

    MinStack() {
        while(!Stack.empty())
            Stack.pop();
        while(!Stack2.empty())
            Stack2.pop();
    }
    
    void push(int x) {
        Stack.push(x);
    }
    
    void pop() {
        Stack.pop();
    }
    
    int top() {
        return Stack.top();
    }
    
    int min() {
        int ans=Stack.top();
        while(!Stack.empty())
        {
            Stack2.push(Stack.top());
            if(ans>Stack.top())
                ans=Stack.top();
            Stack.pop();
        }
        while(!Stack2.empty())
        {
            Stack.push(Stack2.top());
            Stack2.pop();
        }
        return ans;
    }
};
  • 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

代码2:

class MinStack {
public:
    stack <int> Stack;
    stack <int> Stack2;
   
    MinStack() {
        while(!Stack.empty())
            Stack.pop();
        while(!Stack2.empty())
            Stack2.pop();
        Stack2.push(INT_MAX);
    }
    
    void push(int x) {
        Stack.push(x);
        if(x<Stack2.top())
            Stack2.push(x);
        else
            Stack2.push(Stack2.top());
    }
    
    void pop() {
        Stack.pop();
        Stack2.pop();
    }
    
    int top() {
        return Stack.top();
    }
    
    int min() {
        return Stack2.top();
    }
};
  • 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

复杂链表的复制

一、题目描述
LeetCode-剑指 offer35.复杂链表的复制

二、分析与代码
分析

第一种思路:
1、将初始链表的每一个结点拆分为两个结点,例如将A->B->C复制为A->A’->B->B’->C->C’。主要为:将A的内容复制到A’,A的next指针指向A’,A’的next指针指向B,random指针不设置。
2、设置random指针的指向,例如:A的random指针指向D,我们就要将A’指针指向D’,方法为:将A’的random指针指向A的random指针指向的D的next指针指向的D’。
3、将复制的A->A’->B->B’->C->C’拆分为A->B->C与A’->B’->C’,将A’->B’->C’的头指针返回。
具体代码如代码1

第二种思路:
由复制可想到用map <typename1,typename2> name来复制链表,例如:初始链表为A->B->C,复制链表为A’->B’->C’,A与A’对应……,则用name[A]=A’来设置A与A’的对应关系。具体代码如代码2

具体代码

代码1:

class Solution {
public:
    Node* copyRandomList(Node* head) {
        //为空返回
        if(head==NULL)
            return NULL;
        //将A->B->C复制为A->A'->B->B'->C->C'
        for(Node *q=head;q!=NULL;q=q->next->next)
        {
            Node *p=new Node(q->val);
            p->next=q->next;
            q->next=p;
        }
        //将复制后的A->A'->B->B'->C->C'其中A、B、C的random指针复制到A'、B'、C'上
        for(Node *q=head;q!=NULL;q=q->next->next)
            if(q->random!=NULL)
                q->next->random=q->random->next;
        Node *newhead=head->next;
        //将A->A'->B->B'->C->C'拆分为A->B->C与A'->B'->C',A->B->C为原链表,A'->B'->C'为复制链表
        for(Node *p=head;p!=NULL;p=p->next)
        {
            Node *mid=p->next;
            p->next=p->next->next;
            if(mid->next!=NULL)
                mid->next=mid->next->next;
        }
        return newhead;
    }
};
  • 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

代码2:

class Solution {
public:
    map<Node*, Node*> cachedNode;
    Node* copyRandomList(Node* head) {
        //为空返回
        if(head==NULL)
            return NULL;
        //不包含则创建
        if (!cachedNode.count(head)){
            Node* headNew = new Node(head->val);
            cachedNode[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }
        return cachedNode[head];
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

对称的二叉树

一、题目描述
LeetCode-剑指 offer28.对称的二叉树

二、分析与代码
分析
判断一棵树是否为对称的二叉树,只需要判断该树根结点的左子树与右子树是否关于根结点对称,具体步骤如下:
1、特殊情况:若该树为空,则返回true;
2、对该树根结点的左右子树进行递归判断,共有以下情况:(1)若左子树与右子树都不存在,则左子树与右子树对称,返回true;(2)若左、右子树只有一个存在,则左、右子树不对称,返回false;(3)若左右子树都存在,则返回q->val==p->val(左右子树根结点值比较)&&check(p->left,q->right)(左子树的左结点与右子树的右结点比较)&&check(p->right,q->left)(右子树的左结点与左子树的右结点比较)。
具体代码如下:

具体代码

代码:

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

两个链表的第一个公共结点

一、题目描述
LeetCode-剑指 offer52.两个链表的第一个公共结点

二、分析与代码
分析
设链表link1的结点数为l1+c,link2的结点数为l2+c,c则为两链表公共部分的长度。则可有以下思路:
1、设p指向link1的表头,q指向link2的表头;
2、p与q同时向后移动,当p遍历完link1时使其指向link2的表头,当q遍历完link2时使其指向link1的表头,并使p,q继续同时向后移动;
3、当p、q指向同一结点时,该结点就是两链表的第一个公共点(因为此时p遍历了l1+c+l2个结点,q遍历了l2+c+l1个结点,遍历的结点数相同,二者指向的都是公共部分c的第一个结点)。
具体代码如下:

具体代码

代码1:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *node1 = headA;
        ListNode *node2 = headB;
        
        while (node1 != node2) 
        {
            if(node1!=NULL)
                node1=node1->next;
            else
                node1=headB;
            if(node2!=NULL)
                node2=node2->next;
            else    
                node2=headA;
        }
        return node1;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

代码2:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==NULL||headB==NULL)    
            return NULL;
        ListNode *p=headA,*q=headB;
        while(p!=NULL&&q!=NULL&&p!=q)
        {
            p=p->next;
            q=q->next;
        }
        if(p==q)
            return p;
        if(p==NULL)
        {
            p=headB;
            while(q!=NULL)
            {
                p=p->next;
                q=q->next;
            }
            q=headA;
            while(p!=NULL&&q!=NULL&&p!=q)
            {
                p=p->next;
                q=q->next;
            }
            if(p==q)
                return p;
            return NULL;
        }
        if(q==NULL)
        {
            q=headA;
            while(p!=NULL)
            {
                p=p->next;
                q=q->next;
            }
            p=headB;
            while(p!=NULL&&q!=NULL&&p!=q)
            {
                p=p->next;
                q=q->next;
            }
            if(p==q)
                return p;
            return NULL;
        }
        return NULL;
    }
};
  • 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

把数组排成最小的数

一、题目描述
LeetCode-剑指 offer45.把数组排成最小的数

二、分析与代码
分析
要将nums利用类似冒泡排序排列(将两数字x,y拼接字符串x+y与y+x,比较它们的大小),之后将nums数组按序拼接起来即可。

具体代码

代码:

class Solution {
public:
    int num(int x){
        if(x==0)
            return 1;

        int ans=0;
        while(x)
        {
            ans++;
            x=x/10;
        }
        return ans;
    }

    bool compare(int x,int y){
        if(x*pow(10,num(y))+y>x+y*pow(10,num(x)))
            return true;
        return false;
    }

    string minNumber(vector<int>& nums) {
        for(int i=0;i<nums.size()-1;i++)
            for(int j=0;j<nums.size()-i-1;j++)
                if(compare(nums[j],nums[j+1]))
                {
                    int x=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=x;
                }
        
        string ans;
        vector<int> a;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]==0)
                ans.push_back('0');
            else
            {
                a.clear();
                int x=nums[i];
                while(x)
                {
                    a.push_back(x%10);
                    x/=10;
                }
                reverse(a.begin(),a.end());
                for(int j=0;j<a.size();j++)
                    ans.push_back('0'+a[j]);
            }
        }
        return ans;
    }
};
  • 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

数据流中的中位数

一、题目描述
LeetCode-剑指 offer41.数据流中的中位数
LeetCode-295.数据流中的中位数
二、分析与代码
分析
剑指 offer41:
该题对时间复杂度要求较低,故可用以下方法:
1、定义一个vector<int> a,用来存放所有的数字;
2、在加入数字时,利用二分法找到数字该插入的位置,将数字插入;
3、按对应的中位数的定义输出中位数。
具体代码如代码1。

对于LeetCode-295,以上方法时间复杂度较高,会引起超时。故需转用以下方法:
1、定义两个优先队列que_Min、que_Max。其中que_Min用来存储较小的一半数字,使用默认比较方式,top()方法返回最大值;que_Max用来存储较大的一半数字,使用greater<>比较方式,top()返回最小值;
2、在加入数字数,当que_Min.empty()||num<=que_Min.top()时,num一定是插入que_Min中,插入后,若que_Min.size()-1>que_Max.size(),则将que_Min中的最大值移入que_Max中;当!que_Min.empty()&&num>que_Min.top()时,num一定插入que_Max中,插入后,若que_Max.size()>que_Min.size(),则将que_Max中的最小值移入que_Min中;
3、若que_Min.size()==que_Max.size(),则取出que_Min.top()与que_Max.top()求和除以2;否则输出que_Min.top()即可。

具体代码

代码1:

class MedianFinder {
public:
    vector<int> a;
    MedianFinder() {
        a.clear();
    }

    void addNum(int num) {
        //特例
        if(a.size()==0||a[a.size()-1]<=num)
        {
            a.push_back(num);
            return;
        }
        if(a[0]>=num)
        {
            a.insert(a.begin(),num);
            return;
        }

        //二分法找到插入位置
        int x;
        int left=0,right=a.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(a[mid]>=num&&a[mid-1]<=num)
            {
                x=mid;
                break;
            }
            if(a[mid]<num)
                left=mid+1;
            else
                right=mid-1;
        }
        a.insert(a.begin()+x,num);
    }
    
    double findMedian() {
        double ans;
        int n=a.size();
        if(a.size()%2==0)
            ans=(double)(a[n/2]+a[n/2-1])/2.0;
        else
            ans=(double)a[n/2];
        return ans;
    }
};
  • 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

代码2:

class MedianFinder {
public:
    priority_queue<int,vector<int>,greater<>> que_Max;  //greater<>方法使优先队列队头返回最小值
    priority_queue<int,vector<int>> que_Min;

    MedianFinder() {
        //初始化,将队列处理空
        while(!que_Max.empty())
            que_Max.pop();
        while(!que_Min.empty())
            que_Min.pop();
    }
    
    void addNum(int num) {
        if(que_Min.empty()||num<=que_Min.top())
        {
            que_Min.push(num);
            if(que_Min.size()-1>que_Max.size())
            {
                que_Max.push(que_Min.top());
                que_Min.pop();
            }
        }
        else
        {
            que_Max.push(num);
            if(que_Max.size()>que_Min.size())
            {
                que_Min.push(que_Max.top());
                que_Max.pop();
            }
        }
    }
    
    double findMedian() {
        if(que_Max.size()==que_Min.size())
            return (que_Min.top()+que_Max.top())/2.0;
        return que_Min.top()/1.0;
    }
};
  • 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

求1+2+…+n

一、题目描述
LeetCode-剑指 offer64. 求1+2+…+n

二、分析与代码
分析
若无题目中的限制要求,我们可用递归实现1+2+……+n,代码如下:

class Solution {
public:
    int sumNums(int n) {
        if(n==0)
            return 0;
        return n+sumNums(n-1);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

但是题目中要求不允许使用if,则我们需要考虑如何代替掉if,自然可想到&&,具体如下:
1、使用n&&A,当n=0时,不会执行A,则可模拟if的效果(如果n!=0,则执行A,否则不执行A)。
2、当n=0时返回0,即返回n也可;n!=0时返回n+sumNums(n-1),则将n+sumNums(n-1)赋值给n,也是返回n,故A可写为n+=sumNums(n-1)。
3、返回n即可。
具体代码如下:

具体代码

代码:

class Solution {
public:
    int sumNums(int n) {
        n&&(n+=sumNums(n-1));
        return n;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

二叉树的最近公共祖先

一、题目描述
LeetCode-剑指 offer68.二叉树的最近公共祖先

二、分析与代码
分析
二叉树两个结点的最近公共祖先满足以下条件之一:(1)左子树与右子树分别包含一个结点;(2)左子树或右子树包含一个结点,且本身就是一个结点;(3)两结点相同且本身就是这两个结点。
故可采用以下思路:
1、定义一指针ans用以指向答案;
2、定义bool型函数dfs,当以root为根的树包含p或q结点时,返回true,否则返回false;
3、在dfs中用ll与rr记录root的左右子树是否包含p或q结点;当root为空时dfs返回false,当ll为true或rr为true或root本身就是结点之一时,返回true;
4、若ll&&rr或root==p&&root==q或(ll||rr)&&(root==p||root==q),则说明root为所求结点,用ans记录;(注意:满足这些条件之一的结点只有一个,故ans不会重复赋值)。
具体代码如下:

具体代码

代码:

class Solution {
public:
    TreeNode *ans;
    //检查root为根的树是否最少包括p、q之一
    bool dfs(TreeNode *root,TreeNode *p,TreeNode *q){
        if(root==NULL)
            return false;
        bool ll=dfs(root->left,p,q);
        bool rr=dfs(root->right,p,q);
        if((ll&&rr)||(root==p&&root==q)||((ll||rr)&&(root==p||root==q)))
            ans=root;
        return ll||rr||(root==p||root==q);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,q);
        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

不用加减乘除做加法

一、题目描述
LeetCode-剑指 offer65.不用加减乘除做加法

二、分析与代码
分析
该题不允许用加减乘除做加法,故自然想到运用位运算:
1、将a与b做与运算,运算结果左移一位,再保存到c中,c就是a与b求和的进位;
2、将a与b做异或运算,并将结果保存在a中,a就是a与b求和未考虑进位的结果;
3、此时只需要将a与c相加即可,但是该题不允许用加法,故只能将c赋值给b重复以上步骤,直到进位为0返回a即可。
具体代码如下:

具体代码

代码:

class Solution {
public:
    int add(int a, int b) {
        while(b!=0)
        {
            int c=(unsigned)(a&b)<<1;//进位无负数情况
            a^=b;
            b=c;
        }
        return a;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

二叉搜索树的后序遍历序列

一、题目描述
LeetCode-剑指 offer33.二叉搜索树的后序遍历序列

二、分析与代码
分析
后序遍历的最后一个元素是根结点,二叉搜索树的左子树小于根结点小于右子树,故可有以下思路:
1、最后一个元素为根结点,从左往右遍历,找出左子树结点(即值比根结点小的);
2、验证右子树是否元素值都大于根结点,若存在小于根结点的元素值,则返回false;
3、递归验证左右子树是否都为二叉搜索树,若是,则返回true(即返回左右子树结果的&&)。
具体代码如下:

具体代码

代码:

class Solution {
public:
    bool check(vector<int>postorder,int left,int right){
    	//只有一个结点,一定为二叉搜索树
        if(left>=right)
            return true;
        int mid;
        for(mid=left;postorder[mid]<postorder[right]&&mid<right;mid++);
        for(int i=mid;i<right;i++)
            if(postorder[i]<postorder[right])
                return false;
        return check(postorder,left,mid-1)&&check(postorder,mid,right-1);
    }

    bool verifyPostorder(vector<int>& postorder) {
        return check(postorder,0,postorder.size()-1);
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

构建乘积数组

一、题目描述
LeetCode-剑指 offer66.构建乘积数组

二、分析与代码
分析
思路1:
将数组所有的数做乘法运算,结果记为n,之后遍历数组,当遍历到第i个时,记录n/a[i]的值即可。但是本题不允许用除法。

思路2:
直接遍历数组,当遍历到第i个时,将i前所有数与i后所有数做乘法运算,记录结果即可,但是时间复杂度大,会造成超时。

思路3:
将思路2进行改进:
1、定义vector<int> left, right,将数组的前i个数与后i个数的乘积分别记录到left与right中。
2、遍历数组,当遍历到第i个时只需要用left与right中的对应数相乘即可。
具体代码如下:

具体代码

代码:

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> ans,left,right;
        if(a.size()==0)
            return ans;
        int l=1,r=1;
        for(int i=0;i<a.size();i++)
        {
            l*=a[i];
            left.push_back(l);
            r*=a[a.size()-1-i];
            right.push_back(r);
        }
        ans.push_back(right[a.size()-2]);
        for(int i=1;i<a.size()-1;i++)
            ans.push_back(left[i-1]*right[a.size()-i-2]);
        ans.push_back(left[a.size()-2]);
        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

圆圈中最后剩下的数字

一、题目描述
LeetCode-剑指 offer62.圆圈中最后剩下的数字

二、分析与代码
分析
本题是著名的“约瑟夫环”问题,可使用动态规划解决。
首先说明lastRemaining(n,m)函数的返回值为0到n-1共n个数组成的首尾相连的数字环进行操作——删除第m个数,从删除的数的下一个数开始计数,再删除第m个数,直到剩下最后一个数的值。
思路如下:
1、设lastRemaining(n-1,m)=x,即从0到n-2共n-1个数进行以上操作后剩下的值为x,则说明lastRemaining(n-1,m)剩下的是第x+1个数。
2、lastRemaining(n,m)首先删除的是第m%n个数,之后从第m%n个数的下一个数开始计数,计数到第m个为需要删除的数字。该过程可等同于:当删除了第m%n个数字后,数的量为n-1(刚开始有n个减去了1个),之后将第m%n个数后的数字放到数列前方,就可以从第一个开始重新计数,这也就转换成了lastRemaining(n-1,m)的情况(注意:lastRemaining(n-1,m)中的数对应的是0到n-2共n-1个数,但是由lastRemaining(n,m)删除一个数字后对应的lastRemaining(n-1,m)中的数却不是0到n-2);
3、已知lastRemaining(n-1,m)=x,即lastRemaining(n-1,m)剩下的是第x+1个数。则lastRemaining(n,m)返回的数就是由lastRemaining(n,m)删除一个数字后对应的lastRemaining(n-1,m)中的第x+1个数,即在lastRemaining(n,m)中的(m%n+x+1)%n个数,值为(m%n+x)%n=(m+x)%n,则可得lastRemaining(n,m)=(m+lastRemaining(n-1,m))%n。
具体代码如下:
约瑟夫环状态模拟过程

具体代码

代码:

class Solution {
public:
    int lastRemaining(int n, int m) {
        if(n==1)
            return 0;
        int x=lastRemaining(n-1,m);
        return (x+m)%n;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

滑动窗口的最大值

一、题目描述
LeetCode-剑指 offer59.I.滑动窗口的最大值

二、分析与代码
分析
思路1:
可用暴力法将每个窗口的k个元素遍历,记录其中最大值,共n-k+1个窗口。该方法的时间复杂度过大,会超时。

思路2:
对于思路1的暴力法,我们可以发现每两个相邻的窗口之间有k-1个数字是相同的,只是删除了前一窗口中的第一个值,加入了后一窗口的最后一个值,故后一窗口的最大值可借助上一窗口的比较情况得出(对前一窗口加入后一窗口的最后一个值,之后找到最大值,保证最大值的下标是在后一窗口内即可,故需使用pair方便存储值及对应下标),可以使用优先队列比较和存储值的大小情况。具体如下:
1、申请一个priority_queue,队列元素为pair<int,int>,名称为a,存储值的大小及下标;申请vector ans,存储满足条件值;
2、将前k个数的信息存储进优先队列中,并保存a.top()的值到ans中(优先队列默认比较方式的top输出最大值);
3、从下标为k的元素开始依次加入到a中,每加入一个数,都判断a.top()的下标是否在窗口内,若不在,则删除,若在,则保存到ans中。
具体代码如下:

具体代码

代码:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        //特殊情况
        if(nums.size()<k||k==0)
            return ans;
            
        priority_queue<pair<int,int>> a;
        for(int i=0;i<k;i++)
            a.push({nums[i],i});
        ans.push_back(a.top().first);
        for(int i=k;i<nums.size();i++)
        {
            a.push({nums[i],i});
            while(a.top().second<=i-k)
                a.pop();
            ans.push_back(a.top().first);
        }
        return ans;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

数组中的逆序对

一、题目描述
LeetCode-剑指 offer51.数组中的逆序对

二、分析与代码
分析
见到逆序对就要想到归并排序!!!
见到逆序对就要想到归并排序!!!
见到逆序对就要想到归并排序!!!

可通过对原数组进行归并排序来计算原数组的逆序对。
具体代码如下:

具体代码

代码:

class Solution {
public:
    int ans=0;
    //nums修改后需要进行更新,别忘了加&
    void mergesort(vector<int>& nums,int left,int right){
        if(left>=right)
            return;
        int mid=(left+right)/2;
        mergesort(nums,left,mid);
        mergesort(nums,mid+1,right);
        int b[right-left+1],a=0,i=left,j=mid+1;   
        while(i<=mid&&j<=right)
            if(nums[i]>nums[j])
            {
                b[a++]=nums[j++];
                //只需在将后半部分的数放在前面时计算该数后有几个前半部分数
                ans+=mid-i+1;
            }
            else
                b[a++]=nums[i++];
        while(i<=mid)
            b[a++]=nums[i++];
        while(j<=right)
            b[a++]=nums[j++];
        for(int i=0;i<right-left+1;i++)
            nums[left+i]=b[i];
    }

    int reversePairs(vector<int>& nums) {
        mergesort(nums,0,nums.size()-1);
        return ans;
    }
};
  • 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

一、题目描述
LeetCode-剑指 offer

二、分析与代码
分析

具体代码

代码:


  • 1

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小桥流水78/article/detail/1005075
推荐阅读
相关标签
  

闽ICP备14008679号