前言：
今天给自己开一个坑，100Days of 100 line Code。在接下来的一百天里面，每天保持100行的有效代码量，并讲思路和错误写在博客上面。
当然，日期可能不是一百天，代码也不会只是100行。
希望自己坚持。
-------------------------------------------------------------------------------------------------------------------------------------
LeetCode #1 两数之和
题目链接：https://leetcode-cn.com/problems/two-sum/description/
代码：
class Solution: def twoSum(self, nums, target): new_dict = {} # 创建储存结果字典 for i in range(len(nums)): # 遍历列表的所有元素 new_dict[target - nums[i]] = i # 将target-i作为key，i作为value，储存到字典内 for i in range(len(nums)): if nums[i] in new_dict and new_dict[nums[i]] != i: # 判断i是否在储存结果的字典内，且i不等于target-i return [i, new_dict[nums[i]]] nums = [2,7,15,11] target = 9 Solution.twoSum(0,nums,target)
LeetCode #4 两个排序数组的中位数
题目链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/description/
代码：
class Solution: def findMedianSortedArrays(self, nums1, nums2): new_nums = [] # 创建新数组 ''' 两个循环将数组合并 ''' for i in range(len(nums1)): new_nums.append(nums1[i]) for i in range(len(nums2)): new_nums.append(nums2[i]) new_nums.sort() # 对合并数组进行排序处理 mid = int(len(new_nums)/2) # 取出新数组中间值的索引 if len(new_nums)%2 == 0: # 对数组进行判断，是否是偶数 rmid = (new_nums[mid] + new_nums[mid-1])/2 # 为偶数 中位数则为两数之和的除数 else : rmid = new_nums[mid] return float(rmid) nums1 = [1,3] nums2 = [2] s=Solution() print (s.findMedianSortedArrays(nums1,nums2))
LeetCode #11盛最多水的容器
题目链接：https://leetcode-cn.com/problems/container-with-most-water/description/
代码：
暴力解法：
对每个顶点进行遍历
class Solution: def maxArea(self, height): new_area = [] # 创建新数组，储存面积 for i in range(len(height)): # 遍历所有的坐标点height[i] for j in range(i+1,len(height)): # 遍历与height[i]对应的所以坐标点height[j] if height[i]>=height[j]: # 判断高度 高度以低的为ture new_area.append(height[j]*(j-i)) # 计算面积并储存到new_area数组 else : new_area.append(height[i]*(j-i)) new_area.sort() # 对储存面积的数组进行排序 得到最大值 return new_area[len(new_area)-1] height = [5,4,3,2,1] s=Solution() print(s.maxArea(height))
二分法
从两头开始往中间开始遍历
class Solution: def maxArea(self, height): left = 0 right = len(height)-1 area = 0 while left < right: if height[left] >= height[right]: if area < height[right]*(right-left): # 判断 左顶点指针高度是否大于右顶点指针高度， 面积指针是否大于当前顶点指针面积 area = height[right]*(right-left) # 对面积指针进行更新 right -= 1 # 对左顶点指针进行更新 else : if area < height[left]*(right-left): # 判断 左顶点指针高度是否小于右顶点指针高度， 面积指针是否大于当前顶点指针面积 area = height[left]*(right-left) left += 1 return area height = [1, 8, 6, 2, 5, 4, 8, 12, 7] s=Solution() print(s.maxArea(height))
LeetCode #14 三数之和
题目链接：https://leetcode-cn.com/problems/3sum/description/
代码：
暴力解法
class Solution(object): def threeSum(self,nums): new_nums=[] for i in range(len(nums)): for j in range(i+1,len(nums)): for k in range(j+1,len(nums)): if nums[i]+nums[j]+nums[k] == 0:# 判断三个元素相加是否为0 if new_nums==[]: # 如果新数组内容为空 new_nums.append([nums[i],nums[j],nums[k]]) #将目标值的索引append到新数组种 else: count = 0 for t in range(len(new_nums)):# 遍历已有的结果数组 if not ((nums[i] in new_nums[t]) and (nums[j] in new_nums[t]) and (nums[k] in new_nums[t])): # 判断循环值是否存在于子列表里面 count+=1 # 如果存在+1 if count == len(new_nums): #判断是否全部存在 new_nums.append([nums[i],nums[j],nums[k]]) return new_nums
结果很悲剧，开始只AC二十多组数据，后面修改之后AC了200组数据，一直没有全部AC
后面在群里，各位大佬讲解了二分法的思路
二分法
class Solution: def threeSum(self, nums): new_nums = [] # 创建新的数组储存数据 nums.sort() # 对原有数组进行排序处理 for i in range(len(nums)-2): # 从小到大遍历所有的元素 if i == 0 or nums[i] > nums[i-1]: # 去重处理以0分分界点避免重复 left = i+1 # 创建左指针 right = len(nums)-1 # 创建右指针 while left < right: ident = nums[left] + nums[right] + nums[i] #将nums[i]加上最大的 和 最小的 数字 ''' 判断ident 如果为0，append到新的数组种，并更新指针 并对指针进行判断是否有重复值，如果有，就跳过 如果ident大于0，则想要的结果在左边，更新左边的指针 如果ident小于0，则想要的结果在右边，更新右边的指针 ''' if ident == 0: new_nums.append([nums[i], nums[left], nums[right]]) left += 1; right -= 1 while left < right and nums[left] == nums[left-1]: # skip duplicates left += 1 while left < right and nums[right] == nums[right+1]: right -= 1 elif ident < 0: left += 1 else: right -= 1 return new_nums nums=[-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0] new_nums=Solution.threeSum(0,nums) print(new_nums)