彻底理解原码、反码和补码

本科时从计算机组成原理这门课程上学习计算机的编码方式,原码反码和补码,始终是很混乱,也可以说学了就忘忘了再看看了又忘,。从网上的一些博客也好,也很难找到一种特别具象化形象的理解方式,因此本人制作了一个较为具象化的视频来讲解原码反码和补码的区别以及计算机为什么最终采用补码作为编码方式。视频如下:

https://www.bilibili.com/video/BV1Yk4y1r7D4/

LeetCode 23 合并K个有序链表

这道题可以采用类似于归并排序的方式进行解题,一种自顶向下的方法,关键在于partition函数和merge两个函数。partition函数问题的规模大于2就不断的往下分,直至问题的规模小于等于2,当问题的规模为1的话就直接返回那个有序列表单问题的规模为2的话,就用merge函数合并两个列表并返回。

书写代码的过程中需要注意两个事项,

  • 当k等于0的时候,应该直接返回空
  • partition函数的一个边界情况,也需要好好斟酌一下
    • 因为在最终调用partition的时候,[0,len(lists)-1],也就是左闭右闭的一个区间
    • 只当左边界和右边界相同的时候,就直接返回的那个链表就可以,
    • 当左右边左边接小于右边界的时候就要取一个中间值,中间值是两数相加除以2并向下取整,所以厄在求左半边的一个partition结果的时候可以取m,右半边的左边界就要取m加1,因为是 左闭右闭的一个区间,这样也可以保证m不会大于右边界。
 class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        return self.partition(0, len(lists) - 1, lists)

    def partition(self,start,end,lists):
        # 左闭右闭
        if start == end:
            return lists[start]
        else:
            m = (start + end) // 2
            left = self.partition(start, m, lists)
            right = self.partition(m+1, end, lists)
            return self.merge(left, right)
        
    
    def merge(self, a ,b):
        dummy = tail = ListNode(0)
        while a and b:
            if a.val < b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a if a else b
        return dummy.next

有空可以练习一下非递归自底向上的归并代码。

Leetcode 21 合并两个有序链表

常规思路遍历比较进行合并

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(l1 != null && l2 != null){
            ListNode temp;
            if (l1.val < l2.val){
                temp = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                temp = new ListNode(l2.val);
                l2 = l2.next;
            }
            tail.next = temp;
            tail = temp;
        }
        if (l1 != null)
            tail.next = l1;
        if (l2 != null)
            tail.next = l2;
        return dummy.next;
    }

另一个比较有意思的思路是采用递归的方法。因为当某个链表中的元素已经加入有序链表中时,原始问题就转换为一个较小规模的问题。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null)
            return l1 == null? l2 : l1;

        if (l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
        l2.next = mergeTwoLists(l1,l2.next);
        return l2;
}

LeetCode 2 & LeetCode 445 两数相加

总结:

  • 熟练掌握单项链表的翻转操作(头插法),通常会使用一个dummy节点以辅助链表操作
  • 当一些问题存在逆序的情况下可以考虑用栈数据结构(具有先进后出的特点)进行操作

LeetCode 2

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = tail = ListNode(0)
        c = 0
        while (l1 or l2 or c != 0):
            a = l1.val if l1  else 0
            b = l2.val if l2  else 0
            temp = a + b + c
            c = temp // 10
            tail.next = ListNode(temp % 10)

            tail = tail.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return head.next

LeetCode 445

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1 = []
        stack2 = []
        while(l1):
            stack1.append(l1.val)
            l1 = l1.next
        while(l2):
            stack2.append(l2.val)
            l2 = l2.next
        dummy = ListNode(0)

        c = 0
        while(len(stack1) > 0 or len(stack2) > 0 or c != 0):
            a = stack1.pop() if len(stack1)>0 else 0
            b = stack2.pop() if len(stack2)>0 else 0
            s = a + b + c
            c = s // 10
            temp = ListNode(s % 10)

            p = dummy.next
            dummy.next = temp
            temp.next = p
        return dummy.next

二分搜索

一般的方法用于搜索有序递增的速度里面的某一个目标值,在写二分算法时,需要注意的是循环的条件以及各种不同情况下上下界的变化,具体需要注意以下3点:

  • 搜索区间的开闭情况,以及跳出循环的条件是否满足题意
  • 循环体内不同情况下,上下界的处理方法
  • 处理潜在的数组越界问题

left = mid 有可能造成死循环,因为m是下取整,取不到right

练习Leetcode 035:

题目

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
链接:https://leetcode-cn.com/problems/search-insert-position

下面提供两种解法,注意 循环结束条件中 left 和 right 的关系,更新 left 和 right 位置时要不要加 1 减 1

class Solution:
def searchInsert(self, nums, target: int) -> int:
if len(nums) == 0: return 0
left, right = 0, len(nums) - 1
while (left + 1 < right):
m = (left + right) // 2
if nums[m] == target:
return m
elif nums[m] < target:
left = m
else:
right = m
if target <= nums[left]:
return max(left - 1, 0)
elif target <= nums[right]:
return right
else:
return right + 1

def searchInsert1(self, nums, target: int) -> int:
if len(nums) == 0: return 0
left, right = 0, len(nums) - 1
while (left <= right):
m = (left + right) // 2
if nums[m] == target:
return m
elif nums[m] < target:
left = m + 1
else:
right = m - 1
return left

小记链表编程题

链表有关的一些编程题的小技巧包括

第1、使用哨兵头节点。这有利于某些判断以及最终结果的返回,或者对原始链表做一些更改等操作。

第2、通过画图来分析某个操作的指针,交换赋值过程,凭空想象容易出现混乱。

Leetcod 147 链表的插入排序

个人AC代码如下

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        res = ListNode(0)
        res.next = pre = head
        cur = head.next

        while(cur):
            if pre.val < cur.val:
                pre, cur = cur, cur.next
                continue
            else:
                p = res
                q = p.next
                while(q.val < cur.val):
                    p = q
                    q = q.next
                pre.next = cur.next
                p.next = cur
                cur.next = q
                cur = pre.next
        return res.next

算法学习:递归与回溯、主定理证明与复杂度分析

递归算法的复杂度分析

迭代分析

公式分析

以上是定理称为主定理,具体简单的证明如下:

上述的证明过程是在百度文库上找到的一个PPT所提供的证明,过程比较精彩。

体现了算法复杂性评价里面的一些概念定义。

渐近上界记号O

设函数f(n)和g(n)是定义在非负整数集合上的正函数,如果存在两个正常数c和n0,使得当n≥n0时,有f(n)≤cg(n),则记做f(n) = O(g(n)),

Ω记号(渐近下界记号)

定义2-2    设有函数f(n)和g(n)是定义在非负整数集合上的正函数,如果存在两个正常数 c和n0,使得当n≥n0时,有f(n)≥c g(n),则记做f(n) = Ω (g(n)).

θ记号(紧渐近界记号)

设有函数f(n)和g(n)是定义在非负整数集合上的正函数,如果存在正常数c1,c2和n0,使得当n≥n0时,有c1 g(n)≤f(n)≤c2 g(n),则记做f(n) = θ(g(n)),称为θ记号(Theta notation)

回溯问题模板与套路

Reference

Leetcode 93 回溯法 IP复原问题

看到这一题就能想到的一个思路,就是用回溯法在搜索树中搜索所有符合条件的结果。回溯法关键在于如何定义回溯函数的参数。

第一、因为Ip地址分为4段,在回溯的过程中需要存储临时的一些结果,采用数组来存储这些结果的话,数组的长度就是表示Ip地址的段数,并且可以作为而回溯结束的一个判别标志。

第二在不同阶段每次进入回溯函数里面处理的字符串应该是不同的,所以当前处理的字符串也可以做一个参数。

def recurrent_traceback(s, temp):
    '''s 当前待处理的字符串'''
    '''temp 当前的临时结果'''
    if len(s) == 0 and len(temp) == 4:
        print(".".join(temp))
    elif len(s) > 0 and len(temp) < 4:
        if s[0] == "0":
            recurrent_traceback(s[1:], temp + ["0"])
        else:
            for i in range(min(3,len(s))):
                p = s[:i + 1]
                n = s[i + 1:]
                if  int(p) <= 255 :
                    recurrent_traceback(n, temp + [p])

recurrent_traceback(s, [])

代码中需要注意的一个细节就是Ip地址的数字不能以0打头如023.1.1.3,除非该段的数字就是0,应该是0.23.1.13或者其他满足条件的地址。

数据库的一道笔试题编程题分享

本人在本地没有数据库的环境,并且这道题所用的数据库系统是SQLite,不是MySQL、Oracle、SQLServer等数据库,可能在函数库会有一些区别。因此我找到了网上的一个在线数据库调试的一个工具SQL Fiddle。在这个平台上可以很方便的对各种类型的数据库进行建表、插入、查询等操作。

本人对这道题的思考方式是首先对订单表格进行,按用户的Id进行聚类group by操作,然后用一个average函数来对cost进行聚合,求平均的订单花费,接着将两个表进行连接,由于要求输出所有的用户,即使用户没有历史订单,因此需要,将用户表左连接上刚才聚合出来的结果,并且将缺省值设置为0,这样才能符合题目的要求。

select user1.uid,name, ifnull(temp.avg_cost,0) as avg_cost from (
    user1 left outer join(
    select uid, round(avg(cost),1) as avg_cost from order1 group by uid) temp 
    on temp.uid=user1.uid) 
    order by avg_cost desc, user1.uid asc

这个sql语句里面有趣的问题在于,通过average聚合 操作查询的临时结果是作为左连接的一个右项,所以要对临时结果进行重新命名,上述代码重新命名成temp,这样才好书写on连接条件。

这是本人的简介,可能没有在查询性能上做更多的考量。

在SQL Fiddle上调试的结果如下:

CREATE TABLE user1(
     uid integer primary key, 
     name varchar(20));

INSERT INTO user1 VALUES (1, 'Amy');
INSERT INTO user1 VALUES (2, 'Ben');
INSERT INTO user1 VALUES (4, 'David');
INSERT INTO user1 VALUES (3, 'Cindy');

CREATE TABLE order1(
     orderid integer primary key,
     uid integer,
     cost float,
     hotelid integer);

INSERT INTO order1 VALUES (1,1,2,1);
INSERT INTO order1 VALUES (2,1,4,1);
INSERT INTO order1 VALUES (3,1,5,1);
INSERT INTO order1 VALUES (4,2,44,1);
INSERT INTO order1 VALUES (5,2,40.5,1);
INSERT INTO order1 VALUES (6,3,44,1);
INSERT INTO order1 VALUES (7,3,40.5,1);