5 划分树

Wu Jun 2020-01-14 21:27:23
01 数据结构与算法 > 数据结构 > 02 高级数据结构

1. 两数之和 - Easy

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numIndexMap = new HashMap<>(nums.length);
    int frontNum;
    int endNum;
    for (int index = 0; index < nums.length; index++) {
        endNum = nums[index];
        frontNum = target - endNum;
        if (numIndexMap.get(frontNum) == null) {
            numIndexMap.put(endNum, index);
        } else {
            return new int[]{numIndexMap.get(frontNum), index};
        }
    }
    return null;
}

2. 两数相加 - Medium

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解答:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode curr = result;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            int sum = carry + val1 + val2;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return result.next;
    }
}

拓展解法:递归或者栈

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

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。

解答:滑动窗口

public int lengthOfLongestSubstring(String s) {
    int length = 0;
    if (null != s && !s.isEmpty()) {
        int start = 0;
        for (int end = 1; end <= s.length(); end++) {
            String substring = s.substring(start, end);
            if (substring.length() > length) {
                length = substring.length();
            }

            if(end < s.length()){
                char c = s.charAt(end);
                if (substring.contains(c + "")) {
                    start += substring.indexOf(c + "") + 1;
                }
            }
        }
    }
    return length;
}

4. 寻找两个有序数组的中位数 - Hard

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

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

则中位数是 2.0

示例 2:

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

则中位数是 (2 + 3)/2 = 2.5

解答:理解 “中位数的作用是什么”

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    // to ensure m<=n
    if (m > n) {
        int[] temp = A; A = B; B = temp;
        int tmp = m; m = n; n = tmp;
    }
    int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
    while (iMin <= iMax) {
        int i = (iMin + iMax) / 2;
        int j = halfLen - i;
        if (i < iMax && B[j - 1] > A[i]) {
            // i is too small
            iMin = i + 1;
        } else if (i > iMin && A[i - 1] > B[j]) {
            // i is too big
            iMax = i - 1;
        } else {
            // i is perfect
            int maxLeft;
            if (i == 0) { maxLeft = B[j-1]; } 
            else if (j == 0) { maxLeft = A[i-1]; } 
            else { maxLeft = Math.max(A[i-1], B[j-1]); } 
            if ( (m + n) % 2 == 1 ) { return maxLeft; } 
            
            int minRight;
            if (i == m) { minRight = B[j]; } 
            else if (j == n) { minRight = A[i]; } 
            else { minRight = Math.min(B[j], A[i]); } 
            
            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;
}

5. 最长回文子串 - Medium