IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 力扣每日一题(四十七——统计道路上的碰撞次数) -> 正文阅读

[数据结构与算法]力扣每日一题(四十七——统计道路上的碰撞次数)

仅以此纪录每日LeetCode所刷题目。

题目描述:

示例:

??

思路:

这道题一开始的想法是使用模拟来解答,但是如果我们遇到'RRRRL'这种情况,我们在判断‘RL’相撞之后还需要回退到前面,因为前面的'RRRR'也有相撞,因此模拟方法相当麻烦,我们换一种思路。首先,如果directions串的前n个字符是'L',那么他们不会发生碰撞,我们可以将其剔除;同理如果directions串的后n个字符是'R',那么他们也不会发生碰撞,我们可以将其剔除。此时剩余的directions串中,一定会发生碰撞(除非串中全是'S')。此时,我们即可使用directions的长度,减去其中'S'字符的数量,就可以得到碰撞的次数了。最后还有两种特殊情况,即字符串中全是'R'或者全是'L',这个时候我们返回0即可。

代码:

class Solution:
    def countCollisions(self, directions: str) -> int:
        left = 0
        right = 0
        for i in range(len(directions)):
            if directions[i] == 'R':
                left = i
                break
        d1 = directions[::-1]
        for j in range(len(directions)):
            if d1[j] == 'L':
                right = j
                break
        right = len(d1) - right
        if left == right:
            return 0
        directions = directions[left:right]
        if len(directions) == 1:
            return 0
        count = len(directions)
        print
        for i in range(len(directions)):
            if directions[i] == 'S':
                count -= 1
        return count

题目描述:

示例:

?

思路:

这道题在做题的时候我写的方法都超时了,之后想到自己是没有考虑pattern中的两个字符串都相同的情况。因此我们需要首先讨论这两个字符相同的情况。因为字符相同,我们及其放在任何位置都可以,只需要求出原来的text串中pattern的数量即可。讨论第二种情况,此时我们需要分别求出text串中pattern[0]、pattern[1]的数目,之后取max(sum_a, sum_b)来判断应该放置a在前面还是b在后面,而遍历的时候我们同时可以得到pattern串的数目。

代码:

class Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        a, b = pattern[0], pattern[1]

        #相同的时候直接计算
        if a == b:
            s = text.count(a)
            return (s*s +s)//2

        sum_a, sum_b, ans = 0, 0, 0
        for n in text:
            if n == a:
                sum_a += 1
            elif n == b:
                sum_b += 1
                ans += sum_a

        #可以选择放一个a在最前,也可以选择放一个b在最后
        return max(sum_a, sum_b) + ans

题目描述:

?

示例:

?

思路:

这道题就是求列表中存在多少个数小于前面的数同时小于后面的数(我们称之为谷),存在多少个数大于前面的数同时大于后面的数(我们称之为峰)。首先我们应该将列表中相邻的相同的数去掉,只留下相同数中的一个即可。之后我们遍历列表,求出峰和谷的数量即可得到答案。

代码:

class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        num = [nums[0]]
        for j in range(len(nums)-1):
            if nums[j] != nums[j+1]:
                num.append(nums[j])
        if len(num) == 0:
            num.append(nums[0])
        if nums[-1] != num[-1]:
            num.append(nums[-1])
        if len(num) < 3:
            return 0
        count = 0
        for i in range(1,len(num)-1):
            if num[i-1]<num[i] and num[i]>num[i+1]:
                count += 1
            if num[i-1]>num[i] and num[i]<num[i+1]:
                count += 1
        return count
            

题目描述:

示例:

?

思路:

这道题我们直接使用字典存储,数字作为kay,数字的数量作为value。之后遍历value,存在奇数value即返回False,遍历完成之后即返回True。

代码:

class Solution:
    def divideArray(self, nums: List[int]) -> bool:
        dict1 = {}
        for i in nums:
            if i in dict1:
                dict1[i] += 1
            else:
                dict1[i] = 1
        for i in dict1.values():
            if i%2 != 0:
                return False
        return True

?

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-03-22 20:49:54  更:2022-03-22 20:53:15 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 11:31:58-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码