174. 地下城游戏

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

数据范围

• m == dungeon.lengtz
• n == dungeon[i].length
• 1 <= m, n <= 200
• -1000 <= dungeon[i][j] <= 1000

分析

二分答案+dp，存在一个点k，小于$k$时所有方案都无法使骑士救出公主，大于等于k时一定存在一种方案使骑士救出公主，然后$check$函数里面进行$dp$，$dp[i][j]$表示到达$(i,j)$后的最大血量，最后判断$dp[n][m]$是否为正

代码

class Solution {
public:const static int N = 205;int dp[N][N];bool check(int mid, vector<vector<int>> &dungeon) {memset(dp, -0x3f, sizeof(dp));int n = dungeon.size();int m = dungeon[0].size();dp[1][1] = mid;if(mid + dungeon[0][0] <= 0) return false;dp[1][1] += dungeon[0][0];for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= m; j ++ ) {if(j == 1 && i == 1) continue;dp[i][j] = max(dp[i][j], dp[i - 1][j] + dungeon[i - 1][j - 1]);if(j != 1) dp[i][j] = max(dp[i][j], dp[i][j - 1] + dungeon[i - 1][j - 1]); if(dp[i][j] <= 0) dp[i][j] = -0x3f3f3f3f;}}return dp[n][m] > 0;}int find(int l, int r, vector<vector<int>>& dungeon) {while(l < r) {int mid = (l + r) >> 1;if(check(mid, dungeon)) r = mid;else l = mid + 1;}return l;}int calculateMinimumHP(vector<vector<int>>& dungeon) {int l = 1, r = 20005;int res = find(l, r, dungeon);return res;}
};

---

1436. 旅行终点站

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

数据范围

• 1 <= paths.length <= 100
• paths[i].length == 2
• 1 <= cityAi.length, cityBi.length <= 10
• cityAi != cityBi
• 所有字符串均由大小写英文字母和空格字符组成。

分析

出度为0的点即为答案

代码

class Solution {
public:const static int N = 105;map<string, int> mp;string destCity(vector<vector<string>>& paths) {for(auto k : paths) {mp[k[0]] = mp[k[0]] + 1;}string res;for(auto k : paths) {if(mp.find(k[1]) == mp.end()) res = k[1];}return res;}
};