题目描述：
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element. ...
类别归档：LeetCode
LeetCode OJ is a platform for preparing technical coding interviews.
[LeetCode]Min Stack
[Leetcode]Find Minimum in Rotated Sorted Array II
作者是
发布于
在
LeetCode,
Python.
题目描述：
LeetCode 154. Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at ...
[Leetcode]Max Points on a Line
作者是
发布于
在
LeetCode,
Python.
题目描述
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
题目大意
平面上有n个点，找出共线的点的最大个数
解题思路
很容易想到O(n^3)的解法，通过起点i，终点j枚举直线，然后枚举中间点k，依次判断k与i,j是否共线，统计最大值。
实际上，采用此题可以采用O(n^2 * log(n))的复杂度解答，思路为：枚举起点i，与终点j，依次计算i，j的斜率，统计斜率相同的点的个数的最大值（另外需要考虑起点终点重合的情况）。此法实际上采用了起点分组统计的思想，因此减少了一重循环。
Python代码如下：
# Definition for a point
# class Point:
# def __init__(self, ...
[Leetcode]Evaluate Reverse Polish Notation
作者是
发布于
在
LeetCode,
Python.
题目描述
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) ...
[Leetcode]Reverse Words in a String
作者是
发布于
在
LeetCode,
Python.
题目描述
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the ...