[八股速成]5.手撸代码题

前言

感觉面试问的算法题都非常沙雕，在这记录一下

数据结构

链表

链表快速排序

class Solution {
public:
    ListNode* func(ListNode *l,ListNode *r) {
        ListNode *p=l,*q=l->next;
        int key=p->val;
        while(q!=r) {
            if(q->val<key)
            {
                p=p->next;
                swap(p->val,q->val);
            }
            q=q->next;
        }
        swap(p->val,l->val);
        return p;
    }
    void qsort(ListNode *l,ListNode *r) {
        if(l == r || l->next == r)
            return;
        ListNode *p =func(l,r);
        qsort(l,p);
        qsort(p->next,r);
    }
    ListNode* sortList(ListNode* head) {
        qsort(head,nullptr);
        return head;
    }
};

148.链表归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode *p1=head, *p2=head->next;
        while(p2 && p2->next)
        {
            p1 = p1->next;
            p2 = p2->next->next;
        }
        ListNode *st1 = head;
        ListNode *st2 = p1->next;
        p1->next = nullptr;
        p1 = sortList(st1);
        p2 = sortList(st2);
        return Merge(p1,p2);
    }
    ListNode* Merge(ListNode *p1, ListNode *p2)
    {
        if(p1==nullptr)
            return p2;
        else if(p2==nullptr)
            return p1;
        ListNode *ph = nullptr,tmp;
        ph = &tmp;
        while(p1&&p2)
        {
            if(p1->val < p2->val)
            {
                ph->next = p1;
                p1 = p1->next;
            }
            else  
            {
                ph->next = p2;
                p2 = p2->next;
            }
            ph = ph->next;
        }
        if(p1)
            ph->next = p1;
        else
            ph->next = p2;
        return tmp.next;
    }
};

环形链表

class Solution {
public:
    bool hasCycle(ListNode *head) {
        bool ok=0;
        ListNode *p1=head,*p2=head;
        do{
            if(p1==nullptr)
                break;
            p1=p1->next;
            p2=p2->next;
            if(p2==nullptr)
                break;
            p2=p2->next;
            if(p1==p2)
            {
                ok=1;
                break;
            }
        }while(p1&&p2);
        return ok;
    }
};

合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head=nullptr, node;
        head = &node;
        while(l1&&l2)
        {
            if(l1->val <= l2->val)
            {
                (*head).next = l1;
                l1 = l1->next;
            }
            else
            {
                (*head).next = l2;
                l2 = l2->next;
            }
            head = head->next;
        }
        if(l1)
            (*head).next = l1;
        else
            (*head).next = l2;
        return node.next;
    }
};

反转链表 II

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left==right)
            return head;
        ListNode *ph = head,*st = nullptr, *ed = nullptr, *pre, *nex = nullptr,*rec;
        int cnt = right-left;
        for(int i=1;i<left;i++)
        {//ph指的就是反转的节点
            rec = ph;
            ph = ph->next;
        }
        st = ph;//指向反转起点
        pre =ph;
        ph = ph->next;
        while(cnt--)
        {
            nex = ph->next;
            ph -> next = pre;//改成指向上一个
            pre = ph;//pre记录为当前节点
            if(cnt>0)//走到下一个点
                ph = nex;
        }
        st->next = nex;//第一个点指向后面的
        if(left==1)
            head = ph;
        else
        {
            rec->next = ph;
        }
        //rev(ph,right-left+1);
        return head;
    }
};

字符串

43. 字符串相乘

class Solution {
public:
    string multiply(string num1, string num2) {
        int l1=num1.length(),l2=num2.length();
        if(l1==0||l2==0)
            return "";
        string ans(l1+l2,'0');
        for(int i=l1-1;i>=0;i--) {//从低向高依次与num2相乘
            int add=0;//进位
            for(int j=l2-1;j>=0;j--) {
                int mul=(num1[i]-'0')*(num2[j]-'0');
                int sum=ans[i+j+1]-'0'+mul+add;//这一位的总共
                ans[i+j+1]=sum%10+'0';
                add=sum/10;//进位
            }
            ans[i]+=add;
        }
        for(int i=0;i<l1+l2;i++)
            if(ans[i]!='0')
                return ans.substr(i);
        return "0";
    }
};

其他

用 Rand7() 实现 Rand10()

class Solution {
public:
    int rand10() {
        int val;
        do
        {
            val=(rand7()-1)*7+rand7();
        }while(val>10);
        return val;
    }
};

寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n=nums.size()-1;
        int l=0,r=n,ans=0;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(nums[mid]<nums[r])
                r=mid;
            else
                l=mid+1;
        }
        return nums[l];
    }
};

31. 下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int p1=0,p2=0;
        bool ok=0;
        for(p2=nums.size()-1,p1=p2-1;p1>=0;p1--,p2--) {
            if(nums[p1]<nums[p2]) {
                ok=1;
                break;
            }
        }
        if(!ok)
        {
            reverse(nums.begin(),nums.end());
            return;
        }
        int k=p2;
        for(k=nums.size()-1;k>p2;k--) {
            if(nums[p1]<nums[k])
            {
                break;
            }
        }
        swap(nums[p1],nums[k]);
        reverse(nums.begin()+p2,nums.end());
    }
};