标签归档：leetcode

题目描述：

Sort a linked list in O(n log n) time using constant space complexity.

题目大意：

使用常数空间复杂度，对一个链表执行O(n log n）时间复杂度的排序

解题思路：

归并排序，链表的中点可以通过“快慢指针”法求得。

Python代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self ...

题目描述：

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.
• getMin() -- Retrieve ...

题目描述：

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 ...

题目描述

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 ...

题目描述

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) * 3) -> 9 ...