LeetCode小白入门——八道简单题合集，每道题有两种解法一些，第二种会更高效，尽量避免使用Python的内置函数，这样才能真正理解算法原理。链接：https://leetcode-cn.com/probl...1.两数之和题目描述：给定一个整数数组nums和一个目标值target，请求数组中目标值之和那两个整数，并返回它们的数组下标。您可以假设每个输入只有一个答案。但是，数组中的同一个元素不能使用两次。示例：给定nums=[2,7,11,15]，target=9。由于nums[0]+nums[1]=2+7=9，因此返回[0,1]。这道题的大意是num[i]一定位于数组中，所以只要找出target-num[i]在数组中的位置即可。第一种方法是遍历数组，但是每次循环都会使用切片将i之前的元素转换成新的数组。这样做是为了处理数组中出现类似[2,3,3,5]的相邻数字。地位。如果找到匹配值，则将其分配给j，并且由于j始终在i之前，因此返回[j,i]。deftwoSum(nums,target):j=-1foriinrange(1,len(nums)):new_nums=nums[:i]iftarget-nums[i]innew_nums:j=new_nums.index(target-nums[i])breakifj>=0:return[j,i]第二种方法是利用哈希表，先初始化一个空字典，遍历数组，如果target-num[i]在dictionary值的索引和i；如果没有出现在字典中，则以该值作为键，将索引作为值传入字典，在下一次循环中进行判断。deftwoSum(nums,target):dict_={}foriinrange(len(nums)):iftarget-nums[i]indict_:return[dict_[target-nums[i]],i]else:dict_[nums[i]]=iMethod1takes548ms,memoryconsumption14.8MBMethod2takes68ms,memoryconsumption14.9MB反转每个位上的数字。示例：输入：123输出：32，输入：-123输出：-321，输入：120输出：21注：假设我们的环境只能存储32位有符号整数，取值范围为[?231,231?1].根据这个假设，如果整数在反转后溢出，则返回0。第一种方法是使用字符串，先将字符串反转。这一步可以使用切片或者内置函数reverse。如果输入数字$x\geq0$，直接将反转后的字符串转为整数赋值给num；如果$x<0$，则需要??在字符串前加“-”，然后将其转化为整数赋值给numnum。如果num在范围内，直接返回，否则返回0defreverse(x):str1=str(abs(x))str2=str1[::-1]ifx>=0:num=int(str2)else:str3='-'+str2num=int(str3)ifnum<(-2)**31ornum>2**31-1:return0else:returnnum第二种方法是用数学方法，而整数的最后一位可以通过整数除以10取余数得到整数的最后一位数字和整数底除法的组合可以去掉整数的最后一位得到倒数，后面的判断同上以上方法。defreverse(x):temp=abs(x)i=len(str(temp))num=0whilei>0:num=num*10+temp%10temp=temp//10i-=1ifx<0:num=-numifnum<(-2)**31ornum>2**31-1:return0else:returnnum方法一耗时52ms，耗内存13.7MB方法二耗时52ms，耗内存13.4MB13。罗马数字转换示例：输入："III"输出：3，输入："IV"输出：4，输入："MCMXCIV"输出：1994(解释：M=1000,CM=900,XC=90,IV=4).第一种方法是使用字典（哈希表）进行暴力破解，将所有可能的组合以罗马数字为键，阿拉伯数字为值的形式存储在字典中。对于输入的字符串，如果一个字符对应的值小于右边的值，那么这个组合一定是IV、IX、XL、XC、CD、CM中的一个。然后可以用切片截取字符串中的两位，在字典中查询这个组合对应的值，下标需要往后移两位；否则，只需要在字典中查询该字符对应的值，将下标向后移动一位即可。defromanToInt(self,s:str)->int:dict_={"I":1,"IV":4,"V":5,"IX":9,"X":10,"XL":40,"L":50,"XC":90,"C":100,"CD":400,"D":500,"CM":900,"M":1000}sum=0i=0whilei=len(s):returnsumelse:returnsum+dict_[s[-1]]最后为什么还要加一个判断呢？就是因为i的取值范围是(0,len(s)-1)，所以最终的query可能是组合也可能是单个字符，需要区分这两种可能。第二种方法也使用哈希表。这个方法也是遍历整个字符串。如果一个字符比它右边的字符小，则从和中减去该字符的对应值。例如IV不是-1+5=4；否则，就在和的基础上加上字符对应的值即可。由于一次只判断一个字符，所以不需要对结果进行上述区分。defromanToInt(self,s:str)->int:dict_={"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}sum=0foriinrange(len(s)-1):ifdict_[s[i]]len(i):str0=str0[:len(i)]forjinrange(len(str0)):ifstr0[j]!=i[j]:str0=str0[:j]breakreturnstr0第二种方法结合使用zip和set方法，下面结合一些断点程序的运行截图有说明。deflongestCommonPrefix(strs):words=list(zip(*strs))str_=''foriinwords:word=list(set(i))iflen(word)==1:str_+=word[0]else:breakreturnstr_可以看到zip(*strs)会将每个字符串对应位置的字符存储成一个元组，元组的个数就是输入中字符串的最小长度。然后遍历单词列表，并使用set方法为每个祖先删除重复项。如果去重后新列表的长度为1，则证明这个字符是三者共有的，可以将其添加到定义的空字符串str_中；否则，跳出循环并返回字符串str_。方法一耗时48ms，消耗内存13.6MB方法二耗时36ms，消耗内存13.7MB']'判断字符串是否有效。一个有效的字符串需要满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序关闭。请注意，空字符串被视为有效字符串。示例：输入：“()[]{}”输出：true，输入：“(]”输出：false，输入：“([)]”输出：false，输入：“{[]}”输出：true。第一种方法使用内置方法replace。根据例子可以看出，每组括号都需要对应要淘汰的左右括号。只要字符串中包含可以去掉的括号，就可以用空字符串替换。替换，如果最后一个字符串为空，则返回True，否则返回False。defisValid(s):iflen(s)%2!=0:returnFalsewhile'()'insor'[]'insor'{}'ins:s=s.replace('()','').replace('[]','').replace('{}','')returns==''第二种方法使用了栈的思想，先根据右边bracket作为key，将左括号以value的形式传入字典，然后遍历整个字符串。如果是左括号，则入栈。然后，如果是右括号，则比较对应的左括号是否与栈顶的左括号相同。如果相同则出栈，不同则入栈，循环栈与原栈相同则返回True，否则返回False。这里需要注意的是，在新定义栈的时候，需要往里面添加一个元素，防止比较的时候列表下标溢出。defisValid(s):ifs=='':returnTruedict={')':'(',']':'[','}':'{'}stack=[0]foriins:如果我在['(','[','{']:stack.append(i)elifdict[i]==stack[-1]:stack.pop()else:stack.append(i)returnstack==[0]方法一耗时56ms，耗内存13.7MB方法二耗时44ms，耗内存13.7MB这样每个元素只出现一次，返回被移除数组的新长度。不要用extra数组空间，您必须就地修改输入数组并使用O(1)额外空间来执行此操作。示例：给定nums=[0,0,1,1,1,2,2,3,3,4]，函数应返回新的长度5，并将原始数组nums的前五个元素修改为0、1、2、3、4，数组中超出新长度的元素无需考虑。写程序的时候一定要注意题目中的两个关键要求。一种是不使用额外的空间，所以这里不能定义新的数组；另一个是不考虑数组中超出新长度的元素。根据示例中的需求，您可以选择删除、覆盖、交换多种方式。第一种方法使用双指针，分别初始化为0和1，遍历输入数组。如果两个指针对应的元素值相等，则移除后一个指针对应的元素；否则，将两个指针加一并继续检查数组。剩余的元素。defremoveDuplicates(nums):market1,market2=0,1whilemarket20:mar1=mar1-mar2+1#返回下一个匹配的数字mar2=0else:mar1+=1returnmar1-nifmar2==nelse-1方法1耗时28ms，消耗14.8MB内存。方法2耗时60ms，占用内存14.7MB。35、搜索插入位置题目描述：给定一个排序好的数组和一个目标值，在数组中找到目标值并返回其索引。如果数组中不存在目标值，则返回将按顺序插入的位置。您可以假设数组中没有重复元素。示例：输入：[1,3,5,6],5输出：2，输入：[1,3,5,6],2，输出：1，输入：[1,3,5,6],7输出：4.第一种方法使用单层循环搜索。因为输入数组是一个排序数组，所以只需要找到数组中大于等于目标元素的第一个下标即可。如果相等，那么position就是目标在数组中的位置。如果大于，则该位置就是需要插入目标的位置；如果没有满足条件的元素，则证明目标最大，需要插入到链表尾部。defsearchInsert(nums,target):mar=0whilemar=target:returnmarmar+=1returnlen(nums)第二种方法是二分查找法，先初始化一个左指针left，一个右指针right，找到两者中间的下标mid。如果该位置的元素小于target，则下次查找mid+1到right之间的元素；如果该位置的元素大于target，则下次查找left和mid-1之间的元素；如果两者相等（target在array），则直接返回mid，否则返回左指针left。defsearchInsert(nums,target):left=0right=len(nums)-1while(left<=right):mid=(right+left)//2ifnums[mid]target:right=mid-1else:returnmidreturnleft方法一耗时44ms，耗内存14.1MB方法二耗时36ms，耗内存14.4MB
