1219. Gold miners
2022.2.5 one question per day
Title Description
You want to develop a gold mine. Geological surveyors have identified the distribution of resources in the gold mine and marked it with a grid of size m * n. The integer in each cell represents the amount of gold in this cell; If the cell is empty, it is 0.
In order to maximize profits, miners need to mine gold according to the following rules:
Every time a miner enters a cell, he collects all the gold in that cell.
Miners can walk up, down, left and right from their current position at a time.
Each cell can only be mined (entered) once.
Do not mine (enter) cells with a gold number of 0.
Miners can start from any cell with gold in the grid or stop.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
One route to collect the most gold is: 9 - > 8 - > 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
One route to collect the most gold is: 1 - > 2 - > 3 - > 4 - > 5 - > 6 - > 7.
Tips:
1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
There is gold in up to 25 cells.
Source: LeetCode
Link: https://leetcode-cn.com/problems/path-with-maximum-gold
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
thinking
to flash back
class Solution {
int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int[][] grid;
int m;
int n;
public int getMaximumGold(int[][] grid) {
//There are fewer grids and less gold, so it should be possible to trace back
this.grid = grid;
m = grid.length;
n = grid[0].length;
int res = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 0)
continue;
boolean[][] used = new boolean[m][n];
used[i][j] = true;
int t = find(used, i, j, grid[i][j]);
res = Math.max(res, t);
used[i][j] = false;
}
}
return res;
}
public int find(boolean[][] used, int i, int j, int gold){
int res = gold;
for(int[] d : dir){
int x = i + d[0];
int y = j + d[1];
if(x >= 0 && y >= 0 && x < m && y < n && !used[x][y] && grid[x][y] != 0){
used[x][y] = true;
res = Math.max(res, find(used, x, y, gold + grid[x][y]));
used[x][y] = false;
}
}
return res;
}
}
1748. Sum of unique elements
2022.2.6 one question per day
Title Description
Give you an integer array nums. The only elements in the array are those that appear exactly once.
Please return the sum of the only element in num.
Example 1:
Input: num = [1,2,3,2]
Output: 4
Explanation: the only elements are [1,3], and 4.
Example 2:
Input: num = [1,1,1,1,1]
Output: 0
Explanation: there is no unique element, and is 0.
Example 3:
Input: num = [1,2,3,4,5]
Output: 15
Explanation: the only element is [1,2,3,4,5], and is 15.
Tips:
1 <= nums.length <= 100
1 <= nums[i] <= 100
Source: LeetCode
Link: https://leetcode-cn.com/problems/sum-of-unique-elements
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
thinking
class Solution {
public int sumOfUnique(int[] nums) {
int[] count = new int[101];
for(int i = 0; i < nums.length; i++){
count[nums[i]]++;
}
int res = 0;
for(int i = 0; i < 101; i++){
if(count[i] == 1)
res += i;
}
return res;
}
}
1405. Longest happy string
2022.2.7 one question per day, good luck in construction
Title Description
If the string does not contain any strings such as' aaa ',' bbb 'or' ccc 'as substrings, the string is a "happy string".
Here are three integers a, b and c. please return any string s that meets all the following conditions:
s is a happy string as long as possible.
There are at most a letter 'a', b letter 'B', and c letter 'c' in s.
s contains only 'a', 'b' and 'c'.
If such a string s does not exist, return an empty string ''.
Example 1:
Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" is also a correct answer.
Example 2:
Input: a = 2, b = 2, c = 1
Output: "aabbc"
Example 3:
Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: This is the only correct answer for this test case.
Tips:
0 <= a, b, c <= 100
a + b + c > 0
Source: LeetCode
Link: https://leetcode-cn.com/problems/longest-happy-string
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
thinking
The idea is actually very simple, because you can't put three in a row, so you can put two in a row at most
So how to put it
The simplest thing we can think of is that if the three letters are the same, we can put them one by one, so our goal is to make the number of three letters the same
If the number of two letters is the same and greater than the number of the third letter, and the two same letters are placed one by one, it will be the same as the number of the third letter
If the number of three letters is not the same, then put two at most and one more at a time, which will be close to the second case
I write more complex, because I can't think of a simple writing method. I need to pay attention to all kinds of null pointers
class Solution {
public String longestDiverseString(int a, int b, int c) {
//How to put it properly? The number of three letters should be almost the same
//In this way, the placement strategy is to place the most letters first,
//Then put the second most. If the two letters are the same, put two until they are the same as the third
//Then the three are placed in turn
StringBuffer sb = new StringBuffer();
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> (y[1] - x[1]));
if(a != 0)
pq.offer(new int[]{1, a});
if(b != 0)
pq.offer(new int[]{2, b});
if(c != 0)
pq.offer(new int[]{3, c});
while(!pq.isEmpty()){
int t = helper(pq);
if(t == 1){
int[] first = pq.poll();
sb.append((char)(first[0] - 1 + 'a'));
if(first[1] - 1 > 0)
sb.append((char)(first[0] - 1 + 'a'));
if(pq.isEmpty())
return sb.toString();
int[] second = pq.poll();
sb.append((char)(second[0] - 1 + 'a'));
if(first[1] - 2 > 0)
pq.offer(new int[]{first[0], first[1] - 2});
if(second[1] - 1 > 0)
pq.offer(new int[]{second[0], second[1] - 1});
}else if(t == 2){
int[] first = pq.poll();
int[] second = pq.poll();
sb.append((char)(first[0] - 1 + 'a'));
sb.append((char)(second[0] - 1 + 'a'));
if(first[1] - 1 > 0)
pq.offer(new int[]{first[0], first[1] - 1});
if(second[1] - 1 > 0)
pq.offer(new int[]{second[0], second[1] - 1});
}else{
int[] first = pq.poll();
int[] second = pq.poll();
int[] third = pq.poll();
int num = first[1];
while(num-- > 0){
sb.append((char)(first[0] - 1 + 'a'));
sb.append((char)(second[0] - 1 + 'a'));
sb.append((char)(third[0] - 1 + 'a'));
}
return sb.toString();
}
}
return sb.toString();
}
//If the largest is larger than the second largest, it returns 1
//If the first two are the same and larger than the third, 2 is returned
//If the three are the same, return 3
public int helper(PriorityQueue<int[]> pq){
if(pq.size() == 1)
return 1;
int[] first = pq.poll();
int[] second = pq.poll();
int[] third = pq.peek();
int flag = 0;
if(first[1] > second[1])
flag = 1;
else if(third == null || second[1] > third[1])
flag = 2;
else
flag = 3;
pq.offer(first);
pq.offer(second);
return flag;
}
}
In fact, according to the constructed string, judge whether three characters are connected. If three identical characters are connected, use the second most. It's easier to write this way