Force clasp – Greedy Algorithm problem Solving (simple, medium, difficult)
Greed – Easy difficulty
392 Judgment subsequence
First sort from small to large and get the sum, and then sum from back to front, if the sum is more than half of the sum, it is stable
class Solution {
public boolean isSubsequence(String s, String t) {
int index = -1;
for(char c:s.toCharArray){
index = t.indexOf(c,index+1);
if(index == -1)
return false;
}
return true; }}Copy the code1403 The smallest sequence in non-increasing order
You sort them, you sum them, and then you sum them in reverse order, and when you get more than half of them, you’re good
class Solution {
public List<Integer> minSubsequence(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
int total = 0;
for(int s:nums){
total += s;
}
Arrays.sort(nums);
int temp = 0;
for(int i = nums.length() - 1; i >=0; i--){ temp += num[i]; list.add(nums[i]);if(2 * temp > total){
break; }}returnlist; }}Copy the code1518 Alcohol exchange problem
- Solution 1: Directly simulate the process
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int bottle = numBottles,ans = numBottles;
while(bottle >= numExchange){
bottle -= numExchange;
++ans;
++bottle;
}
returnans; }}Copy the code
- Solution # 2: Mathematical Solution
Here’s the idea:
By value. Assume that the value of the bottle is 1, then the total value of all the wine is numExchange so remove the bottle, we can drink the price of the wine is numExchange-1 wonderful!
class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
return (numBottles * numExchange-1)/(numExchange-1); }}Copy the codeThe weight of the last stone
Build a big pile of roots and bump the top two each time to get smaller stones and put them in the pile until only the smallest one is left
import java.util.PriorityQueue;
public class Solution {
public int lastStoneWeight(int[] stones) {
int len = stones.length;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len,(o1,o2)->-o1+o2);
for(int stone:stones){
maxHeap.add(stone);
}
while(maxHeap.size() >= 2){
Integer head1 = maxHeap.poll();
Integer head2 = maxHeap.poll();
maxHeap.offer(head1 - head2);
}
returnmaxHeap.poll(); }}Copy the codeThe sum of the array maximized by taking the inverse 1005 times
General idea:
If K is greater than 0, take the minimum of array A and take the negative otherwise sum array A
class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
int[] number = new int[201];
for(int t: A){
number[t + 100] + +; }int i = 0;
while(K > 0) {while(number[i] == 0)
i++;
number[i]--;
number[200 - i]++;
if(i > 100){
i = 200 - i;
}
K--;
}
int sum = 0;
for(intj = i; j < number.length; j++){ sum += (j -100) * number[j];
}
returnsum; }}Copy the code1221 Split balance string
First understand the question:
First of all, we define what a balanced string is: the number of letters L in a string is the same as the number of letters R. Then we define how to split it: one cut, the two new strings that are cut must be balanced strings, otherwise they cannot be cut. Then we ask how many balanced strings can be cut at most
And the idea here is very simple, as you traverse, you cut once if the number of L is equal to the number of R
One neat idea is to take the ACCIi codes of L and R, and then treat the string as an array of -3 and 3, and find the number of times the first n digits sum to zero
class Solution {
public int balancedStringSplit(String s) {
int stack = 0;
int cnt = 0;
for(char c:s.toCharArray()){
if(c == 'R'){
stack++;
}
else{
stack--;
}
if(stack == 0)
cnt++;
}
returncnt; }}Copy the codeGreed – Medium difficulty
Avoid the minimum deletion cost of duplicate letters
If the character s[I] is the same as the character s[I +1] to s[j], count the sum of s[I..j] and keep the largest sum Max. Then the minimum cost of S [I..j] is (sum-max).
class Solution {
public int minCost(String s, int[] cost) {
int res = 0;
char[] word = s.toCharArray();
for(int i = 0; i < word.length; i++){char c = word[i];
int max = cost[i];
int sum = max;
while(i + 1 < word.length && word[i + 1] == c){
sum += cost[++i];
max = Math.max(max,cost[i]);
}
if(sum != max){
res += sum - max;
}
}
returnres; }}Copy the codeReconstruct the queue based on height
Here’s the general idea:
You sort everyone from tall to short, and you’re going to put them in a queue; The rule for putting in a queue is, from the height to the height, just look at the k value and put it in, because the next person in the queue is shorter, so even if the short person is put in front of the tall person, it doesn’t affect the k value of the tall person
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people,(o1,o2) -> o1[0] == o2[0]? o1[1] - o2[1] : o2[0] - o1[0]);
LinkedList<int[]> list = new LinkedList<>();
for(int[] i : people){
list.add(i[1],i);
}
return list.toArray(new int[list.size()][2]); }}Copy the code1497 checks whether an array pair is divisible by k
It’s easy to think:
Modulo all the numbers of the original array with k, the remainder +k becomes a positive number, which is used as the subscript of the array to store the corresponding remainder value. Finally, the pair is made: the number of remainder of the set of k is equal && and the number of remainder 0 is even, then it can be divisible by K
class Solution {
public boolean canArrange(int[] arr, int k) {
int[] mod = new int[k];
for(int i:arr){
mod[(i % k + k) % k]++;
}
for(int i = 1; i < k; i++){if(mod[i] ! = mod[k - i])return false;
}
return mod[0] % 2= =0 ? true:false; }}Copy the code1338 Array size halved
Ideas:
Sort first, and then record the number of each number, save, and then sort the number of numbers, and then pick the most start delete, delete more than half of the stop
class Solution {
public int minSetSize(int[] arr) {
Arrays.sort(arr);
ArrayList<Integer> cnt = new ArrayList<>();
cnt.add(1);
for(int i = 1; i < arr.length; i++){if(arr[i] == arr[i - 1])
cnt.set(cnt.size() - 1,cnt.get(cnt.size() - 1) + 1);
else cnt.add(1);
}
Collections.sort(cnt);
int num = 0;
for(int i = cnt.size() - 1; i >=0; i--){ num += cnt.get(i);if(num * 2 >= arr.length)
return cnt.size() - i;
}
return 0; }}Copy the code1405 Longest happy string
Just read the notes
class Solution {
public String longestDiverseString(int a, int b, int c) {
// Three letters and the number of letters
MyChar[] myChars = new MyChar[]{
new MyChar('a',a),
new MyChar('b',b),
new MyChar('c',c),
};
StringBuilder sb = new StringBuilder();
while(true) {MyChars [2] = myChars[2] = myChars[2
Arrays.sort(myChars);
if(sb.length() >= 2 &&
sb.charAt(sb.length() - 1) == myChars[2].ch &&
sb.charAt(sb.length() - 2) == myChars[2].ch){
// If the last two letters of the current happy string are the same as the most letters:
if(myChars[1].count-- > 0){
sb.append(myChars[1].ch);
// Many times the host
}else{
break; }}else{
if(myChars[2].count-- > 0){
sb.append(myChars[2].ch);
}else{
break; }}}return sb.toString();
}
// Create a MyChar class to store letters and count them
The //ComparaTo() method is used to prepare for sort
private class MyChar implements Comparable{
char ch;
int count;
public MyChar(char ch,int count){
this.ch = ch;
this.count = count;
}
@Override
public int compareTo(Object o){
MyChar other = (MyChar)o;
return this.count - other.count; }}}Copy the code1589. The largest sum of all permutations
See the comments
class Solution {
public int maxSumRangeQuery(int[] nums, int[][] requests) {
// Construct the difference array of nums, which represents the weight of a day
int[] dnums = new int[nums.length];
dnums[0] = nums[0];
for(int i = 1; i < nums.length; i++){ dnums[i] = nums[i] - nums[i -1];
}
// Count the weights of the interval by difference
// The number of times each position must be queried
for(int i = 0; i < requests.length; i++){ dnums[requests[i][0]] + +;if(requests[i][1] < dnums.length - 1){
dnums[requests[i][1] + 1] -; }}// Restore the difference array to its undifference state
for(int i = 1; i < dnums.length; i++){ dnums[i] += dnums[i-1];
}
// Compare the array dnums with the original array, and finally get the query array for each position of the query number.
for(int i = 0; i < nums.length; i++){ dnums[i] = dnums[i] -nums[i]; } Arrays.sort(dnums); Arrays.sort(nums);long sum = 0;
for(int i = 0; i < nums.length; i++){ sum += dnums[i] * nums[i]; }return (int)(sum % 1000000007); }}Copy the codeArrange cinema seating
Bit operations.
There are three things that satisfy this condition: left,middle,right. These three cases are represented in binary for easy understanding, representation, and computation. (There are only eight seats because the first and tenth seats are meaningless and do not affect the arrangement of the remaining eight seats, whether or not they have been reserved.) Where, 1 means reserved and 0 means not reserved. You just have to do bitwise or bitwise operations with left,middle, and right and if one of these things stays the same after the operation, you can arrange it
class Solution {
public int maxNumberOfFamilies(int n, int[][] reservedSeats) {
int left = 0b11110000;
int middle = 0b11000011;
int right = 0b00001111;
Map<Integer,Integer> occupied = new HashMap<Integer,Integer>();
for(int[] seat:reservedSeats){
if(seat[1] > =2 && seat[1] < =9) {int origin = occupied.containsKey(seat[0])? occupied.get(seat[0) :0;
int value = origin | (1 << (seat[1] - 2));
occupied.put(seat[0],value); }}int ans = (n - occupied.size()) * 2;
for(Map.Entry<Integer,Integer> entry:occupied.entrySet()){
int row = entry.getKey(),bitmask = entry.getValue();
if(((bitmask | left) == left) || ((bitmask | middle) == middle) || ((bitmask | right) == right))
++ans;
}
returnans; }}Copy the code1353 Maximum number of conferences that can be attended
It’s the same old story
In order to attend as many meetings as possible, you need to attend meetings that end early so that you don’t waste too much time
class Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events,new Comparator<int[] > () {@Override
public int compare(int[]a,int[]b){
return a[0] - b[0]; }}); PriorityQueue<Integer> queue =new PriorityQueue<>();
int day = 0;
int id = 0;
int n = events.length;
int res = 0;
while(id < n || ! queue.isEmpty()){if(queue.isEmpty()){
queue.add(events[id][1]);
day = events[id++][0];
}
while(id < n && events[id][0] <= day){
queue.add(events[id++][1]);
}
if(queue.peek() >= day){
day++;
res++;
}
queue.poll();
}
returnres; }}Copy the code842 splits the array into Fibonacci sequences
Just read the comments!
class Solution {
List<Integer> ans;
public List<Integer> splitIntoFibonacci(String S) {
ans = new ArrayList<>();
return dfs(0, S, 0.0.0)? ans :new ArrayList<>();
}
/ * * *@p: The current pointer to the array index *@s: string *@pre1: the next number *@pre2: indicates the previous number *@deep: The current number **/
public boolean dfs(int p, String s, int pre1, int pre2, int deep) {
int length = s.length();
if (p == length)return deep >= 3;
for (int i = 1; i <= 10; i++) {
// Go beyond the length or start with 0 to break;
if (p + i > length || (s.charAt(p) == '0' && i > 1))break;
// Intercepts a string
String sub = s.substring(p, p + i);
long numL = Long.parseLong(sub);
If deep is not 0,1 is greater than the sum of its first two numbers
if(numL > Integer.MAX_VALUE || (deep ! =0&& deep ! =1 && numL > (pre1 + pre2)))break;
/ / to int
Integer num = (int) numL;
// The number satisfies the condition, recursively plus backtracking
if (deep == 0 || deep == 1 || num.equals(pre1 + pre2)) {
ans.add(num);
if (dfs(p + i, s, pre2, num, deep + 1))return true; ans.remove(num); }}return false; }}Copy the code767 Reconstructs the character string
class Solution {
public String reorganizeString(String S) {
int N = S.length();
int[] counts = new int[26];
for(char c:S.toCharArray())
counts[c-'a'] + =100;
for(int i = 0; i <26; i++) counts[i] += i; Arrays.sort(counts);char[] ans = new char[N];
int t = 1;
for(int code:counts){
int ct = code / 100;
char ch = (char) ('a' + (code % 100));
if(ct >(N + 1) / 2) return "";
for(int i = 0; i < ct; ++i){if(t >= N) t = 0;
ans[t] = ch;
t += 2; }}returnString.valueOf(ans); }}Copy the code
class Solution {
public String reorganizeString(String S) {
int N = S.length();
int[] count = new int[26];
for(char c: S.toCharArray())
count[c - 'a'] + +; PriorityQueue<MultiChar> pq =new PriorityQueue<MultiChar>((a,b) ->
a.count == b.count ? a.letter - b.letter : b.count - a.count);
for(int i = 0; i <26; i++){if(count[i] > 0) {if(count[i] > (N + 1) / 2) return "";
pq.add(new MultiChar(count[i],(char) ('a' + i)));
}
}
StringBuilder ans =new StringBuilder();
while(pq.size() >= 2){
MultiChar mc1 = pq.poll();
MultiChar mc2 = pq.poll();
ans.append(mc1.letter);
ans.append(mc2.letter);
if(--mc1.count > 0) pq.add(mc1);
if(--mc2.count > 0) pq.add(mc2);
}
if(pq.size() > 0) ans.append(pq.poll().letter);
returnans.toString(); }}class MultiChar{
int count;
char letter;
MultiChar(int ct,charch){ count = ct; letter = ch; }}Copy the codeReconstruct a 2-row binary matrix
class Solution {
public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
int up = upper,lo = lower,sum = 0,len = colsum.length;
List<List<Integer>> list = new ArrayList<>();
for(int i = 0; i < len; i++){if(colsum[i] == 2){
up--;
lo--;
}
else if(colsum[i] == 1){ sum++; }}if(up + lo ! = sum || up <0 || lo < 0) {return list;
}
List<Integer> upl = new ArrayList<>();
List<Integer> lol = new ArrayList<>();
for(int i = 0; i < len; i++){if(colsum[i] == 2){
upl.add(1);
lol.add(1);
}
else if(colsum[i] == 0){
upl.add(0);
lol.add(0);
}
else{
if(up -- > 0){
upl.add(1);
lol.add(0);
}
else{
lol.add(1);
upl.add(0);
}
}
}
list.add(upl);
list.add(lol);
returnlist; }}Copy the code1567 Count the length of the oldest child whose product is positive
class Solution {
public int getMaxLen(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][2];
int res = 0;
if(nums[0] > 0){
dp[0] [0] = 1;
}else if(nums[0] < 0){
dp[0] [1] = 1;
}
for(int i =1; i < n; i++){if(nums[i] > 0){
dp[i][0] = dp[i-1] [0] + 1;
if(dp[i - 1] [1] > 0)
dp[i][1] = dp[i - 1] [1] + 1;
}else if(nums[i] < 0) {if(dp[i - 1] [1] > 0)
dp[i][0] = dp[i - 1] [1] + 1;
dp[i][1] = dp[i - 1] [0] + 1; }}for(int i = 0; i < n; i++){ res = Math.max(res,dp[i][0]);
}
returnres; }}Copy the code1111 The nesting depth of valid parentheses
A stack simulation process
public class Solution{
public int[] maxDepthAfterSplit(String seq){
int[] ans = new int[seq.length()];
int idx = 0;
for(char c: seq.toCharArray()){
ans[idx++] = c == '(' ? idx & 1 : ((idx + 1) & 1);
}
returnans; }}Copy the codeGreed – Difficult difficulty
Maximum team performance value
class Solution {
public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
int[][] items = new int[n][2];
for(int i = 0; i < n; i++){ items[i][0] = speed[i];
items[i][1] = efficiency[i];
}
Arrays.sort(items,new Comparator<int[] > () {@Override
public int compare(int[] a,int[] b){
return b[1] - a[1]; }}); PriorityQueue<Integer> queue =new PriorityQueue<>();
long res = 0,sum = 0;
for(int i = 0; i < n; i++){if(queue.size() > k - 1){
sum -= queue.poll();
}
res = Math.max(res,(sum + items[i][0]) * items[i][1]);
queue.add(items[i][0]);
sum += items[i][0];
}
return (int)(res % ((int)1e9 + 7)); }}Copy the codeThe 659 split array is a continuous subsequence
class Solution {
public boolean isPossible(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int i : nums){
map.put(i,map.getOrDefault(i,0) + 1);
}
for(int i: nums){
int subNum = 0;
int p = 1;
int next = i;
while(map.getOrDefault(next,0) >= p){
p = map.get(next);
map.put(next,p-1);
++subNum;
++next;
}
if(subNum > 0 && subNum < 3) {return false; }}return true; }}Copy the codeThe minimum number of days the land was separated
See the comments
It will write a Tarjan + and look up the set version
class Solution {
int m, n;
boolean[][] used;
private static final int[][] directions = {{-1.0}, {0, -1}, {1.0}, {0.1}};
public int minDays(int[][] grid) {
m = grid.length;
n = grid[0].length;
used = new boolean[m][n];
if(check(grid)){
return 0;
}else{
// enumerate one of the 1's to see if it satisfies
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1){
grid[i][j] = 0;
if(check(grid)){
return 1;
}
grid[i][j] = 1; }}}return 2; }}public boolean check(int[][] grid){
// Calculate whether there are multiple connected blocks, or 0 connected blocks
int count = 0;
used = new boolean[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(! used[i][j] && grid[i][j] ==1){ count++; dfs(grid, i, j); }}}return count > 1 || count == 0;
}
public void dfs(int[][] grid, int i, int j){
used[i][j] = true;
for(int k = 0; k < 4; k++){
int x = i + directions[k][0];
int y = j +directions[k][1];
if(inArea(x, y) && ! used[x][y] && grid[i][j] ==1){ dfs(grid, x, y); }}}public boolean inArea(int x, int y){
return x >= 0 && x < m && y >= 0&& y < n; }}Copy the code1505 The smallest integer obtained by swapping adjacent digits at most K times
See the comments
class Solution {
public String minInteger(String num, int k) {
// count all positions from 0 to 9
List<Integer>[] idLists = new List[10];
for (int i = 0; i < 10; i++) {
idLists[i] = new ArrayList<>();
}
int n = num.length();
for (int i = 0; i < n; i++) {
idLists[num.charAt(i) - '0'].add(i);
}
// point to the current position of 0-9 on idLists
int[] ids = new int[10];
boolean[] seen = new boolean[n];
StringBuilder res = new StringBuilder();
// The number of subscripts that have been converted to the previous subscripts should be removed when calculating the number of conversions required
FenwichTree fwt = new FenwichTree(new int[n]);
outer:
for (int i = 0; i < n; i++) {
if (seen[i]) { // If it has already been replaced, skip it
continue;
}
int cur = num.charAt(i) - '0';
// Find the smallest subscript smaller than the current element
for (int j = 0; j < cur; j++) {
while (ids[j] < idLists[j].size() && idLists[j].get(ids[j]) < i) {
ids[j]++;
}
if (ids[j] == idLists[j].size()) {
continue;
}
int index = idLists[j].get(ids[j]);
int seenNum = fwt.sumRange(0, index - 1);
if (index - seenNum <= k) {
// Update the status when a value is found
k -= index - seenNum;
ids[j]++;
seen[index] = true;
fwt.update(index, 1);
i--;
res.append(j);
continueouter; }}// A value smaller than the current value cannot be found
seen[i] = true;
fwt.update(i, 1);
res.append(cur);
}
returnres.toString(); }}class FenwichTree {
private int[] sums;
private int[] nums;
public FenwichTree(int[] nums) {
this.sums = new int[nums.length + 1];
this.nums = nums;
for (int i = 0; i < nums.length; i++) {
updateBit(i + 1, nums[i]); }}public void update(int i, int val) {
updateBit(i + 1, val - nums[i]);
nums[i] = val;
}
private void updateBit(int i, int diff) {
while(i < sums.length) { sums[i] += diff; i += lowBit(i); }}public int sumRange(int i, int j) {
return preSum(j + 1) - preSum(i);
}
private int preSum(int i) {
int sum = 0;
while (i > 0) {
sum += sums[i];
i -= lowBit(i);
}
return sum;
}
private int lowBit(int i) {
returni & (-i); }}Copy the code502 IPO
- Store all project information, namely capital and profit, in a project node
- Depending on the size of the capital, put the project into the small root heap
- Take capital less than capital M and put it into a large root heap according to profit size
- The number of pop-ups from the large heap is the most profitable items that can be done (the large heap is sorted by profit, so the most profitable items are taken)
Finally, it ends when k projects are completed or there are no projects that can be done (an empty profit pile indicates that the remaining projects cost more than the capital, or all projects have been completed)
class Solution {
public static class Node{
int profit;
int capital;
public Node(int profit,int capital){
this.profit = profit;
this.capital = capital; }}public static class ComparatorOfProfit implements Comparator<Node>{
@Override
public int compare(Node n1,Node n2){
returnn2.profit - n1.profit; }}public static class ComparatorOfCapital implements Comparator<Node>{
@Override
public int compare(Node n1,Node n2){
returnn1.capital - n2.capital; }}public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<Node> pqByP = new PriorityQueue<>(new ComparatorOfProfit());
PriorityQueue<Node> pqByC = new PriorityQueue<>(new ComparatorOfCapital());
Node[] nodes = new Node[Profits.length];
for(int i = 0; i < Profits.length; i++){ nodes[i] =new Node(Profits[i],Capital[i]);
}
for(int i = 0; i < Profits.length; i++){ pqByC.add(nodes[i]); }for(int i = 0; i < k; i++){while(! pqByC.isEmpty() && pqByC.peek().capital <= W){ pqByP.add(pqByC.poll()); }if(! pqByP.isEmpty()){ W += pqByP.poll().profit; }else{
break; }}returnW; }}Copy the code630 Course Schedule III
Again, take the class that ends first
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses,(a,b) -> a[1] - b[1]);
PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> b - a);
int time = 0;
for(int[] c:courses){
if(time + c[0] <= c[1]){
queue.offer(c[0]);
time += c[0];
}
else if(! queue.isEmpty() && queue.peek() > c[0]){
time += c[0] - queue.poll();
queue.offer(c[0]); }}returnqueue.size(); }}Copy the codeLovers hold hands
Damn. Single dog gets punched in the middle of the night.
This problem can be greedy, very violent, that is, you meet a person, his partner will not sit with him to find his partner to switch to him (but too violent). On and check collection I wrote a special topic, still writing, here will not repeat, after two days to finish writing hair. Personally, although greedy and violent, but also double hundred, but it should be because the data size of the topic is relatively small, so it will be like this.
Method a
// Select * from ()
class Solution {
private class UnionFind{
int[] parent;
int[] weight;
UnionFind(int[] row){
int m = row.length / 2;
parent = new int[m];
weight = new int[m];
for(int i = 0; i < m; i++){
parent[i] = i;
weight[i] = 1; }}public int find(int x){
if(parent[x] ! = x) parent[x] = find(parent[x]);return parent[x];
}
public void union(int x, int y){
int rootx = find(x);
int rooty = find(y);
if(rootx == rooty) return;
if(weight[rootx] > weight[rooty]){
parent[rooty] = rootx;
weight[rootx] += weight[rooty];
}else{ parent[rootx] = rooty; weight[rooty] += weight[rootx]; }}public int getRet(a){
int ret = 0;
for(int i = 0; i < parent.length; i++){
if(parent[i] ! = i) ret++; }returnret; }}public int minSwapsCouples(int[] row) {
UnionFind uf = new UnionFind(row);
for(int i = 0; i < row.length; i += 2){
uf.union(row[i] / 2, row[i + 1] / 2);
}
returnuf.getRet(); }}Copy the codeMethod 2
class Solution {
public int minSwapsCouples(int[] row) {
int ans = 0;
int n = row.length;
int[] indexArr = new int[n];
for (int i = 0; i < n; i++) {
indexArr[row[i]] = i;
}
int next = 0;
for (int i = 0; i < n; i += 2) {
next = (row[i] & 1) = =0 ? row[i] + 1 : row[i] - 1;
if (next == row[i + 1]) {
continue;
}
// There is no need to perform the swap operation, since the person entering the I + 1 position is now paired with a couple, which will not be used later.
// So just update the information of the person leaving the I +1 position
int swapedIndex = indexArr[next];
indexArr[row[i+1]] = swapedIndex;
row[swapedIndex] = row[i + 1];
ans++;
}
returnans; }}Copy the code1591 Strange Printer II
See the comments
class Solution {
public boolean isPrintable(int[][] targetGrid) {
int row_len = targetGrid.length;
int col_len = targetGrid[0].length;
// Determine the range of the four corners
boolean[] visited = new boolean[61]; // check whether the color appears
int[] row_start = new int[61];
int[] row_end = new int[61];
int[] col_start = new int[61];
int[] col_end = new int[61];
// Enter the number of nodes to determine the array
int[] into_degree = new int[61];
int visited_count = 0;
{int i = 0, j;
for (int[] ints : targetGrid) {
j = 0;
for (int anInt : ints) {
if (visited[anInt] == false) {
visited[anInt] = true;
visited_count++;
row_start[anInt] = row_end[anInt] = i;
col_start[anInt] = col_end[anInt] = j;
} else { //row_start does not need to update col_start does
row_end[anInt] = i;
col_start[anInt] = Math.min(col_start[anInt], j);
col_end[anInt] = Math.max(col_end[anInt], j);
}
j++;
}
i++;
}}
boolean[][] compare = new boolean[61] [61]; //compare[I] with [j]; //compare[I] with [j]
for (int target = 0; target <= 60; target++) {
if (visited[target]) {
for (int i = row_start[target]; i <= row_end[target]; i++) {
for (int j = col_start[target]; j <= col_end[target]; j++) {
if(target ! = targetGrid[i][j]) {if (compare[targetGrid[i][j]][target] == true) return false;
if (compare[target][targetGrid[i][j]] == false) { // This ensures that the input is only added once
into_degree[targetGrid[i][j]] ++;
compare[target][targetGrid[i][j]] = true;
}
}
}
}
}
}
for (int i = 1; i <= 5; i++) {
for (int j = 1; j <= 5; j++) {
// System.out.print((compare[i][j] == true ? 1:0) + "");
}
// System.out.println();
}
Return true; // Return true
// The stack should be used normally because the size of the case is small so I will go through each round from the beginning
int used_count = 0;
// LinkedList
ans = new LinkedList<>(); // This variable is used to output soluiton
for (int i = 0; i < 61;) {if (visited[i] == true && into_degree[i] == 0) {
used_count++;
// ans.addLast(i);
visited[i] = false;
for (int j = 0; j < 61; j++) {
if (compare[i][j] == true) into_degree[j]--;
}
i = 0; continue;
} else i++;
}
//System.out.println(ans); // This sentence can print a solution
returnused_count == visited_count; }}Copy the code1585 checks if a string can get another string by sorting substrings
The official solution is pretty good
class Solution {
public boolean isTransformable(String s, String t) {
int n = s.length();
Queue<Integer>[] pos = new Queue[10];
for (int i = 0; i < 10; ++i) {
pos[i] = new LinkedList<Integer>();
}
for (int i = 0; i < n; ++i) {
pos[s.charAt(i) - '0'].offer(i);
}
for (int i = 0; i < n; ++i) {
int digit = t.charAt(i) - '0';
if (pos[digit].isEmpty()) {
return false;
}
for (int j = 0; j < digit; ++j) {
if(! pos[j].isEmpty() && pos[j].peek() < pos[digit].peek()) {return false;
}
}
pos[digit].poll();
}
return true; }}Copy the code
conclusion
The above questions are not completely solved by greedy algorithm, because it is under the greedy label in the force buckle, so it is recorded in. Considering that sometimes greedy is too low efficiency, so it is not all done by greedy.
Done so many with greedy algorithm related topics, I also have their own little summary and experience.
Greedy is an algorithm that only considers the optimal choice in the current state, that is, always chooses the optimal solution in the current state. The general idea is:
- Build a mathematical model to describe the problem
- Divide the problem into subproblems
- Each problem is solved and the local optimal solution of the sub-problem is obtained
- The locally optimal solution of the subproblem is synthesized into a solution of the original problem
Feeling greedy topics are generally you want to understand the topic first, find a greedy entry point, generally there will be a law, is “choose the most… Is in the best situation. In addition, some preprocessing, such as sorting, prefix sum, difference, and so on, is generally required.