两数之和

LeetCode 1.两数之和

问题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

哈希法

使用哈希Map，存储格式为<数值, 索引>。用哨兵i遍历数组，同时查找哈希表中是否含有target-nums[i]，如果有，则返回答案。如果没有，则把当前遍历的元素<nums[i], i>存入哈希，继续遍历下一个元素即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 哈希法
public int[] twoSum(int[] nums, int target) {

    // 定义哈希
    Map<Integer, Integer> map = new HashMap<>();

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

总结反思

使用哈希可以快速存储目标元素，减少查询某元素时间复杂度开销

两数相加

LeetCode 2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

博主解法：暴力解法

设置两个指针指向两个链表表头，变量ans用于存储两个指针元素与ans之和，取出元素的个位作为新节点，然后将十位数字存储到ans中，两个指针右移，开始下一次循环，计算两个指针元素以及ans的和，重复上述步骤，当一方指针走到尽头时，将ans与另一方元素求和得到新的ans，继续取出个位和十位，如果十位不是0，则存入链表节点

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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p = l1, q = l2, s = null;
    int ans = 0;

    // 虚拟节点
    ListNode h = new ListNode(0);
    s = h;

    while (p != null && q != null) {
        // 求两个指针与ans的和
        ans += p.val + q.val;
        // 分别取出个位和十位。将个位存入新链表，十位存入ans
        ListNode node = new ListNode(ans % 10);
        ans = ans / 10;
        s.next = node;
        s = node;
        p = p.next;
        q = q.next;
    }

    while (p != null) { // p 指向的链表长
        ans += p.val;
        ListNode node = new ListNode(ans % 10);
        ans = ans / 10;
        s.next = node;
        s = node;
        p = p.next;
    }

    while (q != null) { // q 指向的链表长
        ans += q.val;
        ListNode node = new ListNode(ans % 10);
        ans = ans / 10;
        s.next = node;
        s = node;
        q = q.next;
    }

    // 处理两位数字首位和大于10的情况
    if (ans != 0) {
        ListNode node = new ListNode(ans);
        s.next = node;
        s = node;
    }

    return h.next;
}

模拟

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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = null, tail = null;
    int carry = 0;

    while (l1 != null || l2 != null) {
        int n1 = l1 != null ? l1.val : 0;
        int n2 = l2 != null ? l2.val : 0;
        int sum = n1 + n2 + carry;
        if (head == null) {
            head = tail = new ListNode(sum % 10);
        } else {
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        carry = sum / 10;
        if (l1 != null) {
            l1 = l1.next;
        }
        if (l2 != null) {
            l2 = l2.next;
        }
    }
    if (carry > 0) {
        tail.next = new ListNode(carry);
    }
    return head;
}

无重复字符的最长子串

LeetCode 3.无重复字符的最长子串

问题

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

解法：滑动窗口

  • 使用两个指针表示字符串中的某个子串（或窗口）的左右边界，其中左指针代表着上文中「枚举子串的起始位置」
  • 在每一步的操作中，我们会将左指针向右移动一格，表示 我们开始枚举下一个字符作为起始位置，然后我们可以不断地向右移动右指针，但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后，这个子串就对应着 以左指针开始的，不包含重复字符的最长子串。我们记录下这个子串的长度；
  • 在枚举结束后，我们找到的最长的子串的长度即为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int lengthOfLongestSubstring(String s) {
    // 哈希集合，记录每个字符是否出现过
    Set<Character> set = new HashSet<>();
    int n = s.length();
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    int right = -1, ans = 0;

    for (int left = 0; left < n; left++) {
        if (left != 0) {
            // 左指针向右移动一格，移除一个字符
            set.remove(s.charAt(left - 1));
        }
        while (right + 1 < n && !set.contains(s.charAt(right + 1))) {
            // 不断移动右指针
            set.add(s.charAt(right + 1));
            ++right;
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

寻找两个正序数组的中位数

LeetCode 4.寻找两个正序数组的中位数

问题

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

算法思想

最长回文子串

LeetCode 5.最长回文子串

问题

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

枚举法

双重for-loop枚举出所有可能性，然后寻找最优解

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
// 枚举法
public String longestPalindrome(String s) {
    // 非法检查
    if (s.length() < 2) {
        return s;
    }
    // 定义最大长度
    int maxLen = 1;
    // 定义初始位置
    int init = 0;
    // 将串转化成字符数组
    char[] ch = s.toCharArray();

    // for-loop
    for (int i = 0; i < s.length() -1;; ++i) {
        for (int j = i + 1; j < s.length(); ++j) {
            if (j - i + 1 > maxLen && validPalindrome(chars, i, j)) {
                // 更新maxLen
                maxLen = j - i + 1;
                // 更新起始检查位置
                init = i;
            }
        }
        return s.substring(init, init + maxLen);
    }

}

// 判断是否回文
private boolean validPalindrome(char[] ch, int left, int right) {
    while (left < right) {
        if (ch[left] != ch[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

动态规划

对于一个子串而言，如果它是回文串，并且长度大于2，那么将它首尾的两个字母去除之后，它仍然是个回文串。用 $P(i,j)$ 表示字符串 $s$ 的第 $i$ 到 $j$ 个字母组成的串是否为回文串。

[其他情况] ：

  • $s[i,j]$ 本身不是一个回文串
  • $i>j$ ，此时 $s[i,j]$ 本身不合法

因此，dp公式为 $P(i,j)=P(i+1,j-1)∧(S_i==S_j)$。即只有s[i+1:j-1]是回文串，并且s的第i和j个字母相等时，s[i:j]才会是回文串。
上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1 或 2。

  • 对于长度为1的子串，显然是个回文串；
  • 对于长度为2的子串，仅需要两个字母相同，就是一个回文串
    因此加上dp边界：

根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 P(i,j)=true中j-i+1的最大值。注意：在dp公式中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意表格的计算顺序。

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
// dp
public String longestPalindrome(String s) {

    if (s.length() < 2) {
        return s;
    }

    int maxLen = 1;
    int begin = 0;

    // dp[i][j] 表示s[i..j] 是否是回文串
    boolean[][] dp = new boolean[s.length()][s.length()];

    // 初始化表格 所有长度为1的都是回文串
    for (int i = 0; i < s.length(); ++i) {
        dp[i][i] = true;
    }

    char[] chars = s.toCharArray();

    // 开始计算表格
    // 先枚举子串长度
    for (int subLen = 2; subLen <= s.length(); subLen++) {
        // 枚举左边界
        for (int left = 0; left < s.length(); left++) {
            // 由子串长度和左边界进而确定右边界
            int right = subLen + left - 1;
            // 若右边界越界，则退出当前循环
            if (right >= s.length()) {
                break;
            }

            if (chars[left] != chars[right]) {
                // 如果left和right指向的字符不相等，s[left:right]表示的子串自自然不是回文串
                dp[left][right] = false;
            } else {
                // 考虑除左右两边界元素子串长度小于2的情况
                if (right - left < 3) { // 考虑到j-i=3，除i、j外仅有两个元素，那么小于3就是除i和j外小于两个元素，那自然为true
                    dp[left][right] = true; // base case
                } else {
                    // dp[i][j]答案取决于dp[i+1][j-1]
                    dp[left][right] = dp[left + 1][right - 1];
                }
            }

            // 只有dp[left][right]==true，则表示子串s[left:right]回文，此时记录回文长度和起始位置
            if (dp[left][right] && right - left + 1 > maxLen) {
                // 更新最大长度
                maxLen = right - left + 1;
                // 更新枚举的左边界位置
                begin = left;
            }
        }
    }
    return s.substring(begin, begin + maxLen);

}

中心扩散法

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 String longestPalindrome(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCounter(s, i, i); // 以s[i]为回文中心，并返回回文直径长度
        int len2 = expandAroundCounter(s, i, i + 1); // 以s[i,i+1]为回文中心，并返回回文直径长度
        int curLen = Math.max(len1, len2);

        // curLen 当前遍历位置所计算的回文直径长度
        // end - start 表示截止目前最大回文直径长度
        if (curLen > end - start) {
            start = i - (curLen - 1) / 2; // start指向len中以回文中心点为中心的，可以扩展成回文串的回文左边界
            end = i + curLen / 2; // end指向len中以回文中心点为中心的，可以扩展成回文串的回文右边界
        }

    }
    return s.substring(start, end + 1);
}

public int expandAroundCounter(String s, int left, int right) {
    // 扩展回文半径直到两边字母不相同时停止扩展
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        --left; // 向左扩展
        ++right; // 向右扩展
    }
    // 返回以s[left,right]为回文中心的最长回文串长度（回文直径）
    return right - left - 1;
}

Manacher

具体请看 数据结构-11-Manacher

N 字形变换

LeetCode 6.N 字形变换

问题

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。