美文网首页
双指针(链表、数组)

双指针(链表、数组)

作者: lililililiyan | 来源:发表于2019-07-05 14:55 被阅读0次

二分查找用于有序的排列
python中的二分查找模块bisect,Python中的list.inidex时间复杂度是O(n),bisect复杂度小些
\color{pruple}{二分查找的模板-->}
[图片上传失败...(image-580b0b-1562308505200)]

704. 二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid - 1
            else:
                return mid
        return -1

二分查找的升级版
https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
见题#34

86. 分隔链表

给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

def partition(self, head: ListNode, x: int) -> ListNode:
    h1 = l1 = ListNode(0)
    h2 = l2 = ListNode(0)
    while head:
        if head.val < x:
            l1.next = head
            l1 = l1.next
        else:
            l2.next = head
            l2 = l2.next
        head = head.next
    l2.next = None
    l1.next = h2.next
    return h1.next

61. 旋转链表

给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。
示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
这个我也能写出来,但是就是不如人家写的规范,关于什么时候定义的指针是当前指向head,还是下一步指向head还混淆
很厉害,人家是先连起来,再找头

class Solution:
    def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':
        # base cases
        if not head or not head.next:
            return head

        # close the linked list into the ring
        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head
        
        # find new tail : (n - k % n - 1)th node
        # and new head : (n - k % n)th node
        new_tail = head
        for i in range(n - k % n - 1):
            new_tail = new_tail.next
        new_head = new_tail.next
        
        # break the ring
        new_tail.next = None
        
        return new_head

归并算法的两种类型 top-down(递归)、bottom-up(迭代)
用在链表里的归并算法空间复杂度可以是O(1)

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

其实我觉得两种写法空间复杂度都是O(n)
递归写法

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

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        cut = slow = fast = head
        while fast and fast.next:
            cut = slow
            fast = fast.next.next
            slow = slow.next
        cut.next = None
        left = self.sortList(head)
        right = self.sortList(slow)
        return self.merge(left, right)
    
    def merge(self, left, right):
        m = n = ListNode(0)
        while left and right:
            if left.val <= right.val:
                n.next = left
                left = left.next
            else:
                n.next = right
                right = right.next
            n = n.next
        n.next = left or right
        return m.next
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None: return None
        
        def getSize(head):
            counter = 0
            while(head is not None):
                counter +=1
                head = head.next
            return counter
        
        def split(head, step):
            i = 1
            while (i < step and head):
                head = head.next
                i += 1
                
            if head is None: return None
            #disconnect
            temp, head.next = head.next, None
            return temp
        
        def merge(l, r, head):
            cur = head
            while(l and r):
                if l.val < r.val:
                    cur.next, l = l, l.next
                else:
                    cur.next, r = r, r.next
                cur = cur.next
            
            cur.next = l if l is not None else r
            while cur.next is not None: cur = cur.next
            return cur

        size = getSize(head)
        bs = 1
        dummy = ListNode(0)
        dummy.next = head
        l, r, tail = None, None, None
        while (bs < size):
            cur = dummy.next
            tail = dummy
            while cur:
                l = cur
                r = split(l, bs)
                cur = split(r, bs)
                tail = merge(l, r, tail)
            bs <<= 1
        return dummy.next

相关文章

网友评论

      本文标题:双指针(链表、数组)

      本文链接:https://www.haomeiwen.com/subject/hjxehctx.html