# 剑指 Offer 11. 旋转数组的最小数字

LeetCode Find Minimum in Rotated Sorted Array II相同，即旋转有序数组中包含重复元素，求最小值。考虑nums[m]==nums[r]的情况，退化为线性查找，完整代码如下：

class Solution {
public:
int minArray(vector<int>& numbers) {
int n = numbers.size();
int l = 0, r = n - 1;
while(l <= r) {
if(r - l <= 1) return min(numbers[l], numbers[r]);
int m = l + (r - l) / 2;
if(numbers[m] > numbers[r]) l = m;
else if(numbers[m] == numbers[r]) --r;
else r = m;
}
return 0;
}
};

# 剑指 Offer 10- II. 青蛙跳台阶问题

0 <= n <= 100

class Solution {
public:
int numWays(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
if(n == 2) return 2;
int a = 1, b = 2;
for(int i = 3; i <= n; ++i) {
int tmp = (a + b) % 1000000007;
a = b;
b = tmp;
}
return b;
}
};

# LeetCode K Closest Points to Origin

973. K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].


Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)


Note:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000

1.先排序（快排）时间复杂度为nlogn
2.建堆，堆的大小为K，建立大根堆或者小根堆，时间复杂度为nlogK(如果要求出前K个较大的，那么就建立小根堆，一旦比堆顶大，那么就入堆)；
3.结合快速排序划分的方法，不断减小问题的规模

class Solution {
private:
vector<int> origin;

int CalDist(vector<int> &p1, vector<int> &p2) {
return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
}

void MySwap(vector<vector<int>>& points, int u, int v) {
swap(points[u][0], points[v][0]);
swap(points[u][1], points[v][1]);
}

void Work(vector<vector<int>>& points, int l, int r, int K) {
if (l >= r) return;

int pivot = r;
int pdist = CalDist(points[pivot], origin);
int i = l;
for (int j = l; j < r; ++j) {
int idist = CalDist(points[j], origin);
if (idist < pdist) {
MySwap(points, i++, j);
}
}
MySwap(points, i, pivot);

if (K == i)return;
else if (K < i)Work(points, l, i - 1, K);
else Work(points, i + 1, r, K);
}
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
origin = { 0, 0 }; // 求与该点距离最近的top-k个点，本题中该点是原点

for (int i = 0; i < points.size(); ++i) {
printf("x=%d,y=%d,dist=%d\n", points[i][0], points[i][1], CalDist(points[i], origin));
}

Work(points, 0, points.size() - 1, K - 1);

vector<vector<int>> ans;
for (int i = 0; i < K; ++i) ans.push_back(points[i]);
return ans;
}
};

# HDOJ 1007-Quoit Design

HDOJ 1007-Quoit Design

# Quoit Design

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 77740    Accepted Submission(s): 20729

Problem DescriptionHave you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.

Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

InputThe input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

OutputFor each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input

2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

Sample Output

0.71
0.00
0.75

AuthorCHEN, Yue
SourceZJCPC2004
RecommendJGShining   |   We have carefully selected several similar problems for you:  10061009100510081004

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

struct Point
{
double x_, y_;
Point() :x_(0), y_(0) {};
Point(double x, double y) :x_(x), y_(y) {};
};

bool CmpX(const Point &p1, const Point &p2) {
return p1.x_ < p2.x_;
}

bool CmpY(const Point &p1, const Point &p2) {
return p1.y_ < p2.y_;
}

// 暂时只算距离平方，最后开平方根
double CalDist(const Point &p1, const Point &p2) {
return (p1.x_ - p2.x_)*(p1.x_ - p2.x_) + (p1.y_ - p2.y_)*(p1.y_ - p2.y_);
}

double CalMinDist(vector<Point> &data, int l, int r) {

if (r - l == 2) {
return CalDist(data[l], data[l + 1]);
}
else if (r - l == 3) {
double d1 = CalDist(data[l], data[l + 1]);
double d2 = CalDist(data[l], data[l + 2]);
double d3 = CalDist(data[l + 1], data[l + 2]);
return min(min(d1, d2), d3);
}

int m = l + (r - l) / 2;
int mx = data[m].x_;
double dd = min(CalMinDist(data, l, m), CalMinDist(data, m, r));
double d = sqrt(dd);

vector<Point> rect;
for (int i = l; i < r; ++i) {
if (data[i].x_ > mx - d && data[i].x_ < mx + d) {
rect.push_back(data[i]);
}
}

sort(rect.begin(), rect.end(), CmpY);
for (int i = 0; i < rect.size(); ++i) {
for (int j = i + 1; j < rect.size(); ++j) {
double tmpd = CalDist(rect[i], rect[j]);
if (tmpd > dd)break;
dd = min(dd, tmpd);
}
}

return dd;
}

int main() {
freopen("input.txt", "r", stdin);

int n;
while (scanf("%d", &n)) {
if (n == 0)break;
vector<Point> data(n, Point());
for (int i = 0; i < n; ++i) {
scanf("%lf %lf", &data[i].x_, &data[i].y_);
}
sort(data.begin(), data.end(), CmpX);
printf("%.2lf\n", sqrt(CalMinDist(data, 0, data.size())) / 2);
}

return 0;
}

# 剑指 Offer 10- I. 斐波那契数列

F(0) = 0,   F(1) = 1
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.

0 <= n <= 100

class Solution {
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
long long a = 0, b = 1;
for(int i = 2; i <= n; ++i) {
long long tmp = a + b;
tmp %= 1000000007;
a = b;
b = tmp;
}
return b;
}
};

typedef long long LL;

class Solution {
private:
vector<vector<LL>> multiply(vector<vector<LL>> &m1, vector<vector<LL>> &m2) {
int n = m1.size();
vector<vector<LL>> ans(n, vector<LL>(n, 0));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
for(int k = 0; k < n; ++k) {
ans[i][j] += m1[i][k] * m2[k][j] % 1000000007;
}
}
}
return ans;
}
public:
int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;

vector<vector<LL>> matrix = {{1,1},{1,0}};

vector<vector<LL>> ans = {{1,0},{0,1}};
while(n != 0) {
if(n % 2 == 1) ans = multiply(ans, matrix);
matrix = multiply(matrix, matrix);
n >>= 1;
}

return ans[0][1] % 1000000007;
}
};

# 剑指 Offer 09. 用两个栈实现队列

[[],[3],[],[]]

[[],[],[5],[2],[],[]]

1 <= values <= 10000

class CQueue {
private:
stack<int> stk_in_, stk_out_;
public:
CQueue() {

}

void appendTail(int value) {
stk_in_.push(value);
}

if(!stk_out_.empty()) {
int ans = stk_out_.top();
stk_out_.pop();
return ans;
} else if(!stk_in_.empty()) {
while(stk_in_.size() != 1) {
int tmp = stk_in_.top();
stk_in_.pop();
stk_out_.push(tmp);
}
int tmp = stk_in_.top();
stk_in_.pop();
return tmp;
} else {
return -1;
}
}
};

# 剑指 Offer 07. 重建二叉树

3


/ \
9 20
/ \
15 7

0 <= 节点个数 <= 5000

class Solution {
private:
TreeNode* buildTree(vector<int>& preorder, int pl, int pr, vector<int>& inorder, int il, int ir, unordered_map<int,int> &hash) {
if(pr < pl || ir < il) return NULL;
TreeNode *root = new TreeNode(preorder[pl]);
int im = hash[preorder[pl]];
int len_left = im - il, len_right = ir - im;
root->left = buildTree(preorder, pl + 1, pl + len_left, inorder, il, im - 1, hash);
root->right = buildTree(preorder, pl + len_left + 1, pr, inorder, im + 1, ir, hash);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int,int> hash;
for(int i = 0; i < inorder.size(); ++i) hash[inorder[i]] = i;

int n = preorder.size();
return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, hash);
}
};

# LeetCode Maximum Sum Circular Subarray

918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3


Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10


Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4


Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3


Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1


Note:

1. -30000 <= A[i] <= 30000
2. 1 <= A.length <= 30000

LeetCode Maximum Subarray的升级版，即数组首尾相连了。我一开始想到的解法是，既然数组首尾相连了，那就2*n次dp即可，即把原数组复制一遍，接到原数组后面，形成2*n长的数组，然后照样跑原来的DP算法。这个解法是不对的，比如如果数组是[1,2,3,4]这种全是正数，则跑2n遍之后，ans会一直max更新，导致最后的ans是1+…+4+1+…4，即数组加了两遍，每个数重复加了。另外对于数组[5,-3,5]这种，也会完整数组加两遍。

class Solution {
public:
int maxSubarraySumCircular(vector<int>& A) {
int n = A.size();
vector<int> dp(n, 0);

// 最大连续子串
dp[0] = A[0];
int ans1 = A[0], sum = A[0];
for(int i = 1; i < n; ++i) {
dp[i] = max(dp[i - 1], 0) + A[i];
ans1 = max(ans1, dp[i]);

sum += A[i];
}

// 最小连续子串
fill(dp.begin(), dp.end(), 0);
dp[0] = A[0];
int ans2 = A[0];
for(int i = 1; i < n; ++i) {
dp[i] = min(dp[i - 1], 0) + A[i];
ans2 = min(ans2, dp[i]);
}

if(ans2 == sum) ans2 = INT_MIN; // 注意最小连续子串和不能是全长数组
else ans2 = sum - ans2;

return max(ans1, ans2);
}
};

# 剑指 Offer 36. 二叉搜索树与双向链表

class Solution {
private:
void DFS(Node *root) {
if(root == NULL) return;

DFS(root->left);
else pre->right = root;

root->left = pre;
pre = root;
DFS(root->right);
}
public:
Node* treeToDoublyList(Node* root) {

if(root == NULL) return NULL;

DFS(root);

}
};

# LeetCode Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).


Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3


Example 4:

Input: nums = [0,0,0], target = 0
Output: 3


Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 0 <= target <= 10^6

class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int n = nums.size();
vector<int> dp(n + 1, 0);
for(int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
int sum = 0;
for(int j = i; j > 0 && dp[j] == dp[i]; --j) {
sum += nums[j - 1];
if(sum == target) dp[i] = max(dp[i], dp[j - 1] + 1);
}
}
return dp[n];
}
};

class Solution {
public:
int maxNonOverlapping(vector<int>& nums, int target) {
int n = nums.size();
unordered_map<int, int> hash;
hash[0] = -1;
int prefix_sum = 0, right_most = -1;
int ans = 0;
for(int i = 0; i < n; ++i) {
prefix_sum += nums[i];
int supplement = prefix_sum - target;
if(hash.find(supplement) != hash.end()) {
int left = hash[supplement];
if(left >= right_most) {
++ans;
right_most = i;
}
}
hash[prefix_sum] = i;
}
return ans;
}
};