虽然是简单题,但是有递归思想。
不断地将一维列表转化为二维列表进行操作(这样可以避免因为index的改变造成的混乱)
然后用flag进行计数,进行最大值和最小值的比较。
最后返回就行了,虽然肯定返回一个数字,不过还是‘nums[0]’来避免警告。
1 | 2293. 极大极小游戏 |
1 | class Solution: |
虽然是简单题,但是有递归思想。
不断地将一维列表转化为二维列表进行操作(这样可以避免因为index的改变造成的混乱)
然后用flag进行计数,进行最大值和最小值的比较。
最后返回就行了,虽然肯定返回一个数字,不过还是‘nums[0]’来避免警告。
1 | 2293. 极大极小游戏 |
1 | class Solution: |
2283.判断一个数的数字计数是否等于数位的值。
1 | class Solution: |
这道题读题读了好一会儿,意思就是按照index
来读取,index
要出现num[index]
次,1210就是说”0出现1次,”1出现2次,”2出现1次,”3出现0次。然后对num里的东西进行计数即可。
因为前两天都在做哈希表的练习,所以这道题一眼哈希表,再直接用Counter函数进行计数,比较一下,结束
思路历程:
1 | def rearrangeArray(self, nums: List[int]) -> List[int]: |
1 | class Solution: |
那天心血来潮做了一套小米的测开题,其中第一道就是计算1~n中1出现的次数。
力扣的题号是剑指offer 43
n是12的情况下,1 10 11 12中就出现了5次1。
因为那套题中选择题都是简单难度,所以很自然地就想用暴力算法破解。
但是拿到力扣中找相同的题的时候却发现标签是困难[汗颜R]。果不其然超时了[图2]。
然后当时其实也想过直接用数学方法计算,但奈何太懒了不想去找规律,[图三]是标答,感觉以后得沉下心来慢慢去做才形捏。
#力扣 #算法#力扣算法 #Python
错误答案:
1 | def countDigitOne(self, n: int) -> int: |
就是每天写一道题,然后写下能让自己看懂的题解吧!
新的一年已经过了5天了,就一次性写完这5天的吧。
首先是1801.1802.1803,这三天的每日一题其实是去年的一场高质量的周赛,连简单标签的也是普通的难度。
解法的话就是进行一个三角形的堆叠,当达到边界后停止增加(如果继续增加的话会导致超时) 。
当两边边界都达到后,直接在最上层平铺所有剩余砖块即可。
1 | 1802. 有界数组中指定下标处的最大值 |
1 | class Solution: |
Pyhton collection
包里 Counter()
可以对list里出现的元素进行计数,并且输出是字典。
比如nums=[1, 1, 1, 2, 2, 3]
对其Counter后的结果是Counter({1: 3, 2: 2, 3: 1})
。
value>3
的时候value=2
,就可以将大于2个的元素计数变成2个。Counter({1: 3, 2: 2, 3: 1})
变成Counter({1: 2, 2: 2, 3: 1})
后再对其elements进行list操作就可以得到改变后的列表了。由于题意中“输入数组是以「引用」方式传递的”,所以我们将nums清空再填入就好
1 | from collections import Counter # 导入包 |
复杂度分析
时间复杂度:O(n)
,其中 n
是数组的长度。我们最多遍历该数组一次。
空间复杂度:O(1)
。我们只需要常数的空间存储若干变量。
今天的每日一题太难了,于是自己找题做。今天的题是哈希表+滑动窗口算法,虽然感觉只用了滑动窗口算法。
1 |
|
这是一开始我的做法,虽然用了双指针,但是却没有那种灵活性,很空洞的感觉,很干巴巴的滑动。
以下@Lincoln@Lincoln 大佬的 做法,只做为一个记录自己看,不作为我的题解发表
1 | class Solution: |
看了Lincoln大佬的思路,非常清晰,记住了
这道题一开始是在手机上做的,直接用的是双哈希表,一个存元素,一个存index,当某个元素超过2个的时候判断是否存在某两个他们的index相减小于等于k的情况。因此时间复杂度是O(n^3)
。
1 | class Solution: |
看@宫水三叶宫水三叶的解法后,才想起来,这道题的目的是为了练习双指针在哈希表中的应用,TA的原话是整理题意:是否存在长度不超过的 k+1k + 1k+1 窗口,窗口内有相同元素。
1 | #整理题意:是否存在长度不超过的 k+1k + 1k+1 窗口,窗口内有相同元素。 |
Problem: 271. 字符串的编码与解码
[TOC]
第一反应是不是对字符串进行加密解密,但是读题后发现是将列表转化为字符串,然后第二部分对自己处理过的字符串转化回源列表。
列表可能有多个元素(由‘,’区分开的单词组),在每个元素中可能存在多个由空格隔开的单词。于是分开对list中的元素和空格进行处理。
''.join()
转换成字符串,return。Str = ''.join([Str, ' '])
,同理,读取到’\n’的时候就将Str添加到List中,并且将Str置空进行下一次的循环。时间复杂度:
添加时间复杂度, 示例: $O(n)$
空间复杂度:
添加空间复杂度, 示例: $O(n)$
1 |
|
6289.查询数组 Xor 美丽值。
这道题研究了很久,发现是一道数学题,但是又没想通透,因为不熟悉异或值。所以没有相出更好的解法。
首先是读题得知需要计(nums[i]|nums[j])&nums[k],因为ijk可以是数组里的任意值,所以用的三重for循环(肯定会超时),然后自己灵光了一点,也就一点,觉得i,j值互换的值是一样的,所以多加了一层判断(用的字典)。
1 | class Solution: |
今天出门的时候还一直在想怎么判断答案一样的情况,结果一看大@灵茶山艾府的解法,就一行,那没事了。
1 | class Solution: |
接着做,在网上搜了一下,原来如果两个值是一样的话求异或会抵消掉,比如A^B^A = B,所以用的append,remove来实现这个功能。最后for循环求异或值。
大佬代码还在研究ing