Leetcode算法解析101+

2018-08-18 本文已影响12人铛铛铛clark

<center>#104 Maximum Depth of Binary Tree</center>

link
Description:
- Given a binary tree, find its maximum depth.
- The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Solution:
- 递归，以当前节点为根的树最大深度是左右子树中深度更高的那一棵加一

Code:

# code block
public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);
    return Math.max(left, right) + 1;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#118 Pascal's Triangle</center>

link
Description:
- Given numRows, generate the first numRows of Pascal's triangle.
Input: 5

Output:

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution:
- 模拟题，根据图上的规律来进行循环
- 注意防止数组越界

Code:

# code block
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> result = new ArrayList<>();
    if (numRows <= 0) {
        return result;
    }
    List<Integer> firstRow = new ArrayList<Integer>();
    firstRow.add(1);
    result.add(firstRow);
    for (int i = 2; i <= numRows; i++) {
        List<Integer> ithRow = new ArrayList<>();
        List<Integer> lastRow = result.get(result.size() - 1);
        for (int j = 0; j < i; j++) {
            if (j == 0 || j == i - 1) {
                ithRow.add(1);
            } else {
                ithRow.add(lastRow.get(j - 1) + lastRow.get(j));
            }
        }
        result.add(ithRow);
    }
    return result;
}

<center>#119 Pascal's Triangle II</center>

link
Description:
- Given an index k, return the kth row of the Pascal's triangle.
Input: 3
Output: [1,3,3,1]
Assumptions:
- Could you optimize your algorithm to use only O(k) extra space?
Solution:
- Pascal's Triangle 的follow up，重点在于O(k)的空间复杂度
- 通过滚动数组的方式可以达到O(k)的空间复杂度

Code:

# code block
public List<Integer> getRow(int rowIndex) {
    Integer[][] rows = new Integer[2][rowIndex + 1];
    rows[0][0] = 1;
    rows[1][0] = 1;
    for (int i = 0; i <= rowIndex; i++) {
        for (int j = 1; j < i; j++) {
            rows[i % 2][j] = rows[(i + 1) % 2][j - 1] + rows[(i + 1) % 2][j];
        }
        rows[i % 2][i] = 1;
    }
    List<Integer> result = Arrays.asList(rows[rowIndex % 2]);
    return result;
}

Time Complexity: O(k ^ 2)
Space Complexity: O(k)

<center>#119 Pascal's Triangle II</center>

link
Description:
- Given an index k, return the kth row of the Pascal's triangle.
Input: 3
Output: [1,3,3,1]
Assumptions:
- Could you optimize your algorithm to use only O(k) extra space?
Solution:
- Pascal's Triangle 的follow up，重点在于O(k)的空间复杂度
- 通过滚动数组的方式可以达到O(k)的空间复杂度

Code:

# code block
public List<Integer> getRow(int rowIndex) {
    Integer[][] rows = new Integer[2][rowIndex + 1];
    rows[0][0] = 1;
    rows[1][0] = 1;
    for (int i = 0; i <= rowIndex; i++) {
        for (int j = 1; j < i; j++) {
            rows[i % 2][j] = rows[(i + 1) % 2][j - 1] + rows[(i + 1) % 2][j];
        }
        rows[i % 2][i] = 1;
    }
    List<Integer> result = Arrays.asList(rows[rowIndex % 2]);
    return result;
}

Time Complexity: O(k ^ 2)
Space Complexity: O(k)

<center>#121 Best Time to Buy and Sell Stock</center>

link
Description:
- Say you have an array for which the ith element is the price of a given stock on day i.
- If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Input: [7, 1, 5, 3, 6, 4]
Output: 5
Solution:
- 记录当前遇到的最小值，每次将当前卖出与最小值买入所得利润与最大利润进行比较

Code:

# code block
public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int profit = 0;
    int min = prices[0];
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > min && prices[i] - min > profit) {
            profit = prices[i] - min;
        }
        min = Math.min(min, prices[i]);
    }
    return profit;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#122 Best Time to Buy and Sell Stock II</center>

link
Description:
- Say you have an array for which the ith element is the price of a given stock on day i.
- Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Input: [1,2,3,1,6]
Output: 7
Solution:
- 这题可以简化为找到所有的递增区间的总增长

Code:

# code block
public int maxProfit(int[] prices) {
    int profit = 0;
    if (prices == null || prices.length <= 1) {
        return profit;
    }
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit = profit + prices[i] - prices[i - 1];
        }
    }
    return profit;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#125 Valid Palindrome</center>

link
Description:
- Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Input: "A man, a plan, a canal: Panama"
Output: true
Solution:
- 相向型的两根指针题
- 熟悉Java的Character和String的API会很容易做

Code:

# code block
public boolean isPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return true;
    }
    int start = 0, end = s.length() - 1;
    char[] sc = s.toCharArray();
    while (start < end) {
        while (start < end && !Character.isLetterOrDigit(sc[start])) {
            start++;
        }
        while (start < end && !Character.isLetterOrDigit(sc[end])) {
            end--;
        }
        if (start < end) {
            char startL = Character.toLowerCase(sc[start]);
            char endL = Character.toLowerCase(sc[end]);
            if (startL != endL) {
                return false;
            }
            start++;
            end--;
        }
    }
    return true;
}

Time Complexity: O(n)

<center>#141 Linked List Cycle</center>

link
Description:
- Given a linked list, determine if it has a cycle in it.
- Follow up:
  - Can you solve it without using extra space?
Solution:
- 最简单的想法就是用HashSet存访问过的点，再遇到就返回true
- 不用额外空间的话，就最好使用快慢指针，如果快指针走到底了，就说明无环，如果快慢指针相遇了，就是有环

Code:

# code block
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head.next;
    ListNode fast = head.next.next;
    while (fast != null && fast.next != null) {
        if (fast == slow) {
            return true;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return false;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#Find Minimum in Rotated Sorted Array</center>

link
Description:
- Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
- Find the minimum element.
Input: [4 5 6 7 0 1 2]
Output: 4
Assumptions:
- You may assume no duplicate exists in the array.
Solution:
- rotated排序数组，无重复，满足使用二分法的条件。取中点的值，如果小于最后一个值，说明从中点到最后一个值为递增，中间不会有最小值，反之则在。
- 注意点：
  - Corner case：数组是一个未翻转的排序数组。

Code:

# code block
public int findMin(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int start = 0, end = nums.length - 1;
    while (start < end - 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] < nums[end]) {
            end = mid;
        } else {
            start = mid;
        }
    }
    return nums[start] < nums[end] ? nums[start] : nums[end];
}

Time Complexity: O(lg n)
Space Complexity: O(1)

<center>#154 Find Minimum in Rotated Sorted Array II</center>

link
Description:
- Follow up for "Find Minimum in Rotated Sorted Array":
  - What if duplicates are allowed?
  - Would this affect the run-time complexity? How and why?
- Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
  (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
- Find the minimum element.
Input: [4 5 6 7 0 0 1 2]
Output: 4
Assumptions:
- The array may contain duplicates.
Solution:
- 复杂度上升到O(n)，不能用二分法。这题重点是不能使用二分法的原因。
- 二分法的本质是通过每一次判断舍弃一半的不可能为答案的值，或者保留有可能是答案的那一半的值。
- 假设一个数组全是0，其中有一个-1. 当我们尝试做二分，不可能在O(1)的时间内发现答案会在哪一边。
- Code:
```
# code block
public int findMin(int[] nums) {
    int result = Integer.MAX_VALUE;
    for (int i = 0; i < nums.length; i++) {
        result = Math.min(nums[i], result);
    }
    return result;
}
```
Time Complexity: O(n)
Space Complexity: O(1)

<center>#160 Intersection of Two Linked Lists</center>

link
Description:
- Write a program to find the node at which the intersection of two singly linked lists begins.

Input:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗
B:     b1 → b2 → b3

Output: c1
Solution:
- 这道题的基础解法是使用hashtable遍历其中一条链表，存储经过的节点，在与另一个链表一一比较
- 最优的解法请参考如下solution，从算法的角度来讲记下来就好，如果有兴趣做数学证明的也可以尝试一下

Code:

# code block
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pt = headA;
    while (pt.next != null) {
        pt = pt.next;
    }
    pt.next = headB;
    ListNode slow = headA.next;
    ListNode fast = headA.next.next;
    while (fast != null && fast.next != null && slow != fast) {
        fast = fast.next.next;
        slow = slow.next;
    }
    if (fast == null || fast.next == null) {
        pt.next = null;
        return null;
    }
    while (slow != headA) {
        slow = slow.next;
        headA = headA.next;
    }
    pt.next = null;
    return slow;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#162 Find Peak Element</center>

link
Description:
- A peak element is an element that is greater than its neighbors.
- Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
- The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
Input: [1, 2, 3, 1]
Output: 2
Assumptions:
- You may imagine that num[-1] = num[n] = -∞.
Solution:
- 二分法，如果中间值大于左右邻居则为peak，如果中间值小于右邻居，则保证右边肯定有peak，如果中间值小于左邻居，则保证左边肯定有peak，保留有peak的一半。

Code:

# code block
public int findPeakElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int start = 0, end = nums.length - 1;
    while (start < end - 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
            return mid;
        } else if (nums[mid] > nums[mid - 1]) {
            start = mid;
        } else {
            end = mid;
        }
    }
    return nums[start] > nums[end] ? start : end;
}

Time Complexity: O(lg n)
Space Complexity: O(1)

<center>#167 Two Sum II - Input array is sorted </center>

link
Description:
- Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
- The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
- You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Assumptions:
- each input would have exactly one solution
- you may not use the same element twice
Solution:
- Two Sum 的题一般有两种解法，一种是用hash，一种是用两根指针。
- 对于本题来说，在排序数组中两根指针时间复杂度为O(n)与hash相同，空间复杂度为O(1)优于hash的O(n)。
- 所以Two Sum加排序数组就意味着最优解是使用两根指针.初始化左指针left指向数组起始，初始化右指针right指向数组结尾。根据已排序这个特性:
  *如果numbers[left]与numbers[right]的和value小于target，说明应该增加value,因此left右移指向一个较大的值。
  *如果value大于target，说明应该减小value,因此right左移指向一个较小的值。
  *value等于target，则找到，返回left+1和right+1。
  *注意点：
  *注意返回值是1-based索引，不是0-based索引
  *两个int相加可能会溢出，但是使用int可以通过leetcode的test case，用long更优

Code:

# code block
public int[] twoSum(int[] numbers, int target) {
    if (numbers == null || numbers.length < 2) {
        return new int[0];
    }
    int[] result = new int[0];
    // 初始化两根指针
    int left = 0, right = numbers.length - 1;
    while (left < right) {
        int val = numbers[left] + numbers[right];
        if (val == target) {
            // find the answer and return it
            result = new int[2];
            // the result should be 1-based index not the 0-based
            result[0] = left + 1;
            result[1] = right + 1;
            return result;
        } else if (val > target) {
            // drop the right
            right--;
        } else {
            // drop the left
            left++;
        }
    }
    return result;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#175 Combine Two Tables</center>

link
Description:
- Write a SQL query for a report that provides the following information for each person in the Person table, regardless if there is an address for each of those people:
- FirstName, LastName, City, State

Input:

Table: Person
+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+
PersonId is the primary key column for this table.
Table: Address
+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+
AddressId is the primary key column for this table.

Solution:
- 因为每个人不管地址存不存在都要在新表中，所以用person表左外连接address表

Code:

# code block
SELECT a.FirstName, a.LastName, b.City, b.State
FROM Person a
LEFT OUTER JOIN Address b
on a.PersonId = b.PersonId;

<center>#189 Rotate Array</center>

link
Description:
- Rotate an array of n elements to the right by k steps.
- For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
  Could you do it in-place with O(1) extra space?
Input: [1,2,3,4,5,6,7] 3
Output: [5,6,7,1,2,3,4]
Assumptions:
- 三步翻转法，原理可以通过折纸来模拟。解决O(n)时间O(1)空间数组或者字符串左右移的最优方法。
Solution:

Code:

# code block
public void rotate(int[] nums, int k) {
    if (nums == null || nums.length < 2) {
        return;
    }
    int n = nums.length;
    k = k % n;
    if (k == 0) {
        return;
    }
    reverse(nums, 0, n - k - 1);
    reverse(nums, n - k, n - 1);
    reverse(nums, 0, n - 1);
}

private void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int tmp = nums[start];
        nums[start] = nums[end];
        nums[end] = tmp;
        start++;
        end--;
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#206 Reverse Linked List</center>

link
Description:
- Reverse a singly linked list.
Input: [1,2,3,4]
Output: [4,3,2,1]
Solution:
- 链表头的next记得置null

Code:

# code block
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode prev = head;
    ListNode next = head.next;
    while (next != null) {
        ListNode tmp = next.next;
        next.next = prev;
        prev = next;
        next = tmp;
    }
    head.next = null;
    return prev;
}

Time Complexity: O(n)
Space Complexity: O(1)

<center>#216 Combination Sum III</center>

link
Description:
- Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
Solution:
- 典型的隐式图DFS遍历，与combination sum的区别在于多了combination元素个数的限制，解决方案是在dfsHelper中加入一个变量记录还需要的元素的数量。

Code:

# code block
public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> result = new ArrayList<>();
    if (k == 0 || n <= 0) {
        return result;
    }
    dfsHelper(1, n, k, new ArrayList<Integer>(), result);
    return result;
}

private void dfsHelper(int start, int n, int k, List<Integer> state, List<List<Integer>> result) {
    if (k == 0 && n == 0) {
        result.add(new ArrayList<Integer>(state));
        return;
    }
    if (k <= 0 || n <= 0) {
        return;
    }
    for (int i = start; i <= 9; i++) {
        if (i <= n) {
            state.add(i);
            dfsHelper(i + 1, n - i, k - 1, state, result);
            state.remove(state.size() - 1);
        }
    }
}

<center>#217 Contains Duplicate</center>

link
Description:
- Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Input: [1,1]
Output: true
Solution:
- 判断重复使用哈希表

Code:

# code block
public boolean containsDuplicate(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        if (set.contains(nums[i])) {
            return true;
        }
        set.add(nums[i]);
    }
    return false;
}

Time Complexity: O(n)
Space Complexity: O(n)

<center>#283 Move Zeroes</center>

link
Description:
- Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Input: [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Assumptions:
- You must do this in-place without making a copy of the array.
- Minimize the total number of operations.
Solution:
- 最基本的两根指针问题，要求in-place并且最小化操作数量。最能理解的方法是循环一遍，去零，再将后面意义置零。假设这个数组大部分都是零，那么总操作数就大约是两次循环。
- 优化的办法是使用快慢指针。定义左指针左边的数不是零，遍历数组，一旦遇到不是零的就将左右指针的值交换，是零就将右指针又移一格。这样就只遍历数组一遍。
- 该算法保证了如果右指针大于左指针，那么左指针向右（包含左指针），右指针向左（不包含右指针）的区域内全部都是0.

Code:

# code block
public void moveZeroes(int[] nums) {
    if (nums == null || nums.length == 0) {
        return;
    }
    int left = 0, right = 0;
    while (right < nums.length) {
        if (nums[right] != 0) {
            int tmp = nums[right];
            nums[right] = nums[left];
            nums[left] = tmp;
            left++;
        }
        right++;
    }
}

Time Complexity: O(n)
Space Complexity: O(1)

Leetcode算法解析101+

<center>#104 Maximum Depth of Binary Tree</center>

<center>#118 Pascal's Triangle</center>

<center>#119 Pascal's Triangle II</center>

<center>#119 Pascal's Triangle II</center>

<center>#121 Best Time to Buy and Sell Stock</center>

<center>#122 Best Time to Buy and Sell Stock II</center>

<center>#125 Valid Palindrome</center>

<center>#141 Linked List Cycle</center>

<center>#Find Minimum in Rotated Sorted Array</center>

<center>#154 Find Minimum in Rotated Sorted Array II</center>

<center>#160 Intersection of Two Linked Lists</center>

<center>#162 Find Peak Element</center>

<center>#167 Two Sum II - Input array is sorted </center>

<center>#175 Combine Two Tables</center>

<center>#189 Rotate Array</center>

<center>#206 Reverse Linked List</center>

<center>#216 Combination Sum III</center>

<center>#217 Contains Duplicate</center>

<center>#283 Move Zeroes</center>

猜你喜欢

热点阅读