威安姆位尔

Posted on | Edited on | In | | Views:
Symbols count in article: 6k | Reading time ≈ 6 mins.

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

minimum cost

  • 给一个int数组，要把它变成单调递增或者单调递减（相等也行），可以对数组内任意一个数字加或者减任意值，把这个加减的绝对值称为cost，问要实现最后单调递增或者递减的效果，最少的cost总和是多少？
  • 参考了DP做法。原数组为nums，先尝试递增，排序得到sorted。input作row，sorted作col，dp[i][j]表示以sorted[j]为最大值、input[0~i]所需的minCost，dp[0][0]表示input[0]维持单调需要的minCost，自然就是abs(input[0] - sorted[0])了，dp[i][0]表示以sorted[0]为基准的到input[i]为止累计的minCost，dp[0][j]表示任选sorted[0~j]元素将input[0]变到它所需的cost。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    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的学生数决定。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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;
    }

平移数组

  • 字符串循环平移。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    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赋值为当前元素。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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，同字符串内，奇数位和奇数位的字符可以互相交换，偶数位和偶数位的字符也可以。判断能否通过这种交换操作使两个字符串相等。
  • 分别统计奇数位和偶数位每个字母的出现次数，然后比较两个字符串的统计结果是否相等即可。