Add files via upload

linwt · web-flow · commit 1357b0def7fc · 2019-09-23T23:39:55.000+08:00
diff --git a/leetcode/011.盛最多水的容器.py b/leetcode/011.盛最多水的容器.py
@@ -0,0 +1,15 @@
+# 双指针移动
+class Solution(object):
+    def maxArea(self, height):
+        l, r, m = 0, len(height)-1, 0
+        while l < r:
+            # 记录当前最大面积
+            hl, hr = height[l], height[r]
+            cur = min(hl, hr) * (r-l)
+            m = max(m, cur)
+            # 高度较小一端向内移动，获得可能更大的面积
+            if hl < hr:
+                l += 1
+            else:
+                r -= 1
+        return m
diff --git a/leetcode/015.三数之和.py b/leetcode/015.三数之和.py
@@ -0,0 +1,20 @@
+# 数组排序后，先固定一个数，再用双指针从头尾向内移动确定另外两个数
+class Solution(object):
+    def threeSum(self, nums):
+        n = len(nums)
+        nums.sort()
+        res = set()
+        for i in range(n-2):
+            x, y = i+1, n-1
+            while x < y:
+                if nums[i] + nums[x] + nums[y] == 0:
+                    # 去重
+                    res.add((nums[i], nums[x], nums[y]))
+                    x += 1
+                    y -= 1
+                if nums[i] + nums[x] + nums[y] > 0:
+                    y -= 1
+                if nums[i] + nums[x] + nums[y] < 0:
+                    x += 1
+        # 还原为列表
+        return [list(l) for l in res]
diff --git a/leetcode/018.四数之和.py b/leetcode/018.四数之和.py
@@ -0,0 +1,23 @@
+# 数组排序后，先固定两个数，再用双指针从头尾向内移动确定另外两个数
+class Solution(object):
+    def fourSum(self, nums, target):
+        n = len(nums)
+        nums.sort()
+        res = set()
+        for i in range(n-3):
+            for j in range(i+1, n-2):
+                l, r = j+1, n-1
+                while l < r:
+                    temp = nums[i] + nums[j] + nums[l] + nums[r]
+                    if temp == target:
+                        # 去重
+                        res.add((nums[i], nums[j], nums[l], nums[r]))
+                        l += 1
+                        r -= 1
+                    # 结果比目标值大，右指针左移减小数值
+                    if temp > target:
+                        r -= 1
+                    # 结果比目标值小，左指针右移增大数值
+                    if temp < target:
+                        l += 1
+        return [list(t) for t in res]
diff --git a/leetcode/043.字符串相乘.py b/leetcode/043.字符串相乘.py
@@ -0,0 +1,3 @@
+class Solution(object):
+    def multiply(self, num1, num2):
+        return str(int(num1)*int(num2))
diff --git a/leetcode/050.Pow(x, n).py b/leetcode/050.Pow(x, n).py
@@ -0,0 +1,15 @@
+# 折半计算，每次将n缩小一半
+class Solution(object):
+    def myPow(self, x, n):
+        if n < 0:
+            n, x = abs(n), 1/x
+        res = 1
+        while n:
+            # n为奇数则需要乘一个x
+            if n % 2:
+                res *= x
+            # x翻倍
+            x *= x
+            # n缩小一半
+            n //= 2
+        return res
diff --git a/leetcode/151.翻转字符串里的单词.py b/leetcode/151.翻转字符串里的单词.py
@@ -0,0 +1,4 @@
+# 按空格切分单词再反转
+class Solution(object):
+    def reverseWords(self, s):
+        return ' '.join(s.split()[::-1])
diff --git a/leetcode/215.数组中的第K个最大元素.py b/leetcode/215.数组中的第K个最大元素.py
@@ -0,0 +1,10 @@
+# 遍历数组，用一个长度为k的列表存放最大的k个数，返回列表中的最小值即为第k大的数
+class Solution(object):
+    def findKthLargest(self, nums, k):
+        res = []
+        for num in nums:
+            if len(res) < k:
+                res.append(num)
+            elif num > min(res):
+                res[res.index(min(res))] = num
+        return min(res)
diff --git a/leetcode/238.除自身以外数组的乘积.py b/leetcode/238.除自身以外数组的乘积.py
@@ -0,0 +1,35 @@
+# 方法一：分类讨论
+class Solution(object):
+    def productExceptSelf(self, nums):
+        z = nums.count(0)
+        # 大于1个0的情况，累积结果全部为0
+        if z > 1:
+            return [0]*len(nums)
+        # 1个0的情况，除了0位置，其他都为0
+        if z == 1:
+            res = [0]*len(nums)
+            index = nums.index(0)
+            nums.pop(index)
+            r = 1
+            for num in nums:
+                r *= num
+            res[index] = r
+            return res
+        # 没有0的情况，先算累积，再用总积去除逐个位置的数
+        res = 1
+        for num in nums:
+            res *= num
+        return [res/i for i in nums]
+
+
+# 方法二：当前数 = 左边的乘积 x 右边的乘积
+class Solution(object):
+    def productExceptSelf(self, nums):
+        n = len(nums)
+        l, r, res = 1, 1, [1]*n
+        for i in range(n):
+            res[i] *= l
+            l *= nums[i]
+            res[n-1-i] *= r
+            r *= nums[n-1-i]
+        return res
diff --git a/leetcode/376.摆动序列.py b/leetcode/376.摆动序列.py
@@ -0,0 +1,17 @@
+# 贪心算法
+class Solution(object):
+    def wiggleMaxLength(self, nums):
+        # 边界条件
+        n = len(nums)
+        if n < 2:
+            return n
+
+        # 以正/负结尾时的最长摆动序列长度
+        up = down = 1
+        # 正负性相同则长度不变，相反则加1
+        for i in range(1, n):
+            if nums[i-1] < nums[i]:
+                up = down + 1
+            if nums[i-1] > nums[i]:
+                down = up + 1
+        return max(up, down)
diff --git a/leetcode/402.移掉K位数字.py b/leetcode/402.移掉K位数字.py
@@ -0,0 +1,17 @@
+# 利用栈弹出元素，使前面的数字尽可能小
+class Solution(object):
+    def removeKdigits(self, num, k):
+        res = []
+        for n in num:
+            while res:
+                if not k or n >= res[-1]:
+                    res.append(n)
+                    break
+                else:
+                    res.pop()
+                    k -= 1
+            else:
+                if n != '0':
+                    res.append(n)
+        res = res[:len(res)-k]
+        return ''.join(res) if res else '0'
diff --git a/leetcode/825.适龄的朋友.py b/leetcode/825.适龄的朋友.py
@@ -0,0 +1,14 @@
+class Solution(object):
+    def numFriendRequests(self, ages):
+        count = [0]*121
+        for age in ages:
+            count[age] += 1
+        res = 0
+        for ageB in range(1, 121):
+            for ageA in range(ageB, 121):
+                if (ageB <= 0.5*ageA+7) or (ageB > ageA) or (ageB > 100 and ageA < 100):
+                    continue
+                res += count[ageA] * count[ageB]
+                if ageA == ageB:
+                    res -= count[ageA]
+        return res
diff --git a/leetcode/870.优势洗牌.py b/leetcode/870.优势洗牌.py
@@ -0,0 +1,19 @@
+class Solution(object):
+    def advantageCount(self, A, B):
+        n = len(B)
+        A.sort()
+        # 记录元素的值和索引
+        B = [(B[i], i) for i in range(n)]
+        B.sort()
+        # 使用左右指针指向B的左右两端
+        l, r, k, res = 0, n-1, 0, [0]*n
+        for a in A:
+            # A的元素大于B的元素，则将A的元素放到B的元素对应的索引位置上
+            if a > B[l][0]:
+                res[B[l][1]] = a
+                l += 1
+            # 否则放到B最后一个元素对应的索引位置上
+            else:
+                res[B[r][1]] = a
+                r -= 1
+        return res
diff --git a/leetcode/910.最小差值 II.py b/leetcode/910.最小差值 II.py
@@ -0,0 +1,14 @@
+# 数组排序后分成两部分，前一部分全部加K，后一部分全部减K
+# 取出两部分的第一个元素的更小者，最后一个元素的更大者，得到变化后的数组的最大最小值
+class Solution(object):
+    def smallestRangeII(self, A, K):
+        n = len(A)
+        if n < 2:
+            return 0
+        A.sort()
+        res = A[n-1] - A[0]
+        for i in range(1, n):
+            minu = min(A[0] + K, A[i] - K)
+            maxu = max(A[i-1] + K, A[n-1] - K)
+            res = min(res, maxu - minu)
+        return res
diff --git a/leetcode/921.使括号有效的最少添加.py b/leetcode/921.使括号有效的最少添加.py
@@ -0,0 +1,12 @@
+# 最坏情况下需要添加次数等于字符串长度，利用栈存放左括号，当遇到右括号时栈中有左括号配对，则弹出一个左括号并且减少两次添加
+class Solution(object):
+    def minAddToMakeValid(self, S):
+        res = len(S)
+        stack = []
+        for s in S:
+            if s == '(':
+                stack.append(s)
+            if s == ')' and stack:
+                stack.pop()
+                res -= 2
+        return res
diff --git a/leetcode/984.不含 AAA 或 BBB 的字符串.py b/leetcode/984.不含 AAA 或 BBB 的字符串.py
@@ -0,0 +1,21 @@
+class Solution(object):
+    def strWithout3a3b(self, A, B):
+        # 使A大于B
+        a, b = 'a', 'b'
+        if A < B:
+            a, b = b, a
+            A, B = B, A
+
+        res = ''
+        # A的数量多于B时构造 'aab'，否则构造 'ab'
+        while A > 0 or B > 0:
+            if A > 0:
+                res += a
+                A -= 1
+            if A > B:
+                res += a
+                A -= 1
+            if B > 0:
+                res += b
+                B -= 1
+        return res
diff --git a/leetcode/991.坏了的计算器.py b/leetcode/991.坏了的计算器.py
@@ -0,0 +1,16 @@
+# 逆向求解，对Y进行除、加逐步逼近X
+class Solution(object):
+    def brokenCalc(self, X, Y):
+        if X > Y:
+            return X - Y
+        res = 0
+        while X < Y:
+            # Y为奇数时除后非整所以只能加
+            if Y % 2:
+                Y += 1
+            # Y为偶数时就除，逼近X
+            else:
+                Y /= 2
+            res += 1
+        # Y比X小后逐步加直到等于X
+        return X - Y + res

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,3 @@`
	`1`	`+class Solution(object):`
	`2`	`+ def multiply(self, num1, num2):`
	`3`	`+ return str(int(num1)*int(num2))`