当前位置: 首页 > 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…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...