威安姆位尔

迎难而上，祝我好运。面朝大海，春暖花开。

minimum cost

• 给一个int数组，要把它变成单调递增或者单调递减（相等也行），可以对数组内任意一个数字加或者减任意值，把这个加减的绝对值称为cost，问要实现最后单调递增或者递减的效果，最少的cost总和是多少？
• 参考了DP做法。原数组为nums，先尝试递增，排序得到sorted。input作row，sorted作col，dp[i][j]表示以sorted[j]为最大值、input[0i]所需的minCost，dp[0][0]表示input[0]维持单调需要的minCost，自然就是abs(input[0] - sorted[0])了，dp[i][0]表示以sorted[0]为基准的到input[i]为止累计的minCost，dp[0][j]表示任选sorted[0j]元素将input[0]变到它所需的cost。

public int getMinimumCost(int[] input) {
    if (input == null || input.length == 0) {
        return 0;
    }
    return Math.min(getMinimumCost(input, false), getMinimumCost(input, true));
}
private int getMinimumCost(int[] input, boolean reverse) {
    int[] sorted = Arrays.copyOf(input, input.length);
    Arrays.sort(sorted);
    if (reverse) {
        for (int i = 0, j = sorted.length - 1; i < j; i++, j --) {
            int temp = sorted[i];
            sorted[i] = sorted[j];
            sorted[j] = temp;
        }
    }
    int[][] dp = new int[input.length][sorted.length];
    dp[0][0] = Math.abs(input[0] - sorted[0]);
    for (int i = 1; i < input.length; i++) {
        dp[i][0] = dp[i - 1][0] + Math.abs(input[i] - sorted[0]);
    }
    for (int j = 1; j < sorted.length; j++) {
        dp[0][j] = Math.min(dp[0][j - 1], Math.abs(input[0] - sorted[j]));
    }
    for (int i = 1; i < input.length; i++) {
        for (int j = 1; j < sorted.length; j++) {
            dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j] + Math.abs(input[i] - sorted[j]));
        }
    }
    return dp[input.length - 1][sorted.length - 1];
}

完美分配队员

• 根据skill看最多能分成几个组，由最少skill的学生数决定。

public int getTeamCount(String skills) {
    if (skills == null || skills.length() == 0 || skills.length() % 5 != 0) {
        return 0;
    }
    Map<Character, Integer> skillCount = new HashMap<>();
    for (char c : skills.toCharArray()) {
        skillCount.put(c, skillCount.getOrDefault(c, 0) + 1);
    }
    if (skillCount.size() < 5) {
        return 0;
    }
    int min = Integer.MAX_VALUE;
    for (char c : skillCount.keySet()) {
        min = Math.min(min, skillCount.get(c));
    }
    return min;
}

平移数组

• 字符串循环平移。

public String getShiftedString(String str, int leftShifts, int rightShifts) {
    if (str == null || str.length() == 0) {
        return null;
    }
    if (leftShifts + rightShifts == 0) {
        return str;
    }
    leftShifts = (leftShifts - rightShifts) % str.length();
    return str.substring(leftShifts) + str.substring(0, leftShifts);
}

偶数子数组

• 给一个int数组，求有多少个至多含有k个奇数的、不重复出现的子数组。使用滑动窗口保证奇数count不超过k，同时每次右指针纳入新元素时就从左指针开始将已有的元素encode成字符串存入set，这样就可以保证是dinstinct的subarray了。

public int getDistinctSubarray(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int left = 0, right = 0, oddCount = 0;
    Set<String> set = new HashSet<>();
    StringBuilder sb = new StringBuilder();
    while (right < nums.length) {
        oddCount += nums[right] % 2 == 1 ? 1 : 0;
        while (oddCount > k) {
            if (nums[left] % 2 == 1) {
                oddCount--;
            }
            left++;
            sb.delete(0, sb.indexOf(",") + 1);
        }
        sb.append(nums[right]);
        sb.append(',');
        updateSet(set, sb);
        right++;
    }
    return set.size();
}
private void updateSet(Set<String> set, StringBuilder sb) {
    int start = 0, end = sb.indexOf(",");
    while (end > 0) {
        set.add(sb.substring(start, sb.length()));
        start = end + 1;
        end = sb.indexOf(",", start);
    }
}

// 然而超时了，没搞出来。当时想用两个set来做的：
public int getDistinctSubarray2(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int left = 0, right = 0, oddCount = 0;
    Set<String> set = new LinkedHashSet<>();
    Set<String> prevSet = new LinkedHashSet<>();
    prevSet.add("");
    while (right < nums.length) {
        oddCount += nums[right] % 2 == 1 ? 1 : 0;
        while (oddCount > k) {
            if (nums[left] % 2 == 1) {
                oddCount--;
            }
            List<String> prevSetList = new ArrayList<>(prevSet);
            for (int i = prevSetList.size() - 1; i >= 0 && prevSetList.get(i).startsWith(String.valueOf(nums[left])); i--) {
                prevSet.remove(prevSetList.get(i));
            }
            left++;
        }
        prevSet = updateSet2(set, prevSet, nums[right]);
        right++;
    }
    return set.size();
}
private Set<String> updateSet2(Set<String> set, Set<String> prevSet, int num) {
    Set<String> newSet = new LinkedHashSet<>();
    newSet.add("");
    for (String prev : prevSet) {
        String curr = prev + num + ",";
        if (!set.contains(curr)) {
            set.add(curr);
            newSet.add(curr);
        }
    }
    return newSet;
}

minimum increments

• 给一个int数组，其中可能含有duplicate，对其中的元素进行++操作，使得所有数字都distinct，返回最小sum。
• 先排序，然后遍历原数组，用一个prev记录之前的元素（可能经过++）了，若当前元素小于等于prev，就需要++，直接累加到sum中；否则就直接累加并将prev赋值为当前元素。

public int getMinSum(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int sum = nums[0], prev = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] <= prev) {
            prev++;
            sum += prev;
        } else {
            sum += nums[i];
            prev = nums[i];
        }
    }
    return sum;
}

孪生字符串

• 个字符串a和b，同字符串内，奇数位和奇数位的字符可以互相交换，偶数位和偶数位的字符也可以。判断能否通过这种交换操作使两个字符串相等。
• 分别统计奇数位和偶数位每个字母的出现次数，然后比较两个字符串的统计结果是否相等即可。