leetcode日常总结一

26：删除排序数组中的重复项 题目描述： 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 思路： 设j=0用来存储第一个值的位置，从前往后依次遍历数组，一旦对比找到不等于第一个值的就把它的数值移到数组的第二个位置，然后j值设为第二个数下标，完成后通过i下标继续再往后对比。结束后下标j+1往后的位置就是重复项删除即可。 代码：

class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ if len(nums)==0: print(0) j=0 for i in range(len(nums)-1): if nums[i]!=nums[i+1]: nums[j+1]=nums[i+1] j+=1 del nums[j+1:] print len(nums)

27：移除元素 题目描述： 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。 思路： 将j的初值设为0，遍历数组只要不等于val,就将此值赋给下标为j的位置，相应j下标自动加一，最后返回的j就是数组的新长度。 代码：

class Solution(object): def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rtype: int """ j=0 for i in range(len(nums)): if nums[i]!=val: nums[j]=nums[i] j+=1 return j

35：搜索插入位置 题目描述： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 思路一： 设一个变量初值为0，从前往后遍历数组，只要不相等且大于目标值则此位置就为插入位置；否则继续往后遍历相应的j自加一。若相等则返回j,遍历完若都比目标值小则返回j。 思路二： 由于条件注明数组有序，则可以用二分查找。分别将数组首尾位置赋予变量i，j，找到中间位置mid=(i+j)//2，将目标值与mid位置的值比较，若相等此位置就为插入位置，若目标值大于mid位置的值，则下次查找位置为下半部分mid+1~j,否则就从上半部分i到mid-1查找。 代码：

class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ i=0 j=len(nums)-1 if nums[i]>target: return 0 if nums[j]<target: return j+1 while(i<=j): mid=(i+j)//2 if nums[mid]>target: j=mid-1 elif nums[mid]<target: i=mid+1 else: return mid return i

38：报数 题目描述： 报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。前五项：

1 11 21 1211 111221

思路： 使用递归先获取上次的报数得到当前要统计的字符串l，把l的首位赋给a作为初始值，再设一个变量j为0用来计算相同字符出现的次数。开始遍历l,如果当前查找的数与当前a的值相等，则j+1；否则首先报数，然后将当前i赋值给a重新开始统计当前a的次数，此时j应赋值为1（由于已经出现了第一个a值）。退出循环的时候最后一个或几个相同的字符并没有连接在字符串后面，所以后面一个加上now+=str(j)+a。 代码：

class Solution(object): def countAndSay(self, n): """ :type n: int :rtype: str """ if n==1: return '1' else: l=self.countAndSay(n-1) now='' a=l[0] j=0 for i in l: if i==a: j+=1 else: now+=str(j)+a j=1 a=i now+=str(j)+a return now

58：最后一个单词的长度 题目描述： 给定一个仅包含大小写字母和空格 ’ ’ 的字符串，返回其最后一个单词的长度。如果不存在最后一个单词，请返回 0 。 思路： 设初始值j为0，从后往前遍历，只要不为空格j就自加一来统计当前字符的数量，若遇到空格且当前j的值不为零，则证明存在最后一个单词返回j值即可；若循环完都没有空格则证明只存在一个单词或为空的字符串返回当前j值。 代码：

class Solution(object): def lengthOfLastWord(self, s): """ :type s: str :rtype: int """ b=0 for i in s[::-1]: if i!=' ': b+=1 else: if b!=0: return b return b

53:最大子序和 题目描述： 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 思路一： 当加上一个正数时，和会增加；当加上一个负数时，和会减少。所以在数组遍历的过程中，一边累加数组元素，一边比较累加结果和0的关系，如果当前总和是负数那么如果下一个值比你当前总和大那就从下一个地方重新开始，否则就可以一直加下去。 思路二： 动态规划： 首先考虑最后一个元素arr[n-1]与最大子数组的关系，有如下两种情况： 1：最大子数组以arr[n-1]结尾 2：最大子数组跟arr[n-1]没关系，最大子数组在arr[0, n-2]范围内，转为考虑元素arr[n-2] 那么假设： 1：有序列表以arr[n-1]为结尾的最大子数组和为End[n-1] 2：有序列表 在[0-(n-1)]范围内的最大子数组和为All[n-1] 如果最大子数组跟最后一个元素无关，即最大和为All[n-2]（存在范围为[0-n-2]），则解All[n-1]为两种情况的最大值，即 All[n-1] = max(End[n-1]，All[n-2] ) 即All[i] = max(End[i]，All[i-1] ) 当i = 0时， All[0] = End[0] = arr[0], 因此All[i] = max(End[i]，All[i-1] ) = max(End[i]，End[i-1], End[i-2], …, End[0] )(max为幂等运算） 而End[i] = max(arr[i], End[i-1] + arr[i])， 即以arr[i]为结尾的最大子数组和为“以arr[i-1]为结尾的最大子数组和与arr[i]之和” 跟 arr[i]中取较大值。因此当 End[i-1]小于0时，End[i] = arr[i]。 因此我们用nums[i]保存End[i]，从i=1开始依次判断End[i-1]并赋值End[i]，最后从End[n]数组中取出最大值，即为最大子数组和。

代码：

class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ max=nums[0] sum=0 for i in nums: sum+=i if sum>max: max=sum if sum<0: sum=0 return max for i in range(1, len(nums)): nums[i]= nums[i] + max(nums[i-1], 0) return max(nums)

66：加一 题目描述： 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 思路： 遍历数组将每次得到的值强转为字符类型放入一个空字符串中，将得到的字符串强转为整型进行加一操作再转为字符串类型赋值给a,最后遍历a赋值给一个空列表。不会因为加一操作导致溢出问题。

代码：

class Solution(object): def plusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ a='' for i in digits: a+=str(i) a=str(int(a)+1) list1=[] for j in a: list1.append(j) return list1

67：二进制求和 题目描述： 给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。 思路： 首先将两个二进制字符串的长度通过在较短字符串前面添0设置相等，定义一个进位符c值初值为0，取值为0或1，然后从后往前依次将两个字符串对应位置转换为整型再加上c得到sum,其结果为0，1，2，3。当为0，1则进位符c取值为0，将和与之前sum值拼接；否则为进位取1，将0或1拼接到sum值。最后看c值决定是否首位需要进位。 代码：

class Solution(object): def addBinary(self, a, b): """ :type a: str :type b: str :rtype: str """ if len(a)>len(b): b=(len(a)-len(b))*'0'+b elif len(a)<len(b): a=(len(b)-len(a))*'0'+a c=0 sum='' for i in range(len(a)-1,-1,-1): sum1=int(a[i])+int(b[i])+c if sum1==2: c=1 sum='0'+sum elif sum1==3: c=1 sum='1'+sum else: c=0 sum=str(sum1)+sum if c: sum='1'+sum return sum

83：删除排序链表中的重复元素 题目描述： 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 思路： 将链表头记录下防止丢失，从头查找，当前节点的值 如果等于后一个节点的值，这就出现了重复，此时可令 head.next = head.next.next，如果当前节点的值 head.val 不等于后一个节点的值,则head 指向后一个节点。

代码：

class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ a=head while head: if head.next and head.val==head.next.val: head.next=head.next.next else: head=head.next return a

70:爬楼梯 题目描述： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 思路： 动态规划问题，此题抽象出来是一个斐波那契数列。为了避免递归造成的大量重复计算，则从底向上得出结果。 设跳n个台阶有f(n)种方法， 爬1个：1种 爬2个：2种 爬n个：面临两种选择： （1） 第一次爬1个，此时剩余n-1个台阶，有f(n-1)种方法 （2） 第一次爬2个，此时剩余n-2个台阶，有f(n-2)种方法 所以f(n) = f(n-1) + f(n-2)

代码：

class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ if n==1: return 1 elif n==2: return 2 else: s=[0,1,2] for i in range(n-2): a=s[-1]+s[-2] s.append(a) return s[-1]