>>> 维护一个长度固定为len-k的滑动窗口，窗口里的和最小，窗口外(即边上的k张牌)的和就最大

    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;
        int point = 0;		// point存放窗口内的和
        int sum = 0;		// sum存放整个数组的和
        int L = 0;	
        int R = 0;
        while (R < len - k) {
            point += cardPoints[R];
            sum += cardPoints[R];
            R++;
        }
        
        int res = point;	// res维护窗口内和的最小值
        while (R < len) {
            sum += cardPoints[R];
            point -= cardPoints[L++];
            point += cardPoints[R++];
            res = Math.min(res, point);
        }
        return sum - res;
    }
}

 
 
 

>>> 通过率仅有30%的简单题
>>> 当出现严格递减时，我们可断定此时需要修改。难点在于，这时分为了两种情况：

		*
			*	--->		*	*		(1) 修改[i-1]点，实际上此时不需要任何操作，实际基准为[i]点
	*					*

		*					*	*		(2) 修改[i]点，此时需要写代码进行修改，实际基准为[i-1]点
	*			--->	*		
			*			

class Solution {
    public boolean checkPossibility(int[] nums) {
        boolean chance = true;
        for(int i = 1; i < nums.length; i++) {
            if(nums[i] < nums[i - 1]) {
                if(chance) {
                    chance = false;
                    if(i >= 2 && nums[i] < nums[i - 2]) {
                        nums[i] = nums[i - 1];
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

 
 
 

>>> 这道题的困难之处在于，先要看的出这题是图论，然后要看出这是「并查集」

class Solution {
    public int minSwapsCouples(int[] row) {
        int len = row.length;
        UnionSet UnionSet = new UnionSet(len / 2);
        for(int i = 0; i < len; i += 2) {
            UnionSet.union(row[i] / 2, row[i + 1] / 2);
        }
        return len / 2 - UnionSet.count;
    }
}

/**
 * 并差集模板
 */
class UnionSet {

    int[] roots;
    int count;

    public UnionSet(int size) {
        count = size;
        roots = new int[size];
        for(int i = 0; i < size; i++) {
            roots[i] = i;
        }
    }

    public int findRoot(int node) {
        if(roots[node] == node) {
            return node;
        }
        roots[node] = findRoot(roots[node]);
        return roots[node];
    }

    public boolean isUnion(int node1, int node2) {
        return findRoot(node1) == findRoot(node2);
    }

    public void union(int node1, int node2) {
        if(!isUnion(node1, node2)) {
            roots[findRoot(node1)] = findRoot(node2);
            count--;
        }
    }

}

 
 
 
 

 
 
 
 

 
 
 
 

E N D END END