力扣刷题

二分查找法

二分查找法又称折半查找法。

优点:比较次数少,查找速度快,平均性能好;

缺点:要求待查表为有序表,且插入删除困难。

因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较

如果两者相等,则查找成功

否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字

则进一步查找前一子表

否则进一步查找后一子表

重复以上的过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功

![](C:\Users\py\Pictures\Saved Pictures\捕获.JPG)

给定一个只包含小写字母的有序数组letters 和一个目标字母 target,寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。举个例子,如果目标字母target = 'z' 并且有序数组为 letters = ['a', 'b'],则答案返回 'a'

示例:

输入:
letters = ["c", "f", "j"]
target = "a"
输出: "c" 输入:
letters = ["c", "f", "j"]
target = "c"
输出: "f" 输入:
letters = ["c", "f", "j"]
target = "d"
输出: "f" 输入:
letters = ["c", "f", "j"]
target = "g"
输出: "j" 输入:
letters = ["c", "f", "j"]
target = "j"
输出: "c" 输入:
letters = ["c", "f", "j"]
target = "k"
输出: "c"
注: letters长度范围在[2, 10000]区间内。
letters 仅由小写字母组成,最少包含两个不同的字母。
目标字母target 是一个小写字母。

力扣中实现的代码:*

class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
return letters[bisect.bisect(letters, target) - len(letters)] class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
return letters[bisect.bisect(letters, target) % len(letters)]

运行结果:

输入
["c","f","j"]
"a"
输出
"c"
预期结果
"c"

最短完整词

如果单词列表(words)中的一个单词包含牌照(licensePlate)中所有的字母,那么我们称之为完整词。在所有完整词中,最短的单词我们称之为最短完整词。

单词在匹配牌照中的字母时不区分大小写,比如牌照中的 "P" 依然可以匹配单词中的 "p" 字母。

我们保证一定存在一个最短完整词。当有多个单词都符合最短完整词的匹配条件时取单词列表中最靠前的一个。

牌照中可能包含多个相同的字符,比如说:对于牌照 "PP",单词 "pair" 无法匹配,但是 "supper" 可以匹配。

示例 1:

输入:licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出:"steps"
说明:最短完整词应该包括 "s"、"p"、"s" 以及 "t"。对于 "step" 它只包含一个 "s" 所以它不符合条件。同时在匹配过程中我们忽略牌照中的大小写。

示例 2:

输入:licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
输出:"pest"
说明:存在 3 个包含字母 "s" 且有着最短长度的完整词,但我们返回最先出现的完整词。

注意:

牌照(licensePlate)的长度在区域[1, 7]中。
牌照(licensePlate)将会包含数字、空格、或者字母(大写和小写)。
单词列表(words)长度在区间 [10, 1000] 中。
每一个单词 words[i] 都是小写,并且长度在区间 [1, 15] 中。

class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
words.sort(key=len)
licensePlate=licensePlate.lower()
d=collections.defaultdict(int)
for c in licensePlate:
if c.isalpha():
d[c]+=1
for s in words:
t=d.copy()
for c in s:
if c in t:
t[c]-=1
if t[c]==0:
t.pop(c)
if not t:
return s
nums = [1,6,1,0]
r = max(nums)
index=0
for i in range(len(nums)):
if r!=nums[i] and r<2*nums[i]:
print(-1)
if r==nums[i]:
index=i
print(index)

查找至少是其他数字两倍的最大数

在一个给定的数组nums中,总是存在一个最大元素 。

查找数组中的最大元素是否至少是数组中每个其他数字的两倍。

如果是,则返回最大元素的索引,否则返回-1。

示例 1:

输入: nums = [3, 6, 1, 0]
输出: 1
解释: 6是最大的整数, 对于数组中的其他整数,
6大于数组中其他元素的两倍。6的索引是1, 所以我们返回1.

示例 2:

输入: nums = [1, 2, 3, 4]
输出: -1
解释: 4没有超过3的两倍大, 所以我们返回 -1.

提示:

nums 的长度范围在[1, 50].
每个 nums[i] 的整数范围在 [0, 100].

力扣中代码的实现

class Solution:
def dominantIndex(self, nums: List[int]) -> int:
r = max(nums)
index=0
for i in range(len(nums)):
if r!=nums[i] and r<2*nums[i]:
return -1
if r==nums[i]:
index=i
return index

运行结果:
输入
[0,0,0,1]
输出
3
预期结果
3

pycharm中代码实现效果:

nums = [1, 2, 3, 4]
r = max(nums)
index=0
for i in range(len(nums)):
if r!=nums[i] and r<2*nums[i]:#判断比较元素
print(-1)#返回值
if r==nums[i]:
index=i
print(index)# 最大元素索引位置

运行结果:

-1

3

使用最小花费爬楼梯

数组的每个索引做为一个阶梯,第 i个阶梯对应着一个非负数的体力花费值 costi

每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始,然后走两步即可到阶梯顶,一共花费15。
示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始,逐个经过那些1,跳过cost[3],一共花费6。
注意:

cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型,范围为 [0, 999]。

力扣中代码运行

class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
f = [cost[0], cost[1]]
for i in range(2, len(cost)):
f.append(cost[i] + min(f[i-1], f[i-2]))
return min(f[-1], f[-2])

运行结果:

输入
[0,0,0,0]
输出
0
预期结果
0

最新文章

  1. qt creator 使用Ui文件的问题
  2. hbase集群在启动的时候找不到JAVA_HOME的问题
  3. [2014.5.22][UBUNTU]Ubuntu与Windows系统时间不同步的问题
  4. Google面试题之100层仍两个棋子
  5. 【转载】CANoe 入门 Step by step系列(二)CAPL编程
  6. chrome开发工具指南(四)
  7. zabbix安装步骤
  8. [Python][小知识][NO.4] wxPython 字体选择对话框(O.O 不知道放到那里就放到这个分类的)
  9. Ajax提交用FormData()上传文件
  10. 我的Java之旅 第六课 JAVA WEB 请求与响应
  11. ubuntu 程序后台运行几个方法
  12. strcpy和memcpy的差别
  13. 敏捷Scrum框架最全总结! [转载]
  14. jq插件封装格式
  15. TCP三次握手,四次分手
  16. Word发布到cnblogs文章
  17. 代理模式:利用JDK原生动态实现AOP
  18. H3C笔试题目
  19. python并发编程-线程池
  20. Zabbix的基本安装配置

热门文章

  1. drools跳转出现错误问题(400)
  2. Leetcode950. Reveal Cards In Increasing Order按递增顺序显示卡牌
  3. 为互联网业务而生:阿里云全球首发云Cassandra服务!
  4. Vue的Ajax(vue-resource/axios)
  5. CSS3 进阶
  6. ie浏览器将网页转成pdf
  7. VS2010中Cocos2d-x中文乱码问题
  8. mysql api 不支持source命令
  9. css 始终显示滚动条,内容超出显示有滑块的滚动条,内容没有超出显示空的滚动条
  10. mybatis学习:mybatis的注解开发CRUD操作