This is the 16th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

Some basic examples of greedy algorithms: Leetcode 392, 122, 561, 1710, 1217, 1247, 1400, 921, 1029, 1605

The topic is relatively simple, except the last question is basically second kill

Leetcode 392 judge subsequence

Leetcode portal

So this is a subsequence, and there’s a recursive conclusion here that subsequence if there’s no subsequence for the first bifurcated letter you see, there’s no subsequence for the same letter you see later. It’s a bit of a brain teaser.

var isSubsequence = function(s, t) { if(! s.length){return true} if(s.length>t.length){return false} let i = 0, j=0,sl = s.length, tl=t.length; while(i<sl&&j<tl){ if(s[i]===t[j]){ i++ } j++ } return i===sl };Copy the code

Idea 2

I didn’t come up with this. What I came up with was a double pointer, moving from both ends to the middle, actually using the idea of idea 1. I just didn’t sum it up by myself. After looking at the code, theirs is simpler, but mine is slightly faster than 4ms. Maybe it’s the data. Theoretically, it should be the same.

var isSubsequence = function(s, t) { if(! s.length){return true} if(s.length>t.length){return false} let sleft = 0,tleft=0,sright=s.length-1,tright=t.length-1 while(sleft<=sright){ while(s[sleft]! ==t[tleft]){ tleft++ if(tleft>tright){return false} } sleft++ tleft++ if(sleft>sright){ return true } if(tleft>tright){return false} while(s[sright]! ==t[tright]){ tright-- if(tleft>tright){return false} } sright-- tright-- if(tleft>tright){return false} } return sleft>sright };Copy the code

Leetcode 122 The best time to Buy or sell stocks II

Leetcode portal

This problem cut point is very want to think, belong to second kill. You have to earn every day. If you don’t, you don’t buy.

var maxProfit = function(prices) { let res = 0 for(let i=0; i<prices.length-1; i++){ if(prices[i]<prices[i+1]){ res+=prices[i+1]-prices[i] } } return res };Copy the code

Leetcode 561 Array splitting ⅰ

Leetcode portal

This problem is also more want to think, the minimum value of the maximum, naturally is small number want to consume as soon as possible, it is natural to think of a good order, 2 groups, second kill type.

var arrayPairSum = function(nums) { nums.sort((a,b)=>a-b) let res = 0 for(let i=0; i<nums.length; i+=2){ res+=nums[i] } return res };Copy the code

Leetcode 1710 Maximum number of units on a truck

Leetcode portal

This is basically a sorting problem to read the question. By the number of boxes, the bigger the better. It would be nice to optimize the following code slightly and make fewer judgments.

var maximumUnits = function(boxTypes, truckSize) {
    boxTypes.sort((a,b)=>b[1]-a[1])
    let i=0
    let max
    let res=0
    while(truckSize>0&&i<boxTypes.length){
        max = Math.min(boxTypes[i][0],truckSize)
        res += max*boxTypes[i][1]
        truckSize -= max
        i++
    }
    return res
};
Copy the code

Leetcode 1217 play chips

Leetcode portal

It really took me a long time to understand the question. Notice that position is not how many chips there are in a particular position, it’s that each element represents a chip in that position, which I think is completely a problem solver and doesn’t make any sense.

Equivalent conversion, it’s easy to get the smallest of odd and even ratios.

var minCostToMoveChips = function(position) { let odd = 0,even=0 for(item of position){ if(item%2===0){even++}else{odd++} } return odd>even? even:odd };Copy the code

Leetcode 1247 Swaps characters to make strings the same

Leetcode portal

This problem also belongs to read the problem, equivalent conversion can be.

If the string has the same subscript element, it will be skipped. Otherwise, it will be the same as x1 plus one or x2 plus one

And if x1 plus x2 is even, that means that at least we can swap the odd number and return negative 1

Or points to discuss, according to the topic idea to take the most value, equivalent conversion, optimization code

The best solution is to understand xx and yy, which are paired first, xy and yx, which are considered last

Pretty soon we’re equivalent to mod two, and then we’ll extract the same code and it’ll be clear

var minimumSwap = function(s1, s2) { let x1 = x2 = 0 for(let i=0; i<s1.length; i++){ if(s1[i]===s2[i]){continue} if(s1[i]==='x'){x1++; }else{x2++} } let sum =x1+x2 if(sum%2===1){return -1} return sum/2+x1%2 };Copy the code

Leetcode 1400 constructs K palindrome strings

Leetcode portal

The problem is easy to understand, not easy to translate, you have to understand that he means that each palindrome string has at most one independent letter. So you can’t have more than k odd occurrences of all your characters. Direct hash table statistics, and then count the number of odd characters, comparison. The entrance is relatively narrow and, by luck, it’s easy to think of.

var canConstruct = function(s, k) { if(s.length<k){return false} let hashmap = {} for(item of s){ if(hashmap[item]){ hashmap[item] += 1 }else{ hashmap[item] = 1 } } for(item of Object.keys(hashmap)){ if(hashmap[item]%2===1){ k-- if(k<0){ return false } } } return  true };Copy the code

Leetcode 921 makes the minimum addition of parentheses valid

Leetcode portal

So this is very similar to the valid parentheses we saw before. So this is the case, if you have an open parenthesis, you put it in temp. Close parentheses appear, so let’s see if there are any open parentheses, there are no wrong parentheses directly. And just to be clear here, it’s easy to just count the number of errors directly when the closing bracket appears independently.

var minAddToMakeValid = function(s) { let temp = 0 let err = 0 for(item of s){ if(item==='('){ temp++ } else if(temp>0){  temp-- } else { err++ } } return temp + err };Copy the code

Leetcode 1029 for dual scheduling

Leetcode portal

Figuring out what the maximum value means is sort by the difference between ab and ab and this is easy to write, equivalence conversion, sorting, optimizing code

var twoCitySchedCost = function(costs) { costs.sort((a,b)=>(a[0]-a[1])-(b[0]-b[1])) let n = costs.length/2 let res = 0 for(let i=0; i<n; i++){ res+=costs[i][0]+costs[i+n][1] } return res };Copy the code

Leetcode 1605 Find the feasible matrix for a given sum of rows and columns

Leetcode portal

This was the only problem I didn’t think of but it also gave me a chance to study the code that Yu Creek wrote. Worship the big guy!

Initialize the total assignment to 0, and then assign to the minimum value of the sum of the rows and columns, updating the sum of the rows and columns so that each time is greater than or equal to zero, thus gradually achieving all row and column sums to 0. This kind of greedy thinking is really a new one. Hahaha, it’s fun.

var restoreMatrix = function(rowSum, colSum) { const [m,n] = [rowSum.length,colSum.length]; const matrix = Array(m).fill(0).map(()=>Array(n).fill(0)); for(let i = 0; i < m; i ++){ for(let j = 0; j < n; j ++){ matrix[i][j] = Math.min(rowSum[i],colSum[j]); rowSum[i] -= matrix[i][j]; colSum[j] -= matrix[i][j]; } } return matrix; };Copy the code

summary

We’re on 10. We’re starting to feel something

  1. Greedy algorithms, in essence, transform complex problems into simple ones, which is actually a way of thinking. The more familiar you are with the environment, the faster and more accurate your equivalents will be. Obviously, strings and one-dimensional arrays are familiar scenarios. We have many successful cases and can withstand changes. Once the matrix changes, I do not quite know how to change, in fact, is the embodiment of inexperience.
  2. The essence of greedy algorithms is how to simplify complex multidimensional problems into linear dimensional problems. It also keeps the data from being distorted. This is a little bit of machine learning dimension reduction. Maybe there’s a lot of arrays in these problems. If it’s an n-fork tree it’s pruning. After dimensionality reduction, it’s time to compare. The thinking is still very relaxed.
  3. Because the idea is very clear, so in these topics are to strive for 100%, try to find the gap between their code and others, this is also one of the meaning of brush questions, pay attention to the details of programming, look at the excellent code to learn from each other, rather than make it Ok.

Greedy algorithms have the last six hard problems, so let’s see if we have time to solve them together.