两道算法题

一、算法一

Amazon would like to enforce a password policy that when a user changes their password, the new password cannot be similar to the current one. To determine whether two passwords are similar, they take the new password, choose a set of indices and change the characters at these indices to the next cyclic character exactly once. Character 'a' is changed to 'b', 'b' to 'c' and so on, and 'z' changes to 'a'.The password is said to be similar if after applying the operation, the old password is a subsequence of the new password. The developers come up with a set of n password change requests, where newPasswords denotes the array of new passwords and oldPasswords denotes the array of old passwords. For each pair newPasswords[i] and oldPasswords[i], return "YES" if the passwords are similar, that is, newPasswords[i] becomes a subsequence of oldPasswords[i] after performing the operations, and "No" otherwise. Note: A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Example: the two lists of passwords are given as newPasswords = ["baacbab", "accdb", "baacba"], and oldPasswords = ["abdbc", "ach","abb"].

Consider the first pair: newPasswords[0]= "baacbab"and oldPasswords ="abdbc". Change "ac to "bd"at the 3rd and 4th positions, and "b"to "c" at the last position. The answer for this pair is YES.

The newPasswords[1]= "accdb" and oldPasswords = "ach". It is not possible to change the character of the new password to "h" which occurs in the old password, so there is no subsequence that matches. The answer for this pair is NO.

newPasswords[2] = "baacba" and oldPasswords = "abb". The answer for this pair is YES.

Return ["YES", "NO", YES"].

Function Description complete the function findSimilarities below.

findSimilarities has the following parameters:

  • string newPasswords[n]: newPasswords[i] represents the new password of the i-th pair
  • string oldPasswords[n]: oldPasswords[i] represents the old password of the i-th pair

returns

  • string[n]: the i-th string represents the answer to the i-th pair of passwords

constraints:

  • 1、1 <= n <= 10
  • 2、Sum of lengths of all passwords in array newPassword and array oldPassword does not exceed(2*10^5)
  • 3、|oldPasswords[i]| <= |newPasswords[i]|, for all i

算法思路是:遍历每一对oldPasswords[i]和newPasswords[i],判断经过上述的变换之后,oldPasswords[i]是否可以成为newPasswords[i]的子序列,注意这里是序列,而不是子串,由于题目中说了对newPasswords[i]的变换可以不是全部字符,而可以是部分字符,所以思路就是用双指针i,j,i指向newPasswords[k]的起始位置,j指向oldPasswords[k]的起始位置,然后依次向后遍历,每走一个位置判断newPassword. charAt(i) == oldPassword. charAt(j) 或者nextCyclicChar(newPassword.charAt(i))== oldPassword.charAt(j),条件满足则j++,i不论满不满足都执行加一操作,最后判断是否完整遍历了oldPassword,也就是返回时判断j==j oldPassword.length()是否成立。下面是java代码:

二、算法二

An Amazon fulfillment center receives a large number of orders each day. Each order is associated with a range of prices of items that need to be picked from the warehouse and packed into a box. There are n items in the warehouse, which are represented as an array items[n]. The value of items[i] represents the value of i-th item in the warehouse, and subsequently there are m orders. The start_index and end_ index for the i-th order are represented in the arrays start[i] and end[i]. Also start[i] and end[i] are 0-index based.

For each order, all the items are picked from the inclusive range from start[i] through end[i]. Given array items, start, end, and query. For each query[i], find the count of elements in the range with a value strictly less than query[i].

Example:

Given, n = 5, items = [1, 2, 5, 4, 5], m = 3, start = [0, 0, 1], end = [1, 2, 2] and query=[2, 4].

order Numberstart indexend indexpicked items
1st01[1, 2]
2nd02[1, 2, 5]
3rd12[2, 5]

over the 3 orders, the picked items are [1, 2, 1, 2, 5, 2, 5].

For the first query, 2 picked items have values less than 2. 5 picked items have values less than 4. Hence the answer is [2, 5].

Function Description: Complete the function getSmalleritems below.

getSmalleritems has the following parameter(s):

  • int items[n]: the value of each item

  • int start[m]: the start index for each order

  • int end[m]:the end index for each order

  • int query[q]: query values

Returns: long output[q]: the answer for each query, the number of picked items having a value strictly less than query[i].

Constraints:

  • 1≤ n ≤ 10^5

  • 1 ≤ items[i] ≤ 10^9, where 0 ≤ i < n

  • 0 ≤ m ≤ 10^5

  • 0 ≤ start[i] ≤ end[i] < n, where 0 ≤ i < m

  • 1 ≤ q ≤ 10^5

  • 1 ≤ query[i] ≤ 10^9,where 0 ≤ i < q

from typing import List
from collections import defaultdictdef getSmalleritems(items: List[int], start: List[int], end: List[int], query: List[int]) -> List[int]:# 创建一个字典来存储每个值的出现次数value_count = defaultdict(int)# 遍历所有订单,统计每个值的出现次数for i in range(len(start)):for j in range(start[i], end[i] + 1):value_count[items[j]] += 1# 对值进行排序sorted_values = sorted(value_count.keys())# 计算前缀和prefix_sum = [0]for value in sorted_values:prefix_sum.append(prefix_sum[-1] + value_count[value])# 处理查询result = []for q in query:# 使用二分查找找到小于q的最大值的索引left, right = 0, len(sorted_values)while left < right:mid = (left + right) // 2if sorted_values[mid] < q:left = mid + 1else:right = mid# 返回前缀和result.append(prefix_sum[left])return result# 测试代码
# items = [1, 2, 5, 4, 5]
# start = [0, 0, 1]
# end = [1, 2, 2]
# query = [2, 4]
# output = [2, 5]# items = [1, 2, 3, 2, 4, 1]
# start = [2, 0]
# end = [4, 0]
# query = [5, 3]
# output = [4, 2]items = [4, 4, 5, 3, 2]
start = [0, 1, 0, 2]
end = [1, 2, 3, 4]
query = [5, 4, 1]
# output = [8, 3, 0]print(getSmalleritems(items, start, end, query))

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/6232.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

嵌入式硬件电子电路设计(三)电源电路之负电源

引言&#xff1a;在对信号线性度放大要求非常高的应用需要使用双电源运放&#xff0c;比如高精度测量仪器、仪表等;那么就需要给双电源运放提供正负电源。 目录 负电源电路原理 负电源的作用 如何产生负电源 负电源能作功吗&#xff1f; 地的理解 负电压产生电路 BUCK电…

A019基于SpringBoot的校园闲置物品交易系统

&#x1f64a;作者简介&#xff1a;在校研究生&#xff0c;拥有计算机专业的研究生开发团队&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取&#xff0c;记得注明来意哦~&#x1f339; 赠送计算机毕业设计600…

字节青训-小S的倒排索引

问题描述 小S正在帮助她的朋友们建立一个搜索引擎。为了让用户能够更快地找到他们感兴趣的帖子&#xff0c;小S决定使用倒排索引。倒排索引的工作原理是&#xff1a;每个单词都会关联一个帖子ID的列表&#xff0c;这些帖子包含该单词&#xff0c;且ID按从小到大的顺序排列。 例…

2024 CSS - 基础保姆级教程系列一

CSS盒子模型 <style>.box {width: 200px;height: 100px;padding: 20px;} </style> <div class"box">盒子模型 </div><style>.box {width: 200px;height: 100px;padding: 20px;box-sizing: border-box;} </style> <div class&…

道品科技水肥一体化如何确定灌溉需水量呢?

在农业生产进程之中&#xff0c;持续攀升的生产成本&#xff0c;使农民苦不堪言。其一&#xff0c;水肥用量递增&#xff0c;致使成本上扬&#xff1b;其二&#xff0c;种植成效并不显著&#xff0c;所增经济收益颇为有限。另外&#xff0c;不科学的滴灌施肥亦破坏了农业环境架…

北航软件工程考研难度分析!

C哥专业提供——计软考研院校选择分析专业课备考指南规划 总体情况概述 北航软件工程学硕2024届呈现"稳中有降"态势。2024届复试线335分&#xff0c;较2023届上升25分&#xff0c;但较2022届下降10分。实际录取24人&#xff08;含实验室方向&#xff09;&#xff0c…

网页,app,微信小程序互相跳转

1.网页打开小程序 配置&#xff1a;登录小程序账号&#xff0c;找到账号设置&#xff0c;在基本设置中找到隐私与安全 在明文scheme中点击配置&#xff0c;填写要跳转的小程序页面地址即可 此处只展示一种实现方法&#xff0c;其他参照获取 URL Scheme | 微信开放文档 <a …

SQL,力扣题目1767,寻找没有被执行的任务对【递归】

一、力扣链接 LeetCode_1767 二、题目描述 表&#xff1a;Tasks ------------------------- | Column Name | Type | ------------------------- | task_id | int | | subtasks_count | int | ------------------------- task_id 具有唯一值的列。 ta…

【工具】在线一维码生成器

在国外网站上看到一款条形码生成器&#xff0c;它是开源的&#xff0c;很好用。但是访问慢&#xff0c;也不支持下载一维码&#xff0c; 于是我把他翻译了过来&#xff0c;加上下载条码功能&#xff0c;再加了配色&#xff0c;让界面看上来更丰富 一个可直接使用的工具&#x…

PHM技术应用:发电机线棒高温预警

目录 1 案例背景 1.1 事件描述 1.2 设备概况 1.3 事件过程 2 系统动力学模型 典型工况 故障树 潜在业务提升 3 异常预警规则模型 4 故障排查逻辑 5 小结 1 案例背景 1.1 事件描述 某发电厂的某台发电机组&#xff0c;在满功率工况下&#xff0c;因发电机下层线棒温…

Spark on YARN:Spark集群模式之Yarn模式的原理、搭建与实践

Spark 的介绍与搭建&#xff1a;从理论到实践-CSDN博客 Spark 的Standalone集群环境安装与测试-CSDN博客 PySpark 本地开发环境搭建与实践-CSDN博客 Spark 程序开发与提交&#xff1a;本地与集群模式全解析-CSDN博客 目录 一、Spark on YARN 的优势 &#xff08;一&#…

是时候用开源降低AI落地门槛了

过去三十多年&#xff0c;从Linux到KVM&#xff0c;从OpenStack到Kubernetes&#xff0c;IT领域众多关键技术都来自开源。开源技术不仅大幅降低了IT成本&#xff0c;也降低了企业技术创新的门槛。 那么&#xff0c;在生成式AI时代&#xff0c;开源能够为AI带来什么&#xff1f;…

机器学习—矩阵乘法的规则

有一个23的矩阵A&#xff0c;有两行三列&#xff0c;把这个矩阵的列想象成三个向量a1,a2,a3&#xff0c;用一个转置&#xff0c;把它相乘&#xff0c;首先&#xff0c;什么是转置&#xff0c;把一个矩阵进行行变列&#xff0c;列变行的操作&#xff0c;所以这些行现在是一个转置…

字节面试Java基础部分——HashMap

字节面试Java基础部分 面试管&#xff1a;Java应该很熟悉吧&#xff0c;接下来问你几个Java基础问题&#xff1a; HashMap 是什么样的数据结构 JDK 7 中&#xff0c;HashMap 由“数组链表”组成&#xff0c;数组是 HashMap 的主体&#xff0c;链表则是主要为了解决哈希冲突而…

Rust 力扣 - 2461. 长度为 K 子数组中的最大和

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 我们遍历长度为k的窗口&#xff0c;用一个哈希表记录窗口内的所有元素&#xff08;用来对窗口内元素去重&#xff09;&#xff0c;我们取哈希表中元素数量等于k的窗口总和的最大值 题解代码 use std::collecti…

《AI在企业战略中的关键地位:以微软和阿里为例》

内容概要 在当今商业环境中&#xff0c;人工智能&#xff08;AI&#xff09;的影响力如滔滔洪水&#xff0c;愈演愈烈。文章将揭示AI在企业战略中的崛起&#xff0c;尤其以微软和阿里巴巴为代表的企业&#xff0c;这两家科技巨头通过不同方式&#xff0c;将智能技术融入其核心…

线上lgb使用

1. 单机版模型 转 spark集群 打分 速度超快&#xff0c;十亿数据&#xff0c;十多分钟&#xff01;&#xff01;&#xff01; 1.1 主函数-主要获取模型路径 # codingutf-8 import pyspark.sql.functions as F from pyspark.sql import SparkSession from pyspark.sql.types …

Uniapp安装Pinia并持久化(Vue3)

安装pinia 在uni-app的Vue3版本中&#xff0c;Pinia已被内置&#xff0c;无需额外安装即可直接使用&#xff08;Vue2版本则内置了Vuex&#xff09;。 HBuilder X项目&#xff1a;直接使用&#xff0c;无需安装。CLI项目&#xff1a;需手动安装&#xff0c;执行yarn add pinia…

JVM基础

JRE&#xff1a;运行java字节码的环境。它是运行已编译java程序所需要的所有内容的集合&#xff0c;主要包括java虚拟机JVM和java基础类库&#xff08;class library&#xff09; JVM&#xff1a;是Java Virtual Machine的缩写&#xff0c;即Java虚拟机。‌它是一个虚构的计算…

vm虚拟机中添加网卡却在network-scripts文件找不到,解决方法

前言 进入network-scripts文件发现只有eth0网卡 ifconfig发现添加进去了 解决方法 nmcli d s #查看目前服务器中所有网卡 手动启用该接口 nmcli d connect eth1 重启网卡 systemctl restart network 解决问题