leetcode hot 100 刷题记录

题目300：最长递增子序列（NO）

解题思路：动态规划，就是dp[i]的运用，这里dp[i]表示第i个元素为结尾的最长子序列。

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列。

class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        if (n == 0) 
        {
            return 0;
        }
        vector<int> dp(n, 0);
        int max_count=0;
        for (int i = 0; i < n; ++i) 
        {
            dp[i] = 1;//如果前面没有比他小的了，那自己本身就是一个最长子序列
            for (int j = 0; j < i; ++j) 
            {
                if (nums[j] < nums[i]) 
                {
                    //这里是每次扫描前面就记录最大的dp[i]
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }

            if(dp[i]>max_count)
            {
                max_count=dp[i];
            }        
        }
        return max_count;
    }
};

题目215：数组中的第k个最大元素（NO）

解题思路：使用快速排序算法

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
public:

    void quickSort(std::vector<int>& arr, int left, int right) 
    {
        if (left >= right) 
        {
            return;
        }

        int pivot = arr[(left + right) / 2];
        int i = left, j = right;

        //这次一扫描,就会将整个数组划分为两个区域，以pivot为分界线
        while (i <= j) 
        {
            while (arr[i] < pivot) 
            {
                //找到比中间结点大的
                i++;
            }
            while (arr[j] > pivot) 
            {
                //找到比中间结点小的
                j--;
            }
            if (i <= j) 
            {
                //交换两个元素
                swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }

        //检查左边
        if (left < j) 
        {
            quickSort(arr, left, j);
        }

        //检查右边
        if (i < right) 
        {
            quickSort(arr, i, right);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        int len=nums.size();
        quickSort(nums,0,len-1);
        return nums[len-k];
    }
};

题目1：两数之和（YES）

解题思路：使用哈希表

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //使用哈希表
        unordered_map<int,int>map;

        for(int i=0;i<nums.size();i++)
        {
            if(map.find(target-nums[i])!=map.end())
            {
                return {i,map[target-nums[i]]};
            }
            map[nums[i]]=i;
            
        }
        return {};
    }
};

题目3：无重复字符的最长子串（NO）

解题思路：使用滑动窗口，就是和unordered_set搭配使用，用set来检查是否重复，没有重复在继续添加，如果重复了就删除掉第一个，因为是for一次遍历，所以每个i都可以成为第一个子串。

给定一个字符串 s ，请你找出其中不含有重复字符的最长
子串的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //使用滑动窗口的方法，就是配合unordered_set来实现
        //用set来判断是否出现了重复的字符，如果重复了就删除第一个，否则没重复的话
        //就继续在set中添加字符

        unordered_set<char>set;
        int ans=0;
        int temp=-1;
        int len=s.size();

        for(int i=0;i<s.size();i++)
        {
            //第一个字符是不用删除的
            if(i!=0)
            {
                //删除第一个元素
                set.erase(s[i-1]);
            }

            //以i为起点一直添加元素
            //确保下一个位置合法才能够加入
            while(temp+1<len&&!set.count(s[temp+1]))
            {
                set.insert(s[temp+1]);
                temp++;
            }

            //说明遇到了重复的字符，保存这次的子串长度
            ans=max(ans,temp-i+1);
        }

        return ans;
    }
};

题目11：盛最多水的容器（YES）

解题思路：最刚开始第一想到的是使用双重for遍历一遍，让每个i都作为第一条边，每个的最大的面积，但是显然这样时间复杂度太高了。
错误示例

class Solution {
public:
    int maxArea(vector<int>& height) {
        //我现在突然想到的是使用双重for遍历，每个i都可以当容器的第一个位置
        //然后找到其中最大的

        int max_ans=0;
        for(int i=0;i<height.size();i++)
        {
            for(int j=i+1;j<height.size();j++)
            {
                int area=(j-i)*min(height[i],height[j]);
                max_ans=max(area,max_ans);
            }
        }

        return max_ans;
    }
};

后面我又想到了一个思路，既然是要计算面积，底乘以高，当然是保证底部越长越好，所以在大的情况从两边开始扫描一定不会漏掉。且在靠齐的时候，当然是向边长高的靠齐最好。
正确写法

class Solution {
public:
    int maxArea(vector<int>& height) {
        //此时我又想到了面积的算法是底乘以高，所以底应该尽可能的长，所以直接从两边开始扫描
        //就行了
        int left=0;
        int right=height.size()-1;
        
        int max_area=0;
        while(left<right)
        {
            //从两边开始记录最大面积
            int temp=(right-left)*min(height[right],height[left]);
            if(temp>max_area)
            {
                max_area=temp;
            }

            if(height[left]<height[right])
            {
                //想要面积最大，应该向高的一边靠齐
                left++;
            }else
            {
                right--;
            }
        }

        return max_area;

    }
};

题目70：爬楼梯（YES）

典型的动态规划问题，考察队dp[i]数组的使用，这里dp[i]表示的是到达第i阶楼梯的方法数。这里需要关注的点是第3阶的方法数是第1阶和第2阶方法数的和。

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
public:
    int climbStairs(int n) {
        //这题使用的是动态规划问题
        //dp[i]的含义是到第i阶有多少不同的方法
        vector<int>dp(n+1);
        dp[0]=1;//单纯为了做题而设置的，没意义
        dp[1]=1;

        if(n<2)
        {
            return dp[n];
        }

        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }

        return dp[n];
    }
};

题目146：LRU缓存（NO）

解题思路：使用了双链表和哈希表的结合，这题值得关注。

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

//双向链表
struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

题目200：岛屿数量（YES）

解题思路：用双重for遍历所有的元素，第一个进来的1就是一个岛屿，然后用广度优先遍历遍历这个岛屿的1，并使用check数组设置标记为访问过了。这里可以优化的地方就是使用dx[ ]和dy[ ]来控制方向

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
    if(grid.empty()) {
        return 0;
    }

    int row = grid.size();
    int col = grid[0].size();

    //用来标记是否访问过
    vector<vector<bool>> check(row, vector<bool>(col, false));
    int ans = 0;//记录岛屿的数量

    //用来控制方向的   上  下  右 左
    vector<int> dx = {1, -1, 0, 0};
    vector<int> dy = {0, 0, 1, -1};

    //将所有的元素都检查一遍
    for(int i = 0; i < row; i++) 
    {
        for(int j = 0; j < col; j++) 
        {
            if(grid[i][j] == '1' && check[i][j] == false) 
            {
                ans++;//能进来的就是一个岛屿
                queue<pair<int, int>> que;
                que.push({i, j});
                check[i][j] = true;

                while(!que.empty()) 
                {
                    pair<int,int> temp = que.front();
                    que.pop();

                    for(int k = 0; k < 4; k++) 
                    {
                        int x = temp.first + dx[k];
                        int y = temp.second + dy[k];
                        if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1' && check[x][y] == false) 
                        {
                            que.push({x, y});
                            check[x][y] = true;
                        }
                    }
                }
            }
        }
    }
    return ans;
}
};