Only played one game of the week this week. “Trails” first, which is so trashy, are only number one.
The title
1941
Check whether all characters appear the same number of times
Given a string s, return true if s is a good string, false otherwise.
The string S is called a good string if all characters that have occurred in s have the same number of occurrences.
The sample
Input: s = “abacbc” Output: true Explanation: characters that appear in s are ‘a’, ‘b’, and ‘c’. All characters in s appear twice.
Tip:
1 <= s.length <= 1000sContains only lowercase letters
Answer key
Sign in. Simple simulation. Because it contains only lowercase letters, there are only 26 possible letters. The idea is to scan through the string, counting the number of characters, and then iterate through the 26 letters, returning false if different numbers occur, and true otherwise
The Java code is as follows
class Solution {
public boolean areOccurrencesEqual(String s) {
int[] ctn = new int[26];
for (int i = 0; i < s.length(); i++) {
int j = s.charAt(i) - 'a';
ctn[j]++;
}
int r = 0;
for (int i = 0; i < 26; i++) {
if (ctn[i] > 0) {
if (r == 0) r = ctn[i];
else if(r ! = ctn[i])return false; }}return true; }}Copy the codeThe C++ code is as follows
class Solution {
public:
bool areOccurrencesEqual(string s) {
int occurrences[26] = {0};
for (int i = 0; i < s.size(); i++) {
int j = s[i] - 'a';
occurrences[j]++;
}
int r = 0;
for (int i = 0; i < 26; i++) {
if (occurrences[i] > 0) {
if (r == 0) r = occurrences[i];
else if(r ! = occurrences[i])return false; }}return true; }};Copy the codeC++ local variable arrays, remember to initialize with {0} to all zeros, unlike Java, where local variable arrays default to all zeros.
1942
The number of the smallest unoccupied chair
There are n friends having a party, and these friends are numbered from 0 to N-1. There were an infinite number of chairs, numbered zero to infinity. When a friend arrives at the party, he will take the smallest and unoccupied chair.
For example, when a friend arrives, if chairs 0, 1 and 5 are occupied, he will occupy chair 2. When a friend leaves a party, their chair immediately becomes unocked-out. If another friend arrives at the same time, the chair can be occupied immediately.
I’m going to give you a two-dimensional array of integers with indices starting at 0 called TimestimesTimes, Where times[I]=[arrivali,leavingi]times[I]=[arrival_i, leaving_i]times[I]=[arrivali,leavingi]times[I]=[arrivali,leavingi] At the same time give you an integer targetFriendtargetFriendtargetFriend. All arrival times are different.
Would you please return number for targetFriendtargetFriendtargetFriend friends occupy chair number.
Example:
Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
- Friend 0 arrives at time 1 and occupies chair 0.
- Friend 1 arrives at time 2 and takes chair 1.
- Friend 1 leaves at time 3, chair 1 becomes unoccupied.
- Friend 0 leaves at 4, chair 0 becomes unoccupied.
- Friend 2 arrives at time 4 and occupies chair 0. Friend 1 occupies chair 1, so return 1.
Tip:
n == times.length- 2 <= n <= 10^4^
times[i].length == 2
0 <= targetFriend <= n - 1- Each arrivaliArrival_iarrivali moment is different
Answer key
When I did it that night, I thought a lot about it. All I could think of was, this is an interval kind of problem, sort by arrival and departure times. Then there is the need to maintain chairs that are already occupied, and chairs that are currently available. When a person III arrives at the party, he either occupies the third chair in the order in which he arrived, or the person who arrived before him leaves before he arrives, releasing the smaller numbered chair in front. So the key is to maintain the chairs that are currently available, and for each time of arrival, you need to determine whether anyone left before that time.
The official solution is as follows:
Each person has an effect on the state of the chair at only 2 time points
- When you arrive, occupy a chair
- When you leave, release a chair
Since there are only n people actually attending the party, the number of chairs needed is 0 to N-1 at most (no one releases chairs during the whole process), and for each person we need the smallest chair currently available.
Thus, we can maintain the information about the currently available chairs with the small root heap (the time complexity of obtaining the minimum value in the small root heap is O(1)O(1)O(1)).
-
When someone arrives, the top of the pile pops up and that person occupies the chair.
-
When someone leaves, insert the chair occupied by that person back into the small root pile to indicate that the chair is available.
We also need a hash table to store a person and the number of the chairs he occupies.
Each person has only one chance to occupy a chair, so the chair each person occupies is certain. To determine the number of chairs that someone occupies, we need to determine the availability of chairs when that person arrives. The first to arrive is the first to judge, so we rank them in ascending order by arrival time. When someone arrives, we determine whether anyone left before the time of arrival, so we also need to rank the departure times in ascending order.
And then from small to large, when traversal arrives at time, traversal of departure time does not go backwards. That is, for the ascending array of arrival time and ascending array of departure time, the traversal pointer moves in the same direction and does not move backwards. So we can use the idea of a double pointer.
In this way, our specific code ideas are as follows:
A small root heap is used to store currently available chairs. Initially, n chairs numbered from 0 to N-1 are inserted into the small root heap. At this time, all chairs are available. Let two Pointers I and j traverse the array in ascending order by arrival time and j traverse the array in ascending order by departure time. Each time you traverse an I, try to move j back, deal with those whose departure time is less than the current arrival time, and insert their chairs back into the small root heap. When the processing is complete, the top of the small root heap pops up, which is the smallest numbered chair currently available. Let’s open up a map, a hash table, to store the number of chairs someone occupies. Save the chair occupied by the currently arriving person. After the double pointer traversal, the chair number of the target individual can be obtained from the map.
The Java code is as follows
class Solution {
public int smallestChair(int[][] times, int targetFriend) {
int n = times.length;
// An array in ascending order by departure time
Pair[] leaving = new Pair[n];
// An array in ascending order by arrival time
Pair[] arrival = new Pair[n];
// A chair that someone occupies
Map<Integer, Integer> seatsMap = new HashMap<>();
// Currently available chairs
PriorityQueue<Integer> availableSeats = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
// At the beginning, all chairs from 0 to n-1 are available
availableSeats.offer(i);
// Time of arrival array (time + person number)
arrival[i] = new Pair(times[i][0], i);
// Leave the time array
leaving[i] = new Pair(times[i][1], i);
}
// Sort by time in ascending order
Arrays.sort(leaving, (Comparator.comparingInt(o -> o.first)));
Arrays.sort(arrival, (Comparator.comparingInt(o -> o.first)));
// Double pointer, traverses the arrival array, and handles the departure array before it
for (int i = 0, j = 0; i < n; i++) {
// When the exit array is not traversed and the exit time is less than or equal to the current arrival time
while (j < n && leaving[j].first <= arrival[i].first) {
// Process those leaving before the current arrival time
int s = seatsMap.get(leaving[j].second); // Get the chair that this person occupies
availableSeats.offer(s); // The chair becomes available again
j++;
}
// Take one of the chairs currently available
int s = availableSeats.poll();
seatsMap.put(arrival[i].second, s); // The chair is occupied by the person with the current number
}
returnseatsMap.get(targetFriend); }}class Pair {
int first;
int second;
public Pair(int first, int second) {
this.first = first;
this.second = second; }}Copy the codeThe C++ code is as follows
typedef pair<int.int> PII;
class Solution {
public:
int smallestChair(vector<vector<int>>& times, int targetFriend) {
int n = times.size();
vector<PII> leaving;
vector<PII> arrival;
priority_queue<int.vector<int>, greater<int>> availableSeats; / / small root pile
unordered_map<int.int> seatsMap;
for (int i = 0; i < n; i++) {
arrival.push_back( { times[i][0], i } );
leaving.push_back( { times[i][1], i } );
availableSeats.push(i);
}
sort(arrival.begin(), arrival.end());
sort(leaving.begin(), leaving.end());
for (int i = 0, j = 0; i < n; i++) {
while (j < n && leaving[j].first <= arrival[i].first) {
int p = leaving[j].second;
availableSeats.push(seatsMap[p]);
j++;
}
seatsMap[arrival[i].second] = availableSeats.top();
availableSeats.pop();
}
returnseatsMap[targetFriend]; }};Copy the codeIn the process of writing code in C++, I found some problems, which need to be noted here. (I am not familiar with C++ because I work in Java.)
-
About vector initialization
It can be initialized by variables, for example
int n = times.size(); vector<PII> leaving(n); Insert 10 elements into the vector. Each element defaults to 0 Copy the codeIf we initialize the vector with a size (say, 10), we already have 10 elements in the vector, all zeros. When we call push_back to add an element to the container, we insert it after the tenth element. This is different from the Java container, which passes in a size to indicate the initial capacity without inserting any elements.
-
Typedef pair
PII;
An error was initially reported when writing code in VS. It turns out that pair is STD. Typedef pair
PII; Should be placed in using namespace STD; after
1943
Describe the result of painting
I’m going to give you a long, thin drawing on a number line. The painting is represented by several overlapping line segments, each with a unique color. Segments [I] = [start_i, end_i, color_i]; segments[I] = [start_i, end_i, color_i];
The colors of the overlapping segments are mixed. If two or more colors are mixed, they form a new color, which is represented by a set.
For example, if colors 2,4, and 6 are mixed, the resulting color is {2,4,6}. To simplify things, you don’t have to print the entire set, you just have to represent the set of colors as the sum of all the elements in the set.
You want to represent the mixed-color painting with the minimum number of non-overlapping half-open intervals. These line segments can be represented by the two-dimensional array painting, where painting[j] = [left_j, right_j, mix_j] represents a half-open interval where the color sum of [left_j, right_j] is mix_j.
Segments = [[1,4,5],[1,7,7]]. [4,7] is composed of colors {5,7} from the first segment and the second segment, respectively. This represents the result of the final drawing (unpainted parts do not appear in the result). You can return the result of the final array in any order.
The half-open interval [a, b] is the part of the number line between points A and b, including point A but excluding point B.
Example 1
Input: segments = [].enlighened by,7,7 [4], [1,7,9]] output: [,4,14 [1], [4,7,16]] : painting results can be represented as:
- The [1,4) colors are {5,9} (and are 14) from the first and second line segments, respectively
- The [4,7) colors are {7,9} (and are 16) from the second and third line segments, respectively
Example 2
Input: segments = [,7,9 [1], [6,8,15], [8,10,7]] output: [,6,9 [1], [6,7,24],,8,15 [7], [8,10,7]] : painting, the results can be expressed as:
- [1,6] the color is 9, coming from the first line segment
- The [6,7) colors are {9,15} (and are 24) from the first and second line segments
- [7,8) the color 15 comes from the second line segment
- [8,10] the color 7 comes from the third line segment
prompt
- 1 <= segments.length <= 2 * 10^4^
- segments[i].length == 3
- 1 <= start_i < end_i <= 10^5^
- 1 <= color_i <= 10^9^
- Each color color_i is different
Answer key
That night, I thought about it for a while and realized that it was actually a sort of interval conflation problem. Since colors in the same interval need to be added (all positions in an interval need to be added), I considered adding prefix sum with difference at that time, but found that every line segment was an interval closed on the left and open on the right, and there would be errors in the calculation of endpoints during the interval combination. I was thinking of representing each point with 2 points, for example, 4, 4 left, 4 left and 4 right, 4 right, 4 right, 4 right, 4 right, 4 right, 4 right, 4 left, 4 left, 4 right, 4 right, 4 right. But there are many details that can easily go wrong, such as determining whether a position is the end position of a line segment, not just because the difference array is zero.
The week ends at 12:00, and I almost missed this one! Unwilling ah! So I continued debugging and finally passed the problem at 12:40. The code is ugly, but let’s do my own solution first.
class Solution {
final int SEGMENT_MAX = 100000;
public List<List<Long>> splitPainting(int[][] segments) {
long[] segmentValues = new long[2 * SEGMENT_MAX];
boolean[] flags = new boolean[2 * SEGMENT_MAX];
long max = 0;
for (int[] segment : segments) {
max = Math.max(max, 2 * segment[1] - 1);
add(segment[0], segment[1], segment[2], segmentValues, flags);
}
List<List<Long>> res = new ArrayList<>();
// Count the colors and values of each segment according to the difference array
long l = -1, r = -1, c = -1;
for (int i = 1; i <= max ; i++) {
if (l == -1&& segmentValues[i] ! =0) {
// Start position of interval
segmentValues[i] += segmentValues[i - 1];
l = i / 2 + 1; // The extended point is restored to the original point
c = segmentValues[i]; // differential array restore, summation
} else if (flags[i]) {
// Check whether the current position is the endpoint position of the line segment by flag, and whether to merge
// The difference array is 0
// It is possible that the difference array is just added and subtracted, causing the position to be 0
r = i / 2 + 1;
long t = c; // The range of colors and, temporary storage
List<Long> item = new ArrayList<>();
item.add(l);
item.add(r);
item.add(c);
// Since it is an open interval, the difference value of this point is not included in the current interval, which will be updated later here
segmentValues[i] += segmentValues[i - 1];
c = segmentValues[i];
l = i / 2 + 1;
if(t == 0) continue; // If the sum of colors in this range is 0, skip it
res.add(item);
} else segmentValues[i] += segmentValues[i - 1];
}
return res;
}
// Difference array
private void add(int l, int r, int c, long[] val, boolean[] flags) {
val[2 * l - 1] += c; // The position of the extended point represented by two points
val[2 * r - 1] -= c;
flags[2 * l - 1] = flags[2 * r - 1] = true; // Use flag to indicate the end positions of line segments}}Copy the codeOfficial solution:
It is the difference + prefix sum idea, but note that the difference array 0 May be caused by the left and right increments, does not mean that this position is not a line segment endpoint. So we need to maintain the endpoints of all the segments. The official solution uses a hash table directly to store the end points of a line segment, which is then converted into a difference array. The middle part of the line segment is directly ignored (compressed), which is similar to discretization. Then for the point where the right endpoint is an open interval, the difference component of the right endpoint can be excluded by taking the prefix sum of the position in front of the right endpoint. (Why didn’t I think of that 😓)
The Java code is as follows
class Solution {
public List<List<Long>> splitPainting(int[][] segments) {
// Just use difference + prefix sum
Map<Integer, Long> d = new HashMap<>();
// Record all endpoints and deltas on them
for (int[] s : segments) {
int l = s[0], r = s[1], c = s[2];
long l_c = d.get(l) == null ? 0L : d.get(l);
long r_c = d.get(r) == null ? 0L : d.get(r);
d.put(l, l_c + c);
d.put(r, r_c - c);
}
// Convert to array (difference array)
List<Pair> list = d.entrySet().stream()
.map(e -> new Pair(e.getKey(), e.getValue()))
.collect(Collectors.toList());
// Sort by endpoint position from smallest to largest
list.sort(Comparator.comparingLong(o -> o.i));
List<List<Long>> res = new ArrayList<>();
// The difference array is restored to the prefix and and the solution is solved simultaneously
for (int i = 1; i < list.size(); i++) {
list.get(i).c += list.get(i - 1).c;
if (list.get(i - 1).c ! =0) {
res.add(Arrays.asList(list.get(i - 1).i, list.get(i).i, list.get(i - 1).c)); }}returnres; }}class Pair {
long i;
long c;
public Pair(long i, long c) {
this.i = i;
this.c = c; }}Copy the codeThe C++ code is as follows
class Solution {
public:
vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
unordered_map<int.long long> delta;
for (auto &s : segments) {
int l = s[0], r = s[1], c = s[2];
delta[l] += c;
delta[r] -= c;
}
vector<pair<int.long long>> deltaList;
for (auto& d : delta) {
deltaList.push_back({d.first, d.second});
}
sort(deltaList.begin(), deltaList.end());
vector<vector<long long>> res;
for (int i = 1; i < deltaList.size(); i++) {
deltaList[i].second += deltaList[i - 1].second;
if (deltaList[i - 1].second ! =0) {
res.push_back({deltaList[i - 1].first, deltaList[i].first, deltaList[i - 1].second}); }}returnres; }};Copy the code1944
The number of people visible in the queue
There are n people in a queue, numbered from left to right from 0 to N-1. You are given an array of integers heights. Each integer is different. Heights [I] represents the height of the ith person.
A person can see the other person on his right only if everyone between them is shorter than both of them. More formally, the ith person can see the JTH person if I < j and min(heights[I], heights[j]) > Max (heights[I +1], heights[I +2]… The heights [1]).
Return an array answer of length N, where answer[I] is the number of people the ith person can see in the queue to his right.
The sample
Input: heights = [10,6,8,5,11,9] output: [3,1,2,1,1,0] explanation: the 0th person can see the numbers 1,2, and 4. The first person can see the number 2. The second person can see the numbers 3 and 4. The third person can see the number 4. The fourth person can see the number 5. The fifth man can’t be seen because there’s no one to his right.
prompt
n == heights.length- 1 <= n <= 10^5^
- 1 <= heights[i] <= 10^5^
heightsThe number of allEach other is not the same 。
Answer key
The question was not even read that night. I did it again today, I tried it, and I wrote the violent solution.
class Solution {
public int[] canSeePersonsCount(int[] heights) {
int n = heights.length;
int[] ans = new int[n];
for (int i = 0; i < n - 1; i++) {
int j = i + 1;
int max = 0; // Max is the height between I and j
do {
if (Math.min(heights[i], heights[j]) > max) ans[i]++;
max = Math.max(max, heights[j++]);
} while (j < n);
}
returnans; }}Copy the codeHowever, the time complexity of the violent solution is high, so it needs to be optimized.
However, after thinking about it for a long time, I can only think of: If two adjacent people a and B, a is on the left and B is on the right, if height[a] > height[b], then all the people to the left of A cannot see B. More generally, when there is an interval of decreasing height from left to right, then for all the people to the left of the interval at the left end, You can’t see everyone to the right of the left end of the interval (because the people on the left end of the interval are the highest, blocking out everyone else in the interval). Therefore, for A person A, it may be necessary to pre-process the height increasing sequence to the right of the person A, and then as long as the first position in the increasing sequence that exceeds the height of A is found, the number of people in front of the increasing sequence is the number of people A can see. But after that, I don’t know how to do it. Hold back for 1 hour, still did not hold back, see the problem solved! / (ㄒ o ㄒ) / ~ ~
With monotonous stack (yXC is the previous several chapters of the content, learned and forgotten, practice is not enough, not cooked, but also need to often fry twizhurou!
All the people that a person can see must increase in height from left to right. (That’s what I thought)
Take a monotone stack, and walk through all the people from right to left, the stack is stored: the current walk through the person, the right of the increasing sequence.
As mentioned earlier, for the current person, we need to find the first person in the monotonically increasing sequence to the right who is taller than the current person.
Therefore, we should store the smallest (and closest to the current person in the increasing sequence) at the top of the stack and the largest at the bottom of the stack. So that when the top is smaller than the current one, people can give the current count + 1, and the pop-up stack (because the stack is smaller than the current, the current is larger than the stack, then the people of the left side of the people, see come over, will be the current block), has been to meet the top is higher than the current one, find the increasing sequence is illustrated in the first person is taller than the man, The count of the current person ends, and the current person is found higher in the stack than the current person. The current person is inserted into the stack without blocking the person to the left of the current person, and then traversed further to the left, ensuring that the stack stores a monotonically increasing sequence of people to the right.
A practical example for 10,2,4,3,7,2,9,8,11,13,17,11 sequence, draw a bar chart is as follows
For person 1, whose height is 10, mark the ascending sequence to the right, as follows
In increasing the height of the orange marker sequence above, there are 3 among individuals, because of the high than the previous one short, so I was held up by the former one, and the increasing sequence, the height of the individual is 11, 9 is the first height is more than 10 people, due to its high more than 10, the individual after 9 people, no matter how much is the height, can’t be the first man saw. Because the height of the first person is already less than the height of the middle person.
So in an increasing sequence, the number of people at height 11 and in front of them, is the number of people that the first person can see when they look to the right, which is 5.
For each person, it’s the same, find the increasing sequence to the right of this person, and find the first person in the increasing sequence whose height is greater than or equal to him, and stop, the number of people from the left of the increasing sequence to this stopping position, is the number of people that this person can currently see.
Because we want to maintain the increasing sequence on the right side of a person, so we traverse from right to left, and we have a structure to hold the increasing sequence, what structure? The stack!
The person at the top of the stack is the smallest (and the person closest to the current position in the ascending sequence), and the person at the bottom of the stack is the highest. For example, when traversing from right to left to the eighth person, the state of the stack should look like this
At the top of the stack is this guy at number 9, whose height is 11, and at the bottom of the stack is this guy at number 11, whose height is 17. When the stack is not empty, take the height of the person at the top of the stack and compare it with the current person (number 8). Regardless of the result of the comparison, first add the current person’s count +1, and then decide,
-
If the height of the person at the top of the stack is greater than or equal to that of the current person, then the first position whose height is greater than that of the current person is found according to the above idea, and the count ends, and the current person is added to the stack (keeping the monotonicity of the stack).
-
If the height of the person at the top of the stack is smaller than that of the current person, it indicates
- If the first position in the ascending sequence whose height is greater than the current person has not been found, you need to continue counting
- And because the current person is higher than the top of the stack, the person to the left of the current person is going to block the person behind, and because of the need to maintain the monotonicity of the stack
So, pop the top of the stack, keep counting, and loop.
Until the stack is empty, or the height of the person at the top of the stack is greater than or equal to the current person, indicating that the current person counts, and the current person is inserted into the stack to maintain the monotonicity of the stack, then the stack is pushed.
For no. 8 person, the height of no. 9 at the top of the stack 11 is greater than its height 8, then the count ends, the count result is 1, and no. 8 person is added to the stack. Continue to traverse until number seven makes a judgment call.
In this way, the train of thought is clear
- Walk everyone from right to left
- Use a stack to store the increasing sequence to the right of the person currently traversed
- At the top of the stack is the smallest person
- At the bottom of the stack is the tallest person
- In each attempt to pop the top of the stack, compare the height of the top person with the height of the current person until the stack is empty, or find that the height of the top person is greater than or equal to the height of the current person, stop; The count of the current person ends and the current person is pushed onto the stack
Java code
class Solution {
public int[] canSeePersonsCount(int[] heights) {
int n = heights.length;
Stack<Integer> stack = new Stack<>();
int[] ans = new int[n];
for (int i = n - 1; i >= 0 ; i--) {
while(! stack.empty()) { ans[i]++;// Note here that the heights array varies, which ensures that the monotonic stack is strictly monotonic
if (heights[i] > heights[stack.peek()]) stack.pop();
else break;
}
stack.push(i);
}
returnans; }}Copy the codeC + + code
class Solution {
public:
vector<int> canSeePersonsCount(vector<int>& heights) {
int n = heights.size();
stack<int> stk;
vector<int> ans(n);
for (int i = n - 1; i >= 0; i--) {
while(! stk.empty()) { ans[i]++;if (heights[i] > heights[stk.top()]) stk.pop();
else break;
}
stk.push(i);
}
returnans; }};Copy the codeMonotonous stack this kind of questions have some common characteristics, that is monotonicity, can refer to my previous article: Acwing – algorithm basic course notes (4) in the monotonous stack section, the corresponding exercises to do again, you can do the monotonous stack type of questions.
(after)
(update 2021/07/29: redone each problem in C++)