# Analysis of leetcode problem solving ideas 735 - 743 questions

1. Star collision
Given an integer array astroids, the planets in the same row are represented. For each element in the array, its absolute value represents the size of the planet, and positive and negative represents the moving direction of the planet (positive represents moving to the right, negative represents moving to the left). Each planet moves at the same speed.
Find all the planets left after the collision. Collision rule: two planets collide with each other, and the smaller planet will explode. If two planets are the same size, both planets will explode. Two planets moving in the same direction will never collide.

Very suitable for stack solution

```class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> ans; // Pretend to be a stack and just push_back operation, pop_back() operation
int n = asteroids.size();
for(int i = 0; i < n; ++i){
if(ans.empty() || asteroids[i] > 0) ans.push_back(asteroids[i]);
else{
while(ans.size() && ans.back() > 0 && ans.back() < -asteroids[i])
ans.pop_back(); // If a collision occurs and the absolute value of the positive number is small, delete the positive number
if(ans.empty() || ans.back() < 0) ans.push_back(asteroids[i]);
else if(ans.back() == -asteroids[i]) ans.pop_back(); // Delete both
}
}
return ans;
}
};

```
1. lisp syntax parsing
```class Solution {
struct IncompleteExpression {
unordered_map<string_view, int> variables;
string_view varname;
int count, value;
char type;  // Function name initials

IncompleteExpression() : variables(), varname(), count(0), value(), type() {}

void update_arithmetic(int val) {
if(type == 'a') { // addition
if(count == 1) { // The first argument (the zeroth is the function name)
value = val;
} else {         // Second parameter
value += val;
}
} else {       // multiplication
if(count == 1) {
value = val;
} else {
value *= val;
}
}
}
};

struct Parser {
vector<IncompleteExpression> nested;
int value;

// Find the value of a number
static int eval_int(const char* str, size_t str_len) {
int x = 0;
for(size_t i = 0; i != str_len; ++i) {
x = x * 10 + str[i] - '0';
}
return x;
}

// Find the value of a variable
int eval_variable(string_view name) {
for(auto i = nested.rbegin(), e = nested.rend(); i != e; ++i) {
auto x = i->variables.find(name);
if(x != i->variables.end()) {
return x->second;
}
}
return 0;
}

// Find the value of a variable or number
int eval(const char* str, size_t str_len) {
if(isdigit(*str)) {
return eval_int(str, str_len);
} else if (*str == '-') { // It is not supported to add a minus sign before a variable. The beginning of a minus sign can only be a number
return - eval_int(str + 1, str_len - 1);
} else return eval_variable(string_view(str, str_len));
}

// Left parenthesis encountered
void left_parenthesis() {
nested.emplace_back();
}

// Right parenthesis encountered
void right_parenthesis() {
auto& inner = nested.back();
int val;
if(!inner.varname.empty()) { // There is a variable name before the right parenthesis that has not been resolved e.g. (let x 8 x)
val = eval_variable(inner.varname);
} else {
val = inner.value;
}
nested.pop_back();
if(!nested.empty()) {  // Not the last brace
auto& t = nested.back();
if(t.type == 'l') { // let
if((t.count & 1) != 0) {
t.value = val;
} else {
t.variables[t.varname] = val;
t.varname = string_view(); // Clear unresolved variable names
}
}  else {
t.update_arithmetic(val);
}
++t.count;
} else {// The last curly bracket. The final result is stored in Parser::value
value = val;
}
}

// It can be a function name, a variable name, or a number
void new_identifier(const char* str, size_t str_len) {
auto& t = nested.back();
if(t.count == 0) {
t.type = *str;
} else if(t.type == 'l') { // let
if((t.count & 1) != 0) {
if (isdigit(*str)) {
t.value = eval_int(str, str_len);
} else if (*str == '-') { // It is not supported to add a minus sign before a variable. The beginning of a minus sign can only be a number
t.value = - eval_int(str + 1, str_len - 1);
} else {
t.varname = string_view(str, str_len);
}
} else {
t.variables[t.varname] = eval(str, str_len);
t.varname = string_view(); // Clear unresolved variable names
}
} else {
t.update_arithmetic(eval(str, str_len));
}
++t.count;
}
};
public:
int evaluate(string expression) {
Parser parser;
for(auto i = expression.cbegin(), e = expression.cend(); i != e;) {
if(*i == '(') {
parser.left_parenthesis();
++i;
} else if(*i == ')') {
parser.right_parenthesis();
++i;
} else if(isspace(*i)) {
++i;
} else {
auto j = i;
for(; !isspace(*i) && *i != '(' && *i != ')'; ++i);
parser.new_identifier(addressof(*j), i - j);
}
}
return parser.value;
}
};

```
1. Monotonically increasing number
Given a nonnegative integer n, find the largest integer less than or equal to N. at the same time, this integer needs to meet that the number on each digit is monotonically increasing.

Greedy algorithm

```class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strN = to_string(n);
int i = 1;
while (i < strN.length() && strN[i - 1] <= strN[i]) {
i += 1;
}
if (i < strN.length()) {
while (i > 0 && strN[i - 1] > strN[i]) {
strN[i - 1] -= 1;
i -= 1;
}
for (i += 1; i < strN.length(); ++i) {
strN[i] = '9';
}
}
return stoi(strN);
}
};

```
1. Daily temperature
According to the daily temperature list, please calculate how many days you need to wait for a higher temperature each day. If the temperature will not rise after that, please replace it with 0 in this position.

Use the monotone stack to access the subscript of each element. If the next element is greater than the top of the stack, it will be out of the stack and recorded, otherwise it will be stacked to the end

```class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> ans(n);
stack<int> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
int previousIndex = s.top();
ans[previousIndex] = i - previousIndex;
s.pop();
}
s.push(i);
}
return ans;
}
};

```
1. Delete and get points
Give you an integer array nums, you can do some operations on it. In each operation, select any num [i], delete it and obtain the number of num [i]. After that, you must delete all elements equal to nums[i] - 1 and nums[i] + 1. You have 0 points at the beginning. Returns the maximum number of points you can get through these operations.

Dynamic programming solution after sorting. The key point is that when taking x points, all x points can be actually obtained, but x - 1 and x + 1 cannot. This can be used for dynamic programming with adjacent as 1

```class Solution {
private:
int rob(vector<int> &nums) {
int size = nums.size();
if (size == 1) {
return nums[0];
}
int first = nums[0], second = max(nums[0], nums[1]);
for (int i = 2; i < size; i++) {
int temp = second;
second = max(first + nums[i], second);
first = temp;
}
return second;
}

public:
int deleteAndEarn(vector<int> &nums) {
int n = nums.size();
int ans = 0;
sort(nums.begin(), nums.end());
vector<int> sum = {nums[0]};
for (int i = 1; i < n; ++i) {
int val = nums[i];
if (val == nums[i - 1]) {
sum.back() += val;
} else if (val == nums[i - 1] + 1) {
sum.push_back(val);
} else {
ans += rob(sum);
sum = {val};
}
}
ans += rob(sum);
return ans;
}
};

```
1. Cherry picking
An N x N grid represents a cherry field. Each grid is represented by one of the following three numbers:
0 means the grid is empty, so you can go through it.
1 means that there is a cherry in this grid. You can pick the cherry and pass through it.
-1 means there are thorns in this grid, blocking your way.
Your task is to pick as many cherries as possible under the following rules

In essence, it is no different from the dynamic planning of taking stairs

```class Solution {
public:
int cherryPickup(vector<vector<int>>& grid) {
int N = grid.size(), dp[N+1][N+1];
memset(dp, 0x80, sizeof(dp)); //-2139062144, equivalent to INT_MIN
dp[N-1][N-1] = grid[N-1][N-1]; // Initial boundary conditions
for(int sum = 2*N - 3; sum >= 0; --sum)
for(int i1 = max(0, sum - N + 1); i1 <= min(N-1,sum); ++i1)
for(int i2 = i1; i2 <= min(N-1,sum); ++i2)
{
int j1 = sum - i1, j2 = sum - i2;
if(grid[i1][j1] == -1 || grid[i2][j2] == -1)
dp[i1][i2] = INT_MIN;
else
dp[i1][i2] = grid[i1][j1] + (i1 != i2 || j1 != j2)*grid[i2][j2] + max(
max(dp[i1][i2+1], dp[i1+1][i2]),
max(dp[i1+1][i2+1], dp[i1][i2])
);
}
return max(0, dp[0][0]);
}
};

```
1. Network delay time
There are n network nodes marked 1 to n. Give you a list of times, indicating the transmission time of the signal through the directed edge. times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time when a signal is transmitted from the source node to the target node. Now, a signal is sent from a node K. How long will it take for all nodes to receive the signal? If all nodes cannot receive the signal, return - 1.

disjkstra or Bellman Ford or spfa or floyd can be used, among which dijestra is the most recommended for simplicity and efficiency

```class Solution {
public:
/*Establish adjacent nodes, node represents vertex and weight represents weight*/
struct Nodes {
Nodes(int n, int w, Nodes* s) : node(n), weight(w), next(s) {};
int node;
int weight;
Nodes* next;
};
Heads() : val(INT_MAX / 2), lists(nullptr), visit(true) {};
int val;//Road strength from the source point to the node
bool visit;//Mark whether you can visit
};

/*x->y，Establish an adjacency table. If x is the source point, initialize the val value of y*/
void initialize(Heads*& h, int x, int y, int weight, int k) {
Nodes* ph = new Nodes(y, weight, h[x].lists);
h[x].lists = ph;
if (x == k)     h[y].val = weight;
return;
}
int networkDelayTime(vector<vector<int>>& t, int n, int k) {
int size = t.size();
k--;//Start with 0 and subtract one from the vertex
h[k].val = 0, h[k].visit = false;//Source point processing

/*initialization*/
for (int i = 0; i < size; i++) {
initialize(h, t[i][0] - 1, t[i][1] - 1, t[i][2], k);
}

/*Only the remaining n-1 vertices need to be relaxed at most*/
for (int i = 0; i < n - 1; i++) {

/*Find the nearest to the source point and write it down in book*/
int mi = INT_MAX, book;
for (int i = 0; i < n; i++) {
if (h[i].visit && h[i].val < mi) {
mi = h[i].val;
book = i;
}
}
/*If the source point cannot reach any point at this time, return directly*/
if (mi == INT_MAX)    return -1;
h[book].visit = false;//Mark not accessible

/*Take this point as the center and start to relax*/
Nodes* p = h[book].lists;
while (p) {
if (h[book].val + p->weight < h[p->node].val) {
h[p->node].val = h[book].val + p->weight;
}
p = p->next;
}
}
int ret = 0;
/*Answer processing, the answer is the longest point, that is, the least time we need*/
for (int i = 0; i < n; i++) {
ret = max(ret, h[i].val);
}
return ret == INT_MAX/2 ? -1 : ret;
}
};

```

Added by CrusaderSean on Sat, 15 Jan 2022 00:33:37 +0200