自用力扣刷题记录（Python，数组、字符串）

文章目录

• • 一. 数组
  • • 697
    • 448
    • 442
    • 41
    • 274
    • 453 最小操作次数使数组元素相等
    • 665 非递减数列
    • 283 移动的零
    • 118 杨辉三角形
    • 119 杨辉三角形2
    • 661 图片平滑器
    • 598 范围求和II
    • 419 夹板上的战舰
    • 189 旋转数组
    • 396 旋转函数
    • 54 螺旋矩阵
    • 59 螺旋矩阵II
    • 498 对角线遍历
    • 566 重塑矩阵
    • 48 旋转图像
    • 73 矩阵置零
    • 289 生命游戏
    • 303 区域和检索-数组不可变
    • 304 二维区域和检索-矩阵不可变
    • 238 除自身以外数组的乘积
  • 二、字符串
  • • 520 检测大写字母
    • 125 验证回文
    • 14 最长公共前缀
    • 434字符串中的单词数
    • 58 最后一个单词的长度
    • 344 反转字符串
    • 541 反转字符串II
    • 557 反转字符串中的单词III
    • 151 翻转字符串里的单词
    • 387 字符串中第一个唯一字符
    • 389 找不同
    • 383 赎金信
    • 242 有效的字母异位词
    • 49 字母异位词分组
    • 451 根据字符出现频率排序
    • 423 从英文中重建数字
    • 657 机器人能否返回原点
    • 551 学生出勤记录
    • 696 计数二进制子串
    • 467 环绕字符串中唯一的子字符串
    • 535 TinyURL 的加密与解密
    • 299 猜数字游戏
    • 412 Fizz Buzz
    • 506 相对名次
    • 539 最小时间差
    • 553 最优除法
    • 537 复数乘除法
    • 592 分数加减运算
    • 640 求解方程组
    • 38 外观数列
    • 443 压缩字符串
    • 8 字符串转换整数 (atoi)
    • 13 罗马数字转整形
    • 12 整数转罗马数字
    • 273 整数转换英文表示
    • 165 比较版本号
    • 481 神奇字符串
    • 392 判断子序列
    • 524 通过删除字母匹配到字典里最长单词
    • 521 最长特殊序列 Ⅰ
    • 522 最长特殊序列 II
    • 68
    • 28 实现 strStr()
    • 686 重复叠加字符串匹配
    • 459 重复的子字符串
    • 214 最短回文串
    • 5. 最长回文子串
    • 647. 回文子串

一. 数组

697

参考：
https://blog.csdn.net/qq_32424059/article/details/89390456?ops_request_misc=&request_id=&biz_id=102&utm_term=697.%20%E6%95%B0%E7%BB%84%E7%9A%84%E5%BA%A6%20python&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduweb~default-5-89390456.pc_search_result_before_js
中心思想：寻找度最大那个数，最早出现和最晚出现的下标

448

print (list(set(b).difference(set(a)))) # b中有而a中没有的

442

将数组本身的位置用作标记，如果标记变成负数
[4,3,2,7,8,2,3,1]标记后变成[-4,-3,-2,-7,8,2,3,1]

41

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
注意先set再排序，set不能保障元素位置。

class Solution(object):def firstMissingPositive(self, nums):""":type nums: List[int]:rtype: int"""temp = []for i in nums:if i > 0:temp.append(i)temp = list(set(temp))temp.sort()if len(temp) == 0:return 1elif temp[0] != 1:return 1else:i = 1for j in temp:if i != j:return ielse:i += 1return i

274

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。
这个概念有点难懂，栽到测试用例[1,3,1]上。
[1,3,1]的h数为1，有1篇论文被引用了至少1次（1or3），其余2篇被引用不超过1次（1,1）
先给数列降序，利用数的位置做，这个位置之前的都是引用至少比它高的。要考虑最高引用次数为0的情况。

citations.sort(reverse=True)ans = 0for i in range(len(citations)):ans = max(ans, min(i + 1, citations[i]))if citations[i] <= ans:breakreturn ans
————————————————
版权声明：本文为CSDN博主「长行」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Changxing_J/article/details/109815079

453 最小操作次数使数组元素相等

给定一个长度为 n 的 非空 整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。
思路：整体来看，假设操作k次，最小数增加了k次达到目标，sum+k*(n-1) = n*(k+min)，解出k = s-n*min

class Solution(object):def minMoves(self, nums):""":type nums: List[int]:rtype: int"""n = len(nums)sum_ = sum(nums)min_ = min(nums)ans = sum_ - n*min_return ans

665 非递减数列

给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
1.考虑只有一个数的情况
2.当某个数i不递减时，此时如果能符合题意：
①只有一个需要变动的i处
②i左边只有一个数，降低i-1的值
③i右边没数，增加i的值
④i左右两边都有数：
a。增加i的值
b。降低i-1的值

class Solution(object):def checkPossibility(self, nums):""":type nums: List[int]:rtype: bool"""n = len(nums)if n <= 1:return Truecount = 0for i in range(1,n):if nums[i] < nums[i-1]:if count == 1:return Falsecount += 1if not(#以下为可变更类型i in (1, n-1) or#左边只有一个数，或者右边没数nums[i-1] <=nums[i+1] or#能提高自身nums[i] >= nums[i-2]#能降低前一个):return Falsereturn True

283 移动的零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
这个太简单了

class Solution(object):def moveZeroes(self, nums):""":type nums: List[int]:rtype: None Do not return anything, modify nums in-place instead."""n = len(nums)i = 0while i < n:if nums[i] == 0:nums.pop(i)nums.append(0)n -= 1else:i += 1return nums

118 杨辉三角形

class Solution(object):def generate(self, numRows):""":type numRows: int:rtype: List[List[int]]"""tri = list()for i in range(numRows):temp =[]for j in range(i+1):temp.append(1)tri.append(temp)for i in range(2,numRows):for k in range(1,i):tri[i][k] = tri[i-1][k-1]+tri[i-1][k]return tri

119 杨辉三角形2

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
可以用118算出来后输出-1行，也可以滚动计算。
滚动计算要从后往前滚。

class Solution(object):def getRow(self, rowIndex):""":type rowIndex: int:rtype: List[int]"""tri = [1] * (rowIndex + 1)for i in range(2, rowIndex + 1):for k in range(i - 1, 0, -1):tri[k] += tri[k - 1]return tri

661 图片平滑器

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值
求平均，如果周围的单元格不足八个，则尽可能多的利用它们。
1.python2没有list.clear()
2.二维列表初始化不能用[[0]*m]*n
3.int(float)向下取整

class Solution(object):def imageSmoother(self, img):""":type img: List[List[int]]:rtype: List[List[int]]"""h = len(img)w = len(img[0])temp = list()ans = [[0 for j in range(w)] for i in range(h)]surround = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]for i in range(h):for j in range(w):temp.append(img[i][j])for k in range(8):next_x = i + surround[k][0]next_y = j + surround[k][1]if not (next_x<0 or next_x>=h or next_y<0 or next_y>=w):temp.append(img[next_x][next_y])ans[i][j] = int(sum(temp)/len(temp))temp = list()return ans

598 范围求和II

给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素M[i][j] 的值都增加 1。
直接找被操作最多的元素个数

class Solution(object):def maxCount(self, m, n, ops):""":type m: int:type n: int:type ops: List[List[int]]:rtype: int"""a = mb = nfor i in range(len(ops)):a = min(a,ops[i][0])b = min(b,ops[i][1])return a*b

419 夹板上的战舰

#给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 'X’表示，空位用 '.'表示。 你需要遵守以下规则：
给你一个有效的甲板，仅由战舰或者空位组成。
战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。
两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。
找头，二维数组从左到右从上到下遍历，如果前面和上面没有X就是新战舰。

class Solution(object):def countBattleships(self, board):""":type board: List[List[str]]:rtype: int"""m = len(board)n = len(board[0])count = 0for i in range(m):for j in range(n):if board[i][j] == ".":continueif i > 0 and board[i - 1][j] == "X":continueif j > 0 and board[i][j - 1] == "X":continuecount += 1return count

189 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
选处理k = k%len(nums)
1.一次挪一个，循环
2.新建一个数组，根据公式 (i+k)%len(nums)移动
3.先整体翻转，再局部翻转，代码如下

class Solution(object):def rotate(self, nums, k):""":type nums: List[int]:type k: int:rtype: None Do not return anything, modify nums in-place instead."""k = k % len(nums)self.reverse(nums, 0, len(nums) - 1)self.reverse(nums, 0, k - 1)self.reverse(nums, k, len(nums) - 1)def reverse(self, nums, start, end):while start < end:nums[start], nums[end] = nums[end], nums[start]start += 1end -= 1

396 旋转函数

示例:
A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

规律：
F(1)=F(0)-36+4+3+2=F(0)-36+sum(A)-6=F(0)+sum(A)-6*4
F(n)=F(n-1)+sum(A)-A[-n]*len(n)

class Solution:def maxRotateFunction(self, nums: List[int]) -> int:l = len(nums)temp = 0ans = []sum_ = sum(nums)for i in range(l):temp += nums[i] * ians.append(temp)for i in range(l - 1, -1, -1):temp = ans[l - i - 1] - nums[i] * l + sum_ans.append(temp)return max(ans)

54 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
仔细认真的判断边界条件，每走完一行/列就要缩一下边界。
注意矩阵为空的情况。

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:if not matrix or not matrix[0]: return []m = len(matrix)n = len(matrix[0])ans = []x = y = 0left = up = 0down = m - 1right = n - 1all_ = m * nnext_ = [[0, 1], [1, 0], [0, -1], [-1, 0]]con = 0while len(ans) != all_:ans.append(matrix[x][y])if con == 0 and y == right:con += 1up += 1elif con == 1 and x == down:con += 1right -= 1elif con == 2 and y == left:con += 1down -= 1elif con == 3 and x == up:con += 1left += 1con %= 4x += next_[con][0]y += next_[con][1]return ans

59 螺旋矩阵II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
跟54差不多，比54简单。

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:ans = [[0 for i in range(n)] for i in range(n)]up, down, left, right = 0, n - 1, 0, n - 1x = y = 0next_ = [[0, 1], [1, 0], [0, -1], [-1, 0]]con = 0count = 1while count != n ** 2 + 1:ans[x][y] = countif con == 0 and y == right:con += 1up += 1elif con == 1 and x == down:con += 1right -= 1elif con == 2 and y == left:con += 1down -= 1elif

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！