情侣牵手[贪心 ＆ 抽象]

前言

贪心是考察分析能力的好题，尤其是带干扰性的，即需要我们将有用信息提取，去伪存真，将问题能够抽象出来。动态规划也是一样，如果没有抽象思维提取要害信息，则定义不出状态，自然也找不到状态如何转移。当然阅读理解题/脑筋急转弯，就更需要这种抽象有用信息的能力。

一、情侣牵手

二、贪心&抽象

package everyday.hard;

// 情侣牵手。
public class MinSwapsCouples {
    
    /* 抽象思维：其实我们并不关心1/2/3...这些位置，我们只关心特殊的相邻关系<0,1><2,3>。 那么一对特殊位置<x,y>，有2种情况。一是情侣则不管；二不是情侣，可以换走1个人，也可换走2个人。 由于我们只关心相邻位置，即把两对情侣的男生换掉，换个角度看，其实也可看成把两个女生换掉，所以我们在乎的是相邻对，而不是特别的位置。 所以，根据贪心，换1人的做法是最好的，留下一个人，就少换一次。 */
    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）多练习贪心题，锻炼分析能力 & 信息加工能力 & 信息提取与转换能力。

参考文献

[1] LeetCode 情侣牵手