算法题（二）
非科班出身，在校时没写过算法题，因此特做专题收录。
算法题我会偏向于python和go，说不定也会用java和js写一些，暂时不想用c++，也不会用php（只用它写web）
基础算法
输入a、b，输出a+b
a=input().split()
c = int(a[0])+int(a[1])
print (c)手写进制转化
26进制与10进制互相转化
ALPHBET = ('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z')
def 26210(alphabet)
return sum(ALPHABET.index(a)*(26 ** e) for e,a in enumerate(reversed(alphabet)))
def 10226(digit)
##十进制转26进制
(mod,remainder) = divmod(digit,26)
alphbet = ALPHABET[remainder]
while mod:
mod,remainder = divmod(mod,26)
alphbet = ALPHABET[remainder] + alphabet
return alphabet
for i in ('a','b','c'):
d = 26210(i);
a = 10226(d);
print(d,a)数论算法
实现求平方跟(69)
实现int sqrt(int x)函数
计算并返回x的平方根，其中x是非负整数
返回类型为整数，如果结果是小数只保留整数，小数部分将被舍去。
输入：4
输出：2
输入：8
输出：2
代码
class Solution:
def mySqrt(self, x: int) -> int:
if x <= 1:
return x
r = x
while r > x / r:
r = (r + x / r) // 2
return int(r)斐波那契数列(509)
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。
class Solution:
def fib(self,n:int)->int:
if(n>1):
return self.fib(n-1)+self.fib(n-2)
else:
return n爬楼梯问题(70)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
例如：输入：2
输出：2 有两种方法：一阶一阶上，或者跨两阶直接上
输入：3
输出：3 有三种方法：一阶一阶上、先跨两阶后一阶、先一阶后两阶
class Solution:
def climbStairs(self, n: int) -> int:
dp = [1, 1 ,2]
if n <=2:
return dp[n]
for i in range(3,n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]变形1：爬楼梯的方法
每次你可以爬 1 或 3个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution:
def climbStairs(self, n: int) -> int:
dp = [1, 1 ,2]
if n <=2:
return dp[n]
for i in range(3,n+1):
dp.append(dp[i-1] + dp[i-3])
return dp[n]变形2：不能去指定层数或者指定倍数的层数
不能经过指定的楼层数，或者指定倍数（比如5的倍数的层数或者7的倍数的层数）
在楼层前加if，符合条件则置空
class Solution:
def climbStairs(self, n: int) -> int:
dp = [1, 1 ,2]
if n <=2:
return dp[n]
for i in range(3,n+1):
##假设指定层数为4
if i == 4:
dp.append(0)
##假设指定不能经过5的倍数
elif i % 5 == 0:
dp.append(0)
else
dp.append(dp[i-1] + dp[i-2])
return dp[n]我一开始的思路是总方法数减去删去指定层数的方法数，后面经人提点，经过指定层数也要能够到达终点。所以这种思路的方法应该是减去到达指定层数的方法数*单独后面的层数的方法数，理论上应该也是可行的。但是此种方法对于倍数的问题计算量会很大，也就是每经过一次不能去的楼层都要计算倍数，所以不推荐
变形3:爬两步之后只能爬一步
f(n,status)=f(n-1,1)+f(n-2,2)
快乐数(202)
编写一个算法来判断一个数是不是快乐数
快乐数的定义：
4的幂342
给定一个整数，写一个函数来判断是否是4的幂次方，如果是返回true，如果不是返回false
例：输入：16
返回：true
递归
class Solution:
def isPowerOfFour(self,n:int)->bool:
if n == 0: return False
if n == 1: return True
if n % 4 == 0:
return self.isPowerOfFour(n/4);
return Falsex的n次幂（50）
实现计算x的整数n次幂函数
例： 输入 x = 2， n = 10， 输出1024
输入 x = 2.1，n=3，输出9.261
输入 x = 2，n = -2，输出0.25
var myPow = function(x, n) {
if(n == 0 || n ==1) {
return n == 0 ? 1: x
}else if(n < 0){
return myPow(1/x, Math.abs(n))
}else{
return n % 2 == 0 ? myPow(x * x , n/2) : myPow(x * x ,Math.floor(n/2))* x
}
};计数质数(204)
统计所有小于非负整数 n 的质数的数量。
例：输入：n=10
输出：4，小于10的质数有2，3，5，7四个
杨辉三角(118)
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
例：输入：5
输出：[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
result = []
for i in range(numRows):
now = [1]*(i+1)
if i >= 2:
for n in range(1,i):
now[n] = pre[n-1]+pre[n]
result += [now]
pre = now
return result杨辉三角2(119)
给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
例：输入：3
输出：[1,3,3,1]
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
res = [1]
for i in range(1, rowIndex // 2 + 1):
res.append(res[-1] * (rowIndex + 1 - i) // i)
if rowIndex % 2:
return res + res[::-1]
else:
return res[:-1] + res[::-1]各位相加(258)
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
输入: 38 输出: 2 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
class Solution:
def addDigits(self, num: int) -> int:
while num>=10:
num=str(num)
s=0
for i in num:
s=s+int(i)
num=s
return num至少有1位重复的数字(1012)
给定正整数 N，返回小于等于 N 且具有至少 1 位重复数字的正整数的个数。
例：输入：20
输出：1（20以下具有至少一位重复数字的只有11一个数字）
输入：100
输出：10(11，22，33，44，55，66，77，88，99，100)
总数减去所有不重复的数字，以1234为例
对于输入数，例如1234，我们首先计算[0,999]，我们可以将它拆分为[10,99]和[100,999]来考虑。对于[10,99]，其第一位有9种选法（1~9），第二位要与第一位不同有9种选法，所以总共有9x9=81种。对于[100,999]，第一位有9种选法，第二位和第三位有A 9 2 A_9^2A 92中选法（也就是9个数中取两个数），也就是9x9x8=648。
接着思考[1000, 1199]内有多少个元素？第二位要和第一位不同，所以有1种选法，第二位和第三位有A 8 2 A_8^2A82 中选法（也就是9个数中取两个数），所以总共有1x8x7=56。同理接着计算[1200,1229]，[1230,1233]和1234。结果总共是803，也就是1234-803=431。我们还有一些边界问题没有考虑，例如对于1123，此时当我们遍历到第二个位置的时候，我们发现1在前面已经出现过了，所以我们此时直接返回当前的结果就可以了。
class Solution:
def numDupDigitsAtMostN(self, N: int) -> int:
L = list(map(int, str(N + 1)))
res, n = 0, len(L)
def A(m, n):
return 1 if n == 0 else A(m, n - 1) * (m - n + 1)
for i in range(1, n): res += 9 * A(9, i - 1)
s = set()
for i, x in enumerate(L):
for y in range(0 if i else 1, x):
if y not in s:
res += A(9 - i, n - i - 1)
if x in s: break
s.add(x)
return N - res最大为N的数字组合(902)
我们有一组排序的数字 D，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。
现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。
返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。
例：输入：D=["1","3","5","7"],N=100
输出：20(可以组合出的20个数字：1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77)
输入：D = ["1","4","9"], N = 1000000000 输出：29523 解释： 我们可以写 3 个一位数字，9 个两位数字，27 个三位数字， 81 个四位数字，243 个五位数字，729 个六位数字， 2187 个七位数字，6561 个八位数字和 19683 个九位数字，和为29523 个整数。
思路：我们采用同样的方式思考，例如1234，我们可以先计算[1,999]内有多少个数，怎么算？很简单，对于[1,9]总共有len(D)个数，对于[10,99]，总共有len(D)2个数，通过对于[100,999]总共有len(D)3个数，最后将所有的数加起来就行了。
接着思考[1000,1199]内有多少个数，怎么算？首先计算出[0,1]这个区间内只有一个数满足，而后面总共有两种选择，也就是len(D)2，所以结果就是1*len(D)2。接着思考[1200,1229]，此时我们发现2不在D中，所以我们直接返回最后的结果就好啦！最后的结果就是100。
由于上面的例子提前结束了，所以我们还有最后的[1234, 1234]没有去考虑。如果此时的例子是1357，我们最后就要思考1357是不是满足条件，怎么做？一种做法就是和之前问题的处理手法类似，也就是set(N).issubset(set(D))。或者我们只需要判断我们是不是遍历到最后一个元素就行了，因为只要前面的元素都满足条件，那么D一定满足条件。
class Solution:
def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
N = str(n)
n = len(N)
res = sum(len(digits) ** i for i in range(1, n))
i = 0
while i < n:
res += sum(c < N[i] for c in digits) * (len(digits) ** (n - i - 1))
if N[i] not in digits:
break
i += 1
return res + (i == n)旋转数字(788)
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
输入: 10 输出: 4(2,5,6,9四个数字)
class Solution:
def rotatedDigits(self, N: int) -> int:
res=0
for i in range(1,N+1):
s=str(i)
if '3' in s or '4' in s or '7' in s :continue
if '2' in s or '5' in s or '6' in s or '9' in s:res+=1
return res等差数列划分(413)
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
函数要返回数组 A 中所有为等差数组的子数组个数。
例：输入：A= [1,3,5,7]
输出：[1,3,5],[3,5,7],[1,3,5,7]
动态规划
由上面[1,2,3,4,5,6]的示例可知，(由于数列长度需要大于2，所以dp[0] = dp[1] = 0) dp[2] = dp[1] + 1,因为A[2] - A[1] == A[1] - A[0] dp[3] = dp[2] + 1,因为A[3] - A[2] == A[2] - A[1] （这里有些道友可能认为需要判断以A[2]结尾的步长是否等于以A[3]结尾的等差步长，其实无形之中已经进行了判断，以A[2]结尾的步长就是A[2] - A[1]（如果A[2]找到了等差数列，那么它的步长必定为A[2] - A[1]），而A[3]结尾的等差步长必定是dp[2] + 1） …
如果[1,2,3,4,5,6]是一个等差数列，则 以A[2]结尾的等差数列 [1,2,3] 以A[3]结尾的等差数列 [1,2,3,4],[2,3,4] 以A[4]结尾的等差数列 [1,2,3,4,5],[2,3,4,5],[3,4,5] 以A[5]结尾的等差数列 [1,2,3,4,5,6],[2,3,4,5,6],[3,4,5,6],[4,5,6]
转移方程： dp[i] = dp[i - 1] + 1
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n=len(nums)
dp=[0]*n
for i in range(2,n):
if nums[i]-nums[i-1]==nums[i-1]-nums[i-2]:
dp[i]=dp[i-1]+1
return sum(dp)回文数9
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
else:
y = str(x)[::-1]
if y == str(x):
return True
else:
return False判断一个数是否为质数
方法一：暴力求解，从1到该数一个一个整除验证
方法二：质数为6*n+1或者6n-1，判断
平方数
判断一个数是否为平方数
方法一：暴力求解，从1到该数一个一个平方验证
方法二：平方数的性质——一个平方数可以表达为一个初值为1等差为2的等差数列的和公式，不同的平方数对应的项数不同
所以用该数减从头开始的等差数列，如果减到某一项正好为0，则为平方数，否则不是
车站建造问题
牛牛建造车站，
哥德巴赫猜想：一个偶数必然能拆分成两个质数。一个奇数必然能分解成一个偶质数和一个奇质数之和，偶质数只有2，且减2后的奇数必然能分解成两个质数之和。
所以判断一个数是否为偶数，偶数则增加一个车站。
杨辉三角
给定非负整数numrows，返回杨辉三角前numrows行
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
nums = [ [0] * (i+1) for i in range(numRows)]
for i in range(len(nums)):
for j in range(len(nums[i])):
if j == 0 or j == i:
nums[i][j] = 1
else:
nums[i][j] = nums[i-1][j-1]+nums[i-1][j]
return nums给定非负索引k，返回杨辉三角第k行
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
row = [1 for _ in range(rowIndex+1)] # 先生成一个目标行元素的列表
for i in range(2,rowIndex+1): # 从第3行开始dp
for j in range(i-1,0,-1): # 从后往前，保证O(n)空间
row[j] = row[j-1]+row[j]
return row只出现一次过的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
实例：输入[2,2,1],输出1
#计算出现次数
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = {} # 定义字典
for num in nums: # 遍历数组
if num in count: # 如果字典中存在当前记录
count[num] += 1 # 次数 + 1
else: # 否则
count[num] = 1 # 当前数加入到字典中，且出现次数为1
count = {v: k for k, v in count.items()} # 字典键值交换
return count[1] # 返回出现一次的数字n个数前m大的值
利用堆结构进行排序
先建立m个节点的小根堆，然后对后面n-m个数进行遍历，比根节点大时交换，重新建立小根堆，最后得到m个最大的数
字符串相关算法
有效括号(20)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效括号的原则：
1.左括号必须由相同类型的右括号闭合
2.右括号必须以正确的顺序闭合左括号
比如
输入：s="()"
输出：true
输入：s="{[}]"
输出：false
大神做法（思路巧妙,复杂度较高）
class Solution:
def isValid(self,s):
while '{}' in s or '()' in s or '[]' in s
s = s.replace('{}','')
s = s.replece('()','')
s = s.replace('[]','')
return s == ''js代码
function validate (s) {
while(s.length){
let temp = s;
s = s.replace('()','');
s = s.replace('[]','');
s = s.replace('{}','');
if(s === temp)return false
}
return true
}复杂度较低，用栈数据结构。也就是说把遇到的左括号都放进栈里，然后遇到右括号时取出栈顶的元素匹配 如"{[()]}"遇到{[(放入栈内，然后遇到）与栈顶匹配，栈顶也就是最后一个进栈的元素（，然后把栈的最后一个元素删掉
js版本
var isValid = function(s) {
let a = [];
let res=0;
for(let i=0;i<s.length;i++){
if(s[i]=='('||s[i]=='{'||s[i]=='['){
a.push(s[i]);
res++;
}
else if(s[i]==')'){
if(a[a.length-1]=='('){
a.pop();
res--;
}
else return false
}
else if(s[i]=='}'){
if(a[a.length-1]=='{'){
a.pop();
res--;
}else return false
}
else if(s[i]==']'){
if(a[a.length-1]=='['){
a.pop();
res--;
}else return false
}
}
return res==0
};js中还能使用map数据结构
var isValid = function(s) {
let map = {
"{":"}",
"[":"]",
"(":")",
}
let leftArr = [];
for(let ch of s){
if(ch in map){
leftArr.push(ch)
}else{
if(ch!=map[leftArr.pop()]){
return false
}
}
}
return !leftArr.length
};python版本
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for item in s:
if item == '(':
stack.append(')')
elif item == '[':
stack.append(']')
elif item == '{':
stack.append('}')
elif not stack or stack[-1] != item:
return False
else:
stack.pop()
return True if not stack else False最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""
var longestCommonPrefix = function(strs) {
var re = '';
if (!strs.length) return re;
for (var j=0;j<strs[0].length;j++){//第j位
for (var i=1;i<strs.length;i++){//第i个
if (strs[i][j]!=strs[0][j]) return re
}
re += strs[0][j];
}
return re;
};反转单词序列
class solution
def Reverse(self,s)
if s is None or len(s) ==
return s
return "".join(s.split('')[::-1])无重复最长子串的长度(3)
js
var lengthOfLongestSubstring = function(s) {
let index = 0, max = 0
for(let i = 0, j = 0; j < s.length; j++) {
index = s.substring(i, j).indexOf(s[j])
if(index !== -1) {
i = i + index + 1
}
max = Math.max(max, j - i + 1)
}
return max
};Python
a = input()
temp = ''
length = 0
for i in a:
if i not in temp:
temp+=i
length = max(length,len(temp))
else:
temp+=i
temp = temp[temp.index(i)+1:]
print (length)最长回文子串5
给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = "babad"
输出："bab"或者"aba"
输入：s = "cbbd"
输出："bb"
思路：
对任意字符串，如果头和尾相同，那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。
如果头和尾不同，那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。
js
var longestPalindrome = function(s) {
let str = "";
for(let i = 0; i < s.length; i++) {
for(let j = i + 1; j <= s.length; j++) {
const temp = s.slice(i, j);
if(temp == temp.split("").reverse().join("") && temp.length > str.length) {
str = temp;
}
}
}
return str;
};dp
var longestPalindrome = function(s) {
let res=0,max=0,step
for(let i=0;i<s.length;i+=step){
let l=i-1,r=i+1
step=1
while(r<s.length&&s[i]===s[r]){
r++
step++
}
while(l>=0&&r<s.length&&s[l]===s[r]){
l--
r++
}
if(r-l-1>max){
max=r-l-1
res=s.substr(l+1,max)
}
}
return res
};Python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
maxl = 0
start = 0
for i in range(n):
if i - maxl >= 1 and s[i-maxl-1: i+1] == s[i-maxl-1: i+1][::-1]:
start = i - maxl - 1
maxl += 2
continue
if i - maxl >= 0 and s[i-maxl: i+1] == s[i-maxl: i+1][::-1]:
start = i - maxl
maxl += 1
return s[start: start + maxl]检验一个字符串是否回文
//普通方法
s = input()
a = len(s)
i = 0
count = 1
while i <= (a/2)
if s[i]== s[a-i-1]:
count = 1
i += 1
else:
count = 0
break
if count == 1
print('是回文序列')
else
print('不是回文序列')
//函数
s = input()
a = reversed(list(s))
if list(a)=list(s)
print('是回文序列')
else
print('不是回文序列')字符串相加(415)
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1, num2 = num1[::-1], num2[::-1] # 将输入字符串逆序
len1, len2 = len(num1), len(num2) # 获得字符串长度
res = '' # 初始化结果变量
carry = 0 # 初始化进位
for i in range(max(len1, len2)): # 开始遍历
## 通过ascii码值转换成整数
n1 = ord(num1[i]) - ord('0') if i < len1 else 0 # 取第一个数的当前位
n2 = ord(num2[i]) - ord('0') if i < len2 else 0 # 取第二个数的当前位
s = n1 + n2 + carry # 当前位的计算结果
carry, r = s // 10, s % 10 # 获得余数和进位
res = str(r) + res # 把余数加到当前结果的最高位
if carry: # 如果算完还有进位
res = str(carry) + res # 加到结果最高位
return res # 返回最终结果统计字符串中出现最多的字母
function findMaxDuplicateChar(str) {
if(str.length == 1)
{ return str; }
let charObj = {};
for(let i=0;i<str.length;i++) {
if(!charObj[str.charAt(i)])
{ charObj[str.charAt(i)] = 1; }
else
{ charObj[str.charAt(i)] += 1; }
}
let maxChar = '',
maxValue = 1;
for(var k in charObj)
{ if(charObj[k] >= maxValue)
{ maxChar = k; maxValue = charObj[k]; }
} return maxChar;
}
module.exports = findMaxDuplicateChar;添加最少字符构造回文字符串(1312)
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
返回让 s 成为回文串的 最少操作次数 。
例：输入：s = "zzazz"
输出：0，已经是回文字符串
输入：s = "mbadm"
输出：2，将s变为“mbdadbm”或者“mdbabdm”
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
f = [[0] * n for _ in range(n)]
# 从长度为2的字符串开始枚举
for l in range(1, n):
for i in range(n - l):
j = i + l
if s[i] != s[j]:
f[i][j] = min(f[i][j - 1], f[i + 1][j]) + 1
else:
# 这里长度为2时 i + 1 > j - 1， f[i + 1][j - 1]=0，所以可以省略 if l!=1 else 0 的判断条件
f[i][j] = f[i + 1][j - 1]
return f[0][n - 1]Leetcode93:复原ip地址
给定一个只有数字的字符串，将其转化为合法的ip地址，并存起来
例：
输入“25525511135”
输出：["255.255.11.135","255.255.111.35"]
dfs
当segment=4时结束循环，将结果添加到列表中，每个部分值均需要在0-255之间，所以回溯最多需要判断3个元素，即i-i+2三个数字
class Solution(object)
def restoreIpAddress(self,s):
def dfs(s,segment,res,ip):
if segment = 4:
if s == '':
res.append(ip[1:])
return
for i in range(1,4):
if i <= len(s):
if (ints[:i]) <= 255:
dfs(s[i:],segment+1,res,ip+'.'+s[:i])
if s[0] == '0':
break
res = []
dfs(s,0,res,'')
return res
if _name_ == '_main_':
S = Solution()
s = '25525511135'
S.restoreIpAddress(s)括号生成22
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
递归
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
def f(l, r, s):
l == r == n and ans.append(s)
l < n and f(l + 1, r, s + '(')
r < l and f(l, r + 1, s + ')')
f(0, 0, '')
return ans最长有效括号(32)
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
输入：s=“(()”
输出：2，最长有效子串是()
输入：s=“)()())”
输出：4，最长有效子串是()()
使用栈或者动态规划解决
栈
var longestValidParentheses = function(s) {
let max = 0
if (s.length < 1) return max
let len = s.length
// 栈顶之所有加入一个-1,纯粹是为了方便计算有效括号的长度
// 不然就需要手动调整为i-j+1;同时而确保第一个字符为")"时不需要特殊处理
let stack = [-1]
for(let i = 0; i < len; i++) {
let value = s[i]
if (value === '(') {
stack.push(i)
} else if (value === ')') {
stack.pop()
// 栈顶加入一个pivot字符")",实际上是方便计算有效括号串长度
if (stack.length < 1) {
stack.push(i)
} else {
max = Math.max(max, i - stack[stack.length - 1])
}
}
}
return max
};class Solution:
def longestValidParentheses(self, s: str) -> int:
length = len(s)
if length == 0:
return 0
dp = [0] * length
for i in range(1,length):
#当遇到右括号时，尝试向前匹配左括号
if s[i] == ')':
pre = i - dp[i-1] -1;
#如果是左括号，则更新匹配长度
if pre>=0 and s[pre] == '(':
dp[i] = dp[i-1] + 2
#处理独立的括号对的情形 类似()()、()(())
if pre>0:
dp[i] += dp[pre-1]
return max(dp);实现一个strStr()函数28
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
输入: haystack = "hello", needle = "ll" 输出: 2
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if haystack == needle:
return 0
for i in range(0, len(haystack)+1):
if needle in haystack[0:i]:
return i - len(needle)
return -1比较版本号(165)
给你两个版本号version1和version2，比较。
返回信息：
如果version1>version2，返回1
如果version1<version2，返回-1
除此之外返回0
比较的方式：
比较版本号时，从左到右依次比较修订号，比较时忽略任何前导0，也就是修订号1和001相同
例：输入：version1="1.01"，version2="1.001"
输出：0，规则为忽略前导0，所以相同
输入：version1="1.0.1"，version2="1"
输出：1
class Solution:
def compareVersion(self,version1:str,version2:str)->int:
v1 = version1.split(".")
v2 = version2.split(".")
while v1 or v2
x = int(v1.pop(0)) if v1 else 0
y = int(v2.pop(0)) if v2 else 0
if x > y
return 1
elif x < y
return -1
return 0最后一个单词的长度(58)
给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0
例：输入:"Hello World"
输出:5
class Solution:
def lengthOfLastWord(self, s: str) -> int:
cnt, tail = 0, len(s) - 1
while tail >= 0 and s[tail] == ' ':
tail -= 1
while tail >= 0 and s[tail] != ' ':
cnt += 1
tail -= 1
return cnt有效的字母异位词
给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。
例：输入s = "anagram", t = "nagaram"
输出：true
var isAnagram = function(s, t) {
if(s.length !== t.length) return false;
const resSet = new Array(26).fill(0);
const base = "a".charCodeAt();
for(const i of s) {
resSet[i.charCodeAt() - base]++;
}
for(const i of t) {
if(!resSet[i.charCodeAt() - base]) return false;
resSet[i.charCodeAt() - base]--;
}
return true;
};单词拆分139
给定一个非空字符串s和一个包含非空单词的列表，判断s是否可以拆分成多个或一个在字典中出现的单词
例：输入：s="applepenapple",wordDict = ["apple,pen"]
输出：true
class Solution:
def wordBreak(self,s:str,wordDict:list[str])->bool:
if not s:
return True
breakp = [0]
for i in range(len(s)+1):
for j in breakp:
if s[j:i] in wordDict:
breakp.append(i)
break
return breakp[-1] ==len(s)翻转字符里的单词(151)
给定一个字符串，翻转字符串里的每个单词
说明：
无空格字符串构成一个单词
输入字符串前面可以有空格，输出后的字符不包括
如果两个单词之间有多余的空格，反转后的单词间的空格减少到只剩一个
例：输入：" hello world! "
输出："world! Hello"
输入："a good example"
输出："example good a"
class Solution:
def reverseWords(self,s:str)->str:
return " ".join(s.split())[::-1]判断子序列392
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
输入：s = "abc", t = "ahbgdc" 输出：true
输入：s = "axc", t = "ahbgdc" 输出：false
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
j = 0
while i < len(s) and j < len(t):
# print(i, j)
if s[i] == t[j]:
i += 1
j += 1
else:
j += 1
return i == len(s)字符串编码(394)
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
输入：s = "3[a]2[bc]"
输出："aaabcbc"
输入：s = "3[a2[c]]"
输出："accaccacc"js
var decodeString = function(s) {
// 用两个栈来存放当前状态，前者是重复次数，后者是累积字符串
let numStack=[],strStack=[];
//拼接字符串
let resStr = "";
//表示重复次数
let repet = 0;
// 遍历s
for(let i=0;i<s.length;i++){
let cur = s.charAt(i);
if(cur == '['){
//双双压入栈中,保存当前状态
numStack.push(repet);
resStack.push(resStr);
//置空，准备下面的累积
repet = 0;
resStr = "";
}else if(cur == ']'){
// 取出当前重复次数栈中的值，也就是当前字符串的重复次数
let count = numStack.pop();
// 根据重复次数生成重复字符串，赋值给temp，和resStr拼接
let temp = "";
for(let i = 0;i<count;i++){
temp += resStr;
}
// 和前面已经求得的字符串进行拼接
resStr = strStack.pop() + temp;
}else if(cur>='0' && cur<='9'){
// repet累积
repet = repet*10 + (cur-'0');
}else{
//字符累积
resStr += cur;
}
}
return resStr;
};