【数据结构与算法】之数组系列-20240115

在这里插入图片描述


这里写目录标题

  • 一、599. 两个列表的最小索引总和
  • 二、724. 寻找数组的中心下标
  • 三、面试题 16.11. 跳水板
  • 四、35. 搜索插入位置

一、599. 两个列表的最小索引总和

简单
假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。

示例 1:
输入:
list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”],
list2 = [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]
输出: [“Shogun”]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:
输入:
list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”],
list2 = [“KFC”, “Shogun”, “Burger King”]
输出: [“Shogun”]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”,它有最小的索引和1(0+1)。

list1 = [“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]
list2 = [“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]

思路:
1、获取两个list的相同元素交集
2、对元素交集构建索引和与元素列表的映射(可能答案不止一个)
3、排序返回索引和最小的元素列表

def func599(list1,list2):res=defaultdict(list)for char in set(list1) & set(list2):res[list1.index(char)+list2.index(char)].append(char)   #defaultdict(<class 'list'>, {3: ['KFC'], 1: ['Shogun'], 4: ['Burger King']})return min(res.items())list1= ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["KFC", "Shogun", "Burger King"]
print(func599(list1,list2))

特别注意:
d={1:‘a’,3:‘g’,5:‘u’}
print(d.items()) dict_items([(1, ‘a’), (3, ‘g’), (5, ‘u’)])
print(max(d.items())) (5, ‘u’)
print(min(d.items())) (1, ‘a’)

二、724. 寻找数组的中心下标

简单
给你一个整数数组 nums ,请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。

示例 1:
输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。
示例 2:

输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。
示例 3:

输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

def func724(nums):sum_left=0sum_right=sum(nums)for i in range(len(nums)):sum_right=sum_right-nums[i]if sum_left == sum_right:return isum_left+=nums[i]return -1
nums=[6,1,6]
res=func724(nums)
print(res)

三、面试题 16.11. 跳水板

简单
你正在使用一堆木板建造跳水板。有两种类型的木板,其中长度较短的木板长度为shorter,长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法,生成跳水板所有可能的长度。
返回的长度需要从小到大排列。

示例 1
输入:
shorter = 1
longer = 2
k = 3
输出: [3,4,5,6]
解释:
可以使用 3 次 shorter,得到结果 3;使用 2 次 shorter 和 1 次 longer,得到结果 4 。以此类推,得到最终结果。

思路:动态规划
最开始全是短木板(k*shorter),然后每次都把上一次的一个短木板变为长木板。

class Solution:def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:if not k:return []if shorter == longer:return [shorter * k]result = []for i in range(k+1):result.append(shorter * (k-i) + longer * i)return resultss=Solution()
shorter = 1
longer = 2
k = 3
print(ss.divingBoard(shorter,longer,k))

四、35. 搜索插入位置

简单
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

def func4(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1else:left = mid + 1return leftnums = [1, 3, 5, 6]
target = 5
print(func4(nums, target))

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

网络分流规则

现在的网络是越来越复杂。 有必要进行分流。 有一些geosite.dat是已经整理好的&#xff0c;包含许多的网站的分类&#xff1a; 分流规则&#xff1a; route规则 主要是: {"type": "field","outboundTag": "direct","domain&quo…

优雅草蜻蜓API大数据服务中心v1.0.4更新-加入蓝奏云直链解析·每日Bing·字数统计·今日油价·历史上的今天等接口

2024年1月13日优雅草蜻蜓API大数据服务中心v1.0.4更新-加入蓝奏云直链解析每日Bing字数统计今日油价历史上的今天等接口 优雅草api服务-大数据中心自12月29日推出以来截止2024年1月13日累计被调用次数为413次&#xff0c;共收录23个接口&#xff0c;截止前一日2024年1月12日当…

RSIC-V“一芯”学习笔记(一)——概述

考研的文章和资料之后想写的时候再写怕趴 文章目录 一、阶段设计二、环境、开发语言和工具三、最重要的两个观念四、处理器芯片设计五、处理器芯片设计包含很多软件问题六、处理器芯片的评价指标七、复杂系统的构建和维护八、专业世界观九&#xff0c;提问的艺术(提问模板)十、…

视频做成二维码查看?多格式视频二维码生成器的使用方法

现在音视频是工作和生活中经常需要使用的一种内容表现形式&#xff0c;很多人都通过这种方式来查看视频内容&#xff0c;比如产品介绍、使用说明、安装教程等。通过一个二维码就可以来承载视频内容&#xff0c;与传统的方式相比拥有更快的内容传播速度&#xff0c;简化用户获取…

江山易改本性难移之ZYNQ SDK QSPI固化bug及其解决方法

之前在Vivado2018.3通过QSPI方式固化程序时出现问题&#xff0c;显示flash擦除成功&#xff0c;但最后总是不能写入到flash中。 查资料发现从VIVADO 2017.3版本开始&#xff0c;Xilinx官方为了使Zynq-7000和Zynq UltraScale 实现流程相同&#xff0c;在QSPI FLASH使用上做了变化…

七、Qt 信号和槽

在QT4以上的版本&#xff0c;在窗体上用可以通过选中控件&#xff0c;然后点击鼠标右键单击按钮&#xff0c;选择“转到槽”。可以自动创建信号和槽。 选择clicked(),并点击 ok Qt Creator会给头文件和代码文件自动添加 这个按钮的单击事件&#xff08;信号和槽&#xff09;。 …

3.4 在开发中使用设计模式

现在&#xff0c;我们应该对设计模式的本质以及它们的组织方式有了初步的认识&#xff0c;并且能够理解ROPES过程在整体设计中的作用。通过之前章节对“体系结构”及其五个视图的探讨&#xff0c;我们打下了坚实的基础。初步了解了UML的基本构建模块后&#xff0c;我们现在可以…

响应式Web开发项目教程(HTML5+CSS3+Bootstrap)第2版 例4-1 表单

代码 <!doctype html> <html> <head> <meta charset"utf-8"> <title>表单</title> </head><body> <!--<form action"URL地址" method"提交方式" name"表单名称" /*编码“多部…

Linux 基于 rsync 实现集群分发脚本 xsync

一、rsync 简介 rsync&#xff08;remote synchronize&#xff09;是 Liunx/Unix 下的一个远程数据同步工具。它可以通过 LAN/WAN 快速同步多台主机间的文件和目录&#xff0c;并适当利用 rsync 算法&#xff08;差分编码&#xff09;以减少数据的传输。 rsync 算法并不是每一次…

Maven《一》-- 一文带你快速了解Maven

目录 &#x1f436;1.1 为什么使用Maven 1. Mavan是一个依赖管理工具 ①jar包的规模 ②jar包的来源问题 ③jar包的导入问题 ④jar包之间的依赖 2. Mavan是一个构建工具 ①你没有注意过的构建 ②脱离IDE环境仍需构建 3. 结论 &#x1f436;1.2 什么是Maven &#x…

笔试案例2

目录 一、笔试案例 二&#xff0c;思维导图 一、笔试案例 09&#xff09;查询学过「张三」老师授课的同学的信息 selects.*,c.cname,t.tname,sc.score from t_mysql_teacher t, t_mysql_course c, t_mysql_student s, t_mysql_score sc where t.tidc.cid and c.cidsc.cid and …

Gitlab-ci:从零开始的前端自动化部署

一.概念介绍 1.1 gitlab-ci && 自动化部署工具的运行机制 以gitlab-ci为例&#xff1a; (1) 通过在项目根目录下配置.gitlab-ci.yml文件&#xff0c;可以控制ci流程的不同阶段&#xff0c;例如install/检查/编译/部署服务器。gitlab平台会扫描.gitlab-ci.yml文件&…

力扣刷题(两数相加)

给你两个 非空 的链表&#xff0c;表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的&#xff0c;并且每个节点只能存储 一位 数字。 请你将两个数相加&#xff0c;并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外&#xff0c;这两个数都不会以 0 …

工作压力测试

每个职场人都会遇到工作压力&#xff0c;在企业人力资源管理的角度来看&#xff0c;没有工作压力是人力资源的低效&#xff0c;适当的工作压力可以促使员工不断进取&#xff0c;然而每个人的抗压能力是不同的&#xff0c;同样的工作量和工作难度&#xff0c;不同的人在面对相同…

《Git学习笔记:Git入门 常用命令》

1. Git概述 1.1 什么是Git&#xff1f; Git是一个分布式版本控制工具&#xff0c;主要用于管理开发过程中的源代码文件&#xff08;Java类、xml文件、html页面等&#xff09;&#xff0c;在软件开发过程中被广泛使用。 其它的版本控制工具 SVNCVSVSS 1.2 学完Git之后能做…

原子类-入门介绍和分类说明、基本类型原子类

Atomic翻译成中文是原子的意思。在化学上,我们知道原子是构成一般物质的最小单位,在化学 反应中是不可分割的。在我们这里Atomic是指一个操作是不可中断的。即使是在多个线程一起执 行的时候,一个操作一旦开始,就不会被其他线程干扰。 基本类型原子类 AtomicInteger:整…

代码随想录——回溯

系列文章目录 代码随想录——回溯 文章目录 系列文章目录概述组合组合组合III电话号码的字母组合组合总和组合总和II 分割分割回文串** 复原ip地址 子集子集子集II 概述 回溯的本质就是递归遍历&#xff0c;但在完成某一条路之后会撤回到上一层&#xff0c;然后重新选择另一条…

章鱼网络 2023 年全回顾|暨12月进展报告

2023年&#xff0c;章鱼网络轻装上阵&#xff0c;身处加密行业的低谷中砥砺前行。 12月17日&#xff0c;经过整整1年时间的开发和打磨&#xff0c;章鱼网络在重磅上线 Octopus 2.0&#xff0c;即 $NEAR Restaking 和 NEAR-IBC&#xff0c;获得了社区和市场的一致认可&#xff…

Elasticsearch 快速入门指南【总结记录】

本文将介绍一些基本概念&#xff0c;帮助您快速入门使用Elasticsearch。 一、概述 ES用来解决什么问题&#xff1f;Elasticsearch是解决海量数据&#xff08;已经存在的数据&#xff09;全文检索的不二只选。 Elasticsearch是一个基于Java语言开发&#xff0c;建立在开源搜索…

java SSM物业管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM物业管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和 数据库&#xff0c;系统主要采用B/…