LeetCode 290. Word Pattern [Easy]

发表于 2019-03-08 更新于 2024-08-05 分类于 LeetCode ， Easy

题目来源：https://leetcode.com/problems/word-pattern

题目难度：Easy

解答1[Java]：

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;
    }
}

思路

本解法是借助了 Java 的 HashMap 的特性。HashMap 的 put() 操作，如果 key 已经存在，那么就覆盖掉 key 原来的 value，并把原来的 value 当作返回值。

所以如果两个字符串模式相同，只要按顺序执行 put()，两个字符串执行中的返回值应该相同。

解答2[Java]：

class Solution {
    public boolean wordPattern(String pattern, String str) {
        int n = pattern.length();
        String[] strArr = str.split(" ");
        if (strArr.length != n)
            return false;
        String[] dict = new String[26];
        for (int i = 0; i < n; i++) {
            char c = pattern.charAt(i);
            if (dict[c - 'a'] == null)
                dict[c - 'a'] = strArr[i];
            else if (!dict[c - 'a'].equals(strArr[i]))
                return false;
        }

        // if each character in pattern is different
        // then each string in str should be different as well
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                if (i != j && dict[i] != null && dict[j] != null && dict[i].equals(dict[j]))
                    return false;
            }
        }
        return true;
    }

}

思路

使用字符串数组来进行判断。

第一遍是确定，如果 pattern 中有相同字母，那么 str 对应位置的字符串是否相同。

第二遍是确定，如果 pattern 中每个字母都不相同，那么 str 每个位置的字符也不能相同，如果相同，就不符合题意。

LeetCode 202. Happy Number [Easy]

发表于 2019-03-08 更新于 2024-08-05 分类于 LeetCode ， Easy

题目来源：https://leetcode.com/problems/happy-number

题目难度：Easy

解答1[Java]：

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> exist = new HashSet<>();
        while (n > 1) {
            if (exist.contains(n)) {
                return false;
            }
            exist.add(n);
            n = Square(n);
        }
        return n == 1;
    }

    private int Square(int n) {
        int res = 0;
        while (n > 0) {
            res += (n % 10) * (n % 10);
            n /= 10;
        }
        return res;
    }
}

思路

使用一个 Set，如果 Set 已经包含了当前元素，说明发生循环了。就返回 false。

解答2[Java]：神奇的解法

class Solution {
    public boolean isHappy(int n) {
        int d;
        while (n > 9) {
            d = n;
            n = 0;
            while (d > 0) {
                n += Math.pow(d % 10, 2);
                d = d / 10;
            }
        }
        return n == 1 || n == 7;
    }
}

思路

这个是 1ms 的 sample submission。

最后使用了一个 1 和 7 来进行判断是因为如果是 Happy Number 就一定会经过 7 吗？不知道这背后的数学规律。

LeetCode 242. Valid Anagram [Easy]

发表于 2019-03-08 更新于 2024-08-05 分类于 LeetCode ， Easy

题目来源：https://leetcode.com/problems/valid-anagram

题目难度：Easy

解答1[Java]：

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        
        int[] arr = new int[128];
        for(char c : s.toCharArray()){
            arr[c]++;
        }
        
        for(char c: t.toCharArray()){
            arr[c]--;
            if(arr[c]<0) return false;
        }
        return true;
    }
}

思路

这个解法只适合于 ASCII 字符集的字符串处理。不适合处理 Unicode 字符集的字符串。题目中额外提示了可以考虑算法是否适用于 Unicode 字符集。但是 LeetCode 的测试用例只有 ASCII 字符集的字符串，所以这个算法也可以通过。

解答2[Java] ：

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

思路

先排序，再对比。这个方式也适用于 Unicode 字符集。

参考资料

java – 在String中遍历所有字符的最快方法

LeetCode 350. Intersection of Two Arrays II [Easy]

发表于 2019-03-08 更新于 2024-08-05 分类于 LeetCode ， Easy

题目来源：https://leetcode.com/problems/intersection-of-two-arrays-ii

题目难度：Easy

题目

Given two arrays, write a function to compute their intersection.

Example 1:

1 2	Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]

Example 2:

1 2	Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1‘s size is small compared to nums2‘s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

解答1[Java]

思路

借助一个 Map，先统计数组1中每一个数组的个数，然后再遍历数组2，如果 Map 中存在此元素，则加入到结果数组，并且把 Map 中统计的数量减去 1。

实现

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> result = new ArrayList<>();
        for (int value : nums1) {
            if (map.containsKey(value)) {
                map.put(value, map.get(value) + 1);
            } else {
                map.put(value, 1);
            }
        }

        for (int value : nums2) {
            if (map.containsKey(value) && map.get(value) > 0) {
                result.add(value);
                map.put(value, map.get(value) - 1);
            }
        }

        int[] resultArray = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            resultArray[i] = result.get(i);
        }

        return resultArray;
    }
}

复杂度分析

HashMap 的 get() 时间复杂度为 $O(1)$。

解答2[Java]

思路

先对两个数组进行排序，然后两个数组分别设一个指针，判断当前指针指向的元素是否相等，如果相等就把指针当前指向的元素加入结果数组。如果不相等，哪个指向的元素更小，哪个指针向右移动，另外一个指针保持位置不变。

实现

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> intersection = new ArrayList<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                intersection.add(nums2[j]);
                i++;
                j++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                // nums[i] < nums[j]
                i++;
            }
        }


        int[] res = new int[intersection.size()];
        for (int k = 0; k < intersection.size(); k++) {
            res[k] = intersection.get(k);
        }
        
        return res;
    }
}

LeetCode 349. Intersection of Two Arrays [Easy]

发表于 2019-03-06 更新于 2024-08-05 分类于 LeetCode ， Easy

题目来源：https://leetcode.com/problems/intersection-of-two-arrays/

题目难度：Easy

解答1[Java]

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> set1 = new HashSet();
        HashSet<Integer> set2 = new HashSet();
        HashSet resultSet = new HashSet();
        int[] result = new int[nums1.length];
        int resultIndex = 0;

        for(int num: nums1){
            set1.add(num);
        }

        for(int num:nums2){
            set2.add(num);
        }

        for (Integer num :set2){
            if(set1.contains(num)){
                result[resultIndex++] = num;
            }
        }

        return Arrays.copyOf(result, resultIndex);

    }
}

复杂度分析

没错，hashSet的contains方法是调用map.containsKey(O)方法的，containsKey(o)是根据hash函数去做散列的，所以与元素的多少无关，无论是多少元素containsKey(o)的时间复杂度基本上O(1)。

HashSet细节 - 小菜园博客

解答2[Java]：

import java.util.Arrays;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums1) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        boolean[] exist = new boolean[max - min + 1];
        for (int num : nums1) exist[num - min] = true;
        int[] result = new int[nums2.length];
        int index = 0;
        for (int num : nums2) {
            if (num <= max && num >= min && exist[num - min]) {
                result[index++] = num;
                exist[num - min] = false; //remove from exist array to avoid duplicate
            }
        }
        return Arrays.copyOf(result, index);
    }
}

思路

很巧妙的一个算法，先把一个数组的最大值和最小值圈起来。

复杂度分析

空间复杂度：

result 数组和 exist 数组为 $O(m)$ 或者 $O(h)$。m 和 h 是两个数组的长度。

时间复杂度：$O(n)$。

LeetCode 76. Minimum Window Substring [Hard]

发表于 2019-03-06 更新于 2024-08-05 分类于 LeetCode ， Hard

题目来源：https://leetcode.com/problems/minimum-window-substring/

题目难度：Hard

解答1[Java]：

class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[128];
        for (char c : t.toCharArray()) map[c]++;
        int counter = t.length(), left = 0, right = 0, head = 0, d = Integer.MAX_VALUE;
        while (right < s.length()) {
            if (map[s.charAt(right++)]-- > 0) counter--;
            while (counter == 0) {
                if (right - left < d) d = right - (head = left);
                if (map[s.charAt(left++)]++ == 0) counter++;
            }
        }
        return d == Integer.MAX_VALUE ? "" : s.substring(head, head + d);
    }
}

思路

注意 if (map[s.charAt(right++)]-- > 0) 这句，不论 right 指向位置的字符是哪个，在判断之后都会被减去 1。因为在前边的语句中，已经预先把 t 中的字符在 map 中加 1 了，所以只有不在 t 中的字符才会被减成负数。

同理，if (map[s.charAt(left++)]++ == 0) counter++; 如果判断为真，说明 left 指针指向的字符是 t 中的一个字符，且减去这个字符之后，这个字符的数量就不够了，因此需要把 counter 加1。如果 left 指向的不是 t 中的字符，那么这个字符在 map 中的值一定是负数，因为之前 right 遍历的时候被减过。

假设 t="ABC"，当 counter 为零的时候，map['A']、map['B'] 和 map['C'] 其中至少有两个的值是小于等于零的。可以小于零，但至少要等于零。不然 counter 是不会为零的。

当 map['A'] 被减为零之后，如果再遇到字符 A，就不会再减 counter 了。因为 map['A'] 已经被减到零，说明前面已经匹配到的字符 A 的数量已经足够了。

LeetCode 438. Find All Anagrams in a String [Medium]

发表于 2019-03-06 更新于 2024-08-05 分类于 LeetCode ， Medium

题目来源：https://leetcode.com/problems/find-all-anagrams-in-a-string/

题目难度：Medium

解法1[Java]：

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || p.length() > s.length()) {
            return res;
        }

        int[] map = new int[128];
        for (char ch : p.toCharArray()) {
            map[ch]++;
        }

        int left = 0, right = 0;
        int len_s = s.length();
        int len_p = p.length();
        while (right < len_s) {
            char ch_r = s.charAt(right);
            map[ch_r]--;
            while (map[ch_r] < 0) {
                char ch_l = s.charAt(left++);         
                map[ch_l]++;
            }
            if (right - left + 1 == len_p) {
                res.add(left);
            }
            right++;
        }
        return res;
    }
}

思路

先设计了一个 map，把 p 中所有的字符在 map 中的值先加1。

然后设计两个指针，右指针指向哪个字符，就把这个字符在 map 中对应的值减去 1。如果指向的字符不在 p 中，会导致那个字符对应的值小于0，根据这个条件，把左指针一步一步移到和右指针相同的位置，并且在移动的过程中把 map 恢复成最初的数值。这样就相当于从一个新的位置重新开始。

LeetCode 3. Longest Substring Without Repeating Characters 无重复字符的最长子串[Medium]

发表于 2019-03-05 更新于 2024-08-05 分类于 LeetCode ， Medium

题目来源：

中文版：3. 无重复字符的最长子串 - 力扣（LeetCode）

英文版：https://leetcode.com/problems/longest-substring-without-repeating-characters/

题目难度：Medium

答题思路

最笨的办法就是暴力算法
枚举出所有子串，然后一个一个判定，如果有重复的去掉，最后从中取出最长的子串。如果有重复的，就全部都输出。
如果题目保证只有一个，那最终答案就只有一个。


方案2
优化一下方案就是

可以边找边判断，从每一个索引出发，判断从当前索引开始，能够找到的最长的子串
一边找，一遍把已经出现过的字符保存起来，当遇到重复字符的时候，记录下来当前的子串及其长度。
然后切换到下一个索引再开始判断。

同时，如果遍历到一半的时候，如果判断剩下的最大子串长度都比当前已经找到的最长子串长度还要小，就可以提前结束遍历。


方案3

在方案2中，我们想到了每次遇到重复的字符的时候，就从下一个索引开始遍历，但是
这里其实还可以优化一下，我们从下一个索引开始遍历的时候，不需要完全再从头开始遍历，
因为之前可能已经遍历过一部分了，只需要在遇到重复的元素的时候，把最开头的元素舍弃掉，就相当于是
从下一个索引位置一直遍历到当前位置了。这种思想就被称为滑动窗口。

当下一个元素和之前遇到的某个元素相同的时候，那么当前的元素和之前已经遇到的元素只能保留一个。
需要把索引移动到上次遇到的相同的元素的下一个元素，然后继续。

假如遇到两个连续的字符，那么相当于要从头开始计算了。

方案4
由于只要求最长子串，每次遍历到一个位置的时候，肯定有一个子串开始的索引
我们只要记录下来子串最开始位置的索引，然后从当前位置即可算出子串的长度

解答1[Java]：滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) {
            return 0;
        }

        int[] frequencies = new int[256];
        int left = 0;
        int right = -1;
        int maxSubstringLength = 0;

        while (left < s.length() && (right + 1) < s.length()) {
            char c = s.charAt(right + 1);
            if (frequencies[c] == 0) {
                ++right;
                frequencies[c] = 1;
            } else {
                char c1 = s.charAt(left);
                frequencies[c1]--;
                ++left;
            }
            maxSubstringLength = Math.max(maxSubstringLength, right - left + 1);
        }

        return maxSubstringLength;
    }
}

根据出现频率来的，只要右指针当前指向的字符串出现的频率不是 0 次，左指针就继续向右移动，每次移动的时候，把左指针当前指向的字符串的频率给相应的减掉。一直到发现右指针指向的字符串出现的频率是 0 次的时候，此时右指针就可以继续向右移动了。

追问

Follow-up：如果允许重复一次字符呢——微软-苏州-Lead面（2020.11.24）【来自 CodeTop 题目评论】

3. 无重复字符的最长子串 - 力扣（LeetCode）【仅供参考】

允许重复k个字符，字节-国际化电商-后端2022-4-22

base:3 follow up :395 424 2024

20230913 滴滴要求，滑动窗口检测不能用hashmap，真是弱智要求。

Peng：估计面试官是想让面试者使用数组，而不使用 HashMap。

20220213：

JD 后端二面 +打印最长子串

字节变式题：给定一个字符串s，以及一个数字k，求s中最多不超过k个不同字符的最长子串长度【2022-11-27】

解答1[Java]：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int right = -1;
        int sum = 0;
        int result = nums.length + 1;

        while (left < nums.length) {
            if (right + 1 < nums.length && sum < s) {
                sum += nums[++right];
            } else {
                sum -= nums[left++];
            }

            if (sum >= s) {
                result = min(result, right - left + 1);
            }
        }

        if (result == nums.length + 1) {
            result = 0;
        }

        return result;
    }

    private int min(int a, int b) {
        return a < b ? a : b;
    }
}

思路

left 和 right 之间形成一个动态窗口，每次根据窗口内的元素的和与给定的数字作比较，确定是收缩窗口还是向右扩大窗口。

LeetCode 167. Two Sum II - Input array is sorted [Easy]

发表于 2019-03-05 更新于 2024-08-05 分类于 LeetCode ， Easy

题目来源：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

题目难度：Easy

解答1[Java]：

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length - 1;
        int[] result = new int[2];
        for (; i < j;) {
            if (numbers[i] + numbers[j] == target) {
                result[0] = i + 1;
                result[1] = j + 1;
                return result;
            } else if (numbers[i] + numbers[j] < target) {
                i++;
            } else {
                j--;
            }
        }

        return result;
    }
}

思路

一头一尾两个指针不断向中间靠拢。

解答2

思路

利用传入的数组已经有序的特点。

从头开始选一个值 i，然后在剩下的长度中进行二分搜索 target-i 这个值。

解答1[Java]：

思路

解答2[Java]：

思路

解答1[Java]：

思路

解答2[Java]：神奇的解法

思路

解答1[Java]：

思路

解答2[Java] ：

思路

参考资料

题目

解答1[Java]

思路

实现

复杂度分析

解答2[Java]

思路

实现

解答1[Java]

复杂度分析

解答2[Java]：

思路

复杂度分析

解答1[Java]：

思路

解法1[Java]：

思路

答题思路

解答1[Java]：滑动窗口

追问

相关题目

LeetCode 395

解答1[Java]：

思路

解答1[Java]：

思路

解答2

思路