88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。

注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=nums1.size()-1;
        m--;
        n--;
        while(n>=0)
        {
            while(m>=0&&nums1[m]>nums2[n])
            {
                swap(nums1[m--],nums1[i--]);
            }
            swap(nums1[i--],nums2[n--]);
        }
    }
};

25. K 个一组翻转链表

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy=new ListNode(-1);
        dummy->next=head;
        ListNode* pre=dummy;
        ListNode *start=head,*end=dummy;
        ListNode* next=end->next;
        while(end->next!=nullptr)
        {
            for(int i=0;i<k;i++)
            {
                end=end->next;
                next=next->next;
                if(next==nullptr&&i!=k-1) return dummy->next;//剩余节点不足k个时直接返回
            }
            end->next=nullptr;	//断开连接
            pre->next=re(start);	//反转链表
            start->next=next;	//重新连接链表
            pre=start;			//	翻转后start位于end位置
            end=start;			//    移动指针归位:end和pre位于dummy节点,start位于pre->next
            next=start->next;	//				 next位于end->next
            start=start->next;  //    
        }
        return dummy->next;

    }

    ListNode* re(ListNode* head)
    {
        ListNode*pre=nullptr;
        while(head!=nullptr)
        {
            ListNode* t=head->next;
            head->next=pre;
            pre=head;
            head=t;
        }
        return pre;
    }
};
  • 需要四个指针,pre指向需要翻转的头结点的前一个节点,start指向需要翻转的头结点,end指向需要翻转的尾结点,next指向需要下一个翻转的头节点

  • 翻转时先吧end==null 断开连接,反转后原start现在是end位置,然后连接链表,则start->next=next

  • 然后移动指针进行下一次翻转

  • 需要特殊判断剩余节点不足k个时,直接返回

415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库(比如 BigInteger), 也不能直接将输入的字符串转换为整数形式。

class Solution {
public:
    string addStrings(string num1, string num2) {
        string s;
        int i=num1.size()-1,j=num2.size()-1;
        bool add=false;
        char a,b;
        while(i>=0||j>=0)
        {
            if(i>=0) a=num1[i];
            else a='0';
            if(j>=0) b=num2[j];
            else b='0';
            int sum=a+b-'0'-'0';
            if(add) sum++;
            add=false;
            if(sum>=10)
            {
                sum-=10;
                add=true;
            }
            char c=sum+'0';
            s.insert(s.begin(), c);
            i--,j--;
        }
        if(add) s.insert(s.begin(), '1');
        return s;
    }
};

199. 二叉树的右视图

给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> q;
        vector<int> vec;
        if(root==nullptr) return vec;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();
            while(size--)
            {
                root=q.front();
                q.pop();
                if(size==0) vec.push_back(root->val);
                if(root->left!=nullptr) q.push(root->left);
                if(root->right!=nullptr) q.push(root->right);
            }
        }
        return vec;
    }
};
  • 层序遍历变种问题

56. 合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> vec;
        int index=0;
        vec.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++)
        {
            if(intervals[i][0]<=vec[index][1]&&intervals[i][1]>vec[index][1])   //有交集但非子集 [1,3][2,4]
            {
                vec[index][1]=intervals[i][1];
            }
            else if(intervals[i][0]>vec[index][1])  //无交集 [1,3][5,7]
            {
                vec.push_back(intervals[i]);
                index++;
            }
        }
        return vec;
    }
};

82. 删除排序链表中的重复元素 II

定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        if(head->val!=head->next->val)
        {
            head->next=deleteDuplicates(head->next);
        }
        else
        {
            ListNode* t=head->next;
            while(t!=nullptr&&t->val==head->val)
            {
                t=t->next;
            }
            return deleteDuplicates(t);
        }
        return head;
    }
};
  • 递归版本

143. 重排链表

class Solution {
public:
    void reorderList(ListNode* head) {
        vector<ListNode*> vec;
        ListNode* dummy=head;
        while(dummy!=nullptr)
        {
            vec.push_back(dummy);
            dummy=dummy->next;
        }
        int l=0,r=vec.size()-1;
        while(l<r)
        {
            vec[l]->next=vec[r];
            l++;
            if(l==r) break;
            vec[r]->next=vec[l];
            r--;
        }
        vec[l]->next=nullptr;
    }
};
  • 空间复杂度O(n)
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head==nullptr) return;
        //找中点
        ListNode* slow=head,*fast=head->next;
        while(fast!=nullptr&&fast->next!=nullptr)
        {
            slow=slow->next;
            fast=fast->next->next;
        }


        //slow->next 为中点
        //断开连接
        ListNode*t =slow->next;
        slow->next=nullptr;

        //反转链表
        ListNode* mid=t;
        ListNode*pre=nullptr;
        while(mid!=nullptr)
        {
            ListNode* t=mid->next;
            mid->next=pre;
            pre=mid;
            mid=t;
        }


        //合并链表
        ListNode* pren;
        ListNode* headn;
        while(head!=nullptr&&pre!=nullptr)
        {
            headn=head->next;
            pren=pre->next;

            head->next=pre;
            head=headn;

            pre->next=head;
            pre=pren;
        }
    }
};
  • 找中点+翻转+合并

Q.E.D.