DataWhale Task03：查找之 查找表

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        LinkedList<Integer> arr1=new LinkedList<Integer>();
        ArrayList<Integer> ans=new ArrayList<Integer>();
        for(int i:nums1){
            arr1.add(i);
        }
        for(int i:nums2){
            if(arr1.contains(i)){
                //todo
                ans.add(i);
                arr1.removeFirstOccurrence(i);
            }
        }
        int[] res=new int[ans.size()];
        int index=0;
        for(Integer i:ans){
            res[index++]=i;
        }
        return res;
 
    }//method end
}//class end

class Solution {
    public boolean wordPattern(String pattern, String str) {
    HashMap<Character, String> map = new HashMap<>();
    HashSet<String> set = new HashSet<>();
    String[] array = str.split(" ");
    if (pattern.length() != array.length) {
        return false;
    }
    for (int i = 0; i < pattern.length(); i++) {
        char key = pattern.charAt(i);
        if (map.containsKey(key)) {
            if (!map.get(key).equals(array[i])) {
                return false;
            }
        } else {
            // 判断 value 中是否存在
            if (set.contains(array[i])) {
                return false;
            }
            map.put(key, array[i]);
            set.add(array[i]);
        }
    }
    return true;
}

}

class Solution {
    public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
        return false;
    Map index = new HashMap();
    for (Integer i = 0; i < words.length; ++i)
        if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
            return false;
    return true;
    }
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        return isIsomorphicHelper(s).equals(isIsomorphicHelper(t));
    }

    private String isIsomorphicHelper(String s) {
        int[] map = new int[128];
        int n = s.length();
        StringBuilder sb = new StringBuilder();
        int count = 1;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            //当前字母第一次出现,赋值
            if (map[c] == 0) {
                map[c] = count;
                count++;
            }
            sb.append(map[c]);
        }
        return sb.toString();
}

}

/*

我们可以利用一个 map 来处理映射。对于 s 到 t 的映射，我们同时遍历 s 和 t ，假设当前遇到的字母分别是 c1 和 c2 。

如果 map[c1] 不存在，那么就将 c1 映射到 c2 ，即 map[c1] = c2。

如果 map[c1] 存在，那么就判断 map[c1] 是否等于 c2，也就是验证之前的映射和当前的字母是否相同。


对于这里，我们需要验证 s - > t 和 t -> s 两个方向。如果验证一个方向，是不可以的。

举个例子，s = ab, t = cc，如果单看 s -> t ，那么 a -> c, b -> c 是没有问题的。

必须再验证 t -> s，此时，c -> a, c -> b，一个字母对应了多个字母，所以不是同构的。

代码的话，只需要调用两次上边的代码即可。

*/
public boolean isIsomorphic(String s, String t) {
    return isIsomorphicHelper(s, t) && isIsomorphicHelper(t, s);

}

private boolean isIsomorphicHelper(String s, String t) {
    int n = s.length();
    HashMap<Character, Character> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        char c1 = s.charAt(i);
        char c2 = t.charAt(i);
        if (map.containsKey(c1)) {
            if (map.get(c1) != c2) {
                return false;
            }
        } else {
            map.put(c1, c2);
        }
    }
    return true;
}

/*
通过 int 数组记录 每个字符出现的次数
通过 HashMap 将出现次数相同的字符进行拼接
将 出现次数 排序, 倒序取出所有字符进行拼接
*/
class Solution {
    public String frequencySort(String s) {
        HashMap<Integer, String> map = new HashMap<>();

        int[] freq = new int[256];
        for (char c : s.toCharArray()) {
            freq[c]++;
        }

        for (int i = 0; i < freq.length; i++) {
            if (freq[i] != 0) {
                char ch = (char) i;

                String str = map.get(freq[i]);
                // 字符出现次数相同, 进行拼接
                if (str != null) {
                    String strNew = str.concat(build(ch, freq[i]));
                    map.put(freq[i], strNew);
                }else {
                    map.put(freq[i], build(ch, freq[i]));
                }
            }
        }

        Integer[] keys = map.keySet().toArray(new Integer[]{});
        Arrays.sort(keys);
        StringBuilder sbl = new StringBuilder();
        for (int i = keys.length - 1; i >= 0; i--) {
            sbl.append(map.get(keys[i]));
        }

        return sbl.toString();
    }

    private String build(char ch, int times) {
        String string = Character.toString(ch);
        StringBuilder res = new StringBuilder(string);
        int t = 1;
        while (t < times) {
            res.append(string);
            t++;
        }

        return res.toString();
    }
}

/*
用哈希表存储每个字符的出现次数，再通过一个大顶堆（根据出现次数排序），不断取出堆顶元素，使用StringBuilder不断append即可。
*/
class Solution {
    public String frequencySort(String s) {
        int[] letters = new int[128];
        for (char c : s.toCharArray()) {
            letters[c]++;
        }
        PriorityQueue<Character> heap = new PriorityQueue<>(128, (a, b) -> Integer.compare(letters[b], letters[a]));
        StringBuilder res = new StringBuilder();

        for (int i = 0; i < letters.length; ++i) {
            if (letters[i] != 0) heap.offer((char)i);
        }

        while (!heap.isEmpty()) {
            char c = heap.poll();
            while (letters[c]-- > 0)
                res.append(c);
        }
        return res.toString();
    }
}

    int[] array = new int[10];
	String str = "hello dave";
	List<String> list = new ArrayList<String>();
		
	System.out.println("数组的length属性：" + array.length);
	System.out.println("字符串的length()方法：" + str.length());
	System.out.println("集合的size()方法：" + list.size());