LeetCode 解题笔记

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 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
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
package com.diguage.algorithm.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * = 1. Two Sum
 *
 * https://leetcode.com/problems/two-sum/description/[Two Sum - LeetCode]
 *
 * Given an array of integers, return indices of the two numbers such that they
 * add up to a specific target.
 *
 * You may assume that each input would have exactly one solution, and you may
 * not use the same element twice.
 *
 * .Example:
 * [source]
 * ----
 * Given nums = [2, 7, 11, 15], target = 9,
 *
 * Because nums[0] + nums[1] = 2 + 7 = 9,
 * return [0, 1].
 * ----
 *
 * @author D瓜哥, https://www.diguage.com/
 * @since 2018-06-30
 */
public class _0001_TwoSum {
    /**
     * 原始算法，时间复杂度为 `O(n^2^)`.
     *
     * @param nums   数组
     * @param target 目标
     * @return 结果
     */
    public static int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return null;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }

        return null;
    }

    /**
     * 优化后的算法，时间复杂度减低为 `O(n)`， 空间复杂度提高了。
     *
     * @param nums   数组
     * @param target 目标
     * @return 结果
     */
    public static int[] twoSumO1(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return null;
        }

        Map<Integer, Integer> diffNumToIndexMap = new HashMap<>(nums.length * 4 / 3);
        for (int i = 0; i < nums.length; i++) {
            if (diffNumToIndexMap.containsKey(nums[i])) {
                return new int[]{diffNumToIndexMap.get(nums[i]), i};
            } else {
                diffNumToIndexMap.put(target - nums[i], i);
            }
        }

        return null;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{4, 9, 2, 7, 11, 15};
        int target = 8;
        System.out.println(Arrays.toString(twoSumO1(nums, target)));
    }
}

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
package com.diguage.algorithm.leetcode;

import com.diguage.algorithm.util.ListNode;
import com.diguage.algorithm.util.ListNodeUtils;

import java.util.Arrays;
import java.util.Objects;

import static com.diguage.algorithm.util.ListNodeUtils.printListNode;

/**
 * = 2. Add Two Numbers
 *
 * https://leetcode.com/problems/add-two-numbers/description/[Add Two Numbers - LeetCode]
 *
 * You are given two non-empty linked lists representing two non-negative
 * integers. The digits are stored in reverse order and each of their nodes
 * contain a single digit. Add the two numbers and return it as a linked list.
 *
 * You may assume the two numbers do not contain any leading zero, except the number 0 itself.
 *
 * .Example:
 * [source]
 * ----
 * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
 * Output: 7 -> 0 -> 8
 * Explanation: 342 + 465 = 807.
 * ----
 *
 * @author D瓜哥, https://www.diguage.com/
 * @since 2018-09-17 11:42
 */
public class _0002_AddTwoNumbers {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode h1 = l1;
//        ListNode h2 = l2;
//        ListNode mergeList = null;
//        int carryOver = 0;
//        while (Objects.nonNull(h1) && Objects.nonNull(h2)) {
//            int v1 = h1.val;
//            int v2 = h2.val;
//            int newVal = v1 + v2 + carryOver;
//            if (newVal >= 10) {
//                carryOver = 1;
//                newVal -= 10;
//            } else {
//                carryOver = 0;
//            }
//            ListNode listNode = new ListNode(newVal);
//            listNode.next = mergeList;
//            mergeList = listNode;
//            h1 = h1.next;
//            h2 = h2.next;
//        }
//
//        ListNode rest = null;
//        if (Objects.nonNull(h1)) {
//            rest = h1;
//        }
//        if (Objects.nonNull(h2)) {
//            rest = h2;
//        }
//
//        ListNode restHead = rest;
//        while (Objects.nonNull(rest) && carryOver > 0) {
//            int newVal = rest.val + carryOver;
//            if (newVal >= 10) {
//                carryOver = 1;
//                newVal -= 10;
//            } else {
//                carryOver = 0;
//            }
//            rest.val = newVal;
//            if (Objects.isNull(rest.next) && carryOver > 0) {
//                ListNode carryNode = new ListNode(carryOver);
//                rest.next = carryNode;
//                carryOver = 0;
//            }
//            rest = rest.next;
//        }
//        if (Objects.isNull(restHead) && carryOver > 0) {
//            restHead = new ListNode(carryOver);
//        }
//
//        while (Objects.nonNull(mergeList)) {
//            ListNode next = mergeList.next;
//            mergeList.next = restHead;
//            restHead = mergeList;
//            mergeList = next;
//        }
//
//        return restHead;
/**
 * 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; }
 * }
 */
/**
 * 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; }
 * }
 */
        ListNode result = l1;
        int digit = 0;
        while (Objects.nonNull(l1.next) && Objects.nonNull(l2.next)) {
            int sum = l1.val + l2.val + digit;
            l1.val = sum % 10;
            digit = sum / 10;
            l1 = l1.next;
            l2 = l2.next;
        }
        int sum = l1.val + l2.val + digit;
        l1.val = sum % 10;
        digit = sum / 10;
        if (Objects.isNull(l1.next) && Objects.nonNull(l2.next)) {
            l1.next = l2.next;
            l1 = l1.next;
        }
        ListNode tail = null;
        ;
        while (digit > 0 && Objects.nonNull(l1)) {
            tail = l1;
            sum = l1.val + digit;
            l1.val = sum % 10;
            digit = sum / 10;
            l1 = l1.next;
        }
        if (digit > 0) {
            tail.next = new ListNode(digit);
        }
        return result;
//        ListNode result = l1;
//        int digit = 0;
//        while (Objects.nonNull(l1.next) && Objects.nonNull(l2.next)) {
//            int sum = l1.val + l2.val + digit;
//            l1.val = sum % 10;
//            digit = sum / 10;
//            l1 = l1.next;
//            l2 = l2.next;
//        }
//        int sum = l1.val + l2.val + digit;
//        l1.val = sum % 10;
//        digit = sum / 10;
//        if (Objects.isNull(l1.next) && Objects.nonNull(l2.next)) {
//            l1.next = l2.next;
//            l1 = l1.next;
//        }
//        while (digit > 0 && Objects.nonNull(l1.next)) {
//            sum = l1.val + digit;
//            l1.val = sum % 10;
//            digit = sum / 10;
//            l1 = l1.next;
//        }
//        if (digit > 0) {
//            l1.next = new ListNode(digit);
//        }
//        return result;
    }


    public static void main(String[] args) {
        _0002_AddTwoNumbers result = new _0002_AddTwoNumbers();
//        ListNode list1 = result.convertNumberToList(1);
//        ListNode list2 = result.convertNumberToList(99);
//        ListNode sum = result.addTwoNumbers(list1, list2);
//        printListNode(sum);
        ListNode list = result.addTwoNumbers(ListNodeUtils.build(Arrays.asList(9, 8)), ListNodeUtils.build(Arrays.asList(8)));
        ListNodeUtils.printListNode(list);
    }


    public ListNode convertNumberToList(int number) {
        ListNode result = null;
        for (int i = number; i > 0; i /= 10) {
            int vaule = i % 10;
            ListNode listNode = new ListNode(vaule);
            if (Objects.isNull(result)) {
                result = listNode;
            } else {
                ListNode last = result;
                while (Objects.nonNull(last.next)) {
                    last = last.next;
                }
                last.next = listNode;
            }
        }
        return result;
    }
}

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package com.diguage.algorithm.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * = 3. Longest Substring Without Repeating Characters
 *
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/[Longest Substring Without Repeating Characters - LeetCode]
 *
 * Given a string, find the length of the *longest substring* without repeating characters.
 *
 * .Example 1:
 * [source]
 * ----
 * Input: "abcabcbb"
 * Output: 3
 * Explanation: The answer is "abc", with the length of 3.
 * ----
 *
 * .Example 2:
 * [source]
 * ----
 * Input: "bbbbb"
 * Output: 1
 * Explanation: The answer is "b", with the length of 1.
 * ----
 *
 * .Example 3:
 * [source]
 * ----
 * Input: "pwwkew"
 * Output: 3
 * Explanation: The answer is "wke", with the length of 3.
 * Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
 * ----
 *
 * @author D瓜哥, https://www.diguage.com/
 * @since 2019-07-11 21:31
 */
public class _0003_LongestSubstringWithoutRepeatingCharacters {
  /**
   * Runtime: 6 ms, faster than 85.45% of Java online submissions for Longest Substring Without Repeating Characters.
   *
   * Memory Usage: 36.4 MB, less than 99.80% of Java online submissions for Longest Substring Without Repeating Characters.
   */
  public int lengthOfLongestSubstring(String s) {
    if (Objects.isNull(s) || s.length() == 0) {
      return 0;
    }
    int result = 0;
    int length = s.length();
    Map<Character, Integer> charToIndexMap = new HashMap<>(length * 4 / 3);
    for (int i = 0, j = 0; j < length; j++) {
      char aChar = s.charAt(j);
      if (charToIndexMap.containsKey(aChar)) {
        // 这里，如果存在重复的，则从上一个重复字符的下一个字符开始计算。
        Integer index = charToIndexMap.get(aChar);
        if (index + 1 > i) {
          i = index + 1;
        }
      }
      charToIndexMap.put(aChar, j);
      if (j - i + 1 > result) {
        result = j - i + 1;
      }

    }
    return result;
  }

  /**
   * Runtime: 9 ms, faster than 49.55% of Java online submissions for Longest Substring Without Repeating Characters.
   *
   * Memory Usage: 36 MB, less than 99.88% of Java online submissions for Longest Substring Without Repeating Characters.
   */
  public int lengthOfLongestSubstringWithSlidingWindow(String s) {
    if (Objects.isNull(s) || s.length() == 0) {
      return 0;
    }
    int result = 0;
    int length = s.length();
    int head = 0;
    int tail = 0;
    Set<Character> characters = new HashSet<>(length * 4 / 3);
    while (head < length && tail < length) {
      if (!characters.contains(s.charAt(tail))) {
        characters.add(s.charAt(tail));
        tail++;
        if (result < tail - head) {
          result = tail - head;
        }
      } else {
        characters.remove(s.charAt(head));
        head++;
      }
    }
    return result;
  }

  /**
   * Runtime: 221 ms, faster than 5.02% of Java online submissions for Longest Substring Without Repeating Characters.
   *
   * Memory Usage: 37.3 MB, less than 97.43% of Java online submissions for Longest Substring Without Repeating Characters.
   */
  public int lengthOfLongestSubstringWithBruteForce(String s) {
    if (Objects.isNull(s) || s.length() == 0) {
      return 0;
    }
    char[] chars = s.toCharArray();
    int result = 0;
    for (int i = 0; i < chars.length; i++) {
      Set<Character> characters = new HashSet<>(chars.length * 4 / 3);
      for (int j = i; j < chars.length; j++) {
        char aChar = chars[j];
        if (characters.contains(aChar)) {
          break;
        } else {
          characters.add(aChar);
        }
      }
      if (characters.size() > result) {
        result = characters.size();
      }
    }
    return result;
  }

  public static void main(String[] args) {
    _0003_LongestSubstringWithoutRepeatingCharacters result = new _0003_LongestSubstringWithoutRepeatingCharacters();
    System.out.println("2 - " + result.lengthOfLongestSubstring("aab"));
    System.out.println("3 - " + result.lengthOfLongestSubstring("abcabcbb"));
    System.out.println("1 - " + result.lengthOfLongestSubstring("bbbbb"));
    System.out.println("3 - " + result.lengthOfLongestSubstring("pwwkew"));
  }
}

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
package com.diguage.algorithm.leetcode;

/**
 * = 4. Median of Two Sorted Arrays
 *
 * https://leetcode.com/problems/median-of-two-sorted-arrays/description/[Median of Two Sorted Arrays - LeetCode]
 *
 * There are two sorted arrays nums1 and nums2 of size m and n respectively.
 *
 * Find the median of the two sorted arrays. The overall run time complexity
 * should be latexmath:[O(log(m+n))].
 *
 * .Example 1:
 * [source]
 * ----
 * nums1 = [1, 3]
 * nums2 = [2]
 *
 * The median is 2.0
 * ----
 *
 * .Example 2:
 * [source]
 * ----
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 *
 * The median is (2 + 3)/2 = 2.5
 * ----
 *
 * @author D瓜哥, https://www.diguage.com/
 * @since 2018-07-01
 */
public class _0004_MedianOfTwoSortedArrays {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (isEmpty(nums1) && isEmpty(nums2)) {
            return 0;
        }
        if (isEmpty(nums1)) {
            return singleArray(nums2);
        }
        if (isEmpty(nums2)) {
            return singleArray(nums1);
        }

        int length = nums1.length + nums2.length;
        boolean isOdd = (length & 1) == 1;
        int i1 = 0;
        int i2 = 0;
        int min = nums1[0] < nums2[0] ? nums1[0] : nums2[0];
        int temp = min;
        int last = min;
        int now = min;
        for (int i = 0; i < length; i++) {
            if (i1 < nums1.length && i2 < nums2.length) {
                if (nums1[i1] <= nums2[i2]) {
                    temp = nums1[i1];
                    i1++;
                } else {
                    temp = nums2[i2];
                    i2++;
                }
            } else if (i1 < nums1.length) {
                temp = nums1[i1];
                i1++;
            } else {
                temp = nums2[i2];
                i2++;
            }

            if (i > 0) {
                last = now;
                now = temp;
            }

            if (length / 2 == i) {
                if (isOdd) {
                    return now;
                } else {
                    return ((double) (last + now)) / 2.0;
                }
            }
        }
        return 0;
    }

    private static boolean isEmpty(int[] nums) {
        return nums == null || nums.length == 0;
    }

    public static double findMedianSortedArraysBest(int[] nums1, int[] nums2) {
        // TODO
        return 0;
    }

    private static double singleArray(int[] nums2) {
        boolean isOdd = (nums2.length & 1) == 1;
        if (isOdd) {
            return nums2[nums2.length / 2];
        } else {
            return (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0;
        }
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{100001};
        int[] nums2 = new int[]{100000};

        System.out.println(findMedianSortedArrays(nums1, nums2));
    }
}

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

P   A   H   N
A P L S I I G
Y   I   R

string convert(string s, int numRows);

Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:

P     I    N
A   L S  I G
Y A   H R
P     I

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
package com.diguage.algorithm.leetcode;

import java.util.Objects;

/**
 * = 6. ZigZag Conversion
 *
 * https://leetcode.com/problems/zigzag-conversion/[ZigZag Conversion - LeetCode]
 *
 * The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number
 * of rows like this: (you may want to display this pattern in a fixed font for
 * better legibility)
 *
 * [source]
 * ----
 * P   A   H   N
 * A P L S I I G
 * Y   I   R
 * ----
 *
 * And then read line by line: `"PAHNAPLSIIGYIR"`
 *
 * Write the code that will take a string and make this conversion given a number of rows:
 *
 * [source]
 * ----
 * string convert(string s, int numRows);
 * ----
 *
 * .Example 1:
 * [source]
 * ----
 * Input: s = "PAYPALISHIRING", numRows = 3
 * Output: "PAHNAPLSIIGYIR"
 * ----
 *
 * .Example 2:
 * [source]
 * ----
 * Input: s = "PAYPALISHIRING", numRows = 4
 * Output: "PINALSIGYAHRPI"
 * Explanation:
 *
 * P     I    N
 * A   L S  I G
 * Y A   H R
 * P     I
 * ----
 *
 * @author D瓜哥, https://www.diguage.com/
 * @since 2019-07-14 18:20
 */
public class _0006_ZigZagConversion {
    /**
     * Runtime: 5 ms, faster than 73.81% of Java online submissions for ZigZag Conversion.
     *
     * Memory Usage: 38.7 MB, less than 77.68% of Java online submissions for ZigZag Conversion.
     */
    public String convert(String s, int numRows) {
        if (Objects.isNull(s) || s.length() == 0) {
            return "";
        }
        if (numRows == 1) {
            return s;
        }
        int length = s.length();
        int columnLength = length / numRows;

        StringBuilder[] builders = new StringBuilder[numRows];
        for (int i = 0; i < builders.length; i++) {
            builders[i] = new StringBuilder(columnLength);
        }

        int direction = 1;
        int selector = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (selector == 0) {
                direction = 1;
            }
            if (selector == numRows - 1) {
                direction = -1;
            }
            char aChar = chars[i];
            builders[selector].append(aChar);
            selector += direction;
        }

        StringBuilder result = new StringBuilder(length);
        for (StringBuilder builder : builders) {
            result.append(builder);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        _0006_ZigZagConversion solution = new _0006_ZigZagConversion();

        String example3 = solution.convert("AB", 1);
        System.out.println(example3 + " " + "AB".equals(example3));

        String example1 = solution.convert("PAYPALISHIRING", 3);
        System.out.println(example1 + " " + "PAHNAPLSIIGYIR".equals(example1));

        String example2 = solution.convert("PAYPALISHIRING", 4);
        System.out.println(example2 + " " + "PINALSIGYAHRPI".equals(example2));
    }
}

Input: 123
Output: 321

Input: -123
Output: -321

Input: 120
Output: 21

Input: "42"
Output: 42

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
             digit or a +/- sign. Therefore no valid conversion could be performed.

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (-231) is returned.