8000 update at 2018-07-24 · mz09code/leetcode@7374370 · GitHub
[go: up one dir, main page]
Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 7374370

Browse files
bonfybonfy
committed
update at 2018-07-24
1 parent 23a3f14 commit 7374370

File tree

10 files changed

+230
-56
lines changed

10 files changed

+230
-56
lines changed

‎011-container-with-most-water/container-with-most-water.py

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,23 @@
11
# -*- coding:utf-8 -*-
22

33

4-
# Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
4+
# Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
55
#
6-
# Note: You may not slant the container and n is at least 2.
6+
# Note: You may not slant the container and n is at least 2.
7+
#
8+
#  
9+
#
10+
#
11+
#
12+
# The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
13+
#
14+
#  
15+
#
16+
# Example:
17+
#
18+
#
19+
# Input: [1,8,6,2,5,4,8,3,7]
20+
# Output: 49
721
#
822

923

‎034-find-first-and-last-position-of-element-in-sorted-array/find-first-and-last-position-of-element-in-sorted-array.py

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
# -*- coding:utf-8 -*-
2+
3+
4+
# Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
5+
#
6+
# Your algorithm's runtime complexity must be in the order of O(log n).
7+
#
8+
# If the target is not found in the array, return [-1, -1].
9+
#
10+
# Example 1:
11+
#
12+
#
13+
# Input: nums = [5,7,7,8,8,10], target = 8
14+
# Output: [3,4]
15+
#
16+
# Example 2:
17+
#
18+
#
19+
# Input: nums = [5,7,7,8,8,10], target = 6
20+
# Output: [-1,-1]
21+
#
22+
23+
24+
class Solution(object):
25+
def searchRange(self, nums, target):
26+
"""
27+
:type nums: List[int]
28+
:type target: int
29+
:rtype: List[int]
30+
"""
31+
n = len(nums)
32+
left, right = -1, -1
33+
l, r = 0, n-1
34+
while l < r:
35+
m = (l+r)/2
36+
if nums[m] < target: l = m+1
37+
else: r = m
38+
if nums[l] != target: return -1, -1
39+
left = l
40+
l, r = left, n-1
41+
while l < r:
42+
m = (l+r)/2+1
43+
if nums[m] == target: l = m
44+
else: r = m-1
45+
right = l
46+
return left, right

‎237-delete-node-in-a-linked-list/delete-node-in-a-linked-list.py

Lines changed: 30 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,40 @@
11
# -*- coding:utf-8 -*-
22

33

4-
#
54
# Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
65
#
6+
# Given linked list -- head = [4,5,1,9], which looks like following:
7+
#
8+
#
9+
# 4 -> 5 -> 1 -> 9
10+
#
11+
#
12+
# Example 1:
13+
#
14+
#
15+
# Input: head = [4,5,1,9], node = 5
16+
# Output: [4,1,9]
17+
# Explanation: You are given the second node with value 5, the linked list
18+
#   should become 4 -> 1 -> 9 after calling your function.
19+
#
20+
#
21+
# Example 2:
22+
#
23+
#
24+
# Input: head = [4,5,1,9], node = 1
25+
# Output: [4,5,9]
26+
# Explanation: You are given the third node with value 1, the linked list
27+
# should become 4 -> 5 -> 9 after calling your function.
28+
#
29+
#
30+
# Note:
31+
#
732
#
33+
# The linked list will have at least two elements.
34+
# All of the nodes' values will be unique.
35+
# The given node will not be the tail and it will always be a valid node of the linked list.
36+
# Do not return anything from your function.
837
#
9-
# Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
1038
#
1139

1240

‎240-search-a-2d-matrix-ii/search-a-2d-matrix-ii.py

Lines changed: 4 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@
88
# Integers in each column are sorted in ascending from top to bottom.
99
#
1010
#
11+
# Example:
12+
#
1113
# Consider the following matrix:
1214
#
1315
#
@@ -20,19 +22,9 @@
2022
# ]
2123
#
2224
#
23-
# Example 1:
24-
#
25-
#
26-
# Input: matrix, target = 5
27-
# Output: true
28-
#
29-
#
30-
# Example 2:
31-
#
32-
#
33-
# Input: matrix, target = 20
34-
# Output: false
25+
# Given target = 5, return true.
3526
#
27+
# Given target = 20, return false.
3628
#
3729

3830

‎274-h-index/h-index.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@
1313
# Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
1414
# received 3, 0, 6, 1, 5 citations respectively.
1515
#   Since the researcher has 3 papers with at least 3 citations each and the remaining
16-
#   two with no more than 3 citations each, his h-index is 3.
16+
#   two with no more than 3 citations each, her h-index is 3.
1717
#
1818
# Note: If there are several possible values for h, the maximum one is taken as the h-index.
1919
#

‎275-h-index-ii/h-index-ii.py

Lines changed: 13 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,9 @@
11
# -*- coding:utf-8 -*-
22

33

4-
# Given an array of citations in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
4+
# Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
55
#
6-
# According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than hcitations each."
6+
# According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
77
#
88
# Example:
99
#
@@ -13,9 +13,18 @@
1313
# Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had
1414
# received 0, 1, 3, 5, 6 citations respectively.
1515
#   Since the researcher has 3 papers with at least 3 citations each and the remaining
16-
#   two with no more than 3 citations each, his h-index is 3.
16+
#   two with no more than 3 citations each, her h-index is 3.
17+
#
18+
# Note:
19+
#
20+
# If there are several possible values for h, the maximum one is taken as the h-index.
21+
#
22+
# Follow up:
23+
#
24+
#
25+
# This is a follow up problem to H-Index, where citations is now guaranteed to be sorted in ascending order.
26+
# Could you solve it in logarithmic time complexity?
1727
#
18-
# Note: If there are several possible values for h, the maximum one is taken as the h-index.
1928
#
2029

2130

‎313-super-ugly-number/super-ugly-number.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
#
1111
# Input: n = 12, primes = [2,7,13,19]
1212
# Output: 32
13-
# Explanation: [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12
13+
# Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12
1414
# super ugly numbers given primes = [2,7,13,19] of size 4.
1515
#
1616
# Note:

‎335-self-crossing/self-crossing.py

Lines changed: 14 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,56 +1,52 @@
11
# -*- coding:utf-8 -*-
22

33

4+
# You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.
45
#
5-
# You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west,
6-
# x[2] metres to the south,
7-
# x[3] metres to the east and so on. In other words, after each move your direction changes
8-
# counter-clockwise.
6+
# Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
97
#
10-
#
11-
# Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
8+
# Example 1:
129
#
1310
#
11+
# Input: [2,1,1,2]
1412
#
15-
# Example 1:
16-
#
17-
# Given x = [2, 1, 1, 2],
1813
# ?????
1914
# ? ?
2015
# ???????>
2116
# ?
2217
#
23-
# Return true (self crossing)
18+
# Input: true
19+
# Explanation: self crossing
2420
#
2521
#
22+
# Example 2:
2623
#
2724
#
28-
# Example 2:
25+
# Input: [1,2,3,4]
2926
#
30-
# Given x = [1, 2, 3, 4],
3127
# ????????
3228
# ? ?
3329
# ?
3430
# ?
3531
# ?????????????>
3632
#
37-
# Return false (not self crossing)
33+
# Output: false
34+
# Explanation: not self crossing
3835
#
3936
#
37+
# Example 3:
4038
#
4139
#
42-
# Example 3:
40+
# Input: [1,1,1,1]
4341
#
44-
# Given x = [1, 1, 1, 1],
4542
# ?????
4643
# ? ?
4744
# ?????>
4845
#
49-
# Return true (self crossing)
50-
#
46+
# Output: true
47+
# Explanation: self crossing
5148
#
5249
#
53-
# Credits:Special thanks to @dietpe FDD7 psi for adding this problem and creating all test cases.
5450

5551

5652
class Solution(object):

‎458-poor-pigs/poor-pigs.py

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# -*- coding:utf-8 -*-
2+
3+
4+
# There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour.
5+
#
6+
# Answer this question, and write an algorithm for the follow-up general case.
7+
#
8+
# Follow-up:
9+
#
10+
# If there are n buckets and a pig drinking poison will die within m minutes, how many pigs (x) you need to figure out the "poison" bucket within p minutes? There is exact one bucket with poison.
11+
#
12+
13+
14+
class Solution(object):
15+
def poorPigs(self, buckets, minutesToDie, minutesToTest):
16+
"""
17+
:type buckets: int
18+
:type minutesToDie: int
19+
:type minutesToTest: int
20+
:rtype: int
21+
"""
22+
# corner case
23+
if buckets == 1:
24+
return 0
25+
if minutesToTest // minutesToDie <= 1:
26+
return buckets - 1
27+
# general case: just get the n in n^(test_times + 1) = buckets
28+
return int(math.ceil(math.log(buckets, (minutesToTest // minutesToDie) + 1)))

0 commit comments

Comments
 (0)
0