6.11号刷题

第一题 535. Encode and Decode TinyURL

题目描述

将一个较长的URL 编译为较短的TinyURL, 之后又可以解码回来原来的URL

算法

public class Codec {
    List<String> urls = new ArrayList<>();

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        urls.add(longUrl);
        return String.valueOf(urls.size() - 1);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        int index = Integer.valueOf(shortUrl);
        return index > urls.size() ? "" : urls.get(index);
    }
}

第二题 438. Find All Anagrams in a String

题目描述

给定一个字符串s与一个非空字符串p，寻找s中所有p的字谜变换的起始下标。

字符串只包含小写英文字母并且s和p的长度均不超过20100。

输出顺序无所谓。

算法

很重要的一道题目，可以帮助熟悉寻找Substring类型的题目

主要有两种算法，一种是利用HashMap，一种是使用char [256]。原理都是HashMap，处理的方式是使用一个窗口，窗口有Left和right，如果窗口中的情况满足要求了，则输出。如果并不满足，整个窗口移动，并对left边缘的值进行操作

HashMap

hashmap这个思路是找到一个满足要求的长序列，即在这个长序列中，肯定包含了目标String的所有Character但是我们需要对这些character的情况进行验证。

public class findAnagrams438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;
        Map<Character, Integer> map = new HashMap<>();
        for (char c : p.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);

        int leftPoint = 0, rightPoint = 0, count = map.size();
        while(rightPoint < s.length()) {
            char cur = s.charAt(rightPoint);
            if (map.containsKey(cur)) {
                map.put(cur, map.get(cur) - 1);
                if (map.get(cur) == 0) count--;
            }
            rightPoint++;

            while (count == 0) {
                char left = s.charAt(leftPoint);
                if (map.containsKey(left)) {
                    map.put(left, map.get(left) + 1);
                    if (map.get(left) > 0) count++;
                }

                if (rightPoint - leftPoint == p.length()) result.add(leftPoint);
                leftPoint++;
            }
        }
        return result;
    }
}

Array

同样的方法，但是这个的窗口大小是固定的，算法思路相似

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;
        int[] hash = new int[256];
        for (char c : p.toCharArray()) hash[c]++;

        int leftPoint = 0, righPoint = 0, count = p.length();
        while (righPoint < s.length()) {
            
            char c = s.charAt(righPoint);
            hash[c]--;
            if (hash[c] >= 0) count--;
            
            righPoint++;

            if (count == 0) result.add(leftPoint);

            if (righPoint - leftPoint == p.length()) {
                char charLeft = s.charAt(leftPoint);
                hash[charLeft]++;
                if (hash[charLeft] > 0) count++;
                leftPoint++;
            }
        }
        return result;        
    }
}

第三题 76. Minimum Window Substring

题目描述

在一个String中寻找一个Substring包含目标String的所有字符。如果存在多个Substring，找最小的那一个

算法

与之前的题目相似，两种方法，同样利用一个窗口。可以使用相同的模板，只是在细微的地方有所变化

HashMap

利用HashMap的模板是先找到所有包含在LeftPoint 和RightPoint的Substring的范围，然后再按照要求，修改count部分

public class minWindow76 {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        String result = new String();
        Integer minimum = Integer.MAX_VALUE;
        Map<Character, Integer> map = new HashMap<>();
        for (char c : t.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        int leftPoint = 0, rightPoint = 0, count = map.size();
        while (rightPoint < s.length()) {
            char cRight = s.charAt(rightPoint);
            if (map.containsKey(cRight)) {
                map.put(cRight, map.get(cRight) - 1);
                if (map.get(cRight) == 0) count--;
            }
            rightPoint++;
            while (count == 0) {
                if (rightPoint - leftPoint < minimum) {
                    minimum = rightPoint - leftPoint;
                    result = s.substring(leftPoint, rightPoint);
                }
                char cLeft = s.charAt(leftPoint);
                if (map.containsKey(cLeft)) {
                    map.put(cLeft, map.get(cLeft) + 1);
                    if (map.get(cLeft) > 0) count++;
                }
                leftPoint++;
            }
        }
        return result;
    }
}

Array

public class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        Integer minimum = Integer.MAX_VALUE;

        int[] hash = new int[256];
        for (char c : t.toCharArray()) hash[c]++;
        int leftPoint = 0, rightPoint = 0, count = t.length();
        int resRight = 0, resLeft = 0;

        while (rightPoint < s.length()) {
            char cRight = s.charAt(rightPoint);
            hash[cRight]--;
            if (hash[cRight] >= 0) count--;
            rightPoint++;
            while (count == 0) {
                if (rightPoint - leftPoint < minimum) {
                    minimum = rightPoint - leftPoint;
                    resRight = rightPoint; resLeft = leftPoint;
                }

                char cLeft = s.charAt(leftPoint);
                hash[cLeft]++;
                if (hash[cLeft] > 0) count++;
                leftPoint++;
            }
        }
        return minimum == Integer.MAX_VALUE ? "" : s.substring(resLeft, resRight);        
    }
}

第四题 3. Longest Substring Without Repeating Characters

题目描述

给定一个字符串，从中找出不含重复字符的最长子串的长度。例如，”abcabcbb”的不含重复字母的最长子串为”abc”，其长度是3。”bbbbb”的最长子串是”b”，长度为1。

算法

仍然采用滑动窗口的方法，分别用HashMap和Array解决这个问题

HashMap

public class lengthOfLongestSubstring3 {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int leftPoint = 0, rightPoint = 0, max = 0;

        while (rightPoint < s.length()) {
            char cRight = s.charAt(rightPoint);
            if (map.containsKey(cRight)) {
                map.put(cRight, map.get(cRight) + 1);
                int count = map.get(cRight);
                while(count != 1) {
                    max = Math.max(max, rightPoint - leftPoint);
                    char cLeft = s.charAt(leftPoint);
                    map.put(cLeft, map.get(cLeft) - 1);
                    count = map.get(cRight);
                    leftPoint++;
                }
                rightPoint++;
            } else {
                map.put(cRight, 1);
                rightPoint++;
            }
            max = Math.max(max, rightPoint - leftPoint);
        }
        return max;
    }
}

Array

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] hash = new int[256];
        int leftPoint = 0, rightPoint = 0, max = 0;
        while (rightPoint < s.length()) {
            char cRight = s.charAt(rightPoint);
            hash[cRight]++;
            rightPoint++;
            while (hash[cRight] != 1) {
                char cLefg = s.charAt(leftPoint);
                hash[cLefg]--;
                leftPoint++;
            }
            max = Math.max(max, rightPoint - leftPoint);
        }
        return max;        
    }
}

第五题 30. Substring with Concatenation of All Words

题目描述

主字符串S，模式字符串list：L（L中的元素等长，有可能重复），寻找L以任意顺序拼接后得到的字符串在S中的索引。

算法

速度快的复杂的

还没搞懂，鸡儿

利用两个HashMap

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int n = words.length, len = words[0].length();

        Map<String, Integer> map = new HashMap<>();
        for (String str : words) map.put(str, map.getOrDefault(str, 0) + 1);

        for (int i = 0; i <= s.length() - words.length * len; i++) {
            Map<String, Integer> temp = new HashMap<>(map);
            for (int j = 0; j < words.length; j++) {
                String str = s.substring(i + j * len, i + j * len + len);
                if (temp.containsKey(str)) {
                    int count = temp.get(str);
                    if (count == 1) temp.remove(str);
                    else temp.put(str, count - 1);
                }
                else break;
            }
            if (temp.isEmpty()) res.add(i);
        }
        return res;      
    }
}

第六题 380. Insert Delete GetRandom O(1)

题目描述

设计一个数据结构支持在O(1)时间内完成如下操作：

insert(val): 如果集合中不包含val，则插入val

remove(val): 如果集合中包含val，则移除val

getRandom: 从现有集合中随机返回一个元素，每个元素被返回的概率应该相等

算法

哈希表 + 数组 （HashMap + Array）

利用数组存储元素，利用哈希表维护元素在数组中的下标

由于哈希表的新增/删除操作是O(1)，而数组的随机访问操作开销也是O(1)，因此满足题设要求

记数组为dataList，哈希表为dataMap

insert(val): 将val添至dataList末尾，并在dataMap中保存val的下标idx

remove(val): 记val的下标为idx，dataList末尾元素为tail，弹出tail并将其替换至idx处，在dataMap中更新tail的下标为idx，最后从dataMap中移除val

getRandom: 从dataList中随机选取元素返回

public class RandomizedSet380 {
    List<Integer> list;
    Map<Integer, Integer> map;
    Random rand;
    /** Initialize your data structure here. */
    public RandomizedSet380() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;

        int index = map.get(val);
        if (index != list.size() - 1) {
            int num = list.get(list.size() - 1);
            list.set(index, num);
            map.put(num, index);
        }
        map.remove(val);
        list.remove(list.size() - 1);
        return true;
     }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}