890. find and replace mode / Sword finger offer II 080 Combination with k elements

890. Find and replace patterns 【 Medium question 】【 A daily topic 】

Ideas ：【 Hash table emulation 】

See code Notes

Code ：

class Solution {
    
    public List<String> findAndReplacePattern(String[] words, String pattern) {
    
        List<String> ans = new ArrayList<>();
        // Find out pattern Templates for patterns mode
        String mode = make(pattern);
        for (String word : words) {
    
            // Find out the pattern of each word , Determine whether it is consistent with mode equal , If it is equal, it will word Add to ans In the list 
            if (mode.equals(make(word))){
    
                ans.add(word);
            }
        }
        return ans;
    }

    /** *  Use the hash table to simulate the incoming words word The pattern of  * @param word  Pass in the word  * @return  Returns the pattern of the incoming word  */
    public String make(String word){
    
        StringBuilder sb = new StringBuilder();
        // Record the letters that appear in the current word , And its corresponding mode letters 
        Map<Character,Character> map = new HashMap<>();
        char ch = 'A';
        char[] chars = word.toCharArray();
        // First traversal , Find the letters in the word , And its corresponding mode letters 
        for (char c : chars) {
    
            if (!map.containsKey(c)){
    
                map.put(c,ch++);
            }
        }
        // Second traversal , according to map The letters recorded in and their pattern letters , Simulate the pattern corresponding to the current word 
        for (char c : chars) {
    
            sb.append(map.get(c));
        }
        return sb.toString();
    }
}

---

The finger of the sword Offer II 080. contain k A combination of elements 【 Medium question 】

Ideas ：【 Binary analog 】

Use binary numbers to simulate from 1 To n this n Number , Count the current binary number 1 The number of , If there is k individual 1, It means that we have found a k A combination of elements , Number the binary number from right to left 1,2,...n, Take out 1 The corresponding number , Add it to list Collection , The final will be list Add collection into ans In the answer list .

Code ：

class Solution {
    
    public List<List<Integer>> combine(int n, int k) {
    
        List<List<Integer>> ans = new ArrayList<>();
        int mask = 1 << n;
        for (int i = 0; i < mask; i++) {
    
            if (Integer.bitCount(i) == k){
    
                List<Integer> list = new ArrayList<>();
                int n1 = i,num = 1;
                while (n1 != 0){
    
                    if ((n1 & 1) == 1){
    
                        list.add(num);
                    }
                    num++;
                    n1 >>= 1;
                }
                ans.add(new ArrayList<>(list));
            }
        }
        return ans;
    }
}