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

在二叉树中增加一行
给定一个二叉树，根节点为第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;
}
};

换座位
小美是一所中学的信息科技老师，她有一张 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;

变更性别
给定一个 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;
```
三个数的最大乘积
给你一个整型数组 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);
    }
};

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];
    }
};

课程表
这里有 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();
    }
};

最小区间
你有 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;
    }
};