Couple Holding Hands [Greedy & Abstract]

前言

Greed is a good question to examine analytical skills,Especially the ones that are intrusive,That is, we need to extract useful information,去伪存真,The problem can be abstracted away.动态规划也是一样,If there is no abstract thinking to extract vital information,The state cannot be defined,Naturally, there is no way to find out how to transfer the state.Of course reading comprehension questions/脑筋急转弯,This ability to abstract useful information is even more needed.

一、情侣牵手

二、贪心&抽象

package everyday.hard;

// 情侣牵手.
public class MinSwapsCouples {
    
    /* 抽象思维：其实我们并不关心1/2/3...这些位置,We only care about special adjacencies<0,1><2,3>. Then a pair of special positions<x,y>,有2种情况.First, couples don't care;The second is not a couple,can be replaced1个人,Can also be replaced2个人. Since we only care about adjacent positions,That is to replace the boys of the two couples,换个角度看,In fact, it can also be seen as replacing the two girls,So what we care about is the adjacent pair,rather than a special location. 所以,根据贪心,换1The way of man is the best,leave alone,Just replace it less often. */
    public int minSwapsCouples(int[] row) {
    
        int cnt = 0;
        for (int i = 0; i < row.length; i += 2) {
    
            int target = (row[i] & 1) == 0 ? row[i] + 1 : row[i] - 1;

            if (target == row[i + 1]) continue;

            findAndSwap(row, i + 1, target);

            cnt++;
        }
        return cnt;
    }

    private void findAndSwap(int[] row, int begin, int target) {
    
        int i = begin + 1;
        while (i < row.length && target != row[i]) ++i;

        row[i] = row[begin];
        row[begin] = target;
    }
}

总结

1）Practice greed problems more,Exercise analytical skills & Information processing ability & Information extraction and transformation capabilities.

参考文献

[1] LeetCode 情侣牵手