Leetcode(27) Remove Element

发表于 2018-03-29 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given an array and a value, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:

Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2.

解法：

此题与26题类似，同样两个指针，快指针用于遍历数组，慢指针用于覆盖指定值，当快指针的值和给定值不同，我们就把慢指针处的值用快指针的值覆盖，并将慢指针加1，快指针加1。代码如下：

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        if(len(nums) == 0):
            return 0;
        p = 0;
        q = 0;
        while(q<len(nums)):
            if(nums[q] != val):
                nums[p] = nums[q];
                p+=1;
                q+=1;
            else:
                q+=1;
        return p;

Leetcode(26) Remove Duplicates from Sorted Array

发表于 2018-03-29 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given a sorted array, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

解法：

采用双指针法，最开始时两个指针都指向第一个数字，如果两个指针指的数字相同，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标加1就是数组中不同数字的个数，代码如下：

class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if(len(nums) == 0):
            return 0;
        p = q = 0;
        while(p<len(nums) and q < len(nums)):
            if(nums[p] == nums[q]):
                q+=1;
            else:
                p+=1;
                nums[p] = nums[q];
        return p+1;

Leetcode(25) Reverse Nodes in k-Group

发表于 2018-03-28 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given a linked list, reverse the nodes of a linked list _k_ at a time and return its modified list. _k_ is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of _k_ then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.

For example, Given this linked list: 1->2->3->4->5

For _k_ = 2, you should return: 2->1->4->3->5

For _k_ = 3, you should return: 3->2->1->4->5

解法：

一般在处理链表问题时，我们大多时候都会在开头再加一个dummy node，因为翻转链表时头结点可能会变化，为了记录当前最新的头结点的位置而引入的dummy node。具体到思路，每次以k为分段，翻转这k个节点，整体需要翻转的数减去k，如果剩余翻转点小于k无需继续进行翻转。翻转的过程中从前往后扫描，需要pre,last,tmp和cur四个指针。具体代码如下：

# Definition for singly-linked list.
class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if(head == None or k == 1):
            return head;
        dummy = ListNode(-1);
        dummy.next = head;
        pre = dummy;
        cur = head;
        num = 0;
        while(cur):
            cur = cur.next;
            num+=1;
        while(num>=k):
            cur = pre.next;
            last = cur;
            for i in range(k):
                last = last.next;
            for i in range(k):
                t = cur.next;
                cur.next = last;
                last = cur;
                cur = t;
            tmp = pre.next;
            pre.next = last;
            pre = tmp;
            num -= k;
        return dummy.next;

Leetcode(24) Swap Nodes in Pairs

发表于 2018-03-28 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

iven a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space.

You may not modify the values in the list, only nodes itself can be changed.

解法：

需要建立dummy节点，（即头指针前的虚拟节点），注意在连接节点的时候，最好画个图，以免把自己搞晕了，代码如下：

# Definition for singly-linked list.
class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if(head == None):
            return None;
        dummy = ListNode(-1);
        pre = dummy;
        dummy.next = head;
        while(pre.next and pre.next.next):
            tmp = pre.next;
            pre.next = tmp.next;
            tmp.next = pre.next.next;
            pre.next.next = tmp;
            pre = tmp;
        return dummy.next;

Leetcode(23) Merge k Sorted Lists

发表于 2018-03-28 | 更新于 2019-10-02 | 分类于 Leetcode刷题笔记

Description:

Merge _k_ sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解法：

利用了最小堆这种数据结构，我们首先把k个链表的首元素都加入最小堆中，它们会自动排好序。然后我们每次取出最小的那个元素加入我们最终结果的链表中，然后把取出元素的下一个元素再加入堆中，下次仍从堆中取出最小的元素做相同的操作，以此类推，直到堆中没有元素了，此时k个链表也合并为了一个链表，返回首节点即可，代码如下：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode a, ListNode b) {
                return a.val - b.val;
            }
        });
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                q.offer(lists[i]);
            }
        }
        ListNode res = null;
        ListNode tail = null;
        while (!q.isEmpty()) {
            ListNode tmp = q.poll();
            if (res == null) {
                res = tmp;
                tail = tmp;
            } else {
                tail.next = tmp;
                tail = tmp;
            }
            if (tmp.next != null) {
                q.offer(tmp.next);
            }
        }
        return res;
    }
}

Leetcode(22) Generate Parentheses

发表于 2018-03-27 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

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: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

解法：

看到这道题首先想到了DFS，递归可以解决这个问题。

对于递归类问题，解题思路大体是：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集。简而言之，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。结束条件与限制均返回，两者的区别在于结束条件是合法搜索完了返回，而限制是遇上了非法情况返回的。

对于这道题，在任何时刻，你都有两种选择：

加左括号。
加右括号。

这部分构成了递归体

结束条件也很明确：

左右括号都已经用完了

这部分构成了合法完成搜索的递归出口

而限制则考虑搜索过程中的非法情况，即出现了这种情况不再进行递归搜索而返回：

对于该题，从左括号与右括号的数量入手，两者数目相同，显然合法；如果剩余的右括号数量大于左括号数量，说明之前存在没有与右括号匹配的左括号，这种情况是合法有效的；若出现左括号数目大于右括号的情况，则对于之后添加的左括号，一定会存在没有右括号与之匹配的情况，这种情况非法，不用再继续进行搜索了。简而言之：

如果左括号剩余量大于右括号，会出现非法情况，返回

代码如下：

class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = [];
        Solution.dfs(n,n,"",res);
        return res;
        
    def dfs(left,right,nowstr,res):
        if(left>right):
            return;
        if(left == 0 and right == 0):
            res.append(nowstr);
            return;
        if(left > 0):
            Solution.dfs(left - 1, right ,nowstr + '(',res);
        if(right > 0):
            Solution.dfs(left,right - 1,nowstr + ')', res);

Leetcode(21) Merge Two Sorted Lists

发表于 2018-03-21 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

解法：

新建一个链表，然后比较两个链表中的元素值，把较小的那个链到新链表中，由于两个输入链表的长度可能不同，所以最终会有一个链表先完成插入所有元素，则直接另一个未完成的链表直接链入新链表的末尾。代码如下：

# Definition for singly-linked list.
class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p = l1;
        q = l2;
        result = ListNode(-1);
        x = result;
        while(p!= None and q != None):
            if(p.val < q.val):
                tmp = ListNode(p.val);
                x.next = tmp;
                p = p.next;
                x = x.next; 
            else:
                tmp = ListNode(q.val);
                x.next = tmp;
                q = q.next;
                x = x.next;
        if(p != None):
            x.next = p;
        else:
            x.next = q;
        result = result.next;
        return result;

Leetcode(20) Valid Parentheses

发表于 2018-03-21 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

解法：

利用栈做匹配，正括号都入栈，反括号入栈时查看有无匹配，有则对应正括号出栈，否则匹配失败，字符串不合法。当最终栈空时匹配成功，否则失败。特别注意“( [ ) ]”的情况，是不合法的。代码如下：

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        l = [];
        for c in s:
            if(c == '(' or c == '[' or c == '{'):
                l.append(c);
            elif(c == ')'):
                if(len(l) != 0 and l[-1] == '('):
                    l = l[:-1];
                else:
                    return False;
            elif(c == ']'):
                if(len(l) != 0 and l[-1] == '['):
                    l = l[:-1];
                else:
                    return False;
            elif(c == '}'):
                if(len(l) != 0 and l[-1] == '{'):
                    l = l[:-1];
                else:
                    return False;
        if(len(l) == 0):
            return True;
        return False;

Leetcode(19) Remove Nth Node From End of List

发表于 2018-03-20 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

Given a linked list, remove the _n_th 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.

解法：

由于只允许一次遍历，所以我们不能用一次完整的遍历来统计链表中元素的个数，而是遍历到对应位置就应该移除了。那么我们需要用两个指针来帮助我们解题，pre和cur指针。首先cur指针先向前走N步，如果此时cur指向空，说明N为链表的长度，则需要移除的为首元素，那么此时我们返回head->next即可，如果cur存在，我们再继续往下走，此时pre指针也跟着走，直到cur为最后一个元素时停止，此时pre指向要移除元素的前一个元素，我们再修改指针跳过需要移除的元素即可。代码如下：

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        p = head;
        tmp = p;
        for i in range(n):
            q = tmp.next;
            tmp = q;
        if(q == None):
            return head.next;
        while(q.next != None):
            p = p.next;
            q = q.next;
        tmp = p.next;
        if(tmp != None):
            p.next = tmp.next;
        return head;

Leetcode(18) 4Sum

发表于 2018-03-19 | 更新于 2018-10-04 | 分类于 Leetcode刷题笔记

Description:

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] ]

解法：

虽然难度在递增，但是整体的套路都是一样的，在于如何去除重复项，由于Python中list不可哈希，利用set或dict进行去重时需要先把list转化为tuple，此题的解法和3 Sum基本没啥区别，就是多加了一层for循环，其他的都一样，代码如下：

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort();
        result = [];
        for i in range(len(nums) - 3):
            for j in range(i +1,len(nums) - 2):
                p = j+1;q = len(nums) - 1;
                while(p<q):
                    sum = nums[i] + nums[j] + nums[p] + nums[q];
                    if(sum == target):
                        tmp = [nums[i],nums[j],nums[p],nums[q]];
                        result.append(tmp);
                        p+=1;
                        q-=1;
                    elif(sum < target):
                        p+=1;
                    else:
                        q-=1;
        r = [];
        for x in result:
            tmp = tuple(x);
            r.append(tmp);
        r = list(set(tuple(r)));
        result =[];
        for x in r:
            tmp = list(x);
            result.append(tmp);
        return result;