CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

Posted on

LeetCode 232.用栈实现队列

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
class MyQueue {

    // use two stacks to simulate a queue
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }
    
    // stackIn's topside is the end of the queue
    public void push(int x) {
        stackIn.push(x);
    }
    
    // stackOut's topside is the head of the queue
    public int pop() {

        // if there is no element in the stackOut
        // fetch them from the stackIn 
        if (stackOut.empty()) {
            while (!stackIn.empty()) {
                stackOut.push(stackIn.pop());
            }
        } 
        return stackOut.pop();
    }
    
    // the easiest way to get the head element is pop it 
    // then push it back to the head of the queue
    public int peek() {
        int ans = this.pop();
        stackOut.push(ans);
        return ans;
    }
    
    public boolean empty() {
        return stackIn.empty() && stackOut.empty();
    }
}

学习了如何使用栈这种数据结构去模仿队列，想法很巧妙。

LeetCode 225. 用队列实现栈

可以使用两个队列也可以使用一个队列，两个队列的话，一个用于存储，一个用于挪移，使用一个队列的话，需要弹出栈顶元素时，将前面的所有元素poll出然后加到最后一个元素后面即可。

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
class MyStack {

    Deque storage_queue = new LinkedList<Integer>();
    Deque subDeque = new LinkedList<Integer>();

    public MyStack() {
        
    }
    
    public void push(int x) {

        // let's cache the added element in our sub queue
        subDeque.offer(x);

        // then move all the currently stored element into our sub queue
        while ( !storage_queue.isEmpty() ) {
            subDeque.offer(storage_queue.pollFirst());
        }

        // now the sub queue has a correct sequence as a stack
        // let's swap the two references
        Deque temp = subDeque;
        subDeque = storage_queue;
        storage_queue = temp;
    }
    
    public int pop() {
        return (Integer)storage_queue.pollFirst();
    }
    
    public int top() {
        return (Integer)storage_queue.peekFirst();
    }
    
    public boolean empty() {
        return storage_queue.isEmpty();
    }
}

Posted on Edited on

今天的核心内容在于理解KMP算法，还在努力理解中ing～

LeetCode 28.找出字符串中第一个匹配项的下标

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
class Solution {
    public int strStr(String haystack, String needle) {

        int hayIndex = 0, needleIndex = 0;
        int ans = -1;
        char c1, c2;

        // at least we need to full scan the haystack string once
        while (hayIndex < haystack.length()) {
            // iff the first char is the same should we compare the left elements
            while (hayIndex < haystack.length() && (c1 = haystack.charAt(hayIndex)) != needle.charAt(0) ) {
                hayIndex++;
            }
            
            // if there is no same first char
            if(hayIndex == haystack.length()) {
                return -1;
            }else{
                // else let's compare the two str
               
                // first, let's record the hayIndex
                ans = hayIndex;

                while (needleIndex < needle.length() && hayIndex < haystack.length()) {
                    c1 = haystack.charAt(hayIndex);
                    c2 = needle.charAt(needleIndex);
                    if(c1 == c2) {
                        needleIndex++;
                        hayIndex++;
                    }else{
                        break;
                    }
                }

                // if needleIndex is less than needle.length(), it is not the same word
                if(needleIndex < needle.length()){
                    // let's reset hayIndex back to next char in hayStack
                    // and needleIndex to its first char
                    hayIndex = ans + 1;
                    ans = -1;
                    needleIndex = 0;
                }else{
                    return ans;
                }

            }
        }

        return ans;
    }
}

这是没有学习KMP算法前写的朴素解法。

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
class Solution {
    public int strStr(String haystack, String needle) {
        int i = 0, j = 0;
        int nh = haystack.length();
        int nn = needle.length();
        int[] next = getNext(needle);
        
        while ( i < nh) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                
                if ( j == nn){
                    return i - j;
                }
            }else{
                if (j > 0) {
                    j = next[j - 1];
                }else{
                    i++;
                }
            }
        }

        return -1;
    }

    public int[] getNext (String str){
        char[] pat = str.toCharArray();
        // i - > the first element in suffix
        int i = 1;
        // j-> the first element in the prefix substring
        int j = 0;

        int[] next = new int[pat.length];

        while ( i < pat.length) {

            if( pat[i] == pat[j] ) {
                next[i++] = ++j;
             }else {
                if( j == 0) {
                    next[i] = 0;
                    i++;
                }else {
                    j = next[j - 1];
                }
            }


        }

        return next;
    }
}

经过一番学习后，理解了KMP算法的大体思想，不过这里有一些细节之处可能再写时还要进一步的思考。

在KMP算法的学习中发现这个po主的视频讲解的最好，以上代码参考了https://www.bilibili.com/video/BV1iJ411a7Kb?p=5&vd_source=5d8279a9d134034c9a085489dde3d4ac的思路。

Posted on

今天的主题是字符串：

LeetCode 344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 
 a simple simulation of the swap behavior using dual pointer 
 pointing to the first and last element, then step by step swap 
 two pointed elements and swap them 
 until the two pointer pointing to the same element
*/
class Solution {
    public void reverseString(char[] s) {

        int left = 0;
        int right = s.length - 1;
        char temp;

        while (left < right) {
            //swap the pointed two elements 
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left++;
            right--;
        }
    }
}

LeetCode 541.反转字符串II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

1
2
输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104
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
class Solution {
    public String reverseStr(String s, int k) {
        int quotient, remiander;
        quotient = s.length() / (2 * k);
        remiander = s.length() % (2 * k);

        char[] str = s.toCharArray();

        // for (int i = 0; i < quotient; i++) {
        //     reverseFromTo(str, i * 2 * k, i * 2 * k + k - 1);
        // }

        // if ( remiander / k == 0){
        //     reverseFromTo(str, quotient * 2 * k, str.length - 1);
        // }else if (remiander / k >= 1) {
        //     reverseFromTo(str, quotient * 2 * k, quotient * 2 * k - 1 + k);
        // }

        for (int i = 0; i < str.length; i += 2 * k) {
            reverseFromTo(str, i, Math.min(i+k, str.length) - 1);
        }

        return new String(str);

    }

    private void reverseFromTo (char[] chars, int startIndex, int endIndex) {
        
        char temp;
        while (startIndex < endIndex) {
            //swap the pointed two elements 
            temp = chars[startIndex];
            chars[startIndex] = chars[endIndex];
            chars[endIndex] = temp;

            startIndex++;
            endIndex--;
        }
    }
}

这道题的核心思路很简单，其实就是不停的找到下一个需要反转的子串，反转之，然后重复，直到到达输入字符串的末尾，一开始我写了一个相对复杂的版本，试图通过商和余数去判断。后来看了题解发现其实可以直接通过一个for循环更改序号，并通过对i+k和length-1的最小值进行判断从而将边界case纳入一个循环，挺巧妙的，值得学习。

剑指offer 05.替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

1
2
输入：s = "We are happy."
输出："We%20are%20happy."

限制：

1
0 <= s 的长度 <= 10000
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
public class Solution {
    public String replaceSpace(String s) {
        int cnt = 0;
        char[] str = s.toCharArray();
      	
      	// count the numer of space first to decide the length of the new array
        for (int i = 0; i < str.length; i++) {
            char c = str[i];
            if (c == ' '){
                cnt ++;
            }
        }
      	
      	// actually, there is no need for this counting, we can directly claim 
      	// a new array, whose size is triple the previous one which is definitly
      	// enough for our use
        char[] ans = new char[str.length + 2 * cnt];
				
        for (int i = 0, j = 0; i < str.length; i++) {
            if (str[i] != ' '){
                ans[j++] = str[i];
            }else{
                ans[j++] = '%';
                ans[j++] = '2';
                ans[j++] = '0';
            }
        }

        return String.valueOf(ans);
    }
}

另一种方式是使用双指针从后向前遍历，虽然没有本质的区别，但是这里记录一下这种数组填充元素的双指针从后遍历填充方法：

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
//方式二：双指针法
public String replaceSpace(String s) {
    if(s == null || s.length() == 0){
        return s;
    }
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

LeetCode 151.反转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

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
class Solution {

    public String reverseWords(String s) {
        List<String> list = new ArrayList<>();

        int left = 0;

        // step 1: use space dividing the string s into words
        while (left < s.length()) {
            char c = s.charAt(left);

            if ( c == ' ') {
                left++;
            }else {
                int right = left;
                while(right < s.length() && s.charAt(right) != ' '){
                    right++;
                }
                list.add(s.substring(left, right));
                left = right;
            }
        }

        // setp 2: swap the words in the list
        int leftIndex = 0; int rightIndex = list.size() - 1;

        while ( leftIndex < rightIndex) {
            swap(list, leftIndex, rightIndex);
            leftIndex++;
            rightIndex--;
        }

        // step 3: add sapce as divider between the revered words
        StringBuffer sb = new StringBuffer();

        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
            if(i != list.size() - 1){
                sb.append(' ');
            }
        }

        // step4: return the reversed words string
        return sb.toString();
    }

    private void swap (List<String> list, int left, int right) {
        String temp = list.get(left);
        list.set(left,list.get(right));
        list.set(right,temp);
    }
}

如注释所示，把整体任务分解成如上的几步，整体并不复杂，有不同复杂度的各种解法，待后续补充。

剑指Offer58-II.左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例 1：

1
2
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

1
2
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

限制：

  • 1 <= k < s.length <= 10000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {

    // 0 1 2 3 4 5 6, size = 7
    public String reverseLeftWords(String s, int n) {
        char[] input = s.toCharArray();
        int size = input.length;

        char[] output = new char[size];

        for (int i = 0; i < size; i++) {
            output[(i + size - n) % size] = input[i];
        }
      
        return new String(output);
    }
}

计算一下可知，原来的i位置的元素要到 (i + size - n) % size的位置，知道了坐标关系后就可以很方便的进行计算。

除此之外，还可以先反转前n个元素，然后反转后size - n个元素，然后反转整个字符串即可。

Posted on

LeetCode 454.四数相加-ii

这道题的如果直接使用循环的话其时间复杂度是O(n^4)，所以考虑拆成两部分并使用hashmap cache住一部分的结果，可以把时间复杂度降低到O(n^2)

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
class Solution {
    // public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

    //     int ans = 0;
		// a simple way is use 4-level embedded looping, but would result in runtime exceed
    //     for (int i = 0; i < nums1.length; i++) {
    //         for (int j = 0; j < nums2.length; j++) {
    //             for (int k = 0; k < nums3.length; k++) {
    //                 for (int l = 0; l < nums4.length; l++) {
    //                     if(nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
    //                         ans ++;
    //                     }
    //                 }
    //             }
    //         }
    //     }

    //     return ans;
    // }


    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        int ans = 0;

        HashMap<Integer, Integer> sum12 = new HashMap<>();

        // divide 4 arrays into 2 partitions which decrease the complexity to n^2
        // cache the twoSum results, then full scan the other two arrays
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int twoSum = nums1[i] + nums2[j];
                if (sum12.containsKey (twoSum)) {
                    sum12.put(twoSum, sum12.get(twoSum) + 1);
                }else {
                    sum12.put(twoSum, 1);
                }
            }
        }


        for (int k = 0; k < nums3.length; k++) {
            for (int l = 0; l < nums4.length; l++) {
                int target = 0 - nums3[k] - nums4[l];

                if (sum12.containsKey(target)) {
                    ans += sum12.get(target);
                }
            }
        }

        return ans;
    }
}

LeetCode 383.赎金信

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
class Solution {
    // public boolean canConstruct(String ransomNote, String magazine) {
    //     HashMap<Character, Integer> charRecord = new HashMap<>();
        
    //     for (int i = 0; i < magazine.length(); i++) {
    //         char c = magazine.charAt(i);
    //         if (charRecord.containsKey(c)) {
    //             charRecord.put(c, charRecord.get(c) + 1);
    //         }else {
    //             charRecord.put (c, 1);
    //         }
    //     }

    //     for (int i = 0; i < ransomNote.length(); i++) {
    //         char c = ransomNote.charAt(i);

    //         if (charRecord.containsKey(c)) {
    //             charRecord.put(c, charRecord.get(c) - 1);
    //         }else {
    //             charRecord.put (c, -1);
    //         }
    //     }

    //     for (Character c : charRecord.keySet()) {
    //         if (charRecord.get(c) < 0) {
    //             return false;
    //         }
    //     }

    //     return true;
    // }

    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charRecord = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);
            charRecord[c - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            charRecord[c - 'a']--;
        }

        for (int i = 0; i < charRecord.length; i++) {
            if(charRecord[i] < 0) {
                return false;
            }
        }

        return true;
    }
}

这道题的难度不高，使用数组或者hashmap都可以，本题因为限定了两个字符串都由小写英文字母组成所以使用数组更节省空间。

LeetCode 15.三数之和

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
class Solution {

    // result in duplicate answers, for instance, [-1, 0, 1, 2, -1, -4]
    // [-1, 0, 1] and [0, 1, -1], which is hard to check

    // public List<List<Integer>> threeSum(int[] nums) {
    //     List<List<Integer>> ans = new LinkedList<>();

    //     for (int i = 0; i < nums.length; i++) {
    //         for (int j = i + 1; j < nums.length; j++) {
    //             for (int k = j + 1; k < nums.length; k++) {
    //                 if (nums[i] + nums[j] + nums[k] == 0) {
    //                     List<Integer> res = new ArrayList<>(
    //                         Arrays.asList(nums[i], nums[j], nums[k]));
    //                     ans.add(res);
    //                 }
    //             }
    //         }
    //     }
    //     return ans;
    // }


    public List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> ans = new LinkedList<>();
        Arrays.sort(nums);

        // if the smallest element in the sorted array is larger than 0
        // there is no valid element groups
        if (nums[0] > 0) {
            return ans; 
        }

        
        for (int i = 0; i < nums.length; i++) {
            
            // if the same element has been checked before
            // then its corresponding left and right must 
            // be same, thus let's just skip them 
            if (i != 0 && nums[i] == nums[i - 1] ) {
                continue;
            }

            // for any fixed nums[i], use two pointer scanning the array
            // and the three sum problem is converted to finding two sum
            // which is equals to -nums[i]
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if( sum == 0) {
                    ans.add (new LinkedList<>(
                        Arrays.asList(nums[i], nums[left], nums[right])));
                    
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

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

        }

        return ans;
    }
}

这道题的核心难度在于去重，也就是说我们不希望有(a,b,c)这样的三元数组后，再有(b,a,c) 或者（c,a,b, 因此，在循环中我们希望始终保持循环下标间的顺序为 i < j < k.

由于对一个已经排序的数组寻找twoSum的问题可以使用双指针相向遍历的方式解决，因此，考虑通过外层循环固定一个元素，然后在内层循环使用双指针。

需要注意的是，对于a的去重需要check a之前的一位元素是否与其相等，如果相等的话跳过这次循环。因为a确定的情况下，bc是固定的，如果不跳过此次循环则会引入重复元组。对于bc而言，去重的原因和操作也是类似的。

LeetCode 18.四数之和

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new LinkedList<>();

        Arrays.sort(nums);

        if ( nums.length < 4) {
            return ans;
        }

        for (int i = 0; i < nums.length; i++) {

            // if nums[i] is larger than target and not negative
            // no need checking the left number
            if (nums[i] > target && nums[i] >= 0){
                break;
            }
						
            if (i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
						
            for (int j = i + 1; j < nums.length; j++) {
                
                if (nums[i] + nums[j] > target && nums[i] >= 0) {
                    break;
                }
								
              	// if and only if j > i + 1 && nums[j] == left element
                // should we skip it, as there may be a group [2,2,2,2] 
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int left = j + 1; 
                int right = nums.length - 1;

                while ( left < right) {

                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    }else {

                        ans.add (new LinkedList<>(
                            Arrays.asList(nums[i], nums[j], nums[left], nums[right])));

                        while(left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }

                        while(left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }

                        left++;
                        right--;
                    }

                }
            }
        }

        return ans;
    }
}

和三数之和类似，多了一些pruning的判断，以及注意第二层循环j的去重。

Posted on

LeetCode 242. 有效的字母异位词

Ver1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isAnagram(String s, String t) {

        // new two arrays to count the number of each character in each string
        int[] sChars = new int[123];
        int[] tChars = new int[123];

        // full scan two strings and count
        for (int i = 0; i < s.toCharArray().length; i++) {
            sChars[s.charAt(i)]++;
        }

        for (int j = 0; j < t.toCharArray().length; j++) {
            tChars[t.charAt(j)]++;
        }

        // return if these two counter arrays are equal
        return Arrays.equals(sChars, tChars);
    }

Ver2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isAnagram(String s, String t) {

      // better check the length of each string first
      if(s.length() != t.length()) {
          return false;
      }

      // better space usage
      int[] alphabet = new int[123];

      for (int i = 0; i < s.toCharArray().length; i++) {
          alphabet[s.charAt(i)]++;
          alphabet[t.charAt(i)]--;
      }

      return Arrays.equals(alphabet, new int[123]);
  	}


Ver3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
   public boolean isAnagram(String s, String t) {

   if(s.length() != t.length()) {
       return false;
   }

   //better space usage
   int[] alphabet = new int[26];

   for (int i = 0; i < s.length(); i++) {
       alphabet[s.charAt(i) - 'a']++;
       alphabet[t.charAt(i) - 'a']--;
   }

   for (int i = 0; i < alphabet.length; i++) {
       if (alphabet[i] != 0) {
           return false;
       }
   }
   return true;
}

这道题的难度不高，使用数组充当哈希表，记录每个字符串中各个字符的数量，但是一些小的细节方面的优化值得注意

  1. 比如一开始脑子抽风了使用了s.toCharArray().length导致超时
  2. 开辟了两个数组用于记录字符数量
  3. 没有检查字符串长度
  4. 对两个字符串分别遍历

进阶问题:如果字符串包含unicode字符怎么办？

可以使用hashmap，以字符为key，字符的数量为value，思路一致

LeetCode 349. 两个数组的交集

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
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] digit1 = new int[1001];
        int[] digit2 = new int[1001];
      
				// full scan each array and records the number
        for (int i = 0; i < nums1.length; i++) {
            digit1[nums1[i]]++;
        }

        for (int i = 0; i < nums2.length; i++) {
            digit2[nums2[i]]++;
        }
        
      	// if a number exists in both array then record it
        LinkedList<Integer> ans = new LinkedList<>();
        for (int i = 0; i < digit1.length; i++) {
            if(digit1[i] > 0 && digit2[i] > 0) {
                ans.add(i);
            }
        }
				
      	// change the list to an array
        int[] array = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++) array[i] = ans.get(i);

        return array;
    }
}

因为本题限制了数组中包含的数字的范围，所以可以使用开两个数组的方法作为哈希表，如果数字范围更大一些，则应该考虑使用set。

LeetCode 202. 快乐数

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
class Solution {
    public boolean isHappy(int n) {

        HashSet<Integer> seen = new HashSet<>();

        while ( n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNextNumber(n);
        }

        return n == 1;

    }

    private int getNextNumber (int n) {

        int res = 0;

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

        return res;
    }
}

这道题还是蛮有意思的，一开始没有想明白结束循环的条件，后来才意识到，无限循环意味着重复出现的n，如此，将其加入set，利用set查询时间复杂度为O(1)的优势进行快速查询，如果数字已经check过，那么结束循环，或者数字为1，结束循环。

LeetCode 1.两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap <Integer, Integer> visited = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if(visited.containsKey(target - nums[i])) {
                return new int[] {i, visited.get(target - nums[i])};
            }else {
                visited.put(nums[i], i);
            }
        }

        return null;
    }
}

两数之和用暴力法解决思路还是挺直接的，但是暴力法的复杂度太高了。双重遍历的复杂度为n^2，其原因是，对于每一个正在check的数字，搜寻target-nums[i]的开销太大，考虑使用set将已经check过的数字cache起来，并利用其查询O(1)的优势。

Posted on Edited on

LeetCode.24 两两交换链表中的节点

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
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode sentinel = new ListNode (-1, head);
        if (sentinel.next != null) {
            swap(sentinel, sentinel.next, sentinel.next.next);
        }
        return sentinel.next;
    }

    private void swap (ListNode left, ListNode cur1, ListNode cur2) {
        // recursion exits when one of the pair is null
        if (cur1 == null || cur2 == null) {
            return;
        } else {
            // if both nodes are valid, record the next of cur2 and swap them 
            ListNode temp = cur2.next;
            left.next = cur2;
            cur2.next = cur1;
            cur1.next = temp;

            // cur1.next is the next first node to swap thus check whether it's valid
            // if so, recursivelly call this method, else exits
            if(cur1.next != null) {
                swap(cur1, cur1.next, cur1.next.next);
            }else{
                swap(cur1, null, null);
            }
        }
    }
}

LeetCode.19 删除链表的倒数第n个结点

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
class Solution {

    // public ListNode removeNthFromEnd(ListNode head, int n) {
    //     ListNode sentinel = new ListNode (-1, head);
    //     int cnt = 0;
    //     ListNode p = sentinel.next;
        
    //     // count how many nodes this list has
    //     while (p != null) {
    //         cnt++;
    //         p = p.next;
    //     }

    //     int index = cnt - n;
    //     p = sentinel;

    //     while (index > 0) {
    //         p = p.next;
    //         index--;
    //     }

    //     p.next = p.next.next;

    //     return sentinel.next;
    // }
    

    // space O(1) solution
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode (-1, head);
        ListNode slowIndex = sentinel, FastIndex = sentinel;

        // let fastIndex move n times first
        while (n > 0) {
            FastIndex = FastIndex.next;
            n--;
        }

        // then let both pointers move together
        // When fastIndex stops, slowIndex points to exactly the node that needs to be deleted.
        while (FastIndex.next != null) {
            FastIndex = FastIndex.next;
            slowIndex = slowIndex.next;
        }
        // now delete the node
        slowIndex.next = slowIndex.next.next;
        
        return sentinel.next;
    }
}

更新了一种双指针，空间复杂度O(1)的解决方法。

LeetCode.160 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        HashSet<ListNode> visited = new HashSet<>();

        while (pa != null) {
            visited.add(pa);
            pa = pa.next;
        }
        
        while (pb != null) {
            if (visited.contains (pb)) {
                return pb;
            }
            pb = pb.next;
        }

        return null;
    }
}

有空间复杂度O(1)的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    // m = a + c, n = b + c, m + n = n + m, (a + c + b) + c = (b + c + a) + c
  	// thus if there is intersection, pointer A and B would meet at the node
  	// else they would meet at the end of each list
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        while (pa != pb) {
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pa;
    }
}

LeetCode 142.环形链表

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
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slowIndex = head, fastIndex = head;
        
        while (fastIndex != null && fastIndex.next != null) {
            fastIndex = fastIndex.next.next;
            slowIndex = slowIndex.next;

            // there exists a circle
            if (fastIndex == slowIndex) {
                ListNode p = head;
                ListNode q = fastIndex;

                while (p != q) {
                    p = p.next;
                    q = q.next;
                }

                return p;
            }
        }

        return null;
    }

    /*
     * 假设链表的结构为X+X，分界点为环的相接点，则快指针刚好追上满指针，如果环的接入点不等分列表，用另外两个指针相遇
     * 进行相接点判断
     */
}

Posted on

LeetCode.203 移除链表元素

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // add a sentinel node to handle the corner case where 
        // the list is empty
        ListNode sentinel = new ListNode (-1, head);

        ListNode p = sentinel;
        while (p.next != null) {

            if(p.next.val == val) {
                p.next = p.next.next;
            }else {
                p = p.next;
            }

        }

        return sentinel.next;
    }
}

注意链表可能为空，引入哨兵节点处理这种Corner Case即可。

LeetCode.707 设计链表

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
class ListNode {
    public int val;
    public ListNode next;

    ListNode () {};
    ListNode (int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    private int size;
    private ListNode sentinel;

    MyLinkedList () {
        size = 0;
        sentinel = new ListNode(-1, null);
    };
		
		// use static method to operatre the bare ListNode recursively
    private static int getIndex (int index, ListNode node) {
        if (index == 0) {
            return node.val;
        }else {
            return getIndex(index - 1, node.next);
        }
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }else {
            return getIndex(index + 1, sentinel);
        }

    }
    
    public void addAtHead(int val) {
        sentinel.next = new ListNode(val, sentinel.next);
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode p = sentinel;
        while ( p.next != null) {
            p = p.next;
        }
        p.next = new ListNode(val , null);
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index <= 0) {
            addAtHead(val);
        }else if (index > size) {
            return;
        }else {
            ListNode p = sentinel;
            while ( index > 0) {
                p = p.next;
                index--;
            }
            p.next = new ListNode(val, p.next);
            size++;
        }
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }else {
            ListNode p = sentinel;
            while ( index > 0) {
                p = p.next;
                index--;
            }
            p.next = p.next.next;
            size--;
        }
    }
}

关于链表设计的一些思考

  1. 使用List类封装原来裸露的节点结构
  2. 封装的好处还在于可以提供一些如size，lastIndex的field方便链表操作
  3. 使用哨兵节点减少对corner case的考虑
  4. 使用私有静态方法递归的对内部节点进行操作

LeetCode.206 反转链表

反转链表的核心在于保存当前指向节点的prev和next节点信息，因此使用一个prev指针和一个temp指针记录下信息，之后只要递归或者循环遍历整个链表即可。

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
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

    public ListNode reverseListRecurrsively(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse (ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        } else {
            ListNode temp = cur.next;
            cur.next = prev;
            return reverse(cur, temp);
        }
    }
}

Posted on

LeetCode.977 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*
 * as the array is non-decreasing, thus we are sure that the elment that 
 * has the largest squre must be at two end. 
 */
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0; 
        int right = nums.length - 1;

        int[] ans = new int[nums.length];

        for (int i = ans.length - 1; i >= 0; i--) {
            if (Math.abs(nums[left]) >= Math.abs(nums[right])) {
                ans[i] = nums[left] * nums[left];
                left++;
            } else {
                ans[i] =  nums[right] * nums[right];
                right--;
            }
            
        }
        return ans;
    }
}

双指针方法的简单应用

LeetCode.209 长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int sum = 0;
        for(int slowIndex = 0, fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            sum += nums[fastIndex];
            while (sum >= target) {
                ans = Math.min(ans, fastIndex - slowIndex + 1);
                sum -= nums[slowIndex++];
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

注意slowIndex的更新应该使用while循环，更新直到sum<target

LeetCode.59 螺旋矩阵II

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
class Solution {
    public int[][] generateMatrix(int n) {

        int[][] ans = new int[n][n];
        int l = 0, r = n - 1, t = 0, b = n - 1; 
        int cnt = 1;

        while(cnt <= n*n) {
          
            for (int i = l; i <= r; i++) {
                ans[t][i] = cnt++;
            }
            t++;

            for (int i = t; i <= b; i++) {
                ans[i][r] = cnt++;
            }
            r--;

            for (int i = r; i >= l; i--) {
                ans[b][i] = cnt++;
            }
            b--;

            for (int i = b; i >= t; i--) {
                ans[i][l] = cnt++;
            }
            l++;
        }

        return ans;

    }
}

对比了一下我的方法和Carl的方法，我写的这个等于是纯粹模拟行为，感觉思维量更少一点，更straightforward.

LeetCode.54 螺旋矩阵

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {

        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0, r = n - 1, t = 0, b = m - 1; 

        int cnt = 0;
        List<Integer> ans = new ArrayList<>();

        // && cnt < m * n
        // because this matrix is not a square, 
        while ( cnt < m*n) {
            for (int i = l; i <= r && cnt < m * n; i++) {
                ans.add(matrix[t][i]);
                cnt++;
            }
            t++;


            for (int i = t; i <= b && cnt < m * n; i++) {
                ans.add(matrix[i][r]);
                cnt++;
            }
            r--;

            for (int i = r; i >= l && cnt < m * n; i--) {
                ans.add(matrix[b][i]);
                cnt++;
            }
            b--;

            for (int i = b; i >= t && cnt < m * n; i--) {
                ans.add(matrix[i][l]);
                cnt++;
            }
            l++;
        }

        return ans;
    }
}

这一题的思路和螺旋矩阵II类似，但是注意由于矩阵不是正方形的，每一次循环后要check是否已经完成遍历，避免重复打印。

Posted on

LeetCode 704. 二分查找

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
// invirants:
// If the target value is within the array to be searched, at any iteration, it stays within [left,right]

// [0, nums.length - 1] is our seaching range
// keep searching until left > right where there is no element left in our range
// mid = (left + right) / 2

/* if nums[mid] > target, since all the elements left in our range are valid, 
 * thus right = mid - 1, as the mid value is impossible to be target now,
 * which is the same with updating the left index.
 */

class Solution {
    public int search(int[] nums, int target) {
        int ans = -1;
        int left = 0, right = nums.length - 1;
        int mid;

        while(left <= right) {
            mid = (right - left)/2 + left;
            if (nums[mid] == target) {
                ans = mid;
                break;
            }else if (nums[mid] > target ) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }

        return ans;
    }
}

这道题的重点在于循环不变量的确定以及维护，常见的错误点是开闭区间，循环条件，以及循环中左右index的更新。

LeetCode 27.移除元素

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
class Solution {
    public int removeElement(int[] nums, int val) {

        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        // note: when left = right, the current pointing element has not 
        // been checked, thus when and only when left > right, we stop checking
        while (leftIndex <= rightIndex) {
            if (nums[leftIndex] != val) {
                leftIndex ++;
            }else {
                nums[leftIndex] = nums[rightIndex];
                rightIndex--;
            }
        }

        return leftIndex;
    }

    /* [0, nums.length)
    * 
    */
    // public int removeElement(int[] nums, int val) {

    //     int leftIndex = 0;
    //     int rightIndex = nums.length;

    //     while (leftIndex < rightIndex) {
    //         if (nums[leftIndex] != val) {
    //             leftIndex ++;
    //         }else {
    //             nums[leftIndex] = nums[rightIndex - 1];
    //             rightIndex--;
    //         }
    //     }

    //     return leftIndex;
    // }
}

这道题使用双指针方法可以达到O(n)的时间复杂度，最一开始我写的版本双指针在同侧，后来思考后发现这样多扫描了一些元素，所以在此之上做了一些优化，使用两个指针对向遍历，当二者相遇后停止。

Note：循环条件的设定仍然和开闭区间有关

LeetCode 35.搜索插入位置

题目要求在数组中查找指定元素，若检索到该元素，返回其索引，若不包含此元素，返回其应该被插入的位置的索引。

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
 /*
  * try to find the first element in this array which fit a[i] >= target
 	* i.e. nums[pos - 1] < target <= nums[pos]
  */

// @lc code=start
class Solution {
    // public int searchInsert(int[] nums, int target) {
    //     int left = 0;
    //     int right = nums.length - 1;
    //     int mid = 0; 

    //     while (left <= right) {
    //         mid = (right - left) / 2 + left;
    //         if (nums[mid] >= target) {
    //             right = mid - 1;
    //         } else if (nums[mid] < target) {
    //             left = mid + 1;
    //         } 
    //     }
    //     return left;
    // }

    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        int mid = 0; 

        while (left < right) {
            mid = (right - left) / 2 + left;
            if (nums[mid] >= target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } 
        }
        return left;
    }
}

上述同时实现了开闭区间的解法。

一开始一直纠结的一个点是，当nums[mid] >= target时，将right更新为mid - 1会把valid的节点移除出区间，后来思考了一段时间，发现按照这样的更新方法，结束循环时，所有的>=target的元素都在right右侧，即[right + 1, ]，而所有小于target的元素都在left左侧，而退出循环时，总满足left = right + 1, 则left总是指向第一个满足>=target的元素，故而总是返回left即可。

Posted on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment