小白学习打卡03

出错

Python报错 invalid character in identifier： 措施： 说明出现了无效字符 一般都是打入了中文字符 改一下或者重新敲这一行Python 报错 IndentationError: unindent does not match any outer indentation level 措施： 最常见的原因是，的确没有对齐；可以用Notepad++ 视图——显示——显示空格和制表符 新的Python语法，是不支持的代码对齐中，混用TAB和空格的 设置——首选项——语言——以空格取代TABnotepad++ 运行Python文件时，显示找不到文件 措施： 在输入文件名前 加入Python Python Hello.py

题目

以下题目来自于Leetcode

1. 最长有效括号

题目描述

输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

思路：

定义长度 — 循环—找左括号数量 --找右括号数量 —取最小值

Class Solution: def longvalidParentheses(self, s:str)->int: len=s.length while(i<len): if(t=="("): count0=count0+1 else: count1=count1+1 if(count0<count1): return count0 else: return count1

反思

若是"))()))" 这样就没有办法正确判断了

正确解答

等待匹配的左括号索引、充当“分隔符”的右括号索引。后者入栈因为：当左括号匹配光了，栈还需要留一个“垫底”的“参照物” class Solution: def longestValidParentheses(self, s: str) -> int: maxlen = 0 stack = [-1] for i in range(len(s)): if s[i] == “(”: stack.append(i) continue del stack[-1] if stack == []: stack.append(i) else: maxlen = max(maxlen,i-stack[-1]) return maxlen 作者：hyj8

2.搜索旋转排序数组

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

思路

循环 找目标值 找到返回index 找不到 返回-1

解答

class Solution: def search(self, nums: List[int], target: int) -> int: for i in range(len(nums)): if(nums[i]==target): return i else: return -1

运行成功 不过解答错误

反思

根据时间复杂度 只能选择二分查找 可以具体到这个例子的数值 进行分析

正确解答

class Solution: def search(self, nums: List[int], target: int) -> int: if not nums: return -1 l, r = 0, len(nums) - 1 while l <= r: mid = (l + r) // 2 if nums[mid] == target: return mid if nums[0] <= nums[mid]: if nums[0] <= target < nums[mid]: r = mid - 1 else: l = mid + 1 else: if nums[mid] < target <= nums[len(nums) - 1]: l = mid + 1 else: r = mid - 1 return -1 作者：LeetCode-Solution