当前位置: 首页 > news >正文

TikTok真题第4天 | 1366. 通过投票对团队排名、1029.两地调度、562.矩阵中最长的连续1线段

1366. 通过投票对团队排名

题目链接:rank-teams-by-votes/

解法:

这道题就是统计每个队伍在每个排名的投票数,队伍为A、B、C,则排名有1、2、3,按照投票数进行降序排列。如果有队伍在每个排名的投票数都一样,那么按照字母序进行排列。

可以用哈希表也可以用数组处理(因为最多有26个队伍,即26个字母)。

细节在于按照字母序排列,为了统一为按照数字降序排列,可以把队伍(字母)转为 (Z - 队伍),这样的话,如果队伍是A,那么数字为26,字母为Z,那么数字为0,字母序排列=数字降序排列。

参考题解:1.使用哈希表排序 

2.数组+把字母转为数字

边界条件:无

时间复杂度:O(nk+n*nlog⁡n),其中 n 是数组 votes中每一个字符串的长度(参与排名的人数),k 是数组 votes 的长度(参与投票的人数)。「遍历统计」的时间复杂度为 O(nk),「排序」的时间复杂度为 O(nlog⁡n),由于需要两两比较,那么再乘以n。

空间复杂度:O(n*n)。哈希映射中键值对的数量为 n,每个值使用 O(n) 的空间。

class Solution {
public:string rankTeams(vector<string>& votes) {unordered_map<char, vector<int>> ranking;// 初始化map,key是字母(队),value是所有排名的投票数// 为了最后一个排序规则:按照字母序来排,所以value加了一个元素for (char v: votes[0]) {int topn = votes[0].size();ranking[v].resize(topn+1);// 如果v是A,那么最后一位是26,如果是Z,那么为0ranking[v][topn] = 'Z' - v;}//遍历统计每个队伍每个排名的票数for (const string& vote: votes) {for (int i=0; i<vote.size(); i++) {ranking[vote[i]][i]++;}}// 复制到可排序的容器中vector<pair<char, vector<int>>> 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(vector<vector<int>>& costs) {sort(costs.begin(), costs.end(), [] (const vector<int>& c1, const vector<int>& c2) {return (c1[0] - c1[1]) < (c2[0] - c2[1]);});int result = 0;int n = costs.size() / 2;for (int i=0; i<n; i++) {result += costs[i][0] + costs[n+i][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(vector<vector<int>>& mat) {int m = mat.size();int n = mat[0].size();int res = 0;vector<vector<vector<int>>> dp(4, vector<vector<int>>(m, vector<int>(n, 0)));for (int i=0; i<m; i++) {for (int j=0; j<n; j++) {if (mat[i][j] == 0) continue;dp[0][i][j] = j==0? 1: 1+dp[0][i][j-1];dp[1][i][j] = i==0? 1: 1+dp[1][i-1][j];dp[2][i][j] = (i==0 || j==0)? 1: 1+dp[2][i-1][j-1];dp[3][i][j] = (i==0 || j==n-1)? 1: 1+dp[3][i-1][j+1];  // 更新结果   for (int k=0; k<4; k++) {res = max(res, dp[k][i][j]);}}}return res;}
};

相关文章:

TikTok真题第4天 | 1366. 通过投票对团队排名、1029.两地调度、562.矩阵中最长的连续1线段

1366. 通过投票对团队排名 题目链接&#xff1a;rank-teams-by-votes/ 解法&#xff1a; 这道题就是统计每个队伍在每个排名的投票数&#xff0c;队伍为A、B、C&#xff0c;则排名有1、2、3&#xff0c;按照投票数进行降序排列。如果有队伍在每个排名的投票数都一样&#xf…...

时序预测 | Matlab实现SSA-CNN-LSTM麻雀算法优化卷积长短期记忆神经网络时间序列预测

时序预测 | Matlab实现SSA-CNN-LSTM麻雀算法优化卷积长短期记忆神经网络时间序列预测 目录 时序预测 | Matlab实现SSA-CNN-LSTM麻雀算法优化卷积长短期记忆神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 MATLAB实现SSA-CNN-LSTM麻雀算法优化卷积长短…...

负载均衡——Ribbon

文章目录 Ribbon和Eureka配合使用项目引入RibbonRestTemplate添加LoadBalanced注解注意自定义均衡方式代码注册方式配置方式 Ribbon脱离Eureka使用 Ribbon&#xff0c;Nexflix发布的负载均衡器&#xff0c;有助于控制HTTP和TCP客户端的行为。基于某种负载均衡算法&#xff08;轮…...

7.微服务设计原则

1.微服务演进策略 从单体应用向微服务演进策略: 绞杀者策略&#xff0c;修缮者策略的另起炉灶策略&#xff1b; 绞杀者策赂 绞杀者策略是一种逐步剥离业务能力&#xff0c;用微服务逐步替代原有单体应用的策略。它对单体应用进行领域建模&#xff0c;根据领域边界&#xff0…...

【MATLAB库函数系列】线性调频Z(Chirp-Z,CZT)的MATLAB源码和C语言实现

在上一篇博客 【数字信号处理】线性调频Z(Chirp-Z,CZT)算法详解 已经详细介绍了CZT变换的应用背景和原理,先回顾一下: 回顾CZT算法 采用 FFT 算法可以很快计算出全部 N N N点 DFT 值,即Z变换 X ( z ) X(z) <...

BIT-6-指针(C语言初阶学习)

1. 指针是什么 2. 指针和指针类型 3. 野指针 4. 指针运算 5. 指针和数组 6. 二级指针 7. 指针数组 1. 指针是什么&#xff1f; 指针是什么&#xff1f; 指针理解的2个要点&#xff1a; 指针是内存中一个最小单元的编号&#xff0c;也就是地址平时口语中说的指针&#xff0c;通常…...

傻瓜式教学Docker 使用docker compose部署 php nginx mysql

首先你可以准备这个三个服务,也可以在docker compose 文件中 直接拉去指定镜像,这里演示的是镜像服务已经在本地安装好了,提供如下: PHP # 设置基础镜像 FROM php:8.2-fpm# install dependencies RUN apt-get update && apt-get install -y \vim \libzip-dev \libpng…...

node express简单微服务

首先&#xff0c;安装所需的依赖项&#xff0c;可以使用npm或yarn进行安装&#xff1a; $ npm install express axios接下来&#xff0c;创建一个名为service1.js的文件&#xff0c;用于实现第一个微服务&#xff1a; const express require(express); const axios require…...

nginx-proxy-manager初次登录502 bad gateway

nginx-proxy-manager初次登录502 bad gateway 按照官方docker-compose安装后,页面如下: 默认账户密码: adminexample.com/changeme点击sign in,提示Bad Gateway 打开调试 重装后依然如此,最后查阅githup issue 找到答案 https://github.com/NginxProxyManager/nginx-proxy-…...

Servlet见解2

4 创建servlet的三种方式 4.1 实现Servlet接口的方式 import javax.servlet.*; import javax.servlet.annotation.WebServlet; import java.io.IOException;WebServlet("/test1") public class Servlet1 implements Servlet {Overridepublic void init(ServletConf…...

【SpringCloud】-OpenFeign实战及源码解析、与Ribbon结合

一、背景介绍 二、正文 OpenFeign是什么&#xff1f; OpenFeign&#xff08;简称Feign&#xff09;是一个声明式的Web服务客户端&#xff0c;用于简化服务之间的HTTP通信。与Nacos和Ribbon等组件协同&#xff0c;以支持在微服务体系结构中方便地进行服务间的通信&#xff1b…...

走进数字金融峰会,为金融科技数字化赋能

12月20—21日&#xff0c;FSIDigital数字金融峰会在上海圆满召开。本次峰会包含InsurDigital数字保险峰会和B&SDigital数字银行与证券峰会2场平行峰会&#xff1b;吸引了近600位来自保险、银行、证券以及金融科技等行业的领导者和专家齐聚一堂&#xff0c;共同探讨金融业数…...

docker-compose部署kafka

docker-compose.yml配置 version: "3" services:kafka:image: bitnami/kafka:latestports:- 7050:7050environment:- KAFKA_ENABLE_KRAFTyes- KAFKA_CFG_PROCESS_ROLESbroker,controller- KAFKA_CFG_CONTROLLER_LISTENER_NAMESCONTROLLER- KAFKA_CFG_LISTENERSPLAIN…...

Spark与Hadoop的关系和区别

在大数据领域&#xff0c;Spark和Hadoop是两个备受欢迎的分布式数据处理框架&#xff0c;它们在处理大规模数据时都具有重要作用。本文将深入探讨Spark与Hadoop之间的关系和区别&#xff0c;以帮助大家的功能和用途。 Spark和Hadoop简介 1 Hadoop Hadoop是一个由Apache基金会…...

蓝桥杯-Excel地址[Java]

目录&#xff1a; 学习目标&#xff1a; 学习内容&#xff1a; 学习时间&#xff1a; 题目&#xff1a; 题目描述: 输入描述: 输出描述: 输入输出样例: 示例 1: 运行限制: 题解: 思路: 学习目标&#xff1a; 刷蓝桥杯题库日记 学习内容&#xff1a; 编号96题目Ex…...

OSPF多区域配置-新版(12)

目录 整体拓扑 操作步骤 1.基本配置 1.1 配置R1的IP 1.2 配置R2的IP 1.3 配置R3的IP 1.4 配置R4的IP 1.5 配置R5的IP 1.6 配置R6的IP 1.7 配置PC-1的IP地址 1.8 配置PC-2的IP地址 1.9 配置PC-3的IP地址 1.10 配置PC-4的IP地址 1.11 检测R5与PC1连通性 1.12 检测…...

华为---USG6000V防火墙web基本配置示例

目录 1. 实验要求 2. 配置思路 3. 网络拓扑图 4. USG6000V防火墙端口和各终端相关配置 5. 在USG6000V防火墙web管理界面创建区域和添加相应端口 6. 给USG6000V防火墙端口配置IP地址 7. 配置通行策略 8. 测试验证 8.1 逐个删除策略&#xff0c;再看各区域终端通信情况 …...

Ksher H5页面支付实例指导 (PHP实现)

背景 前两天&#xff0c;公司的项目&#xff0c;为了满足泰国客户的支付需求&#xff0c;要求使用 Ksher (开时支付) 对接任务突然就给了鄙人&#xff0c;一脸懵 … 通过了解客户的使用场景、以及参考官网指导 发现&#xff1a;Ksher支付最令人满意的便是 —— 提供了便捷的 支…...

https密钥认证、上传镜像实验

一、第一台主机通过https密钥对认证 1、安装docker服务 &#xff08;1&#xff09;安装环境依赖包 yum -y install yum-utils device-mapper-persistent-data lvm2 &#xff08;2&#xff09;设置阿里云镜像源 yum-config-manager --add-repo http://mirrors.aliyun.com/do…...

three.js使用精灵模型Sprite渲染森林

效果&#xff1a; 源码&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs" style"border: 1px solid red"></div><div class"box-right&quo…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

Java并发编程实战 Day 11:并发设计模式

【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天&#xff0c;今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案&#xff0c;它们不仅提供了优雅的设计思路&#xff0c;还能显著提升系统的性能…...