---

1、给定一个包含红色、白色和蓝色、共n 个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色；必须在不使用库的sort函数的情况下解决这个问题。（解决：冒泡排序、选择排序）

不能是快速排序，因为快速排序改变了内存地址

选择排序

def select(nums):n=len(nums)for i in range(n):min_idx=ifor j in range(i+1,n):if nums[j]<nums[min_idx]:min_idx=jnums[i],nums[min_idx]=nums[min_idx],nums[i]
test=[4,6,3,8,1,2,5]
select(test)
print(test)

冒泡排序

def mappao(nums):n=len(nums)for i in range(n-1):flag=Falsefor j in range(0,n-1-i):if nums[j]>nums[j+1]:nums[j],nums[j+1]=nums[j+1],nums[j]flag=Trueif not flag:breaktest=[4,6,3,8,1,2,5]
mappao(test)
print(test)

---

2、编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

def solution(nums):n=len(nums)i=0while i<n//2:s[i],s[n-i-1]=s[n-i-1],s[i]i+=1s = ["h","e","l","l","o"]
solution(s)
print(s)

---

3、给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

class Solution:def __init__(self,s,k):self.s=sself.k=kdef topKFrequent(self):d={}for item in self.s:if item not in d:d[item]=1else:d[item]+=1return ddef 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 d2def topKFrequent2(self):d2=self.topKFrequent1()l=list(d2.keys())return ls=['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 -1s = "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 Falseprint(stack)return len(stack)==1res=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),numsnums = [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 0for i in haystack:if i==needle[0]:return haystack.index(i)else:return -1s=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=0while j<k:nums.insert(0,nums[-1])nums.pop(-1)j+=1return numsnums = [1,2,3,4,5,6,7]
k = 3
res=demo8(nums,k)
print(res)

[5, 6, 7, 1, 2, 3, 4]