Leetcode 刷题笔记-Leetcode 101 第11章 数据结构

Leetcode 刷题笔记-Leetcode 101 第11章 数据结构

数据结构

数组

Leetcode 448

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<bool> vt(n+1,false);
        for(int i=0;i<n;++i){
            vt[nums[i]] = true;
        }
        vector<int> result;
        for(int i=1;i<=n;++i){
            if(vt[i] == false){
                result.push_back(i);
            }
        }
        return result;
    }
};

分析：扫一遍确认一下，再扫一遍找出结果。

一遍AC

Leetcode 48

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像原地顺时针旋转 90 度。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int temp = 0, n = matrix.size()-1;
        for (int i = 0; i <= n / 2; ++i) {
            for (int j = i; j < n - i; ++j) {
                temp = matrix[j][n-i];
                matrix[j][n-i] = matrix[i][j];
                matrix[i][j] = matrix[n-j][i];
                matrix[n-j][i] = matrix[n-i][n-j];
                matrix[n-i][n-j] = temp;
            }
        }
    }
};

分析：转转转

错误：没想到原地旋转的思路。

Leetcode 240

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列，每列的元素从上到下升序排列。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int x = 0;
        int y = n-1;
        while(x >= 0 && x < m && y >= 0 && y < n){
            if(matrix[x][y] == target){
                return true;
            }
            else if(target < matrix[x][y]){
                y -= 1;
            }
            else{
                x += 1;
            }
        }
        return false;
    }
};

分析：从右上角开始查找，若当前值大于待搜索值，我们向左移动一位；若当前值小于待搜索值，我们向下移动一位。如果最终移动到左下角时仍不等于待搜索值，则说明待搜索值不存在于矩阵中。

错误：找到思路后一遍AC

Leetcode 769

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。返回数组能分成的最多块数量。

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        int result = 0;
        int maxnum = 0;
        for(int i=0;i<n;++i){
            maxnum = max(maxnum,arr[i]);
            if(maxnum == i){
                ++result;
            }
        }
        return result;
    }
};

分析：从左往右遍历，同时记录当前的最大值，每当当前最大值等于数组位置时，我们可以多一次分割。

错误：看了思路后实现的

栈和队列

Leetcode 232

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）

class MyQueue {
    stack<int> st1;
    stack<int> st2;
public:
    MyQueue() {

    }
  
    void push(int x) {
        st1.push(x);
    }
  
    int pop() {
        while(!st1.empty()){
            st2.push(st1.top());
            st1.pop();
        }
        int a = st2.top();
        st2.pop();
        while(!st2.empty()){
            st1.push(st2.top());
            st2.pop();
        }
        return a;
    }
  
    int peek() {
        while(!st1.empty()){
            st2.push(st1.top());
            st1.pop();
        }
        int a = st2.top();
        while(!st2.empty()){
            st1.push(st2.top());
            st2.pop();
        }
        return a;
    }
  
    bool empty() {
        return st1.empty();
    }
};

分析：比较简单，也没有算法

错误：全局变量没定义好，返回值漏掉了，调通了。

Leetcode 155

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

class MinStack {
    stack<int> s1;
    stack<int> mins;
public:
    MinStack() {

    }
  
    void push(int val) {
        if(mins.empty() || val <= mins.top()){
            mins.push(val);
        }
        s1.push(val);
    }
  
    void pop() {
        int a = s1.top();
        s1.pop();
        if(mins.top() == a){
            mins.pop();
        }
    }
  
    int top() {
        return s1.top();
    }
  
    int getMin() {
        return mins.top();
    }
};

分析：可以额外建立一个新栈，栈顶表示原栈里所有值的最小值。每当在原栈里插入一个数字时，若该数字小于等于新栈栈顶，则表示这个数字在原栈里是最小值，我们将其同时插入新栈内。每当从原栈里取出一个数字时，若该数字等于新栈栈顶，则表示这个数是原栈里的最小值之一，我们同时取出新栈栈顶的值。

错误：没有思路

Leetcode 20

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int n = s.size();
        for(int i=0;i<n;++i){
            if(s[i] == '(' || s[i] == '{' || s[i] == '['){
                st.push(s[i]);
            }
            else{
                if(st.empty()){
                    return false;
                }
                else if(st.top() == '[' && s[i] == ']'){
                    st.pop();
                }
                else if(st.top() == '(' && s[i] == ')'){
                    st.pop();
                }
                else if(st.top() == '{' && s[i] == '}'){
                    st.pop();
                }
                else{
                    return false;
                }
            }
        }
        if(st.empty()){
            return true;
        }
        return false;
    }
};

分析：用栈进行匹配即可

错误：没有考虑只有一个左括号的情况，改正后调通了

单调栈

Leetcode 739

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> answer(n);
        stack<int> s;
        for(int i=0;i<n;++i){
            while (!s.empty()) {
                int pre_index = s.top();
                if (temperatures[i] <= temperatures[pre_index]) {
                    break;
                }
                s.pop();
                answer[pre_index] = i - pre_index;
            }
            s.push(i);
        }
        return answer;
    }
};

分析：我们可以维持一个单调递减的栈，表示每天的温度；为了方便计算天数差，我们这里存放位置（即日期）而非温度本身。我们从左向右遍历温度数组，对于每个日期p，如果p的温度比栈顶存储位置q的温度高，则我们取出q，并记录q需要等待的天数为p-q；我们重复这一过程，直到p的温度小于等于栈顶存储位置的温度（或空栈）时，我们将p插入栈顶，然后考虑下一天。在这个过程中，栈内数组永远保持单调递减，避免了使用排序进行比较。最后若栈内剩余一些日期，则说明它们之后都没有出现更暖和的日期。

错误：感觉并不是非常理解。

优先队列

Leetcode 23

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

class Solution {
public:
    struct Comp{
        bool operator()(ListNode* l1,ListNode* l2){
            return l1->val > l2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()){
            return nullptr;
        }
        priority_queue<ListNode*,vector<ListNode*>,Comp> q;
        for(ListNode* list:lists){
            if(list){
                q.push(list);
            }
        }
        ListNode* dummy = new ListNode(0), *cur = dummy;
        while (!q.empty()) {
            cur->next = q.top();
            q.pop();
            cur = cur->next;
            if (cur->next) {
                q.push(cur->next);
            }
        }
        return dummy->next;
    }
};

分析：即把所有的链表存储在一个优先队列中，每次提取所有链表头部节点值最小的那个节点，直到所有链表都被提取完为止。

错误：优先队列不是很熟悉

Leetcode 218

给定建筑物的起止位置和高度，返回建筑物轮廓（天际线）的拐点。

Hard难度，想不太明白，暂时不做了

分析：使用优先队列储存每个建筑物的高度和右端（这里使用pair，其默认比较函数是先比较第一个值，如果相等则再比较第二个值），从而获取目前会拔高天际线、且妨碍到前一个建筑物（的右端端点）的下一个建筑物。

错误：没有思路

双端队列

Leetcode 239

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq;
        int n = nums.size();
        for(int i=0;i<n;++i){
            if(!dq.empty() && nums[i] > nums[dq.back()]){
                while(!dq.empty() && nums[dq.back()] < nums[i]){
                    dq.pop_back();
                }
            }
            dq.push_back(i);
            if(i >= k-1){
                result.push_back(nums[dq.front()]);
                if(nums[i-k+1] == nums[dq.front()]){
                    dq.pop_front();
                }
            }
        }
        return result;
    }
};

分析：利用双端队列进行操作：每当向右移动时，把窗口左端的值从队列左端剔除，把队列右边小于窗口右端的值全部剔除。这样双端队列的最左端永远是当前窗口内的最大值。

错误：理解了思路后调通了。

哈希表

Leetcode 1

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int, int> hash;
        int n = nums.size();
        for(int i=0;i<n;++i){
            if(hash.count(target - nums[i])){
                result.push_back(hash[target - nums[i]]);
                result.push_back(i);
                break;
            }
            hash[nums[i]] = i;
        }
        return result;
    }
};

分析：利用哈希表存储遍历过的值以及它们的位置，每次遍历到位置i 的时候，查找哈希表里是否存在target - nums[i]，若存在，则说明这两个值的和为target。

一遍AC

Leetcode 128

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        for(const int & num:nums){
            hash.insert(num);
        }
        int ans = 0;
        while(!hash.empty()){
            int cnt = *(hash.begin());
            hash.erase(cnt);
            int pre = cnt - 1;
            int next = cnt + 1;
            while(!hash.empty() && hash.count(pre)){
                hash.erase(pre);
                --pre;
            }
            while(!hash.empty() && hash.count(next)){
                hash.erase(next);
                ++next;
            }
            ans = max(ans,next-pre-1);
        }
        return ans;
    }
};

分析：把所有数字放到一个哈希表，然后不断地从哈希表中任意取一个值，并删除掉其之前之后的所有连续数字，然后更新目前的最长连续序列长度。重复这一过程，我们就可以找到所有的连续数字序列。

错误：看了思路后实现了

Leetcode 149

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        unordered_map<double, int> hash; // <斜率, 点个数>
        int max_count = 0, same = 1, same_y = 1;
        for (int i = 0; i < points.size(); ++i) {
            same = 1, same_y = 1;
            for (int j = i + 1; j < points.size(); ++j) {
                if (points[i][1] == points[j][1]) {
                    ++same_y;
                    if (points[i][0] == points[j][0]) {
                        ++same;
                    }
                }
                else {
                    double dx = points[i][0] - points[j][0], dy = points[i][1] -
                    points[j][1];
                    ++hash[dx/dy];
                }
            }
            max_count = max(max_count, same_y);
            for (auto item : hash) {
                max_count = max(max_count, same + item.second);
            }
            hash.clear();
        }
        return max_count;
    }
};

分析：对于每个点，我们对其它点建立哈希表，统计同一斜率的点一共有多少个。这里利用的原理是，一条线可以由一个点和斜率而唯一确定。另外也要考虑斜率不存在和重复坐标的情况。

错误：好麻烦先算了

多重集合和映射

Leetcode 332

给你一份航线列表 tickets ，其中 tickets[i] = [from<sub>i</sub>, to<sub>i</sub>] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

class Solution {
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> ans;
        if (tickets.empty()) {
            return ans;
        }
        unordered_map<string, multiset<string>> hash;
        for (const auto & ticket: tickets) {
            hash[ticket[0]].insert(ticket[1]);
        }
        stack<string> s;
        s.push("JFK");
        while (!s.empty()) {
            string next = s.top();
            if (hash[next].empty()) {
                ans.push_back(next);
                s.pop();
            } 
            else {
                s.push(*hash[next].begin());
                hash[next].erase(hash[next].begin());
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

分析：本题可以先用哈希表记录起止机场，其中键是起始机场，值是一个多重集合，表示对应的终止机场。因为一个人可能坐过重复的线路，所以我们需要使用多重集合储存重复值。储存完成之后，我们可以利用栈来恢复从终点到起点飞行的顺序，再将结果逆序得到从起点到终点的顺序。

错误：多重集合的第一道题，也是唯一一道题，不是很明白

前缀和和积分图

Leetcode 303

设计一个数据结构，使得其能够快速查询给定数组中，任意两个位置间所有数字的和。

class NumArray {
    vector<int> frontsum;
public:
    NumArray(vector<int>& nums) {
        for(int i=0;i<nums.size();++i){
            if(i == 0){
                frontsum.push_back(nums[i]);
            }
            else{
                frontsum.push_back(nums[i] + frontsum[i-1]);
            }
        }
    }
  
    int sumRange(int left, int right) {
        if(left == 0){
            return frontsum[right];
        }
        return frontsum[right] - frontsum[left-1];
    }
};

分析：前缀和即可

一遍AC

Leetcode 304

设计一个数据结构，使得其能够快速查询给定矩阵中，任意两个位置包围的长方形中所有数字的和。

class NumMatrix {
    vector<vector<int>> frontmatrix;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        for(int i=0;i<m;++i){
            vector<int> temp;
            for(int j=0;j<n;++j){
                if(i == 0 && j == 0){
                    temp.push_back(matrix[i][j]);
                }
                else if(i == 0){
                    temp.push_back(matrix[i][j] + temp[j-1]);
                }
                else if(j == 0){
                    temp.push_back(matrix[i][j] + frontmatrix[i-1][j]);
                }
                else{
                    temp.push_back(matrix[i][j] + frontmatrix[i-1][j] + temp[j-1] - frontmatrix[i-1][j-1]);
                }
            }
            frontmatrix.push_back(temp);
        }
    }
  
    int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1 == 0 && col1 == 0){
            return frontmatrix[row2][col2];
        }
        else if(row1 == 0){
            return frontmatrix[row2][col2]-frontmatrix[row2][col1-1];
        }
        else if(col1 == 0){
            return frontmatrix[row2][col2]-frontmatrix[row1-1][col2];
        }
        return frontmatrix[row2][col2]-frontmatrix[row2][col1-1]-frontmatrix[row1-1][col2]+frontmatrix[row1-1][col1-1];
    }
};

分析：二维上的前缀和（积分图）即可

一遍AC

Leetcode 560

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0, psum = 0;
        unordered_map<int, int> hashmap;
        hashmap[0] = 1; // 初始化很重要
        for (int i: nums) {
            psum += i;
            count += hashmap[psum-k];
            ++hashmap[psum];
        }
        return count;
    }
};

分析：本题同样是利用前缀和，不同的是这里我们使用一个哈希表 hashmap，其键是前缀和，而值是该前缀和出现的次数。在我们遍历到位置i 时，假设当前的前缀和是 psum ，那么 hashmap[psum-k]即为以当前位置结尾、满足条件的区间个数。

错误：直接使用前缀和会超时，然而这个短代码挺难理解的样子。

练习

Leetcode 566

在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int m = mat.size();
        int n = mat[0].size();
        if(m*n != r*c){
            return mat;
        }
        int rowindex = 0;
        int colindex = 0;
        vector<vector<int>> result(r,vector<int>(c));
        for(int i=0;i<r;++i){
            for(int j=0;j<c;++j){
                result[i][j] = mat[rowindex][colindex];
                ++colindex;
                if(colindex == n){
                    ++rowindex;
                    colindex = 0;
                }
            }
        }
        return result;
    }
};

分析：很简单的小题，没有任何难度。

一遍AC

Leetcode 225

用两个队列实现一个栈

class MyStack {
    queue<int> q1;
    queue<int> q2;
public:
    MyStack() {

    }
  
    void push(int x) {
        q1.push(x);
        return;
    }
  
    int pop() {
        while(q1.size() != 1){
            q2.push(q1.front());
            q1.pop();
        }
        int a = q1.front();
        q1.pop();
        while(!q2.empty()){
            q1.push(q2.front());
            q2.pop();
        }
        return a;
    }
  
    int top() {
        while(q1.size() != 1){
            q2.push(q1.front());
            q1.pop();
        }
        int a = q1.front();
        q2.push(q1.front());
        q1.pop();
        while(!q2.empty()){
            q1.push(q2.front());
            q2.pop();
        }
        return a;
    }
  
    bool empty() {
        return q1.empty();
    }
};

分析：也是很简单的题，倒腾倒腾数字就行了

一遍AC

Leetcode 503

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的下一个更大元素 。

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int> st;
        vector<int> result(n,-1);
        for(int i=0;i<2*n-1;++i){
            while(!st.empty() && nums[i%n] > nums[st.top()]){
                result[st.top()] = nums[i%n];
                st.pop();
            }
            st.push(i%n);
        }
        return result;
    }
};

分析：使用单调栈解决本题。单调栈中保存的是下标，从栈底到栈顶的下标在数组 nums中对应的值是单调不升的。每次我们移动到数组中的一个新的位置 i，我们就将当前单调栈中所有对应值小于 nums[i]的下标弹出单调栈，这些值的下一个更大元素即为 nums[i]。随后我们将位置 i入栈。

错误：没有想到单调栈，看了一下思路后自己实现的。

Leetcode 217

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int,int> mp;
        int n = nums.size();
        for(int i=0;i<n;++i){
            if(mp.find(nums[i]) == mp.end()){
                mp[nums[i]] = 1;
            }
            else{
                return true;
            }
        }
        return false;
    }
};

分析：非常简单的哈希表，没什么难度

错误：下标和数字插入看的不太对

Leetcode 697

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int,vector<int>> mp;
        int n = nums.size();
        for(int i=0;i<n;++i){
            if(mp.find(nums[i]) == mp.end()){
                mp[nums[i]].push_back(i);
                mp[nums[i]].push_back(i);
                mp[nums[i]].push_back(1);
            }
            else{
                if(i < mp[nums[i]][0]){
                    mp[nums[i]][0] = i;
                }
                if(i > mp[nums[i]][1]){
                    mp[nums[i]][1] = i;
                }
                ++mp[nums[i]][2];
            }
        }
        int maxnum = 0;
        int result = n+1;
        for(auto it = mp.cbegin();it != mp.cend();++it){
            if(it->second[2] > maxnum){
                maxnum = it->second[2];
                result = it->second[1]-it->second[0]+1;
            }
            else if (it->second[2] == maxnum){
                result = min(result,it->second[1]-it->second[0]+1);
            }
        }
        return result;
    }
};

分析：比较简单的数据结构应用题

错误：语法问题，还有下标数字问题，后面自己调通

Leetcode 594

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

class Solution {
public:
    int findLHS(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        unordered_map<int,int> mp;
        for(int i=0;i<n;++i){
            if(mp.find(nums[i]) == mp.end()){
                mp[nums[i]] = 1;
            }
            else{
                ++mp[nums[i]];
            }
        }
        for(auto it = mp.cbegin();it != mp.cend();++it){
            if(mp.find(it->first-1) != mp.end()){
                ans = max(ans,it->second + mp[it->first-1]);
            }
            if(mp.find(it->first+1) != mp.end()){
                ans = max(ans,it->second + mp[it->first+1]);
            }
        }
        return ans;
    }
};

分析：看起来挺像动态规划，实际上并不是，统计一下就好了

错误：还是map迭代器不太熟练，后面调通。

Leetcode 287

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        int len = nums.length;
        for (int num : nums) {
            int idx = Math.abs(num);
            if (nums[idx] < 0) {
                return idx;
            }
            nums[idx] = -nums[idx];
        }
        return len;
    }
};

分析：考虑到数组元素值的范围是 [1,n]，但数组长度为 n+1，那么很显然在遍历数组的时候，我们将数组的值变为其对应的负数，那么再次遇到负数就得到了答案。

错误：上面不是最优解，没有想到最优解

Leetcode 313

超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<long> dp(n + 1);
        int m = primes.size();
        vector<int> pointers(m, 0);
        vector<long> nums(m, 1);
        for (int i = 1; i <= n; i++) {
            long minNum = INT_MAX;
            for (int j = 0; j < m; j++) {
                minNum = min(minNum, nums[j]);
            }
            dp[i] = minNum;
            for (int j = 0; j < m; j++) {
                if (nums[j] == minNum) {
                    pointers[j]++;
                    nums[j] = dp[pointers[j]] * primes[j];
                }
            }
        }
        return dp[n];
    }
};

分析：动态规划，没有思路

错误：没有思路

Leetcode 870

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        vector<pair<int,int>> vt;
        for(int i=0;i<nums2.size();i++){
            vt.push_back(make_pair(nums2[i],i));
        }
        sort(vt.begin(),vt.end());
        vector<int> ans(nums2.size());
        int l1=0,r1=nums1.size()-1,l2=0,r2=nums2.size()-1;
        while(r2>=0){
            if(nums1[r1]>vt[r2].first){
                ans[vt[r2].second]=nums1[r1];
                r1--;
            }
            else{
                 ans[vt[r2].second]=nums1[l1];
                 l1++;
            }
            r2--;
        }
      
        return ans;
    }
};

分析：田忌赛马，能打就打，打不过让最菜的送人头。

错误：没思路

Leetcode 307

线段树先算了

总结

数据结构是最最基础的算法，没有合适的数据结构就不可能有高效的算法。普通的数据结构掌握的还不错，但是有一些比较高级的数据结构练的比较少，掌握的不太好。今后要注重这些比较高级的数据结构，并尽量去在实际中应用。