什么是网站的入口,制作ppt的软件手机,查企业的app软件 排名,高端品牌女装模特图片1366. 通过投票对团队排名
题目链接#xff1a;rank-teams-by-votes/
解法#xff1a;
这道题就是统计每个队伍在每个排名的投票数#xff0c;队伍为A、B、C#xff0c;则排名有1、2、3#xff0c;按照投票数进行降序排列。如果有队伍在每个排名的投票数都一样#xf…1366. 通过投票对团队排名
题目链接rank-teams-by-votes/
解法
这道题就是统计每个队伍在每个排名的投票数队伍为A、B、C则排名有1、2、3按照投票数进行降序排列。如果有队伍在每个排名的投票数都一样那么按照字母序进行排列。
可以用哈希表也可以用数组处理因为最多有26个队伍即26个字母。
细节在于按照字母序排列为了统一为按照数字降序排列可以把队伍字母转为 (Z - 队伍)这样的话如果队伍是A那么数字为26字母为Z那么数字为0字母序排列数字降序排列。
参考题解1.使用哈希表排序
2.数组把字母转为数字
边界条件无
时间复杂度O(nkn*nlogn)其中 n 是数组 votes中每一个字符串的长度参与排名的人数k 是数组 votes 的长度参与投票的人数。「遍历统计」的时间复杂度为 O(nk)「排序」的时间复杂度为 O(nlogn)由于需要两两比较那么再乘以n。
空间复杂度O(n*n)。哈希映射中键值对的数量为 n每个值使用 O(n) 的空间。
class Solution {
public:string rankTeams(vectorstring votes) {unordered_mapchar, vectorint ranking;// 初始化mapkey是字母(队)value是所有排名的投票数// 为了最后一个排序规则按照字母序来排所以value加了一个元素for (char v: votes[0]) {int topn votes[0].size();ranking[v].resize(topn1);// 如果v是A那么最后一位是26如果是Z那么为0ranking[v][topn] Z - v;}//遍历统计每个队伍每个排名的票数for (const string vote: votes) {for (int i0; ivote.size(); i) {ranking[vote[i]][i];}}// 复制到可排序的容器中vectorpairchar, vectorint sortedRanking(ranking.begin(), ranking.end());// 排序排名相等的情况下按字母序来排sort(sortedRanking.begin(), sortedRanking.end(), [](const auto s1, const auto s2) {return s1.second s2.second;});string res;for (auto rank: sortedRanking) {res rank.first;}return res;}
};
1029.两地调度
题目链接two-city-scheduling/
解法
假定2N人都去B市则费用为 price_B累加sum_b。现在让其中的N个人不去B市而是直接去A市。如果其中一个去A市那么这个费用就变成 sum_b (price_A - price_B)。
所有的price_B累加是固定值要让sum最小我们只要按(price_A - price_B)排序这个值小的前N个人去A市那sum就最小。
参考解法贪心
边界条件无
时间复杂度O(nlogn)排序。
空间复杂度O(n)
class Solution {
public:int twoCitySchedCost(vectorvectorint costs) {sort(costs.begin(), costs.end(), [] (const vectorint c1, const vectorint c2) {return (c1[0] - c1[1]) (c2[0] - c2[1]);});int result 0;int n costs.size() / 2;for (int i0; in; i) {result costs[i][0] costs[ni][1];};return result;}
};
562.矩阵中最长的连续1线段
题目链接longest-line-of-consecutive-one-in-matrix
解法
思路参考yiduobo的每日leetcode 562.矩阵中最长的连续1线段 - 知乎
动态规划问题。令row[i][j]、col[i][j]、left[i][j]、right[i][j]分别表示以单元格(i, j)为终点的水平方向、竖直方向、左对角线方向、右对角线方向上的连续1的数目那么对于这四个值若当前的mat[i][j] 0这四个值都都为0否则
当j 0时row[i][j] 1否则row[i][j] row[i][j -1] 1
当i 0时col[i][j] 1否则col[i][j] col[i - 1][j] 1
当i 0或j 0时left[i][j] 0否则left[i][j] left[i - 1][j - 1] 1
当i 0或j n - 1时right[i][j] 0否则right[i][j] left[i - 1][j 1] 1
计算完成后取四个数组中的最大值作为答案即可。
这个题涉及到4个方向初始化比较麻烦所以没有初始化直接从0开始遍历。
具体代码实现参考动态规划
边界条件无
时间复杂度O(mn)
空间复杂度O(mn)
class Solution {
public:int longestLine(vectorvectorint mat) {int m mat.size();int n mat[0].size();int res 0;vectorvectorvectorint dp(4, vectorvectorint(m, vectorint(n, 0)));for (int i0; im; i) {for (int j0; jn; j) {if (mat[i][j] 0) continue;dp[0][i][j] j0? 1: 1dp[0][i][j-1];dp[1][i][j] i0? 1: 1dp[1][i-1][j];dp[2][i][j] (i0 || j0)? 1: 1dp[2][i-1][j-1];dp[3][i][j] (i0 || jn-1)? 1: 1dp[3][i-1][j1]; // 更新结果 for (int k0; k4; k) {res max(res, dp[k][i][j]);}}}return res;}
};
