1、给定一个包含红色、白色和蓝色、共n 个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色；必须在不使用库的sort函数的情况下解决这个问题。（解决：冒泡排序、选择排序）
不能是快速排序，因为快速排序改变了内存地址
选择排序
class S75:
def func(self,nums):
left=0
right=len(nums)-1
p=0
while p<=right:
if nums[p]==2:
nums[p],nums[right]=nums[right],nums[p]
right-=1
continue
if nums[p]==0:
nums[p],nums[left]=nums[left],nums[p]
left+=1
p+=1
return nums
r=S75()
nums=[2,0,2,1,1,0]
print(r.func(nums))
冒泡排序
def mappao(nums):
n=len(nums)
for i in range(n-1):
flag=False
for j in range(0,n-1-i):
if nums[j]>nums[j+1]:
nums[j],nums[j+1]=nums[j+1],nums[j]
flag=True
if not flag:
break
test=[4,6,3,8,1,2,5]
mappao(test)
print(test)
2、编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
def solution(nums):
n=len(nums)
i=0
while i<n//2:
s[i],s[n-i-1]=s[n-i-1],s[i]
i+=1
s = ["h","e","l","l","o"]
solution(s)
print(s)
3、给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
class Solution:
def __init__(self,s,k):
self.s=s
self.k=k
def topKFrequent(self):
d={}
for item in self.s:
if item not in d:
d[item]=1
else:
d[item]+=1
return d
def topKFrequent1(self):
d=self.topKFrequent()
d1 = sorted(d.items(), key=lambda x: x[1],reverse=True)
d2={}
for i in d1[0:self.k]:
d2[i[0]]=i[1]
return d2
def topKFrequent2(self):
d2=self.topKFrequent1()
l=list(d2.keys())
return l
s=['o', 'l', 'l', 'e', 'h']
res=Solution(s,2)
print(res.topKFrequent2())
4、给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
输入: s = “leetcode”
输出: 0
输入: s = “loveleetcode”
输出: 2
输入: s = “aabb”
输出: -1
def demo2(str1):
#str=''
for i in str1:
if i not in str1[str1.index(i)+1:]:
return str1.index(i)
else:
return -1
s = "aabb"
res=demo2(s)
print(res)
5、给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
def demo4(nums,target):
nums1=[]
for i in nums:
if i<target:
nums1.append(i)
n=len(nums1)
for j in range(n):
for z in range(n-1):
if nums1[j]+nums1[z]==target:
return [z,j]
nums=[2,7,11,15,30,35]
res=demo4(nums,45)
print(res)
6、给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
class Solution:
def isValid(self, s):
dic = {'{': '}', '[': ']', '(': ')', '?': '?'}
stack = ['?']
for c in s:
if c in dic:
stack.append(c)
elif dic[stack.pop()]!=c:
return False
print(stack)
return len(stack)==1
res=Solution()
#s = "()"
s = "()[]{}"
#s = "(]"
print(res.isValid(s))
7、给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
def demo5(nums,target):
print(id(nums))
for i in nums:
if i==target:
nums.remove(target)
return len(nums),nums
nums = [3,2,2,3]
val = 3
len,nums=demo5(nums,val)
print(len,nums)
print(id(nums))
2898355569792
2 [2, 2]
2898355569792
8、给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
输入：haystack = “hello”, needle = “ll”
输出：2
class Solution:
def strStr(self, haystack,needle):
if needle is None:
return 0
for i in haystack:
if i==needle[0]:
return haystack.index(i)
else:
return -1
s=Solution()
haystack = "hello"
needle = "ll"
haystack = "aaaaa"
needle = "bba"
res=s.strStr(haystack,needle)
print(res)
9、给定一个不含重复数字的数组nums ，返回其所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1]
输出：[[1]]
import itertools
def permute(nums):
return list(itertools.permutations(nums))
nums = [1,2,3]
print(permute(nums))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
10、给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
class Solution:
def groupAnagrams(self, strs):
res=[]
dic={}
for s in strs:
keys="".join(sorted(s))
if keys not in dic:
dic[keys]=[s]
else:
dic[keys].append(s)
return list(dic.values())
s=Solution()
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
res=s.groupAnagrams(strs)
print(res)
[[‘eat’, ‘tea’, ‘ate’], [‘tan’, ‘nat’], [‘bat’]]
11、反转字符串中的单词
输入：s = “the sky is blue”
输出：“blue is sky the”
示例 2：
输入：s = " hello world "
输出：“world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
def demo7(strs):
li=strs.split(" ")[::-1]
li1 = []
print(li)
for item in li:
if bool(item) is not False:
li1.append(item)
l=' '.join(li1)
return l
res=demo7(s)
print(res)
12、给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
def demo8(nums,k):
j=0
while j<k:
nums.insert(0,nums[-1])
nums.pop(-1)
j+=1
return nums
nums = [1,2,3,4,5,6,7]
k = 3
res=demo8(nums,k)
print(res)
[5, 6, 7, 1, 2, 3, 4]
