148. 排序链表

148. 排序链表

"""
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
"""
from typing import Optional
from tools import singleChainGenerate


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

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        sort_list = []
        node = head
        while node:
            sort_list.append(node)
            node = node.next
        sort_list.sort(key=lambda x: x.val)
        for i in range(len(sort_list) - 1):
            sort_list[i].next = sort_list[i + 1]
        sort_list[-1].next = None
        return sort_list[0]



print(Solution().sortList(singleChainGenerate(head=[4, 2, 1, 3])))

1232. 缀点成线

1232. 缀点成线

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        for i in range(1, len(coordinates) - 1):
            x0 = (coordinates[i][0] - coordinates[i - 1][0])
            x1 = (coordinates[i + 1][0] - coordinates[i][0])
            if x0 != x1 and (x0 == 0 or x1 == 0):
                return False
            elif x0 == 0 and x1 == 0:
                continue
            else:
                k0 = (coordinates[i][1] - coordinates[i - 1][1]) / x0
                k1 = (coordinates[i + 1][1] - coordinates[i][1]) / x1
                if k0 != k1:
                    return False
        return True

1656. 设计有序流

1656. 设计有序流

class OrderedStream:
    def __init__(self, n: int):
        self.stream = [None for i in range(n + 1)]
        self.ptr = 1

    def insert(self, idKey: int, value: str):
        res = []
        self.stream[idKey] = value
        if idKey == self.ptr:
            for i in range(self.ptr, len(self.stream)):
                if self.stream[i] is None:
                    self.ptr = i
                    break
                res.append(self.stream[i])
        # print(res)
        return res

268. 丢失的数字

268. 丢失的数字

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return sum((i for i in range(len(nums) + 1))) - sum(nums)

2425. 所有数对的异或和

2425. 所有数对的异或和

异或偶数次结果为0

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 0
        if len(nums2) % 2 == 0 and len(nums1) % 2 == 0:
            ans = 0
        elif len(nums2) % 2 == 0:
            for i in range(len(nums2)):
                ans ^= nums2[i]
        elif len(nums1) % 2 == 0:
            for i in range(len(nums1)):
                ans ^= nums1[i]
        else:
            for i in range(len(nums1)):
                ans ^= nums1[i]
            for i in range(len(nums2)):
                ans ^= nums2[i]
        return ans

1046. 最后一块石头的重量

1046. 最后一块石头的重量

可以用堆

import bisect


class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        stones.sort()
        while len(stones) != 1:
            y = stones.pop()
            x = stones.pop()
            if x == y:
                pass
            stones.insert(bisect.bisect_left(stones, y - x), y - x)
        return stones[0]