当前位置:   article > 正文

leetcode部分简单题题解

leetcode部分简单题题解

背景:

        今天翻看了之前练习的一些题。发现还是不够简洁。原来“温故而知新,可以为师矣”是真的。索性直接贴出源码来露个像,当个现眼包。

        以前注重先实现,后优化。现在来看。确实有不少可以采用更简单的策略来实现。这也是编码能力的进阶了。在一些复杂场景下,只有优化代码策略才能满足。

        letcode后面的一些题,开始有二叉树了,那种题,本地还调试不了。慢慢记录就停了。

desc: 145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 

  1. ""
  2. # Definition for a binary tree node.
  3. # class TreeNode:
  4. # def __init__(self, val=0, left=None, right=None):
  5. # self.val = val
  6. # self.left = left
  7. # self.right = right
  8. class Solution:
  9. def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
  10. listt=[]
  11. def rankt(root: Optional[TreeNode], listt:List[int]) -> List[int]:
  12. if not root:
  13. return
  14. if root.left:
  15. rankt(root.left,listt)
  16. if root.right:
  17. rankt(root.right,listt)
  18. listt.append(root.val)
  19. rankt(root,listt)
  20. return listt
  21. """

desc: 121. 买卖股票的最佳时机
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

  1. #2023-9-9 23:44:13 there is no better answer for this problem。 must be out of time including official answer
  2. def max_profit(prices=[]):
  3. lenth = len(prices)
  4. mark = 0
  5. for i in range(1, lenth):
  6. maxt = max(list(set(prices[i::])))
  7. mint = min(list(set(prices[0:i])))
  8. if maxt < mint:
  9. continue
  10. tmp = maxt - mint
  11. mark = tmp if tmp > mark else mark
  12. return mark
  13. def max_profit2(prices=[]):
  14. lenth = len(prices)
  15. mark = 0
  16. for i in range(1, lenth):
  17. maxt = max(list(set(prices[i::])))
  18. mint = min(list(set(prices[0:i])))
  19. if maxt < mint:
  20. continue
  21. tmp = maxt - mint
  22. mark = tmp if tmp > mark else mark
  23. return mark
  24. print(max_profit([1,2,4,11,7]))
  25. """

 没记录题目

  1. """
  2. start_time:
  3. end_time:
  4. desc: 模版
  5. def singleNumber(nums):
  6. nums.sort()
  7. lent = len(nums)-1
  8. t=[nums[k] for k in range(lent) if k % 2 == 0 and nums[k] != nums[k + 1]]
  9. return t[0] if t else nums[-1]
  10. def singleNumber2(nums):
  11. nums.sort()
  12. lent = len(nums)-1
  13. #result = [nums[k] for k,_ in enumerate(nums) if nums[k]!=nums[k+1]]
  14. for k in range(lent):
  15. if k%2 ==0 and nums[k]!=nums[k+1]:
  16. return nums[k]
  17. return nums[-1]
  18. print(singleNumber([1,3,2,2,1,3,4]))
  19. """

desc: 验证回文串

  1. """
  2. desc: 验证回文串
  3. def isPalindrome(s):
  4. s = [x.lower() for x in s if x.isalnum()]
  5. return s==s[::-1]
  6. print(isPalindrome("A man, a plan, a canal: Panama"))
  7. print(isPalindrome("raceacar"))
  8. """

desc: 94:二叉树的中序遍历

  1. """
  2. end_time:
  3. desc: 94:二叉树的中序遍历
  4. def iteration(root,res):
  5. if not root:
  6. return
  7. iteration(root.left,res)
  8. res.append(root)
  9. iteration(root.right,res):
  10. def vsxu(root):
  11. res=[]
  12. iteration(root,res)
  13. return res
  14. """

desc: 88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗?

  1. #pass
  2. def combine_two_list(nums1, nums2, m, n):
  3. i = 0
  4. j = 0
  5. while (i < m+n and j < n):
  6. if nums1[i]< nums2[j]:
  7. if i< m+j:
  8. i+=1
  9. else:
  10. nums1[i] = nums2[j]
  11. j+=1
  12. else:
  13. nums1.insert(i,nums2[j])
  14. nums1.pop(-1)
  15. i+=1
  16. j+=1
  17. def combine_two_list3(nums1, nums2, m, n):
  18. i = 0
  19. j = 0
  20. while (i < m+n and j < n):
  21. if nums1[i] != 0 and nums2[j] < nums1[i]:
  22. nums1[i], nums2[j] = nums2[j], nums1[i]
  23. i += 1
  24. elif nums1[i] == 0 and nums2[j]:
  25. nums1[i], nums2[j] = nums2[j], nums1[i]
  26. j += 1
  27. else:
  28. i += 1
  29. # 用了空间换时间。使用了切片。默认会copy一份nums来赋值。
  30. def combine_two_list2(nums1, nums2, m, n):
  31. nums1 = nums1[:m-n ] + nums2
  32. nums1.sort(reverse=False)
  33. nums1 = [1,2,3,0,0,0]
  34. nums2 = [2,5,6]
  35. combine_two_list(nums1, nums2, 3, 3)
  36. print(nums1)
  37. """

desc: 83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。

  1. """ 麻烦
  2. 二刷
  3. end_time:
  4. desc: 83. 删除排序链表中的重复元素
  5. 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
  6. val ,next
  7. class ListNode:
  8. def __init__(self, val=0, next=None):
  9. self.val = val
  10. self.next = next
  11. def del_repeat(head:ListNode,tmp=[]):
  12. if head is None:
  13. return None
  14. cur = head
  15. while cur.next:
  16. if cur.next.val == cur.val:
  17. cur.next = cur.next.next
  18. else:
  19. cur = cur.next
  20. return head
  21. print(del_repeat({"val":1,"next":{"val":1,"next":{"val":2,"next":{}}}}))
  22. """

desc: 70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
示例 1:
输入:n = 2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2:
输入:n = 3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

  1. """
  2. desc: 70. 爬楼梯
  3. 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
  4. 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
  5. 示例 1:
  6. 输入:n = 2
  7. 输出:2
  8. 解释:有两种方法可以爬到楼顶。
  9. 1. 1 阶 + 1 阶
  10. 2. 2 阶
  11. 示例 2:
  12. 输入:n = 3
  13. 输出:3
  14. 解释:有三种方法可以爬到楼顶。
  15. 1. 1 阶 + 1 阶 + 1 阶
  16. 2. 1 阶 + 2 阶
  17. 3. 2 阶 + 1 阶
  18. def n_n(N):
  19. if N<=1:
  20. return 1
  21. else:
  22. return N*n_n(N-1)
  23. def climb_stairs(stairs=0):
  24. num_method=0
  25. for i in range(stairs+1):
  26. if (stairs-i) % 2==0:
  27. if stairs-i !=0:
  28. tmp1= n_n(i+(stairs-i)//2)
  29. tmp2=(n_n((stairs-i)//2)*n_n(i))
  30. tmp = tmp1/tmp2
  31. print("tmp=",tmp,"i=",i)
  32. num_method+=tmp
  33. else:
  34. num_method+=1
  35. return int(num_method)
  36. print(climb_stairs(stairs=2))
  37. """

desc: 快速排序

如题,快速排序是很牛的一种排序方式。

  1. """
  2. end_time:
  3. desc: 快速排序。
  4. def quick_sort(alist,left=None,right=None):
  5. left=0 if not left else left
  6. right=len(alist)-1 if not right else right
  7. if left>=right or left<0 or right<=0:
  8. return
  9. pivot = alist[left]
  10. index=left+1
  11. while(index<=right):
  12. if alist[index]<pivot:
  13. alist[index],alist[left] = alist[left],alist[index]
  14. left+=1
  15. else:
  16. #index+=1
  17. pass
  18. index+=1
  19. quick_sort(alist,0,left-1)
  20. quick_sort(alist,left,right)
  21. pass
  22. a_list = [random.randint(1, 100) for x in range(10)]
  23. b_list= [5,1,3,4,8,1,7,2,5,9,6,1]
  24. quick_sort(b_list, None, None)
  25. print(b_list)
  26. #用空间换遍历,使用了额外的内存空间。
  27. def quick_sort2(alist, left=None, right=None):
  28. left = 0 if not left else left
  29. right = len(alist) - 1 if not right else right
  30. if left >= right:
  31. return alist
  32. index = left + 1
  33. slist = []
  34. llist = []
  35. while (index <= right):
  36. if alist[left] < alist[index]:
  37. llist.append(alist[index])
  38. else:
  39. slist.append(alist[index])
  40. index += 1
  41. left_list = quick_sort(slist, left=0, right=len(slist) - 1)
  42. right_list = quick_sort(llist, left=0, right=len(llist) - 1)
  43. return left_list+[alist[left]]+right_list
  44. pass
  45. def quick_sort2_x(a_list, left=None, right=None):
  46. if left > right:
  47. return
  48. left = 0 if not left else left
  49. right = len(a_list) - 1 if not right else right
  50. pivot = left
  51. left = left + 1
  52. while (left <= right):
  53. if a_list[left] > a_list[pivot]:
  54. while (a_list(right) < a_list(pivot) and right > left):
  55. right -= 1
  56. a_list[left], a_list[right] = a_list[right], a_list[left]
  57. left += 1
  58. right -= 1
  59. left += 1
  60. a_list[pivot], a_list[left] = a_list[left], a_list[pivot]
  61. quick_sort(a_list, None, left)
  62. quick_sort(a_list, left + 1, None)
  63. pass
  64. """

desc: 69. x 的平方根
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

  1. """
  2. end_time:
  3. desc: 69. x 的平方根
  4. 给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
  5. 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
  6. 注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
  7. 示例 1:
  8. 输入:x = 4
  9. 输出:2
  10. 示例 2:
  11. 输入:x = 8
  12. 输出:2
  13. 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
  14. def squre_root(x):
  15. pass
  16. # 法1:遍历。x越大,耗时越久。
  17. def squre_root1(x):
  18. if x in [0, 1]:
  19. return x
  20. for y in range(2, 2 + x // 2):
  21. if y * y > x:
  22. return y - 1
  23. return -1
  24. pass
  25. print(squre_root(1))
  26. print(squre_root(2))
  27. print(squre_root(4))
  28. print(squre_root(8))
  29. """

两种解法。28min分钟。内存消耗都比较大。24%胜率在内存。
desc: 66. 加一
 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入:digits = [1,2,3]
输出:[1,2,4]
解释:输入数组表示数字 123。
示例 2:
输入:digits = [4,3,2,1]
输出:[4,3,2,2]
解释:输入数组表示数字 4321。
示例 3:

输入:digits = [0]
输出:[1]

  1. """
  2. 两种解法。28min分钟。内存消耗都比较大。24%胜率在内存。
  3. desc: 66. 加一
  4. 给定一个由 整数 组成的 非空 数组所表示的非负整数,在该数的基础上加一。
  5. 最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
  6. 你可以假设除了整数 0 之外,这个整数不会以零开头。
  7. 示例 1:
  8. 输入:digits = [1,2,3]
  9. 输出:[1,2,4]
  10. 解释:输入数组表示数字 123。
  11. 示例 2:
  12. 输入:digits = [4,3,2,1]
  13. 输出:[4,3,2,2]
  14. 解释:输入数组表示数字 4321。
  15. 示例 3:
  16. 输入:digits = [0]
  17. 输出:[1]
  18. def devide_number(int_d):
  19. if int_d // 10 == 0:
  20. return [int_d]
  21. return devide_number(int_d // 10) + [int_d % 10]
  22. # if int_d//10 !=0:
  23. # return devide_number(int_d)+ list[int_d//10]
  24. # return list[int_d]
  25. def add_one(digits=[]):
  26. len_d = len(digits) # 123,3
  27. origin_d = 0
  28. for k, x in enumerate(digits):
  29. origin_d += x * 10 ** (len_d - 1 - k)
  30. arm_d = origin_d + 1
  31. return devide_number(arm_d)
  32. def plusOne(digits=[]):
  33. len_d = len(digits) # 123,3
  34. origin_d = 0
  35. for k, x in enumerate(digits):
  36. origin_d += x * 10 ** (len_d - 1 - k)
  37. arm_d = origin_d + 1
  38. return [int(x) for x in str(arm_d)]
  39. print(add_one([1, 2, 3]))
  40. print(add_one([4, 3, 2, 1]))
  41. print(add_one([0]))
  42. """


desc: 给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
示例 1:
输入:s = "Hello World"
输出:5
解释:最后一个单词是“World”,长度为5。
示例 2:
输入:s = "   fly me   to   the moon  "
输出:4
解释:最后一个单词是“moon”,长度为4。
示例 3:
输入:s = "luffy is still joyboy"
输出:6
解释:最后一个单词是长度为6的“joyboy”。
提示:

1 <= s.length <= 104
s 仅有英文字母和空格 ' ' 组成
s 中至少存在一个单词
 

  1. """
  2. desc: 给你一个字符串 s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
  3. 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
  4. 示例 1:
  5. 输入:s = "Hello World"
  6. 输出:5
  7. 解释:最后一个单词是“World”,长度为5。
  8. 示例 2:
  9. 输入:s = " fly me to the moon "
  10. 输出:4
  11. 解释:最后一个单词是“moon”,长度为4。
  12. 示例 3:
  13. 输入:s = "luffy is still joyboy"
  14. 输出:6
  15. 解释:最后一个单词是长度为6的“joyboy”。
  16. 提示:
  17. 1 <= s.length <= 104
  18. s 仅有英文字母和空格 ' ' 组成
  19. s 中至少存在一个单词
  20. def length_of_last_word(s):
  21. return len(s.strip().split(" ")[-1])
  22. print(length_of_last_word("Hello World"))
  23. print(length_of_last_word(" fly me to the moon "))
  24. print(length_of_last_word("luffy is still joyboy"))
  25. """

number:35. 搜索插入位置
desc: 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

  1. """
  2. number:35. 搜索插入位置
  3. desc: 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
  4. 请必须使用时间复杂度为 O(log n) 的算法。
  5. def search_insert_position2(nums=[], target=None):
  6. for k, x in enumerate(nums):
  7. if x == target:
  8. return k
  9. elif x > target:
  10. return k
  11. else:
  12. continue
  13. return len(nums)
  14. pass
  15. def search_insert_position(nums=[], target=None):
  16. # 内存使用
  17. k = len(nums)
  18. for x in range(k):
  19. if nums[x] == target:
  20. return x
  21. elif nums[x] > target:
  22. return x
  23. return k
  24. def search_insert_position3(nums=[], target=None):
  25. # 内存使用最小,击败92.61%的内存python3用户。
  26. tmp = [k for k, v in enumerate(nums) if v >= target]
  27. if not tmp:
  28. return len(nums)
  29. else:
  30. return tmp[0]
  31. """

desc: 有效的括号,g给定一个只包括(),{},[]的字符串 s ,判断字符串是否有效
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合
2、左括号必须以正确的顺序闭合
3、每个右括号都有一个对应的相同类型的左括号。
test= (),()[]{}, (], ([)], )]([

评价:第一批次处理很快,时间少于20分钟。但是处理两个较复杂的场景时调试耗时较多。超过40分钟

  1. """
  2. desc: 有效的括号,g给定一个只包括(),{},[]的字符串 s ,判断字符串是否有效
  3. 有效字符串需满足:
  4. 1、左括号必须用相同类型的右括号闭合
  5. 2、左括号必须以正确的顺序闭合
  6. 3、每个右括号都有一个对应的相同类型的左括号。
  7. test= (),()[]{}, (], ([)], )]([
  8. 评价:第一批次处理很快,时间少于20分钟。但是处理两个较复杂的场景时调试耗时较多。超过40分钟
  9. def enable_bracket(strs):
  10. # 通过偶数判断是否成对,快速判断有效
  11. if len(strs) % 2 != 0:
  12. return False
  13. # 符合区分判断 周期特长X
  14. # 通过3个计数来判断,+1,-1。小于0时则false 正解
  15. count_s_bra = 0
  16. count_m_bra = 0
  17. count_l_bra = 0
  18. # 需要将记录最后一个add 或者reduce的符号改为 顺序存所有的符号
  19. add_sign_list = []
  20. reduce_sign_list = []
  21. for x in strs:
  22. if count_l_bra < 0 or count_m_bra < 0 or count_s_bra < 0:
  23. return False
  24. if reduce_sign_list != []:
  25. if add_sign_list == []:
  26. return False
  27. rs = reduce_sign_list.pop(-1)
  28. if rs == add_sign_list[-1]:
  29. add_sign_list = add_sign_list[:-1]
  30. else:
  31. return False
  32. if x == "(":
  33. count_s_bra += 1
  34. add_sign_list.append(1)
  35. elif x == ")":
  36. count_s_bra -= 1
  37. reduce_sign_list.append(1)
  38. elif x == "[":
  39. count_m_bra += 1
  40. add_sign_list.append(2)
  41. elif x == "]":
  42. count_m_bra -= 1
  43. reduce_sign_list.append(2)
  44. elif x == "{":
  45. count_l_bra += 1
  46. add_sign_list.append(3)
  47. elif x == "}":
  48. count_l_bra -= 1
  49. reduce_sign_list.append(3)
  50. else:
  51. print("字符串内部存在非法字符")
  52. return False
  53. if count_l_bra != 0 or count_m_bra != 0 or count_s_bra != 0:
  54. return False
  55. else:
  56. return True
  57. print(enable_bracket("()"))
  58. print(enable_bracket("()[]{}"))
  59. print(enable_bracket("(]"))
  60. print(enable_bracket("([)]"))
  61. print(enable_bracket(")](["))
  62. print(enable_bracket("(([]){})"))
  63. print(enable_bracket("[([]])"))
  64. """

 desc: 14 最长公共前缀,查找字符串最长公共前缀
strs=["flower","flow","flight"]
输出:"f1"

  1. """
  2. desc: 14 最长公共前缀,查找字符串最长公共前缀
  3. strs=["flower","flow","flight"]
  4. 输出:"f1"
  5. def common_str(strs):
  6. # 判空:
  7. if not strs:
  8. return ""
  9. # 以最短字符串长度进行遍历,相似则计数+1
  10. min_len = len(strs[0])
  11. for x in strs:
  12. if len(x) < min_len:
  13. min_len = len(x)
  14. times = -1
  15. end_flag=0
  16. for i in range(0, min_len):
  17. value = strs[0][i]
  18. if end_flag == 1:
  19. i-=1
  20. times=i- 1
  21. break
  22. times = i
  23. for x in strs:
  24. if x[i] != value:
  25. end_flag = 1
  26. times = times-1
  27. break
  28. if times == -1:
  29. return ""
  30. else:
  31. # 以结果计数,进行切片返回
  32. return strs[0][:times+1]
  33. strs = ["fltoweradfadf", "fltoweadfad", "fltoweiwght"]
  34. print(common_str(strs))
  35. """

 desc: 一个字符串,求第一个不重复值的下标

  1. """
  2. desc: 一个字符串,求第一个不重复值的下标
  3. def mt_test(test:str):
  4. #test:待测字符串
  5. #第一步:判断为空
  6. if len(test)<1:
  7. return -1
  8. #转换类型
  9. list_test = list(test)
  10. result ={}
  11. #第二步:统计字段个数
  12. for i in list_test:
  13. if i not in result.keys():
  14. result[i] = 1
  15. else:
  16. result[i] += 1
  17. #第三步:
  18. aim = [x for x in result.keys() if result[x] == 1]
  19. tmp_k = -1
  20. for k, v in enumerate(test):
  21. if v == aim[0]:
  22. tmp_k = k
  23. return tmp_k
  24. test = "abcabcdeefg"
  25. print(mt_test(test))
  26. print(mt_test(""))
  27. print(mt_test("adjfklacasnihcuwejccjawoeuirsbncjnajksd"))
  28. print(mt_test([]))
  29. print(mt_test(123))
  30. """

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/685022
推荐阅读
相关标签
  

闽ICP备14008679号