6.9号刷题

第一题 159. Longest Substring with At Most Two Distinct Characters

题目描述

在一个String中找出一个Substring,使得Substring 最多包含2个不同的Char。

算法

利用HashMap存储两个最新的位置，当有第三个加入HashMap的时候，说明已经多于两个，进行操作。注意不要使用for循环，用for循环后很多testcase会出现很难解决的逻辑问题。

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s.length() <= 2) return s.length();
        // Key : Character, value : indexes
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;

        int low = 0, high = 0;
        while(high < s.length()) {
            if (map.size() <= 2) {
                map.put(s.charAt(high), high);
                high++;
            }
            if (map.size() > 2) {
                int mostleft = s.length();
                for (int value : map.values()) mostleft = Math.min(mostleft, value);

                map.remove(s.charAt(mostleft));
                low = mostleft + 1;

            }
            max = Math.max(max, high - low);
        }

        return max;      
    }
}

第二题 340. Longest Substring with At Most K Distinct Characters

题目描述

在一个String中找出一个Substring,使得Substring 最多包含k个不同的Char。

算法

算法与之前相同

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s.length() <= k) return s.length();
        
        Map<Character, Integer> map = new HashMap<>();
        int max = 0;
        int low = 0, high = 0;
        while (high < s.length()) {
            if (map.size() <= k) {
                map.put(s.charAt(high), high);
                high++;
            }
            if (map.size() > k) {
                int mostleft = s.length();
                for (int value : map.values()) mostleft = Math.min(mostleft, value);
                
                map.remove(s.charAt(mostleft));
                low = mostleft + 1;
            }
            max = Math.max(max, high - low);
        }
        return max;        
    }
}

第三题 249. Group Shifted Strings

题目描述

给定很多的String。对每一个String，其中的每一个char可以按照从a -> z -> a的方式循环移动。查看String中能否有相同的String可以通过其他String移动而来，将他们归并为机组。

算法

这道题目我们可以转化成String中每个char的差值的问题。对于acd与bde，或者xza。我们发现，只要他们之间char的差值是一样的，那么他们必然是可以通过移动得到的，这样，我们就只需要将他们的差值作为map存储下来即可

public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();

        for (String s : strings) {
            StringBuilder key = new StringBuilder();
            
            for (int i = 1; i < s.length(); i++) {
                int temp = s.charAt(i) - s.charAt(i-1);
                temp = (temp + 26) % 26;
                char c = (char) temp;
                key.append(c);
            }
            List<String> list;
            if (map.containsKey(key.toString())) {
                list = map.get(key.toString());
            } else {
                list = new ArrayList<>();
            }
            
            list.add(s);
            map.put(key.toString(), list);
            
        }
        
        
        for (List<String> list : map.values()) result.add(list);
        return result;        
    }
}

第四题 246. Strobogrammatic Number

算法

3种算法，可以利用HashSet, HashMap, 或者直接进行String的比对

public class isStrobogrammatic246 {
    public boolean isStrobogrammatic(String num) {
        Set<Character> set = new HashSet<>();
        set.add('1'); set.add('6'); set.add('8'); set.add('9'); set.add('0');

        if (num.length() == 1){
            if (num.equals("1") || num.equals("8") || num.equals("0")) return true;
            else return false;
        }

        for (int i = 0; i < num.length(); i++) {
            char c = num.charAt(i);
            if (!set.contains(c))
                return false;
            else {
                if (c == '6' && i < num.length() / 2) {
                    if (num.charAt(num.length() - i - 1) != '9') return false;
                }
                if (c == '9' && i < num.length() / 2) {
                    if (num.charAt(num.length() - i - 1) != '6') return false;
                }
                if (c == '8' || c == '1' || c == '0') {
                    if (num.charAt(num.length() - i - 1) != c) return false;
                }
            }
        }
        return true;
    }

    public boolean isStrobogrammatic2(String num) {
        Map<Character, Character> map = new HashMap<Character, Character>();
        map.put('6', '9');
        map.put('9', '6');
        map.put('0', '0');
        map.put('1', '1');
        map.put('8', '8');

        int l = 0, r = num.length() - 1;
        while (l <= r) {
            if (!map.containsKey(num.charAt(l))) return false;
            if (map.get(num.charAt(l)) != num.charAt(r))
                return false;
            l++;
            r--;
        }

        return true;
    }

    public boolean isStrobogrammatic3(String num) {
        for (int i=0, j=num.length()-1; i <= j; i++, j--)
            if (!"00 11 88 696".contains(num.charAt(i) + "" + num.charAt(j)))
                return false;
        return true;
    }
}

第五题 594. Longest Harmonious Subsequence

题目描述

给定整数数组nums，求其中最大值与最小值相差恰好为1的子序列的长度的最大值。

注意： 数组长度不超过20000

算法

两种方法，一种用TreeMap(自带key排序)，一种用HashMap

public class findLHS594 {
    public int findLHS(int[] nums) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int previous = Integer.MAX_VALUE, max = 0;
        for (int key : map.keySet()) {
            if (previous == Integer.MAX_VALUE) previous = key;
            else {
                if (key - previous == 1) {
                    max = Math.max(max, map.get(key) + map.get(previous));
                }
                previous = key;
            }
        }
        return max;
    }

    public int findLHS2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);

        int max = 0;
        for (int key : map.keySet()) {
            if (map.containsKey(key + 1)) {
                max = Math.max(max,  map.get(key) + map.get(key + 1));
            }
        }
        return max;
    }
}

第六题 205. Isomorphic Strings

题目描述

给定两个字符串s和t，判断它们是否是同构的。

如果字符串s可以通过字符替换的方式得到字符串t，则称s和t是同构的。

字符的每一次出现都必须被其对应字符所替换，同时还需要保证原始顺序不发生改变。两个字符不能映射到同一个字符，但是字符可以映射到其本身。

测试样例如题目描述。

可以假设s和t等长。

算法

利用HashMap

利用HashMap查看每次出现的值是否已经有正确的对应或者是否为第一次出现。

public class isIsomorphic205 {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Character> map = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char cA = s.charAt(i), cB = t.charAt(i);
            if (map.containsKey(cA)) {
                if (map.get(cA) != cB) return false;
            } else {
                if (map.containsValue(cB)) return false;
                map.put(cA, cB);
            }
        }
        return true;
    }
}

利用数组存储

由于ASC码中总共的character有256个，所以对于情况发生次数有限的情况，可以用数组进行存储。这样的话程序的效率会快得多

public class isIsomorphic205 {
    public boolean isIsomorphic2(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] A = new int[256];
        int[] B = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char cA = s.charAt(i), cB = t.charAt(i);
            if (A[cA] != B[cB]) return false;
            A[cA] = B[cB] = i + 1;
        }
        return true;
    }
}