2021-10-29
路径交叉
给你一个整数数组 distance 。
从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。
判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。
题解
本题看似是一个hard的一个难度，但是如果我们弄懂了它的原理这个就是一个esay的题，本题难就难在这个题他是比较偏向数学分类较多一些，它分为好几种情况相交，我把这些相交的情况都给写在本子上了，大家可以看看！！！
代码
class Solution: def isSelfCrossing(self, distance: List[int]) -> bool: n = len(distance) for i in range(3, n): if (distance[i - 1] <= distance[i - 3] and distance[i] >= distance[i - 2]): return True if (i >= 4 and distance[i - 1] == distance[i - 3] and distance[i - 2] <= distance[i] + distance[i - 4]): return True if (i >= 5 and distance[i - 2] >= distance[i - 4] and distance[i] >= distance[i - 2] - distance[i - 4] and distance[i - 3] >= distance[i - 5] and distance[i - 3] >= distance[i - 1] and distance[i - 3] <= distance[i - 5] + distance[i - 1]): return True return False
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
题解
本题就是变了一个样子的回溯题，本题有几个剪枝的条件，第一：左括号剩的数要大于右括号。第二：左右括号都为0的时候才能结束。
然后我们对这个进行回溯剪枝，并把每一次生成的序列放在列表中，回溯结束则返回列表！
本题主要就是掌握回溯，如果回溯没有掌握好的话，大家可以去csdn上面找一些大佬们的介绍！
代码
class Solution: def generateParenthesis(self, n: int) -> List[str]: res ="" chect =[] def trace(res,r,z,n): if r == n and z == n: chect.append(res) return if z < r: return if z < n: trace(res+"(",r,z+1,n) if r<n: trace(res+")",r+1,z,n) trace(res,0,0,n) return chect
组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 20
1 <= k <= n
题解
然后我发现我这个有点复杂了，所以我看了一些大佬们的题解，我觉得他们的是真简单 然后我就采用他们的方式来写的，
代码
class Solution: def combine(self, n: int, k: int) -> List[List[int]]: res = [] def bracktrace(path,i): if len(path) == k: res.append(path) return for j in range(i,n+1) : bracktrace(path+[j],j+1) bracktrace([],1) return res
字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
这个有很多方法，这个看起来很复杂，其实很简单，最麻烦的是你判断范围时候，你的代码会很多，不注意一些变量的使用导致错误。
我是用的re，也是有点取巧的成分。
class Solution(object): def myAtoi(self, s): """ :type s: str :rtype: int """ import re pattern = r"[\s]*[+-]?[\d]+" match = re.match(pattern, s) if match: res = int(match.group(0)) if res > 2 ** 31 - 1: res = 2 ** 31 -1 if res < - 2 ** 31: res = - 2 ** 31 else: res = 0 return res
实现strStr（）
这个题我开始没有理解题意然后一直卡着，我就看了下面大佬们的解题思路，而且也学到了新的一种方法————滑块。这个方法做这个题是十分简单的，可能以后写项目的也会用这个办法，反正学到就是赚到，嘿嘿。话不多说，直接上代码。
class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ if needle == '' or haystack == 0: return 0 if len(haystack)>=len(needle): right = len(haystack) i = 0 n = len(needle) while i<right: if haystack[i:n] == needle: return i n += 1 i += 1 else: return -1
