发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/minimum-window-substring/

　　给你一个字符串S和字符串T，在S中找到最小的窗口包含所有T中的字符，并输出这个窗口

题目分析

　　利用HashMap维护一个窗口，具体细节可以看下代码注释。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }
        int lenS = s.length();
        int lenT = t.length();
        Map<Character, Integer> hash = new HashMap<Character, Integer>(); // hash统计t中的字符
        
        for (int i = 0; i < lenT; i++) {
            char c = t.charAt(i);
            if (hash.containsKey(c)) {
                hash.put(c, 1 + hash.get(c));
            } else {
                hash.put(c, 1);
            }
        }
        Map<Character, Integer> window = new HashMap<Character, Integer>();
        int left = -1; // 窗口左边界
        int right = 0; // 窗口右边界
        int wCount = 0; //窗口中包含T中字符的个数
        int minLeft = -1; //最小窗口左边界
        int minRight = -1; // 最小窗口右边界
        int minW = Integer.MAX_VALUE; //最小窗口大小
        // 先确定left的第一个位置，也就是s中第一个包含t中的字符
        for (int i = 0; i < lenS; i++) {
            if (hash.containsKey(s.charAt(i))) {
                left = i;
                break;
            }
        }
        if (left == -1) {
            return "";
        }
        while (right < lenS) {
            char cur = s.charAt(right);
            if (!hash.containsKey(cur)) {
                right++;
                continue;
            }
            if (window.containsKey(cur)) {
                window.put(cur, 1 + window.get(cur));
            } else {
                window.put(cur, 1);
            }
            if (window.get(cur) <= hash.get(cur)) {
                wCount++;
            }
            if (wCount == lenT) { // 发现了一个可行的
                if (right - left + 1 < minW) {
                    minLeft = left;
                    minRight = right;
                    minW = right - left + 1;
                }
                // update left
                while (left < right) { // 窗口左边界也要右移
                    char l = s.charAt(left);
                    if (hash.containsKey(l)) {
                        if (window.get(l) <= hash.get(l)) {
                            wCount--;
                        }
                        window.put(l, window.get(l) - 1);
                    }
                    left++;
                    if (wCount < lenT) {
                        while (left < right && !hash.containsKey(s.charAt(left))) {
                            left++;
                        }
                        break;
                    } else { // 窗口在变小，因此也要更新答案。
                        if (right - left< minW) {
                            minLeft = left;
                            minRight = right;
                            minW = right - left + 1;
                        }
                    }
                }
            }
            right++;
        }
        if (minLeft != -1 && minRight != -1) {
            return s.substring(minLeft, minRight + 1);
        }
        return "";
    }
}

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/substring-with-concatenation-of-all-words/

　　给你一个字符串s和字符串数组words，输出字符串数组words中的字符串的任意组合形成的字符串在s中的index的list。

题目分析

　　最开始用暴力方法做，发现超时，最后参考了这篇文章的做法，利用了滑动窗口的做法进行优化，是用HashMap维护了一个words[0].length的窗口。

阅读全文 »

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/median-of-two-sorted-arrays/

　　求两个有序数组的中位数，时间复杂度要求是log(m+n)

题目分析

　　单个数组中位数的问题的讨论见我之前一篇博客

　　思路参考了这里：https://discuss.leetcode.com/topic/28602/concise-java-solution-based-on-binary-search 先把问题转化成两个有序数组的第k小的元素。nums1的长度是l1，nums2的长度是l2，如果要找第k小的元素，可以先这样考虑，分别取nums1和nums2的第k / 2个元素，不妨设为a和b，显而易见，两个数组中的第k小的元素不可能同时小于a和b，而且如果a < b的话，那么a以及nums1中a之前的元素都可以舍弃掉了，这样问题由k降了一半，最后复杂度是o(log(m + n))，当然边界和特殊情况是要做处理的。

阅读全文 »