旋转链表

问题描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list

思路

• 首先将链表存到vector vec中。
• 对特殊情况进行判断，链表为空，vec.size()==0) return nullptr，向右移动0步，直接return head
• 按照题目要求，将移动后的元素存到一个新的vector tmp中
• 根据tmp建立一个新的链表，并返回其头节点

题解

class Solution {
public:
    ListNode *rotateRight(ListNode *head, int k) {
        vector<int> vec;
        ListNode *cur = head;
        while (cur != nullptr) {
            vec.push_back(cur->val);
            cur = cur->next;
        }
        if(vec.size()==0)  return nullptr;
        if(k==0) return head;
        k = k % (vec.size());
        vector<int> tmp;
        for (int i = vec.size()-k; i < vec.size(); i++) {
            tmp.push_back(vec[i]);
        }
        for (int i = 0; i <vec.size()-k; i++) {
            tmp.push_back(vec[i]);
        }
        ListNode *p = nullptr;
        ListNode *newnode;
        for (int i = 0; i < tmp.size(); i++) {
            if (p == nullptr) {
                p=new ListNode(tmp[i]);
                newnode=p;
            } else{
                p->next= new ListNode(tmp[i]);
                p=p->next;
            }
        }
        return newnode;
    }
};

LRU缓存机制

问题描述

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:
LRUCache cache = new LRUCache( 2 / 缓存容量 / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache

思路

题解

下一个排列

问题描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation

思路

使用库函数

题解

class Solution {
public:
    void nextPermutation(vector<int> &nums) {
        if (next_permutation(nums.begin(), nums.end())) {
        }
    }
};

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

问题描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:
输入: 1->1->1->2->3
输出: 2->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

题解

    public static ListNode deleteDuplicates(ListNode head) {
        //baseCase
        if (head == null || head.next == null) {
            return head;
        }

        ListNode next = head.next;
        //如果是这种情况
        //      1 --> 1 --> 1 --> 2 --> 3
        //     head  next
        //1.则需要移动next直到出现与当前head.value不相等的情况（含null）
        //2.并且此时的head已经不能要了，因为已经head是重复的节点
        //--------------else-------------
        //      1 --> 2 --> 3
        //     head  next
        //3.如果没有出现1的情况，则递归返回的节点就作为head的子节点
        if (head.value == next.value) {
            //1
            while (next != null && head.value == next.value) {
                next = next.next;
            }
            //2
            head = deleteDuplicates(next);
        } else {
            //3
            head.next = deleteDuplicates(next);
        }
        return head;
    }

来源：力扣
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/comments/
作者：落寒

合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals

思路

• 首先对特殊情况进行判断，int n=intervals.size(),如果n==0或者n==1那么无需合并，直接返回就可以了
• 然后对intervals进行排序，排序规则为 按照开始位置从小到大进行排序，如果两个元素的开始位置相等，那么结束位置从大到小排序。
• 准备工作做完后，开始正式合并区间。 ret.push_back({intervals[0][0],intervals[0][1]})先在返回结果ret中插入第一个元素，否则第二个无法比较。
• 如果intervals中待合并元素的开始位置intervals[i][0]<ret.back()[1]那么判断，它结束的位置大于等于ret.back()[1]，那么将ret.back()[i]更新为intervals[i][1],否则不做操作。
• 如果intervals中待合并元素的开始位置intervals[i][0]>=ret.back()[1],那么直接将其插入到ret中即可
• 最后，返回ret。

题解

class Solution {
public:
    vector<vector<int>> ret;
    static bool cmp(const vector<int> &a,const vector<int> &b){
        if(a[0]==b[0]){
            return a[1]>b[1];
        } else return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n=intervals.size();
        if(n==0||n==1) return intervals;
        sort(intervals.begin(),intervals.end(),cmp);
        ret.push_back({intervals[0][0],intervals[0][1]});
        for(int i=0;i<n;i++){
            if(ret.back()[1]>=intervals[i][0]){
                if(ret.back()[1]<=intervals[i][1]){
                    ret.back()[1]=intervals[i][1];
                }
            } else{
                ret.push_back({intervals[i][0],intervals[i][1]});
            }
        }
        return ret;
    }
};