做网站只做前端可以用吗,备案号 不放在网站上,wordpress小说站数据,昆山网站建设Leetcode刷题笔记——数组与字符串篇
一、数组
第一题
Leetcode14#xff1a;最长公共前缀#xff1a;简单题 #xff08;详情点击链接见原题#xff09; 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀#xff0c;返回空字符串 当前…Leetcode刷题笔记——数组与字符串篇
一、数组
第一题
Leetcode14最长公共前缀简单题 详情点击链接见原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 当前字符串数组长度为0时则公共前缀为空直接返回令最长公共前缀ans的值为第一个字符串进行初始化遍历后面的字符串依次将其与ans进行比较两两找出公共前缀最终结果即为最长公共前缀如果查找过程中出现了ans为空的情况则公共前缀不存在直接返回
python代码解法:
class Solution:def longestCommonPrefix(self, strs: List[str]) - str:res strs[0] # 初始化strs中的第一个字符串为最长公共前缀for i in range(1, len(strs)):ans temp strs[i]for j in range(0, min(len(temp), len(res))):if temp[j] res[j]:ans temp[j]else:breakres ansif not ans: # 如果查找过程中出现了ans为空的情况则公共前缀不存在直接返回breakreturn res第二题
Leetcode977. 有序数组的平方简单题 详情点击链接见原题 给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序 解题思路借助额外的空间数组其实是有序的只不过负数平方之后可能成为最大数了那么数组平方的最大值就在数组两端不是左边就是右边不可能是中间 python代码解法:
class Solution:def sortedSquares(self, nums: List[int]) - List[int]:result [0] * len(nums)left, right 0, len(nums) - 1i rightwhile i 0:if nums[left] ** 2 nums[right] ** 2:result[i] nums[right] ** 2right - 1elif nums[left] ** 2 nums[right] ** 2:result[i] nums[left] ** 2left 1i - 1return result第三题
Leetcode48:旋转图像/面试题:旋转矩阵中等题 详情点击链接见原题 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像 class Solution:def rotate(self, matrix: List[List[int]]) - None:Do not return anything, modify matrix in-place instead.n len(matrix)# 一圈一圈的转,一共需要转 n // 2 圈# 注意循环不变量原则: 我是按照左闭右开的形式进行旋转,所以是 n - 1 - ifor i in range(n // 2):for j in range(i, n - i - 1):temp matrix[i][j] # 保存左上matrix[i][j] matrix[n - 1 - j][i] # 1.左下赋给左上matrix[n - 1 - j][i] matrix[n - 1 - i][n - 1 - j] # 2.右下赋给左下matrix[n - 1 - i][n - 1 - j] matrix[j][n - 1 - i] # 3.右上赋给右下matrix[j][n - 1 - i] temp # 4.保存起来的左上赋给右上第四题
Leetcode59. 螺旋矩阵 II中等题 详情点击链接见原题 给你一个正整数 n 生成一个包含 1 到 n² 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix python代码解法: # n 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9# n 6
1 2 3 4 5 6
20 21 22 23 24 7
19 32 33 34 25 8
18 31 36 35 26 9
17 30 29 28 27 10
16 15 14 13 12 11class Solution:def generateMatrix(self, n: int) - List[List[int]]:matrix [[0] * n for _ in range(n)]loop n // 2 # 确定迭代次数mid n // 2 # 当 n 为奇数的时候用于填充最后一个位置的空缺start_x, start_y 0, 0 # 在每轮迭代填充数据时的定位count 1# offset 1 填充最外圈# offset 2 填充次外圈# offset 3# offset ...for offset in range(1, loop 1): # offset用来表示每次循环的圈数控制,每轮填充时预留最后一个位置用于下轮填充的起始位置for c in range(start_y, n - offset): # 固定首行,变换列matrix[start_x][c] countcount 1for r in range(start_x, n - offset): # 固定尾列,变换行matrix[r][n - offset] countcount 1for c in range(n - offset, start_y, -1): # 固定尾行,变换列matrix[n - offset][c] countcount 1for r in range(n - offset, start_x, -1): # 固定首列,变换行matrix[r][start_y] countcount 1start_x 1start_y 1if n % 2 ! 0:matrix[mid][mid] countreturn matrix第四题进阶
Leetcode54螺旋矩阵中等题 详情点击链接见原题 给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素 python代码解法:
class Solution:def spiralOrder(self, matrix: List[List[int]]) - List[int]:up, down, left, right 0, len(matrix) - 1, 0, len(matrix[0]) - 1result []while True:for l_to_r in range(left, right 1): # 从左到右result.append(matrix[up][l_to_r])up 1if up down:breakfor u_to_d in range(up, down 1): # 从上到下result.append(matrix[u_to_d][right])right - 1if right left:breakfor r_to_l in range(right, left - 1, -1): # 从右到左result.append(matrix[down][r_to_l])down - 1if down up:breakfor d_to_u in range(down, up - 1, -1): # 从下到上result.append(matrix[d_to_u][left])left 1if left right:breakreturn result第五题
Leetcode189.轮转数组中等题 详情点击链接见原题 给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数 nums [1,2,3,4,5,6,7], k 3 1 2 3 | 4 5 6 7 step1先整体倒叙 7 6 5 | 4 3 2 1 step2将字符串分为两个部分再对两部分进行局部倒叙 5 6 7 | 1 2 3 4
python代码解法:
class Solution:def rotate(self, nums: List[int], k: int) - None:Do not return anything, modify nums in-place instead.if k len(nums):k % len(nums)def reverse(num, start, end):i, j start, endwhile i j:num[i], num[j] num[j], num[i]i 1j - 1reverse(nums, 0, len(nums) - 1)reverse(nums, 0, k - 1)reverse(nums, k, len(nums) - 1)第六题
Leetcode238. 除自身以外数组的乘积中等题 详情点击链接见原题 给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内 初始化数组res其中res[0] 1辅助变量temp 1计算res[i]的下三角各元素的乘积直接乘入res[i]计算 res[i]的上三角各元素的乘积记为 temp并乘入res[i]
python代码解法:
from typing import Listclass Solution:def productExceptSelf(self, nums: List[int]) - List[int]:res [1] * len(nums)temp 1for i in range(1, len(nums)):res[i] res[i - 1] * nums[i - 1]for i in range(len(nums) - 2, -1, -1):temp * nums[i 1]res[i] res[i] * tempreturn res第七题
Leetcode289. 生命游戏中等题 详情点击链接见原题 生命游戏 简称为 生命 是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机 python代码解法:
import copyclass Solution:def gameOfLife(self, board: List[List[int]]) - None:Do not return anything, modify board in-place instead. # 构造 board 的深拷贝matrix copy.deepcopy(board) # 面板上所有格子需要同时被更新你不能先更新某些格子然后使用它们的更新后的值再更新其他格子for r in range(len(board)):for c in range(len(board[0])):if matrix[r][c] 1:count 0for x, y in [(r, c - 1), (r, c 1), (r - 1, c), (r 1, c), (r - 1, c - 1), (r - 1, c 1),(r 1, c - 1), (r 1, c 1)]:if 0 x len(board) and 0 y len(board[0]):if matrix[x][y] 1:count 1if count 2 or count 3:board[r][c] 0 # 活细胞死亡else:count 0for x, y in [(r, c - 1), (r, c 1), (r - 1, c), (r 1, c), (r - 1, c - 1), (r - 1, c 1),(r 1, c - 1), (r 1, c 1)]:if 0 x len(board) and 0 y len(board[0]):if matrix[x][y] 1:count 1if count 3:board[r][c] 1 # 死细胞复活第八题
Leetcode27. 移除元素中等题 详情点击链接见原题 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度 python代码解法:
class Solution:def removeElement(self, nums: List[int], val: int) - int:slow_index, fast_index 0, 0while fast_index len(nums):if nums[fast_index] ! val:nums[slow_index] nums[fast_index]slow_index 1fast_index 1return slow_index二、字符串
第一题
Leetcode443压缩字符串中等题 详情点击链接见原题 给你一个字符数组 chars 请使用下述算法压缩 从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 如果这一组长度为 1 则将字符追加到 s 中。 否则需要向 s 追加字符后跟这一组的长度 第二题
Leetcode151. 反转字符串中的单词中等题 详情点击链接见原题 给你一个字符串 s 请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串 解题思路如下 如 the sky is blue
移除多余空格 the sky is blue将整个字符串反转 eulb si yks eht将每个单词反转 blue is the sky the
python代码解法:
class Solution:def reverseWords(self, s: str) - str:def remove_extra_space(strs): # 1.去除首尾以及中间多余的空格start, end 0, len(strs) - 1while s[start] :start 1while s[end] :end - 1array []while start end:temp s[start]if temp ! or array[-1] ! :array.append(temp)start 1return .join(array)st remove_extra_space(s)st st[::-1] # 2.反转整个字符串def reverse_str(str1):str1 list(str1)i, j 0, len(str1) - 1while i j:str1[i], str1[j] str1[j], str1[i]i 1j - 1return .join(str1)i 0start 0strs while i len(st):if st[i] :strs reverse_str(st[start:i]) # 反转单词strs # 在单词后面补充空格start i 1elif i len(st) - 1:strs reverse_str(st[start:i 1]) # 反转最后一个单词i 1return strs三、其他
第一题
Leetcode13. 罗马数字转整数简单题 详情点击链接见原题 罗马数字包含以下七种字符: I V X LCD 和 M 解题思路 贪心:我们每次尽量使用最大的数来表示,比如 1994 这个数一次选 1000, 900, 90, 4,会得到正确结果 MCMXCIV python代码解法:
class Solution:def romanToInt(self, s: str) - int:hash_map {I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000}pre_num hash_map[s[0]]total 0for i in range(1, len(s)):cur_num hash_map[s[i]]if pre_num cur_num: # 当小值在大值的左边,则减小值total - pre_numelse: # 当小值在大值的右边,则加小值total pre_numpre_num cur_numtotal pre_numreturn total第二题
Leetcode12. 整数转罗马数字中等题 详情点击链接见原题 罗马数字包含以下七种字符: I V X LCD 和 M python代码解法:
class Solution:def intToRoman(self, num: int) - str:hash_map {1000: M, 900: CM, 500: D, 400: CD, 100: C, 90: XC, 50: L, 40: XL, 10: X, 9: IX,5: V, 4: IV, 1: I}res for key in hash_map:if num // key ! 0:remain num // key # 提取最高位res hash_map[key] * remainnum % keyreturn res第三题
Leetcode1419. 数青蛙中等题 详情点击链接见原题 给你一个字符串 croakOfFrogs它表示不同青蛙发出的蛙鸣声字符串 croak 的组合。由于同一时间可以有多只青蛙呱呱作响所以 croakOfFrogs 中会混合多个 “croak” 请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目 遍历到c时看看有没有青蛙刚才发出了k的声音如果有则复用这只青蛙遍历到r时看看有没有青蛙发出c的声音如果有则复用否则产生一只新的青蛙从c开始蛙鸣(如果不是从c开始蛙鸣则终止)其余同理遍历结束后所有青蛙必须在最后发出 k 的声音如果有青蛙在最后发出的声音不是 k 则返回 -1返回counter[k]即最小的青蛙数目
python代码解法:
class Solution:def minNumberOfFrogs(self, croakOfFrogs: str) - int:counter Counter()previous {c: k, r: c, o: r, a: o, k: a}for i in croakOfFrogs:pre previous[i]if counter[pre]: # 遍历到i时,看看发出前一种声音的青蛙能不能复用counter[pre] - 1elif i ! c: # 如果不能复用则青蛙必须从c开始蛙鸣return -1counter[i] counter.get(i, 0) 1for ch in croa:if counter[ch] ! 0:return -1return counter[k]总结
本文介绍了面试中喜欢考的与数组和字符串相关的面试题型提供了每道题的 python解法面试加油冲~
