961. N-Repeated Element in Size 2N Array
In a array A
of size 2N
, there are N+1
unique elements, and exactly one of these elements is repeated N times.
Return the element repeated N
times.
Example 1:
Input: [1,2,3,3]
Output: 3
Example 2:
Input: [2,1,2,5,3,2]
Output: 2
Example 3:
Input: [5,1,5,2,5,3,5,4]
Output: 5
Note:
4 <= A.length <= 10000
0 <= A[i] < 10000
A.length
is even
Approach #1: C++.
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
int size = A.size();
int repeatTime = size / 2;
vector<int> temp(10005, 0); for (int a : A) {
temp[a]++;
if (temp[a] == repeatTime)
return a;
} }
};
962. Maximum Width Ramp
Given an array A
of integers, a ramp is a tuple (i, j)
for which i < j
and A[i] <= A[j]
. The width of such a ramp is j - i
.
Find the maximum width of a ramp in A
. If one doesn’t exist, return 0.
Example 1:
Input: [6,0,8,2,1,5]
Output: 4
Explanation:
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.
Example 2:
Input: [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation:
The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.
Note:
2 <= A.length <= 50000
0 <= A[i] <= 50000
Approach #2: C++.
typedef pair<int, int> pp;class Solution {
public:
int maxWidthRamp(vector<int>& A) {
vector<pp> temp;
int ans = 0;
temp.push_back(make_pair(A[0], 0));
for (int i = 1; i < A.size(); ++i) {
if (A[i] < temp.back().first) {
temp.push_back(make_pair(A[i], i));
} else {
int ramp = i - binarySearch(temp, A[i]);
ans = max(ans, ramp);
}
}
return ans;
} int binarySearch(vector<pp> temp, int target) {
int l = -1, r = temp.size()-1, mid;
while (l+1 < r) {
mid = (l + r) / 2;
if (temp[mid].first > target) l = mid;
else r = mid;
}
return temp[r].second;
}
};
Analysis:
we use a vector to store the decrement elements from the begin to the end of A.
963. Minimum Area Rectangle II
Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.
If there isn’t any rectangle, return 0.
Example 1:
Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.
Example 2:
Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.
Example 3:
Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.
Example 4:
Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.
Note:
1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
- All points are distinct.
- Answers within
10^-5
of the actual value will be accepted as correct.
Approach #1: C++.
Thinking…………………………….
Approach #2: Java.
import java.awt.Point;class Solution {
public double minAreaFreeRect(int[][] points) {
int N = points.length;
Point[] A = new Point[N];
for (int i = 0; i < N; ++i)
A[i] = new Point(points[i][0], points[i][1]); Map<Integer, Map<Point, List<Point>>> seen = new HashMap();
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j) {
// center is twice actual to keep integer precision
Point center = new Point(A[i].x + A[j].x, A[i].y + A[j].y); int r2 = (A[i].x - A[j].x) * (A[i].x - A[j].x);
r2 += (A[i].y - A[j].y) * (A[i].y - A[j].y);
if (!seen.containsKey(r2))
seen.put(r2, new HashMap<Point, List<Point>>());
if (!seen.get(r2).containsKey(center))
seen.get(r2).put(center, new ArrayList<Point>());
seen.get(r2).get(center).add(A[i]);
} double ans = 0.0;
for (Map<Point, List<Point>> info: seen.values()) {
for (Point center: info.keySet()) { // center is twice actual
List<Point> candidates = info.get(center);
int clen = candidates.size();
for (int i = 0; i < clen; ++i)
for (int j = i+1; j < clen; ++j) {
Point P = candidates.get(i);
Point Q = candidates.get(j);
Point Q2 = new Point(center);
Q2.translate(-Q.x, -Q.y);
double area = P.distance(Q) * P.distance(Q2);
if (area > ans)
ans = area;
}
}
} return ans;
}
}
964. Least Operators to Express Number
Given a single positive integer x
, we will write an expression of the form x (op1) x (op2) x (op3) x ...
where each operator op1
, op2
, etc. is either addition, subtraction, multiplication, or division (+
, -
, *
, or /)
. For example, with x = 3
, we might write 3 * 3 / 3 + 3 - 3
which is a value of 3.
When writing such an expression, we adhere to the following conventions:
- The division operator (
/
) returns rational numbers. - There are no parentheses placed anywhere.
- We use the usual order of operations: multiplication and division happens before addition and subtraction.
- It’s not allowed to use the unary negation operator (
-
). For example, “x - x
” is a valid expression as it only uses subtraction, but “-x + x
” is not because it uses negation.
We would like to write an expression with the least number of operators such that the expression equals the given target
. Return the least number of expressions used.
Example 1:
Input: x = 3, target = 19
Output: 5
Explanation: 3 * 3 + 3 * 3 + 3 / 3. The expression contains 5 operations.
Example 2:
Input: x = 5, target = 501
Output: 8
Explanation: 5 * 5 * 5 * 5 - 5 * 5 * 5 + 5 / 5. The expression contains 8 operations.
Example 3:
Input: x = 100, target = 100000000
Output: 3
Explanation: 100 * 100 * 100 * 100. The expression contains 3 operations.
Note:
2 <= x <= 100
1 <= target <= 2 * 10^8
Approach #1: C++.
Thinking………………………………
Approach #2: Python. (can’t understand)
class Solution(object):
def leastOpsExpressTarget(self, x, target):
"""
:type x: int
:type target: int
:rtype: int
"""
# 由于不能有括号,所以每一位(x进制)必须是由自己组成或者由下一位减自己余数组成,所以首先短除法求出每一位的余数
rl = list()
while target:
rl.append(target%x)
target/=x
n = len(rl)
# 在个位的时候,必须用x/x表示1,所以*2,但其它位不用,所以单独先提出
pos = rl[0] * 2
neg = (x-rl[0]) * 2
for i in range(1,n):
# 正数表示时,可用自己+剩下的正数表示或者多加一个本位然后减去上一位的余数表示
# 负数表示时,可用自己的余数加上剩下的正数表示或者用自己的余数+剩下的余数,但此时可以合并同级项减少运算符
# 如在10进制下,86可表示为
# 80 + 6 (6 为下一位正数表示
# 80 + 10 - 4 (4 为下一位负数表示)
# 100 - 20 + 6 (100-20为本位余数表示,6为下一位正数表示
# 100 - 20 + 10 - 4 (100-20为本位余数表示,10 -4 为下一位余数表示
# 在此时, 20 和 10注定为同一位且符号相反,可以省去两个符号(一个符号在该位用i 个符号表示(如100为第二位,所以表示为+10 * 10,用两个符号,在此时所有符号均带自己的正负号
pos, neg = min(rl[i] * i + pos, rl[i] * i + i + neg), min((x - rl[i]) * i + pos, (x-rl[i]) * i + i + neg - 2 * i)
# 因为在前面算法中所有位都带自己的正负号,所以第一位应该减去自己的符号,所以总量减1
# 或者在余数表示法中,加上一个更高位的减去自己表示本位余数
# 所以此题归根结底还是考察对进制的理解而不是简单的理解bfs, dfs,那样复杂度远远高于此,但是是对惯性思维者的一种挑战
return min(pos-1, n+neg-1)
come from: https://leetcode.com/problems/least-operators-to-express-number/discuss/208376/python2-O(log-target)-chinese