leetcode Burst Balloons
nballoons, indexed from
n-1. Each balloon is painted with a number on it represented by array
nums. You are asked to burst all the balloons. If the you burst balloon
iyou will get
nums[left] * nums[i] * nums[right]coins. Here
rightare adjacent indices of
i. After the burst, the
rightthen becomes adjacent.
Find the maximum coins you can collect by bursting the balloons wisely.
(1) You may imagine
nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤
n≤ 500, 0 ≤
[3, 1, 5, 8]
12 nums = [3,1,5,8] --> [3,5,8] --> [3,8] -->  --> coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
Chrome 下的 Vimium 插件 可以让你在浏览 网页的时候 摆脱鼠标的使用。
leetcode Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
The graph contains
nnodes which are labeled from
n - 1. You will be given the number
nand a list of undirected
edges(each edge is a pair of labels).
You can assume that no duplicate edges will appear in
edges. Since all edges are undirected,
[0, 1]is the same as
[1, 0]and thus will not appear together in
n = 4,
edges = [[1, 0], [1, 2], [1, 3]]Python
12345 0|1/ \2 3
leetcode Best Time to Buy and Sell Stock with Cooldown
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
leetcode First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have
[1, 2, ..., n]and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API
bool isBadVersion(version)which will return whether
versionis bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
leetcode Count Primes
Count the number of prime numbers less than a non-negative number, n.
leetcode Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example,
1, 4, 9, 16, ...) which sum to n.
For example, given n =
12 = 4 + 4 + 4; given n =
13 = 4 + 9.
leetcode Range Sum Query – Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
sumRange(0, 2) -> 8
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
leetcode Additive Number
Additive number is a positive integer whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
"112358"is an additive number because the digits can form an additive sequence:
1, 1, 2, 3, 5, 8.Python
1 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199"is also an additive number, the additive sequence is:
1, 99, 100, 199.Python
1 1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence
1, 2, 03or
1, 02, 3is invalid.
Given a string represents an integer, write a function to determine if it’s an additive number.