记录两道笔试

1. 给定一个字符串，每个字符只能选一次，可以拼成多少个“ccbft”？（不限大小写）

思路：遍历字符串，用数组模拟哈希表统计"ccbft"中的字符出现的次数（统一把大写看做小写），遍历数组，最小值就是能拼成的次数。（只过了87%）

    public int countSeq (String mystr) {
        char[] s = mystr.toCharArray();
        char[] target = "ccbft".toCharArray();
        int[] map = new int[26];
        for(char ch: s) {
            if(ch == 'C' || ch == 'c') {
                map['c'-'a']++;
            }
            if(ch == 'B' || ch == 'b') {
                map['b'-'a']++;
            }
            if(ch == 'F' || ch == 'f') {
                map['f'-'a']++;
            }
            if(ch == 'T' || ch == 't') {
                map['t'-'a']++;
            }
        }
        //因为c需要出现两次
        map['c'-'a'] /= 2;
        //遍历map找到最小的val就是能拼的最多次数
        int min = Integer.MAX_VALUE;
        for(int n : map) {
            if(n > 0) {
                min = Math.min(min, n);
            }

        }
        return min < Integer.MAX_VALUE ? min : 0;
    }

2. 给定字符串，可以删除一些字符，至少需要删除多少个字符可以使得各个字符出现的次数各不相同？

用哈希表统计每个字符出现的次数，把values()存入int[]后排序，从后往前遍历，统计当前元素和上限的差值（上限是前一个字符-1）

    public int Delete_character (String s) {
        // write code here
        char[] str = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for(char ch: str) {
            map.put(ch, map.getOrDefault(ch, 0)+1);
        }
        int[] a = new int[map.size()];
        int k = 0;
        for(int n: map.values()) {
            a[k++] = n;
        }
        Arrays.sort(a);
		
		int ans = 0;
		//当前元素上限
        int max = a[a.length-1];
        for(int i = a.length-1; i >= 0; i--) {
            //当超过上限时在统计了差额后，需要更新当前元素
            if(a[i] > max) {
                ans += (a[i]-max);
                a[i] = max;
            }
            //上限是前一个元素（删除后的）-1
            max = Math.max(0, a[i]-1);
        }
        return ans;
    }