python leetcode1_综合

13. 罗马数字转整数

我也不知道为什么这个可以通过,没细想.
我是采用两个一比对,这样的话需要看一看最后一位取的到吗?

# 首先的想法:
# 1.他已经说明输入一定为正确的罗马数字(字符串形式)
# 2.将六种特殊情况现在字符串中排查一遍,转化成数字,并在字符串中删除
# 3.将其他字符将字符串中转化为数字def fun1(s):#创建一个字典dic_liu={
    'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900}dic_={
    'I':1,'V ':5,'X ':10,'L':50,'C':100,'D':500,'M':1000}#用来求和的变量sum_=0#用来记录当前位置的变量i=0if len(s)==1:return dic_[s]while i<len(s)-1:key=s[i:i+2:]print(key)if key in dic_liu.keys():sum_+=dic_liu[key]if i+2==len(s)-1:sum_+=dic_[s[i+2]]i+=2else:sum_+=dic_[key[0]]if i+1==len(s)-1:sum_+=dic_[s[i+1]]i+=1return sum_def fun2(s):#就是什么样的情况-,什么样的情况+dic_={
    'I': 1,'V': 5,'X': 10,'L': 50,'C': 100,'D': 500,'M': 1000,}sum_=0n=len(s)for i,ch in enumerate(s):item=dic_[ch]#输入的一定是正确的if i<n-1 and item<dic_[s[i+1]]:#这样判断的前提是输入是''正确''的sum_-=itemelse:sum_+=itemreturn sum_

14. 最长公共前缀

#首先的想法是每一次将数组中的遍历一遍
#将首位进行比对,如果都一样,在继续比对第二位def fun1(strs):if len(strs)==1:return strs[0]first=strs[0]for i in range(len(first)):#总共遍历数组的次数for j in range(1,len(strs)):#把数组走一遍if i<len(strs[j]):if first[i]!=strs[j][i]:#不相等时进来#假设当前i等于2,后面的代码又是return#说明前面都没有进来过,也就是说first的第0位和第1位与其他元素均一样#这时候i==2在与某个元素判断时却进来了,那么就不可能继续往后面走了return first[0:i:]else:#i和len(strs[j])只有两种情况小于或等于#进来的一定是等于情况#能进来说明此时i对应的数字大于等于当前元素的长度,所以return first[0:i:]return first#又有了一种想法,先将字符串数组中的第一个和第二个拿出来比对一下#1.如果没有共同前缀,则直接输出没有#2.如果有公共前缀(假设为flx),那么最长公共前缀长度一定小于等于flx#3.通过上述可以减少比对的次数def fun2(strs):if len(strs) == 1:return strs[0]# 用来记录相同元素str = ""# 假设一个为abcdffg# 一个为abcd# 只需要循环到长度最短的末尾就行了first = strs[0]dier = strs[1]i = 0while i < len(first) and i < len(dier):if first[i] == dier[i]:str += first[i]else:breaki += 1# 得到了他俩的公共前缀for i in range(2, len(strs)):item = strs[i]j = 0panduan = ""while j < len(item) and j < len(str):if str[j] == item[j]:panduan += str[j]else:if panduan == "":return ""breakj += 1str = panduanreturn str#上面两种方法本质上都是暴力枚举#他可以分解成更小的相似部分进行对比,所以可以使用
#递归
def fun3(strs):right=len(strs)-1if right==0:#说明只有一个元素return strs[0]mid=right//2leftStr,rightStr=fun3(strs[0:mid+1:]),fun3(strs[mid+1::])#这里为了防止有一个list为空所以这样切分#返回的结果为字符串,开始两个两个的找公共部分i=0while i<len(leftStr) and i<len(rightStr):if leftStr[i]!=rightStr[i]:#这里的问题是当前的i对应的值不相等所以后面就不用看了#前面的也没有问题所以直接return(和上面fun1()有点像的对比)return leftStr[0:i:]i+=1#循环结束还没有return的话就将最短的那个输出if len(leftStr)<len(rightStr):return leftStrelse:return rightStrif __name__ == '__main__':fun3(["flower","flow","flight"])

26.删除有序数组中的重复项

#首先给定的是有序的数组
#返回值是不重复元素组成数组的长度
#她会将其输出
#这也就是说,你只需要把重复的挪到后面就行了#双指针的写法
def fun1(nums):#数组为空单独拿出来判断if nums==[]:return 0if len(nums)==1:#只有一个元素可以直接输出return 1quick,slow=1,1while quick<len(nums):#进行一下判断#数组是有序的,相同的元素会一窝一窝的聚集在一起#那么当,当前的quick和quick-1对应的元素不同时#你就到了另一窝if nums[quick]==nums[quick-1]:quick+=1else:nums[slow]=nums[quick]slow+=1quick+=1return slow

27. 移除元素

##这个好像是双指针优化
def fun1(nums,val):right=len(nums)-1cur=0while cur<=right:if nums[cur]!=val:#不相等cur+=1else:#相等#和right换位置nums[right],nums[cur]=nums[cur],nums[right]#因为你不知道换位置的那个元素,是否与val的值相等所以需要再进行一次判断right-=1return cur#正常的双指针
#就是把应该输出的往前移动
#不应该输出的会随着'''应该输出'''的前移而不断后移
def fun2(nums,val):quick=0slow=0while quick<len(nums):if nums[quick]!=val:#将其前移nums[quick],nums[slow]=nums[slow],nums[quick]slow+=1quick+=1return slow#其实fun2的代码nums[quick],nums[slow]=nums[slow],nums[quick]是不需要的
#因为你本身slow位置的元素从来都没有通过''slow下标''被比较过
#也就是说无论你那个位置放什么都行def fun3(nums,val):quick=0slow=0while quick<len(nums):if nums[quick]!=val:#将其前移nums[slow]=nums[quick]slow+=1quick+=1return slow

28. 实现 strStr()
这里其实组好是使用KMP,但是我看了半天吐了

注意fun1和fun2都是暴力方法.但fun1逻辑上有些许问题,不够简洁,错误较多
fun2在80个测试点通过了78个,后面的数据他大了.
注意fun2中采用双指针时,用 slow+quick.这使得slow不需要移动,只需要移动quick
方便了回溯(当匹配不成功回到原点+1)def fun1(haystack,needle):if len(needle) == 0:return 0i = 0while i < len(needle):j = 0while j < len(haystack):if needle[i] != haystack[j]:# 如果是不等于有两种情况# 1.他是needle的首位元素:只需要j+1就行了# 2.他不是needle的首位元素:你是需要退回来if i == 0:j += 1else:i = 0else:if i == len(needle) - 1:return j - ij += 1i += 1# 当你查完了一遍,i还等于0那么肯定是没对应的结果if i == 0:return -1return j - idef fun2(haystack,needle):if len(needle) == 0:return 0slow=0while slow+len(needle)<=len(haystack):#(slow相当于匹配的起点)#这个变量使用了记录needle的位置quick = 0while quick<len(needle):#这里使用的是slow+quick所以在这个quick<len(needle)循环中slow始终不需要#进行数值的更改if needle[quick]==haystack[slow+quick]:#继续下一个字符的匹配quick+=1else:slow+=1breakif quick==len(needle):return slow-1#如果没进来说明#needle的长度是大于haystack的return -1

def fun1(nums,target):#这里使用left和right而不使用len(nums)的原因:#需要返回下标或插入元素.使用len(nums)就必须将<<列表进行切分,和加入变量保证索引的正确>>left=0right=len(nums)-1while left<right:mid = (left + right)//2zhongzhi = nums[mid]if(zhongzhi==target):#这里就可以直接返回了#题目<<提示>>中说:nums 为无重复元素的升序排列数组return midelif(zhongzhi<target):#因为mid这个位置的值已经比较过了#所以赋值的时候为mid+1,不需要再比较left=mid+1elif(zhongzhi>target):right=mid-1#出循环是里面只有一个元素zhongzhi=nums[left]if (zhongzhi == target):# 这里就可以直接返回了# 题目<<提示>>中说:nums 为无重复元素的升序排列数组return leftelif (zhongzhi < target):#这里有个问题,如果插入元素比所有元素都大#那么一定是插入到最后面,但是这不存在溢出数组的问题#所以可以直接插入#将元素插进来return left+1elif (zhongzhi > target):#这种情况需要注意一下#因为是插入到你的左边,所以存在当前位置为下标0的情况if left==0:return 0return left

=============================================================================================================================================================================================================================================================================================
动态规划
53. 最大子序和
fun1对应的方法是暴力破解,没有一点优化,每种情况都需要走一遍.一个203个测试点通过了201个,所以应该写的没问题,时间上需要优化

def fun1(nums):slow = 0max = 0panduan = True #这里是防止第一次的到的结果是个负数,或者所有结果都是负数,导致最后输出了0while slow < len(nums):quick = 0sum = 0while slow + quick < len(nums):sum += nums[slow + quick]if max < sum or panduan:#第一次不管怎么样都能进来,因为panduan为True#这时候:#1.sum为负数,这是需要进行更改的#2.sum为正数,本来就要进来更改#3.sum为0,不影响#之后:#只有sum的值大于max才能进来panduan = Falsemax = sumquick += 1# while slow+quick<len(nums):循环结束,slow后移一下slow += 1return max只有最后一个测试用例没通过,相对于最开始第一次的代码,更加的简洁,已读,高效
#由于有几天没有碰这一题了,所以先把暴力再写一遍
#基本思路就是设置一个最大值列表,用来记录每一个数对应的最大值#而对于某个数的最大值,可以直接通过sum来记录
def fun2(nums):max_list=[]for i in range(len(nums)):sum=nums[i]max_sum=nums[i]for j in range(i+1,len(nums)):#从当前元素的后一位开始计算sum+=nums[j]  #加上当前元素,可能变大也可能变小,但都不能确定后面是否会有"超级super数"if sum>max_sum:#进行一个更换max_sum=sum#当循环结束所得到的max一定是在这个过程中的最大值max_list.append(max_sum)return max(max_list)动态规划
#采用动态规划的方式写,可以看到有大量的重复性计算
#从后往前,用哈希表/字典进行记录(可以是对数据<<但细细想想nums中数据是有可能重复的>>,最好是对下标,下标具有唯一性)#连续的最大子序和,所以假设当前位置为i
#你必须经过i+1,又可知i+1对应的最大值为x,所以i对应的最大值
#只能是i本身或i+x
def fun3(nums):n=len(nums)#创建列表,记录下标i处对应的值nums_copy=nums.copy()for i in range(n-1,0,-1):#这样的话,每一次的i需要-1nums_copy[i-1]=max(nums[i-1],nums[i-1]+nums_copy[i])return max(nums_copy)动态规划,递归版本
def fun4(nums):if len(nums) == 1:return nums[0]  #因为在该种情况下返回值为数字,不是列表,所以直接拿出来单独讨论max_list=nums.copy()max_list=bijiao(max_list,0)return max(max_list)
def bijiao(max_list,i):if i==len(max_list)-1:#在遇见最后一位的时候停下来return max_list[i]max_list[i]=max(max_list[i],max_list[i]+bijiao(max_list,i+1))if i==0:return max_listreturn max_list[i]

这个通过了23个测试用例,因为碰到第22个那个测试用例太大了
def fun1(nums):#不做一点优化,每一种情况都走一遍#即使有重复的/以前走过的也继续走下去list1=[]for i in range(len(nums)):list1.append(bijiao(nums,i))return max(list1)
def bijiao(nums,i):max_len = 1for j in range(i + 1, len(nums)):if nums[i] < nums[j]:max_len=max(max_len,bijiao(nums,j)+1)return max_len这个是模拟递归的非递归版本,想法和递归的思想没什么两样,就是用栈来模仿
主要问题就是代码写起来很难受注意:错误代码
def fun2(nums):#这种方法是f1的迭代版本n=len(nums)max_list=[]for s in range(n):  #0<=s<n#创建一个栈#一个当前s元素对应一个栈stack=[]q=si=1max_len=1     #设置当前元素对应的最长度初始值while q+i<n or stack:# 记录从当前q向后走过的长度,在栈中释放元素时len_ji = 0if nums[q+i]>nums[q]:#当前q入栈#q更换位置#i回归原来stack.append(q)q=q+ii=1len_ji+=1continue#如果没有进来i+=1 #向后继续判断#如果走到末尾,就判断栈中元素是否全部被释放if q+i==n-1:if stack:#释放当前q=stack.pop()+1max_len=max(max_len,max_len+len_ji)i=1#假如说0,3,6,7是由0和3,6,7拼凑起来的
#3,6,7是由3和6,7拼凑起来的
#6,7
#----所以可以将列表从后往前遍历
#记忆化,把自己走过的路记住
def fun3(nums):#获取nums数组长度n=len(nums)#以数组长度开辟空间nums_copy=[1]*nfor i in range(n,0,-1):for j in range(i,n): #因为nums_copy设置的默认值为1,所以nums数组尾部元素可以不进入循环,默认为1if nums[j]>nums[i-1]:#这样写是错误的原因在于#[3,7,101,18]若出现这种情况在运行的3时nums_copy的整体情况为#[1,2,1,1]  这时3,101,18均大于3,所以都会对3对应的最大长度#造成影响#nums_copy[i]=nums_copy[j]+1#所以我需要最大进行比较#就是当前该数(3)对应的最大长度和进行更改后的最大长度进行比较nums_copy[i-1]=max(nums_copy[i-1],nums_copy[j]+1)return max(nums_copy)该方法是直接基于f1的改进通过字典,进行记录
def fun4(nums):dic={
    }max_list=[]for i in range(len(nums)):max_list.append(bijiao1(nums,i,dic))return max(max_list)def bijiao1(nums,i,dic):if i in dic.keys():return dic[i]else:max_len=1for j in range(i+1,len(nums)):if nums[i]<nums[j]:#在字典里面一定是最长长度dic[j]=bijiao1(nums,j,dic)max_len=max(max_len,dic[j]+1)return max_len

#这个题目感觉玩不出来什么花样,就是进行简单的if,elif的判断def fun1(s):sum = 0for i in reversed(range(len(s))):if s[i]!=" ":sum+=1elif s[i]==" " and sum!=0:#说明不是第一次进来breakreturn sum

66. 加一

#第一种方法,很常见的,直接将所有数字拿出
#算出来对应的数,然后加1,在放进去(时间复杂度相对高,且并没有什么技术含量)#第二种方法,将尾部进行加1操作后进行判断
#---如果为10将其上一位进行加1操作
#---如果该位为10,将其上一位进行加1操作
#......
#直到若为列表首位,加1后为10,则需要进位def fun2(digits):#首先将特殊情况999999排除n=len(digits)i=0stop=Falsewhile i<n and not stop:if digits[i]!=9:stop=Trueif stop:j=n-1while j>=0:if digits[j]+1==10:#该位不加1,让首位加1,该位变为0#试想一下如果digits[j]+x(x为任意数)不是一定为10怎么办#答案在最后digits[j]=0j-=1continue#执行若没进入则执行digits[j]+=1breakreturn digitselse:#说明全部都是9,那么直接变成1000...就好了list1=[0]*(n+1)list1[0]=1return list1#(digits[j]+x)%10==1

#第一想法二进制转化为10进制进行求和
def fun1(a,b):#将a转化为10进制a_len=len(a)-1b_len=len(b)-1a_shi=0b_shi=0for i in a:a_shi+=int(i)*2**a_lena_len-=1for i in b:b_shi+=int(i)*2**b_lenb_len-=1sum_=a_shi+b_shi#再转化成二进制he=[]while sum_>0:he.append(sum_%2)sum_//=2sum_=0beishu=10for j in range(len(he),0,-1):sum_=sum_*beishu+he[j-1]return sum_

#这个题目有一种很巧妙的方法来求解
#下面就是代码
def fun1(nums):eor=0#首先是将数组遍历for i in nums:eor^=i#因为恰好有两个元素只出现一次#其他元素均出现偶数次(两次)#所以通过异或后#eor=a^b(a,b为不同数)#eor!=0#因为eor不为0,所以eor至少有一位(二进制存储)对应数为1#假设该位为"第10位"#第10位只有两种情况:0 or 1#所以可以通过第十位将所有数字进行分类  甲类和乙类#a,b一定一个为甲类,一个为乙类#找一个只有"第十位"为一的数 与 甲类做与运算,可以将属于甲类的全部提前出来,这样最后的结果一定为a or bright=eor&(~eor+1)  #这里可以将最右侧的1提取出来#eor=101011001#~eor=010100110#~eor+1=010100111#eor&(~eor+1)=000000001eor_a=0for i in nums:if(right&i==0):#说明该位置不为1eor_a^=ieor_b=eor^eor_alist1=[eor_a,eor_b]return list1

#首先买入为-
#卖出为+#这样的话这个题目就有点像最小子序和问题了
def fun1(prices):#开辟空间len_=len(prices)maichu=[0]*len_mairu=[0]*len_smdbg=[0]*len_for i in reversed(range(len(prices))):if(i==len_-1):maichu[i]=prices[i]elif(i==0):#只有买入情况mairu[i]=-prices[i]+max(max(maichu[i+1::]),0)else:#当前位置卖出可以得到的最大利润maichu[i]=prices[i]+max(max(mairu[i+1::]),0)#当前位置买入可以得到的最大利润mairu[i]=-prices[i]+max(max(maichu[i+1::]),0)return max(mairu)
print(fun1([1,2,3,4,5]))

#这个题目就是给一个数组,只要有一值存在两次即以上就可以输出了#首先的思路就是遍历数组,字典记录还是很常规的操作o(n)的时间复杂度
def fun1(nums):dic={
    }for i in nums:if i in dic.keys():return True#因为说明i不是第一次出现了else:dic[i]=1return False#排序也是可以的,归并排序,快速排序都行,很基础就不写了
#排序结束后相邻数两两比对

=============================================================================================================================================================================================================================================================================================
136. 只出现一次的数字
这个题目当时在学算法的时候是靠位运算写的,不得不说是一种很好的计算方法
以后可以往这里想一想,在这里推荐一下最近在学的算法课程
一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教
讲的是很好的

#这个题目在我最近学习的马士兵算法里面已经做过了,不过现在复习复习还是挺好的''' 神奇的位运算这里是二进制的存储方式1、与（&），按位与运算符：参与运算的两个值，如果两个相应位都为1，则该位的结果为1，否则为0同时为真,结果为真2、或（|），按位或运算符：只要对应的两个二进位有一个为1时，结果位就为1同时为假,结果为假3、异或（^）,按位异或运算符：当两对应的二进位相异时，结果为1不同为1,相同为00与任何数异或结果都为该数本身4、取反（~），按位取反运算符：对数据的每个二进制位取反，即把1变为0，把0变为1按位取反5、左位移（<<）,运算数的各二进位全部左移若干位，由<<右边的数字指定了移动的位数，高位丢弃，低位补06、右位移（>>）,把‘>>’左边的运算数的各二进制位全部右移若干位，>>右边的数字指定了移动的位数这两个好像相当于乘以2,除以2,不过记不太清了 '''#第一种方法使用"异或"运算符,因为一个数出现一次,其他数都出现两次,完全相同的数异或结果为0
def fun1(nums):eor=0for i in nums:eor^=ireturn eor#第二种方法
#依旧是遍历数组
#依旧是哈希表
def fun2(nums):dic={
    }for i in nums:dic[i]=dic.get(i,0)+1#这个代码一定是先执行右边如果有就返回对应value,如果没有就返回0#这样的到的结果你也不知道谁是1#所以你可以将字典.items()转化成列表查找,不过感觉有些麻烦,突然想到了一种更好的方法def fun3(nums):dic={
    }for i in nums:dic[i]=dic.get(i,0)+1if(dic[i]==2):dic.pop(i)for i in dic.keys():return i

'''题目要求:给定两个数组,编写一个函数来计算他们的交集注意:这里是交集,是指只要nums1中出现该元素,且nums2中也出现该元素,则可说该元素存在于交集中并且输出的列表中每个元素出现的次数,等同于该元素在两个列表中出现的最小次数 ''''''第一种方法,遍历大法＋哈希表1.遍历nums1,将结果记录在哈希表(haxi1)当中2.遍历nums2,并查找haxi1中是否有,有则删除添加到输出列表中 '''def fun1(nums1,nums2):#这种方法是我所喜爱的方法哈哈哈ls=[]dic={
    }for i in nums1:dic[i]=dic.get(i,0)+1#这样的话就得到了存储了所有的数据的字典for j in nums2:if j in dic.keys():if dic[j]==1:#说明现在还有一个值,直接删除掉dic.pop(j)ls.append(j)else:#只能是大于1dic[j]-=1ls.append(j)return ls'''第二种方法:想到了一种很蠢的方法,排序+双指针的遍历这样的话nlogn+mlogm+遍历哈哈哈不了不了 ''''''第三种方法:可以直接双指针吗??????两个数组本身都是无序的这就是说你只有暴力,把每种情况走一遍因为你不知道什么时候p_nums1移动,什么时候p_nums2移动所以这种方法可以说是暴力枚举哈哈哈比第二种还蠢,想偷懒,不可能 '''

'''题目要求:给定一个数组nums,编写一个函数将所有的0移动到数组的末尾,同时保持非0元素的相对顺序 ''''''方法一:遇到一个删除一个,最后一起加到最后面#这样的画每次的删除操作都是o(n)最后汇总虽然也是o(n)但是太慢了感觉 '''def fun1(nums):sum1 = 0  # 用来计数的i = 0n = len(nums)while (i < n - sum1):  # 这里不能给len(nums),因为nums的长度在减少这就是:len(nums)<=>n-sum1if (nums[i] == 0):nums.pop(i)sum1 += 1else:i += 1for i in range(sum1):nums.append(0)'''第二种方法开辟空间,用来存放非0数,后面再添加为0数这样的话会快一些,但需要消耗空间并且这个题目好像不想要你这样搞说明:必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。 ''''''那我们想一想怎么才能不额外开辟空间,同时时间复杂度还低换位置可以吗?试想一下,我现在的位置上对应的是个0,我可不可以循环找到第一个非0数(i)和他换位置,如果这样i与其他的相对元素位置不变但是0现在还是不在最后面?????哈哈哈我去看答案了,我发现就是这样,不过他用的是双指针,我是循环当然直接双指针更好 ''''''改进写法,循环+单指针1.假设当前位置为0,循环找到第一个非0数(i)和其换位置2.直到指针溢出需要说明的是这种写法并不好,他只是一种思路我就是因为遍历次数过多才抛弃的 '''
def fun2(nums):for i in range(len(nums)):if nums[i]==0:for j in range(i+1,len(nums)):if nums[j]!=0:nums[i],nums[j]=nums[j],nums[i]break#交换位置结束循环就好,如果为0,先啥都不干吧'''上面的单指针+循环主要的问题是走了太多的重复路,对于每一个元素都什么都不管的遍历而采用双指针可以有效的避免这个问题基本思路:来两个指针一个慢,一个快快的用来找,慢的用来换在这个过程中有两种情况:[q]=0, q+1[q]!=0 交换q+1,s+1假设有一数组[0,7,0,0,9,3,5]1.s=0,[q]=7 交换[7,0,0,0,9,3,5] 此时s=1,q=22.都为[q]=0,只改变q,此时q=43.[q]=9,交换[7,9,0,0,0,3,5],此时s=2,q=54.交换5.交换...在这个过程中观察可以看到,s始终在已经排序的最后一位,等待着q找到!=的数和他交换所以整个过程始终是有序的,如果一直没有碰到0就是自己和自己交换'''
def fun3(nums):s=q=0n=len(nums)while q<n:if nums[q]!=0:nums[s],nums[q]=nums[q],nums[s]s+=1q+=1

'''梦的开始,两数之和,人生第一道leetcode,今天他又回来了要求:给定一个整数数组nums,和一个整数目标值target,找出两个目标值(其和为target)返回对应下标看到这个题直接两种解放上来,双指针和哈希表 ''''''解法1:字典+遍历这种方法就是记录,下标及其对应的值,因为下标唯一,且数组nums中可能存在重复元素,所以使用下标做键元组做值.不这样不好,由于下标做键,你需要遍历键值对,感觉很浪费,并且题目要求的只是返回一组结果所以我们还是元素做键,下标做值.我又感觉每一次查找很麻烦,不知道到底那个好,反正我写的是元素做键,下标做值 '''def fun1(nums,target):dic={
    }for i in range(len(nums)):key=nums[i]for j in dic.keys():if j+key==target:return i,dic[j]#如果循环正常结束,则说明没有找到if key not in dic.keys():#不在则创建dic[key]=i#看了一下答案,发下最好的写法就是哈希表
#然后我发现他是这样写的,查找target-i是否在哈希表中
def fun4(nums,target):dic = {
    }for i in range(len(nums)):key = nums[i]if target - key in dic.keys():#字典的查找是常数级操作return i, dic[target - key]# 能走到这说明没找到dic[key] = i  # 无论有没有key在哈希表中,直接赋值准没错'''双指针懒得写了,有点暴力的感觉,准确来说就是暴力.不知道能不能优化一下在时间复杂度上落后太多 '''def fun2(nums,target):pass'''可不可以先排序,再二分????因为大于目标值的是可以排除掉的选项那么我先通过二分,找到合适的区间再开始查找???有个问题,记录最开始的下标突然又想到,我都已经排序了我直接拿target-当前数得到需要的数,然后二分查找?这不是非常完美那么重点来了,如何记录下标这个玩意我不知道,一会看答案有没有记录,我就直接查找好吧,得到这两个数之后再在未排序数组中直接查找这两个数对应的下标他不香吗?????????? '''def fun3(nums,target):nums1=nums.copy()#复制一个nums.sort()#排序,偷个懒直接用人家的,毕竟我最近刚过完排序,这个代码的核心也是二分for i in range(len(nums1)):j=target-nums1[i]#如果要达到target需要jxiabiao=erfen(nums,j)if xiabiao:#这里是说这个j在nums中是否存在,存在#如果存在进来for c in range(len(nums1)):if nums1[c]==j:if i!=c:#确定不是同一元素return i,c
def erfen(nums,item):l=0r=len(nums)-1while l<=r:mid=(l+r)//2if nums[mid]<item:l=mid+1elif nums[mid]==item:return Trueelse:r=mid-1return Falseprint(fun3([3,2,4],6))

#这个题目是二维数组
#可以说是二维数组的查找
#找不到重复元素就是正确的
'''数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）只会出现重复和刚刚好两种情况注意:我只需要验证已经填入的数字是否是有效的,而不需要在意怎么解 ''''''方法一(暴力循环+字典):直接暴力,这时很简单的思路假如说遍历一次是n,一共需要遍历3次,每一次遍历过程中只需要一个字典进行记录,再说了9*9的二维数组还是很小的 ''''''今天是10月11日,我又一次做这个题,很快的就做出来了,但是很明显,做麻烦了还记得上次做时判断行和列都很简单,唯独一个格子一个格子搞不出来今天我就这个样子想的用当前行(i)//3和当前列(j)//3可以得到:0,0 0,1 0,21,0 1,1 1,22,0 2,1 2,2这样就可以以:通过i//3与j//3的大小进行分组 '''
def fun1(board):ge_all_list1=[[],[],[]]#对角线ge_all_list2=[[],[],[]]#对角线上方ge_all_list3=[[],[],[]]#对角线下方for i in range(9):      #总的遍历次数hang_list=board[i]#第几行,对应的列表dic_hang={
    }#字典进行记录for j in range(9):if hang_list[j]!='.':#说明是数字,进行一个查找,有直接报错if hang_list[j] in dic_hang:#这就是查在不在字典里面return Falseelse:dic_hang[hang_list[j]]=0#这里只要有就行了#这里还需要把格子元素放进去if i//3==j//3:#这样可以证明是对角线ge_all_list1[i//3].append(hang_list[j])elif i//3<j//3:#如果为空所以可以放元素ge_all_list2[i//3+j//3-1].append(hang_list[j])elif i//3>j//3:ge_all_list3[i//3+j//3-1].append(hang_list[j])'''搞列就好了'''for i in range(9):dic_lie={
    }for j in range(9):#board[j][i],这样写,只动列不动行item=board[j][i]if item!='.':if item in dic_lie:return Falseelse:dic_lie[item]=0#看格子:for i in range(3):#里面所具有的列表个数dic_lie1= {
    }dic_lie2= {
    }dic_lie3= {
    }item1=ge_all_list1[i]item2=ge_all_list2[i]item3=ge_all_list3[i]for j in range(len(item1)):if item1[j] in dic_lie1:return Falsedic_lie1[item1[j]]=0for j in range(len(item2)):if item2[j] in dic_lie2:return Falsedic_lie2[item2[j]]=0for j in range(len(item3)):if item3[j] in dic_lie3:return Falsedic_lie3[item3[j]] = 0return Trueprint(fun1([["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]))'''看一下答案是怎么写的,答案只写了一个循环,但是思想没什么区别都是行看一遍,列看一遍,格子里面的看一遍 ''''''注意看一格一格是这样的:假设i是行,j是列,会有i//3,j//30,0 0,1 0,21,0 1,1 1,22,0 2,1 2,2这样可以开辟一个三维数组,长这个样子gezi=int[3][3][9]这样可以以i//3和j//3进行划分'''
def fun2(board):hang=[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]#lie=[[0]*9]*9,我最开是这样开辟数组的,但是有一个问题,对一个列表的更改,会影响其他#元素,我猜测是因为,他们其实是指向投以列表的内存地址,本质上是一个元素lie=[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]gezi=[[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]],[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]],[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]]for i in range(9):for j in range(9):item=board[i][j]if item!='.':ind=eval(item)-1hang[i][ind]+=1#hanglie[j][ind]+=1gezi[i//3][j//3][ind]+=1if hang[i][ind]>1 or lie[j][ind]>1 or gezi[i//3][j//3][ind]>1:return Falsereturn Trueprint(fun2([["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]))ls=[[0]*9]*9#确实是指向同一个内存地址,所以牵一发而动全身
print(ls)#[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], 
# [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], 
# [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
for i in ls:print(id(i))# 2352051450176# 2352051450176# 2352051450176# 2352051450176# 2352051450176# 2352051450176# 2352051450176# 2352051450176# 2352051450176

#这玩意和数组中的第一个数字一样的hash表就能做'''方法一:循环+hash表 '''
def fun1(s):dic={
    }#哈希表for i in range(len(s)):if s[i] in dic:#[i]已经在字典当中#可以进行删除操作#dic.pop(s[i]) 这里不能删除,如果该元素出现了奇数次那么会导致第三次出现的时候被误替了dic[s[i]]=-1#索引不可能出现-1else:#不在字典中dic[s[i]]=i#让他进去#检查一下字典for i in dic:if dic[i]!=-1:return dic[i]#一般元素都是看似尾部的添加return -1'''方法二:队列,队列本身具有先进先出的性质,在每次入对的时候进行一个判断,看元素的首位是否等同于入对元素,如果是进行出队操作.这样的话,遍历一遍字符串得到的队列的首位就是首个不重复元素 '''
'''写的有问题 '''
def fun2(s):#开辟队列空间duilie=[-1]*len(s)duilie[0]=[s[0],0]#记录出现多次但未删除元素dic={
    }#当前首位shouwei=0for i in range(1,len(s)):if s[i]==s[shouwei][0]:pass
print(fun2("aabb"))

#题目要求原地反转(不使用额外空间)
#题目本身的难度并不高所以思路很简单'''方法1:取中值使得i和n-i不断的调换位置 '''def fun1(s):n=len(s)-1mid=n//2i=0while i<=mid:s[i],s[n-i]=s[n-i],s[i]i+=1print(s)
fun1(["H","a","n","n","a","h"])

'''首先直接转化为字符串,反转一下是非常简单的,也是非常愚蠢的,因为在大量使用别人的代码 ''''''根据数学:不断的除以10取余数,是非常方便的 '''def fun1(x):t=10sum1=0a=abs(x)while a>0:sum1=sum1*t+a%10a=a//10if not -2**31<=sum1<=2**31-1:return 0if x<0:return -sum1return sum1
print(fun1(123))

242. 有效的字母异位词

'''字母异位词:若s和t中每个字符出现的次数相同,则称s和t互为字母异位词从这个概念中不难看出:--你必须遍历完s和t,且每一次遍历都需要进行保存--在遍历结束后需要进行比较--如果长度不同,那么不可能字母异位词***** ''''''方法一:遍历+哈希表 '''
def fun1(s,t):cur=0#当前下标len_s=len(s)len_t=len(t)#首先判断长度是否相同if len_s!=len_t:return False#不可能了,我俩s_dic={
    }t_dic={
    }while cur<len_s:s_dic[s[cur]]=s_dic.get(s[cur],0)+1t_dic[t[cur]]=t_dic.get(t[cur],0)+1cur+=1for t_key in t_dic:#循环拿出键if t_key not in s_dic or t_dic[t_key]!=s_dic[t_key]:#只要t的键不在s字典里面,或者该元素,在两个表中出现的次数不同则结束了return Falsereturn True
print(fun1("anagram","nagaram"))'''第二种方法:排序,对字符串进行排序(通过unicode编码转化为数字进行比较)对于字母异位词,排序后,s和t是两个一模一样得字符串 '''
'''这个排序直接用的人家的,要我写的话只能是先转化为对应得数字排序,再转回来,当然因为字符本身是可以比较的,所以不转也行 '''
def fun2(s,t):if len(s)!=len(t):return Falses=list(s)t=list(t)#需要注意一下,字符串是不可以字节排序的,需要转化为列表s.sort()t.sort()for i in range(len(s)):if s[i]!=t[i]:return Falsereturn True
fun2("anagram","nagaram")