leetcode解题思路分析（七十一）623 - 631 题

短命女 2022-10-22 04:20 102阅读 0赞

1.  在二叉树中增加一行  
    给定一个二叉树，根节点为第1层，深度为 1。在其第 d 层追加一行值为 v 的节点。添加规则：给定一个深度值 d （正整数），针对深度为 d-1 层的每一非空节点 N，为 N 创建两个值为 v 的左子树和右子树。将 N 原先的左子树，连接为新节点 v 的左子树；将 N 原先的右子树，连接为新节点 v 的右子树。如果 d 的值为 1，深度 d - 1 不存在，则创建一个新的根节点 v，原先的整棵树将作为 v 的左子树。

**层序遍历至指定深度之后再添加链表即可**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
    TreeNode *addOneRow(TreeNode *root, int v, int d) { 
      //如果d为1，则创建一个新的根节点v，原先的整棵树将作为v的左子树
      if (d == 1) { 
        return new TreeNode(v, root, nullptr);
      }
      queue<TreeNode *> q;
      q.emplace(root);
      //当前层数为 d-1 时，停止遍历
      while (--d != 1) { 
        for (int i = 0, size = q.size(); i < size; ++i) { 
          TreeNode *node = q.front();
          q.pop();
          if (node->left) { 
            q.emplace(node->left);
          }
          if (node->right) { 
            q.emplace(node->right);
          }
        }
      }
      //队列中剩下的节点即为节点N
      while (!q.empty()) { 
        TreeNode *node = q.front();
        q.pop();
        //先创建一个节点P，其左节点为当前节点的左节点
        //然后将当前节点的左节点设置为节点P
        node->left = new TreeNode(v, node->left, nullptr);
        //先创建一个节点P，其右节点为当前节点的右节点
        //然后将当前节点的右节点设置为节点P
        node->right = new TreeNode(v, nullptr, node->right);
      }
      return root;
    }
    };

1.  换座位  
    小美是一所中学的信息科技老师，她有一张 seat 座位表，平时用来储存学生名字和与他们相对应的座位 id。其中纵列的 id 是连续递增的。小美想改变相邻俩学生的座位，你能不能帮她写一个 SQL query 来输出小美想要的结果呢？

**对奇偶的id进行操作，最后一个数需要特判，然后再排序即可**

# Write your MySQL query statement below
    SELECT
        (CASE
            WHEN MOD(id, 2) != 0 AND counts != id THEN id + 1
            WHEN MOD(id, 2) != 0 AND counts = id THEN id
            ELSE id - 1
        END) AS id,
        student
    FROM
        seat,
        (SELECT
            COUNT(*) AS counts
        FROM
            seat) AS seat_counts
    ORDER BY id ASC;

1.  变更性别  
    给定一个 salary 表，如下所示，有 m = 男性 和 f = 女性 的值。交换所有的 f 和 m 值（例如，将所有 f 值更改为 m，反之亦然）。要求只使用一个更新（Update）语句，并且没有中间的临时表。

# Write your MySQL query statement below
    UPDATE salary
    SET
        sex = 
            CASE sex
                WHEN 'm' THEN 'f'
                ELSE 'm'
        END;

1.  三个数的最大乘积  
    给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

**线性扫描一遍即可**

class Solution { 
    public:
        int maximumProduct(vector<int>& nums) { 
            // 最小的和第二小的
            int min1 = INT_MAX, min2 = INT_MAX;
            // 最大的、第二大的和第三大的
            int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
    
            for (int x: nums) { 
                if (x < min1) { 
                    min2 = min1;
                    min1 = x;
                } else if (x < min2) { 
                    min2 = x;
                }
    
                if (x > max1) { 
                    max3 = max2;
                    max2 = max1;
                    max1 = x;
                } else if (x > max2) { 
                    max3 = max2;
                    max2 = x;
                } else if (x > max3) { 
                    max3 = x;
                }
            }
    
            return max(min1 * min2 * max1, max1 * max2 * max3);
        }
    };

1.  K各逆序对数组  
    给出两个整数 n 和 k，找出所有包含从 1 到 n 的数字，且恰好拥有 k 个逆序对的不同的数组的个数。逆序对的定义如下：对于数组的第i个和第 j个元素，如果满i < j且 a\[i\] > a\[j\]，则其为一个逆序对；否则不是。

**假设现在我们已经使用1到i−1构成了一个逆序对数目为jj的序列，如果我们将i插到该序列的倒数第m个数之前，由于i大于原序列中的所有数，因此i与其后的m个数构成了m个新的逆序对，因此插入i后新序列的逆序对为j + m。dp\[i\]\[j\]=\{  
dp\[i\]\[j−1\]+dp\[i−1\]\[j\],if i>j  
dp\[i\]\[j−1\]+dp\[i−1\]\[j\]−dp\[i−1\]\[j−i\],otherwise**

class Solution { 
    public:
    
        const int mod = 1000000007;
    
        int kInversePairs(int n, int k) { 
            int dp[n + 1][k + 1];
            memset(dp, 0, sizeof(dp));
            dp[1][0] = 1;
            for (int i = 2; i <= n; i++) { 
                dp[i][0] = 1;
                for (int j = 1; j <= k; j++) { 
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
                    if (i <= j) { 
                        dp[i][j] = ((dp[i][j] - dp[i - 1][j - i]) % mod + mod) % mod;
                    }
                }
            }
            return dp[n][k];
        }
    };

1.  课程表  
    这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。

**贪心算法挨个加入，不行则删除换下一个**

bool cmp(vector<int> &l, vector<int>& r)
    { 
        return l[1] < r[1];
    }
    
    class Solution { 
    public:
        int scheduleCourse(vector<vector<int>>& courses) { 
            sort(courses.begin(), courses.end(), cmp);
    
            priority_queue<int> qu;
            int day = 0;
            for (int i = 0; i < courses.size(); i++) { 
                if (day + courses[i][0] <= courses[i][1]) { 
                    qu.push(courses[i][0]);
                    day += courses[i][0];
                } else { 
                    qu.push(courses[i][0]);
                    day += courses[i][0];
    
                    int mostwastecousrse = qu.top();
                    qu.pop();
                    day -= mostwastecousrse;
                }
            }
            return qu.size();
        }
    };

1.  最小区间  
    你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 \[a,b\] 比 \[c,d\] 小。

**把多个列表整合成一个列表，然后滑动指针找到满足条件的区间即可（包含各个原区间即可）**

class Solution { 
    public:
        vector<int> smallestRange(vector<vector<int>>& nums) { 
            vector<pair<int, int>> ordered; // (number, group)
            for (size_t k = 0; k < nums.size(); ++k)
                for (auto n: nums[k]) ordered.push_back({ n, k});
            sort(ordered.begin(), ordered.end());
    
            int i = 0, k = 0;
            vector<int> ans;
            unordered_map<int, int> count;
            for (size_t j = 0; j < ordered.size(); ++j) { 
                if (! count[ordered[j].second]++) ++k;
                if (k == nums.size()) {  
                    while (count[ordered[i].second] > 1) --count[ordered[i++].second]; // minialize range
                    if (ans.empty() || ans[1] - ans[0] > ordered[j].first - ordered[i].first) { 
                        ans = vector<int>{ ordered[i].first, ordered[j].first};
                    }
                }
            }
    
            return ans;
        }
    };