2021-03-17 Daily-Challenge
Today I have done Reverse Subarray To Maximize Array Value and leetcode's March LeetCoding Challenge with cpp
.
Reverse Subarray To Maximize Array Value
Description
You are given an integer array nums
. The value of this array is defined as the sum of |nums[i]-nums[i+1]|
for all 0 <= i < nums.length-1
.
You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once.
Find maximum possible value of the final array.
Example 1:
Input: nums = [2,3,1,5,4]
Output: 10
Explanation: By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.
Example 2:
Input: nums = [2,4,9,24,2,1,10]
Output: 68
Constraints:
1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5
Solution
check O(n) Solution with explanation , very clear explanation with helpful image which helps me a lot.
class Solution {
public:
int maxValueAfterReverse(vector<int>& nums) {
int len = nums.size();
int value = 0;
for(int i = 1; i < len; ++i) value += abs(nums[i] - nums[i - 1]);
if(len < 3) return value;
int mmin = INT_MAX;
int mmax = INT_MIN;
for(int i = 0; i < len - 1; ++i) {
mmin = min(mmin, max(nums[i], nums[i + 1]));
mmax = max(mmax, min(nums[i], nums[i + 1]));
}
int change = (mmax - mmin) * 2;
for(int i = 1; i < len; ++i) {
int swap = abs(nums[0] - nums[i]) - abs(nums[i] - nums[i - 1]);
change = max(swap, change);
}
for(int i = 0; i < len - 1; ++i) {
int swap = abs(nums.back() - nums[i]) - abs(nums[i] - nums[i + 1]);
change = max(swap, change);
}
return value + change;
}
};
March LeetCoding Challenge 17
Description
Generate Random Point in a Circle
Given the radius and x-y positions of the center of a circle, write a function randPoint
which generates a uniform random point in the circle.
Note:
- input and output values are in floating-point.
- radius and x-y position of the center of the circle is passed into the class constructor.
- a point on the circumference of the circle is considered to be in the circle.
randPoint
returns a size 2 array containing x-position and y-position of the random point, in that order.
Example 1:
Input:
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]
Example 2:
Input:
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution
's constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint
has no arguments. Arguments are always wrapped with a list, even if there aren't any.
Solution
already done before
const double pi = 3.14159265358979323846264338327950288419;
class Solution {
random_device rd;
mt19937 gen;
uniform_real_distribution<double> distr;
double r;
double x;
double y;
public:
Solution(double radius, double x_center, double y_center): r(radius), x(x_center), y(y_center) {
gen = mt19937(rd());
distr = uniform_real_distribution<double>(0, 1);
}
vector<double> randPoint() {
double r = this->r * sqrt(distr(gen));
double t = distr(gen) * 2 * pi;
return {x + r * cos(t), y + r * sin(t)};
}
};