LeetCode 374. Guess Number Higher or Lower

LeetCode 374. Guess Number Higher or Lower

Description
We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example :

Input: n = 10, pick = 6
Output: 6

继续阅读
LeetCode 365. Water and Jug Problem

LeetCode 365. Water and Jug Problem

Description
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

继续阅读
LeetCode 363. Max Sum of Rectangle No Larger Than K

LeetCode 363. Max Sum of Rectangle No Larger Than K

Description
Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.

Example:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2,
and 2 is the max number no larger than k (k = 2).
Note:

The rectangle inside the matrix must have an area > 0.
What if the number of rows is much larger than the number of columns?

继续阅读
LeetCode 357. Count Numbers with Unique Digits

LeetCode 357. Count Numbers with Unique Digits

Description Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n. Example: Input: 2Output: 91Explanation: The answer should be the total numbers in the range of 0 ≤ x < 100, excluding 11,22,33,44,55,66,77,88,99 描述 给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。 示例: 输入: 2输出: 91解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在 [0,100) 区间内的所有数字。 思路 此题目类似排列组合。 当 n = 1,10 的 1 次方为 10(不含),此时等价于问一个最多有 1 位数的数字,最多有多少个 unique number。 当 n = 2,10 的 2 次方为 100(不含),此时等价于问一个最多有 2 位数的数字,最多有多少个 unique number。 当 n = 1,不重复的数有 10 个,从 0 到 9 任选一个都行。 当 n = 2,1 位数最多有 10个;2位数的最高位不能选 0,因此有 9 种选择,次高位不能选最高位选过的,因此有 10 – 1 共 9 种选择,共 81 个;于是共计 91 个。 当有 3 位时,3位数的最高位有 9 种选择,次高位有 9 种选择,最末位有 8 种选择,共 405 个三位数;加上当 n 为2 的 91 个数,共496 个数。 # -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2019-06-04 13:40:45 # @Last Modified by: 何睿 # @Last Modified time: 2019-06-04 14:57:30 class Solution: def countNumbersWithUniqueDigits(self, n: int) -> int: # n 最大为 9 n = n if n < 10 else 9 # 当 n 为 0 时,只有 0 满足条件 if n == 0: return 1 # count 记录当限定位数为 i 时,能够形成的做多的 unique number […]

继续阅读
LeetCode 354. Russian Doll Envelopes

LeetCode 354. Russian Doll Envelopes

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll? (put one inside other)

继续阅读