剑指offer刷题记录｜顺序刷题第三周

剑指offer 20 表示数值的字符串

class Solution:
    def isNumber(self, s: str) -> bool:
        # 有限状态机，短时间内根本写不出来
        # python直接float 虽然面试0分
        try:
            float(s)
        except:
            return False
        return True

剑指offer 24 反转链表

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 双指针法，有点难理解，还是看解释吧QAQ。反正结果是从后往前构造的，不断地添加前面结点
        cur, pre = head, None
        while cur:
            tmp = cur.next 
            cur.next = pre 
            pre = cur 
            cur = tmp
        return pre

剑指offer 22 链表中倒数第k个节点

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        # 法一：确定返回的列表和原列表中间距离即可得到结果，这个距离是len-k
        res=[]
        pre = head
        while head.next:
            res.append(head.val)
            head = head.next
        res.append(head.val)
        skip = len(res) - k
        while skip:
            pre = pre.next
            skip -= 1
        return pre

        # 法二：双指针，第一个指针先走k步，然后一起走到终点，没走完的那个还剩k步，就是结果
        # 这样就不用统计链条长度len，非常节省时间
        p, q = head, head
        while k:
            p = p.next
            k -= 1
        while p:
            p = p.next
            q = q.next
        return q

剑指offer 28 对称的二叉树

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def is_abba(L, R):
          	# 递归结束条件1，两个节点都为null 则 True
            if not L and not R: return True
            # 递归结束条件2，一个null一个不null 或者 val不同 则 False
            if not L or not R or L.val!=R.val: return False
            # 递归分两种，一个False则 return False，所以是and
            return is_abba(L.left, R.right) and is_abba(L.right, R.left)
        # 对称二叉树，左右结点需要满足三个条件：L.val == R.val & L.left == R.right & L.right == R.left
        return is_abba(root.left, root.right) if root else True

剑指offer 21 调整数组顺序，奇数在偶数前面

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        # 双指针， 奇数往前放，偶数往后放。只需要一遍，不过空间复杂度很高。
        left, right = 0, len(nums)-1
        res = [-1]*len(nums)
        for ele in nums:
            if ele % 2 == 1:
                res[left] = ele
                left += 1
            else:
                res[right] = ele
                right -= 1
        return res