leetcode

my profile @leetcode

日志

2019-5-27

<a id=”sliding-window></a>

sliding-window leetcode 76

思路

since you have to find the minimum window in S which has all the characters from T, you need to expand and contract the window using the two pointers and keep checking the window for all the characters. This approach is also called Sliding Window Approach.

L ———————————— R , Suppose this is the window that contains all characters of T
L————————- R , this is the contracted window. We found a smaller window that still contains all the characters in T

When the window is no longer valid, start expanding again using the right pointer.

2018-12-28

complete-binary-tree-inserter—leetcode 919

题目

CBTInserter(TreeNode root) 使用头结点为 root 的给定树初始化该数据结构；
CBTInserter.insert(int v) 将 TreeNode 插入到存在值为 node.val = v 的树中以使其保持完全二叉树的状态，并返回插入的 TreeNode 的父结点的值；
CBTInserter.get_root() 将返回树的头结点。

2018-12-21

numbers-at-most-n-given-digit—leetcode 902

思路

idea 很简单, 比 N 低位的直接 枚举相加, 与 N 位数相同的, 就从高位到低位依次比较, 当前位, 有 k 位 小于等于 若 k 位全小于, 则结束比较 若 有一位 等于, k-1 小于, 则递归地继续比较

2018-12-18

bitwise-and-of-numbers-range —leetcode 201

题目

bitwise-and-of-numbers-range

2018-12-17

integer-break —leetcode

题目

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

思路

$\sqrt{2}^{n}$, $\sqrt[3]{3}^{n}$

$\sqrt{2} = 1.414, \sqrt[3]{3} = 1.442$

• 动态规划版本
• 非动态规划解法

2018-12-15

Nim game —leetcode-cn 292

思路

233333 上次看见这题还是在小学的 <<举一反三>>上面, 可以说是脑经急转弯了

return n%4!=0

wildcard-matching —leetcode 44

题目

wild card:
*: matches 0 or any chars,
?: matches any single char.

Given two strings s and p. s doesn’t contain wild card and p may contain wild card.
Judge if they are matched.

思路

dynamic programming

dp[m+1][n+1]: bool

i:n, j:m
dp[j][i] indicates if s[:i+1] matches p[:j+1]

initial: dp[0][0] = True, dp[0][i],dp[j][0] = False
only if p startswith ‘*’, dp[1][0] = True.

if p[j] = ‘*’: dp[j][i] = dp[j-1][i] or dp[j][i-1]
elif p[j] = ‘?’: dp[j][i] = dp[j-1][i-1]
else : dp[j][i] = dp[j-1][i-1] and s[i] == p[j]

int(n**0.5)

2018-11-12

One line task:squirrel and tree —codewars 4kyu

题目

Since the weather was good, some students decided to go for a walk in the park after the first lectures of the new academic year. There they saw a squirrel, which climbed a tree in a spiral at a constant angle to the ground. They calculated that in one loop the squirrel climbes h meters (vertical height), the height of the tree is equal to H (v in Ruby), and the length of its circumference equals S.

These calculations were exhausting, so now the students need your help to figure out how many meters the path length of squirrel climbed when it reached the tree top. The result should be rounded to 4 decimal places.

Code Limit
Less than 52 characters (JavaScript & Python)

Less than 48 characters (Ruby)

Example
For h = 4, H = 16, S = 3, the output should be 20.

For h = 8, H = 9, S = 37, the output should be 42.5869

思路

result = $\sqrt{S^2+h^2}\frac{H}{h}$

2018-8-26

counting-bits —leetcode 338

题目

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

range-sum-query-2d —leetcode 304

题目

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

perfect-squares —leetcode 279

题目

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
Example 1:
>
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

思路

numSquare2是 DFS, numSquare是BFS, DFS会超时. DFS优点就是节省空间, 但是时间上会较慢, 而BFS 正好相反.

2018-8-25

Longest Valid Parentheses —leetcode 32

题目

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring*.

思路

cont 变量用来看是否连续的好括号, 用来连接, 用栈的数据结构可以记录当”(“ 多于”)” 时 的状态.

2018-1-23

All-Oone-Data-Structure —leetcode 432

题目

Implement a data structure supporting the following operations:

• Inc(Key) - Inserts a new key with value 1. Or increments an existing key by 1. Key is guaranteed to be a non-empty string.
• Dec(Key) - If Key’s value is 1, remove it from the data structure. Otherwise decrements an existing key by 1. If the key does not exist, this function does nothing. Key is guaranteed to be a non-empty string.
• GetMaxKey() - Returns one of the keys with maximal value. If no element exists, return an empty string “”.
• GetMinKey() - Returns one of the keys with minimal value. If no element exists, return an empty string “”.

Challenge: Perform all these in O(1) time complexity.

2018-1-21

Partition-to-K-Equal-Sum-Subsets—leetcode 698

题目

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

* Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
* Output: True
* Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000

2017-12-8

Word-Search-II—leetcode 212

题目

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"]and board =

Return ["eat","oath"]

2017-12-5

Clone-Graph—leetcode 133

题目

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

思路

dfs,以及记录哪些被访问了，而且要注意复制的时候用self.nd里的结点

1. python

2. c++

Knight-Probability-in-Chessboard—leetcode 688

题目

On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right square is (N-1, N-1).

A chess knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Each time the knight is to move, it chooses one of eight possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly K moves or has moved off the chessboard. Return the probability that the knight remains on the board after it has stopped moving.

• Example:
• Input: 3, 2, 0, 0
• Output: 0.0625
• Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.
• Note:
• N will be between 1 and 25.
• K will be between 0 and 100.
• The knight always initially starts on the board.

2017-12-4

Trim-a-Binary-Search-Tree—leetcode 669

题目

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Number-of-Longest-Increasing-Subsequence—leetcode 673

题目

Given an unsorted array of integers, find the number of longest increasing subsequence.
Input: [2,2,2,2,2]
Output: 5

Daily-Temperatures—leetcode 729

题目

Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

思路

When I saw the question in this competition, I firstly think about Monotonous stack inspired by Largest Rectangle in Histogram.
Because Monotonous stack can help us find first largest element in O(n) time complexity.
But I can’t implement use Monotonous stack idea to solve the problem.But you did it, brilliant bro.

2017-12-1

Merge-k-Sorted-Lists —leetcode23

题目

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

2017-11-27

Longest-Palindromic-Substring

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

2017-11-18

Decode-Ways —leetcode 91

题目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

思路

[ f(n+1)=\begin{cases}
f(n),\quad when \ \ p(s[n]) \\
\end{cases} ]
f(n)表示位数有多少种， fib(N)求fibnaci数列，fib(0)=1,fi(1)=1 ,p(s[n])表示满足性质,大体上是这未为1或2，这样就可能有多种选择， 但要考虑27，28，29，不存在，以及，下一位为0的时候也不算， 具体实现见代码

代码

Decode-Ways II —leetcode 639

A message containing letters from A-Z is being encoded to numbers using the following mapping way:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
Beyond that, now the encoded string can also contain the character ‘*’, which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character ‘*’, return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

• Input: “*”
• Output: 9
• Explanation: The encoded message can be decoded to the string: “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H

2017-11-13

Gray-Code —leetcode 89

题目

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer?n?representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given?n?= 2, return?[0,1,3,2]. Its gray code sequence is:0132
Note:
For a given?n, a gray code sequence is not uniquely defined.
For example,?[0,2,3,1]?is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

2017-11-7

Redundant-Connectionleetcode 684

题目

In this problem, a tree is an undirected graph that is connected and has no cycles.

The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, …, N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.

The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] with u < v, that represents an undirected edge connecting nodes u and v.

Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge [u, v] should be in the same format, with u < v

2017-11-4

Evaluate-Division —leetcode 399

题目

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

Example:
Given a / b = 2.0, b / c = 3.0.
queries are:a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].

The input is: vector> equations, vector& values, vector> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.

2017-10-30

题目

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

• postTweet(userId, tweetId): Compose a new tweet.
• follow(followerId, followeeId): Follower follows a followee.
• unfollow(followerId, followeeId): Follower unfollows a followee.
• getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least * recent.

思路

我另外定义了一个user类，以及用得我前面写的优先队列，写了很长，一点都不简洁。看了别人的代码（如下），真的很佩服。踩知道python有heapq模块，功能很强大，比如，heapify , merge等等

2017-10-23

Trie( Prefix Tree) —leetcode 208

题目

Implement a trie with insert, search, and startsWith methods

思路

trie还是很有趣的，最开始我没弄清楚，以为a->b 再插入abc是

b
/
a->b->c

题目

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:

• Buying at prices[0] = 1
• Selling at prices[3] = 8
• Buying at prices[4] = 4
• Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

思路

动态规划，弄清楚，f(n),与f(n+1)的关系，确定转移方程，以及当再次加入一组时是否可以多于两次的fee，代码29，30行就是处理这点

2017-10-19

Valid-Triangle-Number —leetcode 611

题目

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

2017-10-16

Path-Sum-III —leetcode 437

题目

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

2017-10-14

Top-K-Frequent-Words —leetcode 692

题目

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

2-Keys-Keyboard —leetcode 692

题目

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.
Note:The n will be in the range [1, 1000]

2017-10-12

Unique-Binary-Search-Trees —leetcode 96

题目

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

Path-Sum-II —leetcode 113

题目

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

2017-10-8

Symmetric-Tree —leetcode 101

题目

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

代码

recursive solution

Longest-Univalue-Path —leetcode 687

题目

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Note: The length of path between two nodes is represented by the number of edges between them.
example:output 3

2017-9-25

Remove-Invalid-Parentheses —leetcode 301

题目

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

Valid-Parenthesis-String —leetcode 678

题目

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
2. Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
3. Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
4. ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string.
5. An empty string is also valid.
example: (),(*,(*) are all valid.

思路

根据好括号的判断充要条件：从左往右数，左括号数不少于右括号数，且最终左右括号数相等。在这里，加入了*号，有些难度。可以改进为：从左往右数，左括号数不大于右括号与*号之和。比如((*)(*))((*，本来是错的，但会判对，所以要再改进一下， 可以再来一遍从右往左数。

2017-9-21

24-Game —leetcode 679

题目

You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example 1:
Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24
Example 2`:
Input: [1, 2, 1, 2]
Output: False

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as 3. input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2],   we cannot write this as 12 + 12.

2017-9-18

01-Matrix —leetcode 542

题目

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

Input:
0 0 0
0 1 0
1 1 1

Output:
0 0 0
0 1 0
1 2 1

Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and righ

Integer-to-English-Words —leetcode 273

题目

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

For example,
123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

2017-9-12

Insert-Interval —leetcode 57

题目

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

N-Queens —leetcode 51

题目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

2017-8-31

八数码 —ustc-oj

题目

3×3九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。要求：根据给定初始布局，问：至少移动几次才能从初始布局到达目标布局。

Input Description

3行，每行3个0-8的不重复整数，其中0表示空格所在的位置，数字间用空格隔开，表示初始布局，数据保证该初始布局一定能移到目标布局。
Output Description

eg
input:0 7 6 8 4 3 5 2 1
output:4

2017-8-23

Nth-digit —leetcode 400

题目

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

example:

Single-Number —leetcode 136

题目

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Question 2: How about every element appearing tree times except for one?
Question 3: 一列数中, 除了两个数只出现一次, 其他数都出现两次, 找出这两个数

2017-8-22

ZigZag-Conversion —leetcode 6

题目

The string “asdfghjklqw” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) 原题目的例子有点难懂，我就自己举个例子吧 num > = 4

2017-8-20

Integer to Roman —leetcode 13

题目

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.

1. 重复数次：一个罗马数字重复几次，就表示这个数的几倍。
2. 右加左减
• 在较大的罗马数字的右边记上较小的罗马数字，表示大数字加小数字。
• 在较大的罗马数字的左边记上较小的罗马数字，表示大数字减小数字。
• 左减的数字有限制，仅限于I、X、C。比如45不可以写成VL，只能是XLV
• 左减时不可跨越一个位值。比如，99不可以用IC（ {\displaystyle 100-1} 100-1）表示，而是用XCIX（ {\displaystyle [100-10]+[10-1]} [100-10]+[10-1]）表示。（等同于阿拉伯数字每位数字分别表示。）
• 左减数字必须为一位，比如8写成VIII，而非IIX。
• 右加数字不可连续超过三位，比如14写成XIV，而非XIIII。（见下方“数码限制”一项。）
3. 加线乘千
在罗马数字的上方加上一条横线或者加上下标的Ⅿ，表示将这个数乘以1000，即是原数的1000倍。
同理，如果上方有两条横线，即是原数的1000000（ {\displaystyle 1000^{2} } 1000^{2}）倍。
4. 数码限制
同一数码最多只能连续出现三次，如40不可表示为XXXX，而要表示为XL。
例外：由于IV是古罗马神话主神朱庇特（即IVPITER，古罗马字母里没有J和U）的首字，因此有时用IIII代替IV。

word-search —leetcode 79

题目

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

2017-8-19

3Sum —leetcode 15

题目

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.

2017-8-17

jump-game —leetcode 55

题目

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

super-pow —leetcode 372

题目

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example1:
a = 2
b = [3]
Result: 8

Example2:
a = 2
b = [1,0]
Result: 1024

<--!>