LeetCode解题报告—— 4Sum & Remove Nth Node From End of List & Generate Parentheses

1. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:

[

  [-1,  0, 0, 1],

  [-2, -1, 1, 2],

  [-2,  0, 0, 2]

]

思路：将4sum分解为3sum问题即可，其实按照这个思路可以解决k-Sum问题的。

List<List<Integer>> kSum_Trim(int[] a, int target, int k) {

    List<List<Integer>> result = new ArrayList<>();

    if (a == null || a.length < k || k < 2) return result;

    Arrays.sort(a);

    kSum_Trim(a, target, k, 0, result, new ArrayList<>());

    return result;

}


// 这里的path缓存的是迭代到 k=2 之前的候选数字

void kSum_Trim(int[] a, int target, int k, int start, List<List<Integer>> result, List<Integer> path) {

    int max = a[a.length - 1];

    if (a[start] * k > target || max * k < target) return;

    if (k == 2) {                        // 2 Sum

        int left = start;

        int right = a.length - 1;

        while (left < right) {

            if      (a[left] + a[right] < target) left++;

            else if (a[left] + a[right] > target) right--;

            else {
　　　　　　　　// ArrayList(Collection<? extends E> c)，构造一个包含指定 collection 的元素的列表

                result.add(new ArrayList<>(path));

                result.get(result.size() - 1).addAll(Arrays.asList(a[left], a[right]));

                left++;

                right--;

                while (left < right && a[left] == a[left - 1]) left++;    //去重

                while (left < right && a[right] == a[right + 1]) right--;   //去重

            }

        }

    } else {                      // k Sum

        for (int i = start; i < a.length - k + 1; i++) {

            if (i > start && a[i] == a[i - 1]) continue;　　//注意这里的去重逻辑，只计算重复数字中的第一个数字，这样既不会遗漏也不会计算重复

            if (a[i] + max * (k - 1) < target) continue;

            if (a[i] * k > target) break;

            if (a[i] * k == target) {　　//如果是这种情况则不需要继续向下迭代

                if (a[i + k - 1] == a[i]) {

                    result.add(new ArrayList<>(path));

                    List<Integer> temp = new ArrayList<>();

                    for (int x = 0; x < k; x++) temp.add(a[i]);

                    result.get(result.size() - 1).addAll(temp);    // Add result immediately.

                }

                break;

            }

            path.add(a[i]);

            kSum_Trim(a, target - a[i], k - 1, i + 1, result, path);

            path.remove(path.size() - 1);        // 回溯，以k=4为例，固定住a1,a2去后面找完所有可能的kusm=2的情况，再移出a2,固定a1,a3，以此类推。

        }

    }

}

这里难理解的是 result.add(new ArrayList<>(path)); 这段，因为path是缓存向下迭代到k=2之前的数字，所以再正式往result里加数字组的时候还要加上k=2时找到的那两个数字，所以要用一个新的List集合。

第二次来看这题时发现理解不了其中的去重逻辑，再次感叹一下算法真的是好难。计算既不能包含重复，也不能遗漏由相同数字构成的解，所以去重逻辑是这样的，首先对数组排序，这样重复的数字就挨在一起了，只计算这其中的第一个数字，比如 2，2，2........，先固定住第一个数字2，计算它后面和构成-2的数字对(注意这时的计算要考虑第一个2后面的那些重复的2)，那么可以得到的一个结论是，所有包含数字2的解(一个或多个的情况)都被找到了。这样下次寻找解的时候直接跳过后面重复的2即可，因为对于第一个2的计算已经找到了所以含有2的解，而且是包括了一个或多个的情形，所以之后的解肯定是不包含数字2的，否则肯定重复。

2. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

思路：对于链表，要注意头结点的作用。自己试了写下代码，如果不加一个指向链表中第一个节点的空节点，情况会变得较难考虑。这题可以先遍历求链表全长，再减去n。也可以用两个指针first和second，让first先向后移动距离second n个距离后，first和second再一起向后移动直至first指向null为止。

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode dummy = new ListNode(0);

    dummy.next = head;

    ListNode first = dummy;

    ListNode second = dummy;

    // Advances first pointer so that the gap between first and second is n nodes apart

    for (int i = 1; i <= n + 1; i++) {

        first = first.next;

    }

    // Move first to the end, maintaining the gap

    while (first != null) {

        first = first.next;

        second = second.next;

    }

    second.next = second.next.next;

    return dummy.next;

}

3. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[

  "((()))",

  "(()())",

  "(())()",

  "()(())",

  "()()()"

]

思路：可以使用穷举的方法，遍历所有可能的组合，对每一组判断是否是合法的括号对。这里难点在于如何遍历所有组合以及如何判断是否合法：

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> combinations = new ArrayList();

        generateAll(new char[2 * n], 0, combinations);

        return combinations;

    }


 // 利用递归的方法求所有组合

    public void generateAll(char[] current, int pos, List<String> result) {

        if (pos == current.length) {

            if (valid(current))

                result.add(new String(current));

        } else {

            current[pos] = '(';

            generateAll(current, pos+1, result);

            current[pos] = ')';

            generateAll(current, pos+1, result);

        }

    }


　// 这里判断括号对是否合法，学到了

    public boolean valid(char[] current) {

        int balance = 0;

        for (char c: current) {

            if (c == '(') balance++;

            else balance--;

            if (balance < 0) return false;

        }

        return (balance == 0);

    }

}

解法2是对1的改进，不需要遍历所有再一个个判断。

Instead of adding '(' or ')' every time as in Approach #1, let's only add them when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

class Solution {

    public List<String> generateParenthesis(int n) {

        List<String> ans = new ArrayList();

        backtrack(ans, "", 0, 0, n);

        return ans;

    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max){

        if (str.length() == max * 2) {

            ans.add(cur);

            return;

        }

        if (open < max)

            backtrack(ans, cur+"(", open+1, close, max);

        if (close < open)

            backtrack(ans, cur+")", open, close+1, max);

    }

}

这个算法我还是花了较长时间来理解的，特别是哪个回溯方法backtrack。如果 str 的长度达到了2n，因为再整个添加括号的过程中都是保证合法的，故可以直接加到List集合中。关键就是为什么能保证每步合法的添加括号。每一步的选择：1.如果当前字符串中 ( 的数量是少于n的，那么下个添加的字符可以是 ( ；2. 如果当前的 ) 符号数小于 (，那么下一个添加的字符可以是 )。无论选择的是1还是2，它们之后的部分都是相同的递归方法来处理，更改相关参数再直接调用backtrack来处理后面的部分即可。因为要求所有的情况，所以选择1和2都要走一次才能遍历到所有合法的括号对。

巴特西

LeetCode解题报告—— 4Sum & Remove Nth Node From End of List & Generate Parentheses

最新文章

热门文章