Add files via upload

linwt · web-flow · commit 7f4aa4c62f1f · 2018-12-28T18:56:49.000+08:00
diff --git a/leetcode/400.第N个数字.py b/leetcode/400.第N个数字.py
@@ -0,0 +1,15 @@
+class Solution(object):
+    def findNthDigit(self, n):
+        # 数字位数
+        digit = 1
+        while 1:
+            # 不同位数的第一个整数
+            first = 10**(digit-1)
+            # 该位数里的数字个数
+            cur = 9 * first * digit
+            if cur >= n:
+                # str(first+(n-1)/digit) 获取第n个数所在的整数，(n-1)%digit获取该整数的哪个数
+                return int(str(first + (n-1)/digit)[(n-1) % digit])
+            # 减去不符合的前cur个数，从更长位数开始判断
+            n -= cur
+            digit += 1
diff --git a/leetcode/458.可怜的小猪.py b/leetcode/458.可怜的小猪.py
@@ -0,0 +1,9 @@
+# n维空间定义坐标：按查找时间1h，猪15分钟内死去计算，1只猪最多可检测5只桶，2只猪最多可检测25只桶...
+class Solution(object):
+    def poorPigs(self, buckets, minutesToDie, minutesToTest):
+        # 一只猪在实验时间内最多可检测水桶数量
+        times = minutesToTest/minutesToDie+1
+        num = 0
+        while pow(times, num) < buckets:
+            num += 1
+        return num
diff --git a/leetcode/496.下一个更大元素I.py b/leetcode/496.下一个更大元素I.py
@@ -0,0 +1,12 @@
+# 先用字典存放nums中每个元素后第一个比它大的值，再遍历findNums的元素从字典获取该值
+class Solution(object):
+    def nextGreaterElement(self, findNums, nums):
+        l = []
+        d = {}
+        for num in nums:
+            while l and l[-1] < num:
+                d[l.pop()] = num
+            l.append(num)
+        for i in range(len(findNums)):
+            findNums[i] = d.get(findNums[i], -1)
+        return findNums
diff --git a/leetcode/594.最长和谐子序列.py b/leetcode/594.最长和谐子序列.py
@@ -0,0 +1,10 @@
+# 相邻两个元素的出现次数最大和即为最长和谐子序列
+class Solution(object):
+    def findLHS(self, nums):
+        d = collections.Counter(nums)
+        l = sorted(list(set(nums)))
+        count = 0
+        for i in range(len(l)-1):
+            if l[i]+1 == l[i+1] and d[l[i]] + d[l[i+1]] > count:
+                count = d[l[i]] + d[l[i+1]]
+        return count
diff --git a/leetcode/682.棒球比赛.py b/leetcode/682.棒球比赛.py
@@ -0,0 +1,14 @@
+# 用数组添加、删除数据即可，最后求和
+class Solution(object):
+    def calPoints(self, ops):
+        res = []
+        for op in ops:
+            if op == '+':
+                res.append(res[-1] + res[-2])
+            elif op == 'D':
+                res.append(res[-1] * 2)
+            elif op == 'C':
+                res.remove(res[-1])
+            else:
+                res.append(int(op))
+        return sum(res)
diff --git a/leetcode/690.员工的重要性.py b/leetcode/690.员工的重要性.py
@@ -0,0 +1,13 @@
+# 先用字典存放员工id与员工信息，再将所求员工信息添加到数组中，将重要性累加，并加直系员工信息添加到数组中，循环处理数组
+class Solution(object):
+    def getImportance(self, employees, id):
+        d = {e.id:e for e in employees}
+        res = 0
+        q = []
+        q.append(d[id])
+        while q:
+            cur = q.pop(0)
+            res += cur.importance
+            for i in cur.subordinates:
+                q.append(d[i])
+        return res
diff --git a/leetcode/811.子域名访问计数.py b/leetcode/811.子域名访问计数.py
@@ -0,0 +1,20 @@
+class Solution(object):
+    def subdomainVisits(self, cpdomains):
+        d = {}
+        for i in cpdomains:
+            # 先切分并保存最低一级域名与次数
+            res = i.split()
+            num = int(res[0])
+            addr = res[1]
+            if addr in d:
+                d[addr] += num
+            else:
+                d[addr] = num
+            # 再保存父域名和顶级域名的访问次数
+            while '.' in addr:
+                addr = addr[addr.index('.')+1:]
+                if addr in d:
+                    d[addr] += num
+                else:
+                    d[addr] = num
+        return [str(d[key]) + ' ' + key for key in d]
diff --git a/leetcode/812.最大三角形面积.py b/leetcode/812.最大三角形面积.py
@@ -0,0 +1,9 @@
+# 三角形面积公式 S=(1/2)*(x1y2+x2y3+x3y1-x1y3-x2y1-x3y2)
+class Solution(object):
+    def largestTriangleArea(self, points):
+        res = 0
+        for x in points:
+            for y in points:
+                for z in points:
+                    res = max(res, 0.5*(x[0]*y[1] + y[0]*z[1] + z[0]*x[1]- x[0]*z[1] - y[0]*x[1] - z[0]*y[1]));
+        return res
diff --git a/leetcode/944.删列造序.py b/leetcode/944.删列造序.py
@@ -0,0 +1,8 @@
+# 将A数组解压，遍历解压列表，若元组非降序排列，则需要删除一个索引
+class Solution(object):
+    def minDeletionSize(self, A):
+        res = 0
+        for i in zip(*A):
+            if list(i) != sorted(i):
+                res += 1
+        return res
diff --git a/leetcode/961.重复 N 次的元素.py b/leetcode/961.重复 N 次的元素.py
@@ -0,0 +1,16 @@
+# 方法一：遍历集合，边统计元素的个数
+class Solution(object):
+    def repeatedNTimes(self, A):
+        n = len(A)/2
+        for i in A:
+            if A.count(i) == n:
+                return i
+
+# 方法二：利用字典存放字符与对应个数
+class Solution(object):
+    def repeatedNTimes(self, A):
+        d = collections.Counter(A)
+        n = len(A)/2
+        for i in set(A):
+            if d[i] == n:
+                return i
