leetcode刷题记录---19.9.14 LRU(map,list,迭代器)，排序链表（cut，merge，dummyhead），乘积最大子序列，dfs（bfs），二分查找模板_list+map+模板实现lru

1.LRU缓存机制       微软二面

题目描述：设计和实现(LRU)缓存机制，具有get和put的功能。

get(key),如果key存在，则返回。如果key不存在，返回-1；

put(key,value),如果缓冲区满，替换掉最近最少使用的key。否则直接插入。

参考：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

示例:

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

 

思路：o(1)的时间实现get和put，即o(1)的时间完成，查找，删除，插入，还必须是顺序排列的，因为有尺寸限制。

分析：

数组                  查找快                  删除慢                      插入慢                 数据固定位置

链表                  查找慢                  删除快                      插入快                 数据固定位置

哈希表               查找快                  删除快                      插入快                 数据位置不定

 

所以讲道理，这题哈希数组和哈希链表都可以做。在这里使用哈希链表（双向链表和哈希表的结合）来做。

双向链表list说明：https://www.cnblogs.com/BeyondAnyTime/archive/2012/08/10/2631191.html

其实cache就是缓存，map只是一种方便查找的映射！！！！所以更新的时候一定先更新cache！

为什么使用双向链表？尾节点进行删除，要以o(1)的时间找到他的前驱

1.private中声明合适的数据结构，一个list，一个unordered_map

2.get(key)先查哈希表中，是否存在，不存在-1，存在的话，把他从cache中删除，插入头部，更新哈希表，返回查找值

3.put(key)先查是否存在，如果不存在，在查cache是否满，满的话删除cache，和map中该元组。如果不满直接插入，更新map。

     如果存在，删除cache中元组，但是map中不用删，只用更新map[k]的值。

注意：list是基于stl实现的双向链表，与vector相比较，插入删除比较方便，但是随机访问比较麻烦。

class LRUCache {
public:
    LRUCache(int capacity) {
        this->cap = capacity;
    }
    
    int get(int key) {
        auto it = map.find(key);
        if(it == map.end()) return -1;
        pair<int,int> kv = *map[key];
        cache.erase(map[key]);
        cache.push_front(kv);
        map[key] = cache.begin();
        return kv.second;
    }
    
    void put(int key, int value) {
        auto it = map.find(key);
        //没找到，说明没存过
        if(it == map.end()){
            //缓冲区满了
            if(cache.size() == cap){
                auto temp = cache.back();
                int td = temp.first;
                map.erase(td);
                cache.pop_back();    
            }
            cache.push_front(make_pair(key,value));
            map[key] = cache.begin();            
        }
        else{
            //找到了已经存在的，要更新,但是不用删map记录，覆盖就可以
            cache.erase(map[key]);
            cache.push_front(make_pair(key,value));
            map[key] = cache.begin();
        }
        
    }
private:
    int cap;
    list<pair<int,int>> cache;
    unordered_map<int,list<pair<int,int>>::iterator> map;
};
 
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

2.排序链表

题目描述：以o(nlogn)的时间复杂度和常数级的空间复杂度实现对链表进行排序。

参考：https://leetcode-cn.com/problems/sort-list/solution/148-pai-xu-lian-biao-bottom-to-up-o1-kong-jian-by-/

示例 1:

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

输入: -1->5->3->4->0
输出: -1->0->3->4->5

思路：

本题的三个知识点函数应该作为常识使用。

1.cut(node,n)：此函数是指将链表node切掉前n个节点，并返回后半部分的头节点。

2.merge(node1,node2)：此函数实现将链表node1和链表node2，进行双路归并，返回归并后的头节点。

3.dummyHead：它其实是一个伪头节点，在不知道head节点是否会变化的时候需要用dummy标记。dummyHead.next = head;

(注意ListNode* p = head和ListNode p的区别，一个是声明对象，一个是定义指向对象的指针。对象调用自己的成员函数用.    p.next = .....。而指针则用->不能混淆。)

注意，ListNode dummyHead; auto p = &dummyHead;为什么在p不断的指向后面的节点的时候。dummyHead.next依然能准确的指向头节点？  注意p指针一直在动，但是dummyHead一直没动，所以返回dummyHead.next的时候还是头。 

本题解答思路：

1.统计链表长度

2.归并11，22，44核心.for(int size = 1;size<length;size<<=1){...}

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* p =head;
        ListNode dummyHead(0);
        dummyHead.next = head;
        //ListNode* tail = dummyHead;
        int length = 0;
        while(p){
            length++;
            p = p->next;
        }
        for(int size = 1;size<length;size<<=1){
            auto current = dummyHead.next;
            auto tail = &dummyHead;
            
            while(current){
                ListNode* left = current;
                ListNode* right = cut(left,size);
                current = cut(right,size);
                tail->next = merge(left,right);
                while(tail->next){
                    tail = tail->next;
                }
            }
        }
        return dummyHead.next;
    }
    ListNode* cut(ListNode* node1,int n){
        ListNode* temp = node1;
        while(--n&&temp){
            temp = temp->next;
        }
        //n大于链表长度了
        if(!temp) return nullptr;
        ListNode* next = temp->next;
        temp->next = nullptr;
        return next;
    } 
    ListNode* merge(ListNode* pNode1,ListNode* pNode2){
        ListNode dummyHead(0);
        auto p = &dummyHead;
        while(pNode1&&pNode2){
            if(pNode1->val>pNode2->val){
                p->next = pNode2;
                p = pNode2;
                pNode2 = pNode2->next;
            }else{
                p->next = pNode1;
                p = pNode1;
                pNode1 = pNode1->next;
            }
        }
        p->next = pNode1? pNode1:pNode2;
        return dummyHead.next;   
    }     
};

3.合并两个有序链表，包含是在上一题了，2分钟搞定

题目描述：给定两个有序链表，把他们合并成一个

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummyHead(0);
        auto p = &dummyHead;
        while(l1&&l2){
            if(l1->val<l2->val){
                p ->next = l1;
                p = l1;
                l1 = l1->next;
            }else{
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        p->next = l1 ? l1:l2;
        return dummyHead.next;
    }
};

4.乘积最大子序列

题目描述：给定一个数组，找出乘积最大的连续子序列。

参考：https://leetcode-cn.com/problems/maximum-product-subarray/solution/c-su-du-100nei-cun-92li-yong-zui-da-zhi-he-fu-zui-/

示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

思路：乘积最大值只可能从最大值或者最小值相乘得来。因此对于不大不小的结果直接忽略 ，我们只要最大的，或者最小的。

1.参数判断.if(nums.empty()) return 0;

2.变量定义及初始化。pos = neg = ret = nums[0];

3.遍历一次数组,从一开始，保存最大的，和最小的结果。同时保存当前最大结果。for(int i =1;i<nums.size();++i){temp = pos;pos = max(nums[i],max(pos*nums[i],neg*nums[i]));neg = min(nums[i],min(nums[i]*temp,nums[i]*neg));}

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if(nums.empty()) return 0;
        int pos = nums[0];
        int neg = nums[0];
        int ret = nums[0];
        for(int i = 1;i<nums.size();++i){
            int temp = pos;
            pos = max(nums[i],max(pos*nums[i],nums[i]*neg));
            neg = min(nums[i],min(temp*nums[i],nums[i]*neg));
            ret = max(ret,pos);
        }
        return ret;
    }
};

5.岛屿数量

题目描述：假设岛屿为1，水为0，给定一个由水和岛屿构成的二维网格，求岛屿的数量，假设网格的四周都是水。

参考：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3

思路：用深度优先遍历和广度优先遍历都可以解决

深度优先遍历，就是从遍历矩阵，如果遇到1，那就以这个为根深度优先遍历，并且把能遍历到的1全给替换成0 。最后总共遍历了几次，就是有几个岛屿。

1.依次遍历网格。

2.如果找到1，那么dfs

3.把传过来的根置为0，向他的上下左右扩展，如果有1，全换为0 。

class Solution {
public:
    void dfs(vector<vector<char>>& grid,int i,int j){
        int nx = grid.size();
        int ny = grid[0].size();
        grid[i][j] ='0';
        if(i-1>=0&&grid[i-1][j] == '1') dfs(grid,i-1,j);
        if(i+1<nx&&grid[i+1][j] == '1') dfs(grid,i+1,j);
        if(j-1>=0&&grid[i][j-1] == '1') dfs(grid,i,j-1);
        if(j+1<ny&&grid[i][j+1] == '1') dfs(grid,i,j+1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int x = grid.size();
        if(x == 0) return 0;
        int y = grid[0].size();
        int islands_num = 0;
        for(int i = 0;i<x;++i){
            for(int j = 0;j<y;++j){
                if(grid[i][j] == '1') {
                    islands_num++;
                    dfs(grid,i,j);
                }
            }
            
        }
        return islands_num;
    }
};

6.在排序数组中查找元素的第一个位置和最后一个位置，注意这题需要记二分查找模板

题目描述：给定一个升序数组nums，和一个整数target。。找出target在nums数组中第一次出现的位置和最后一次出现的位置。

要求时间复杂度为o(logn)。如果没有找到target，返回[-1,-1];

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

思路：这题貌似百度那个面试官问过。我答出来了，但是挂了。。。很难受

1.针对最先出现的位置，和最后出现的位置，两次二分检索。

class Solution {
public:
    int finLowerBound(vector<int>& nums,int target){
        int size = nums.size();
        int left = 0;
        int right = size-1;
        while(left<right){
            int mid = (left+right)>>1;
            if(nums[mid]<target) left = mid+1;
            else right = mid;
        }
        if(nums[left] != target) return -1;
        return left;
        
    }
    int finUpBound(vector<int>& nums,int target){
        int size = nums.size();
        int left = 0;
        int right = size-1;
        while(left<right){
            int mid = (left+right+1)>>1;
            if(nums[mid]>target) right = mid-1;
            else left = mid;
        }
        if(nums[left] != target) return -1;
        return left;
        
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0) return {-1,-1};
        int num1 = finLowerBound(nums,target);
        if(num1 == -1) return {-1,-1};
        int num2 = finUpBound(nums,target);
        return {num1,num2};
    }
};