头像

肆十一


访客:6660

离线:1个月前



肆十一
3个月前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

def lowbit(x):
return x & -x

if name == ‘main’:
n = int(input())
nums = list(map(int, input().split()))
for i in range(n):
res = 0
x = nums[i]
while x:
x = x - lowbit(x)
res += 1
print(res, end = ” “)



活动打卡代码 AcWing 84. 求1+2+…+n

肆十一
6个月前
class Solution(object):
    def getSum(self, n):
        """
        :type n: int
        :rtype: int
        """
        return (1 + n) * n // 2



肆十一
6个月前
import heapq


class Solution:
    """
    利用最大堆和最小堆求解
    保证最大堆中的元素都小于最小堆的元素,因此:
    总数为偶数时:mid = (maxheap[0] + minheap[0]) / 2
    总数为奇数时:mid = minheap[0]
    """

    def __init__(self):
        self.maxheap = []
        self.minheap = []
        self.maxHeapCount = 0
        self.minHeapCount = 0

    def insert(self, num):
        # 判断 最大堆 和 最小堆 中的元素数量
        if self.maxHeapCount > self.minHeapCount:  # 在最小堆中插入元素
            self.minHeapCount += 1
            if num < -self.maxheap[0]:
                heapq.heappush(self.minheap, -heapq.heappop(self.maxheap))
                heapq.heappush(self.maxheap, -num)
            else:
                heapq.heappush(self.minheap, num)
        else:
            if self.maxHeapCount == 0:
                heapq.heappush(self.maxheap, -num)
            else:
                if num > self.minheap[0]:
                    heapq.heappush(self.maxheap, -heapq.heappop(self.minheap))
                    heapq.heappush(self.minheap, num)
                else:
                    heapq.heappush(self.maxheap, -num)
            self.maxHeapCount += 1

    def getMedian(self):
        if self.maxHeapCount > self.minHeapCount:
            return -self.maxheap[0]
        else:
            return (self.minheap[0] - self.maxheap[0]) / 2


if __name__ == "__main__":
    solution = Solution()
    inputs = [-3, -1, 1, 0, -4]
    for item in inputs:
        solution.insert(item)
        print(solution.getMedian())




肆十一
6个月前

前言

终于完成了微软的所有面试,安心等待面试结果了。

AA 面遇到一个字符串匹配的问题,闫神算法基础课中的动态规划部分给了很大的启发,所以将思路写出来给大家分享下,也是作为课程的反馈吧,十分感谢。

注意:算法并没有经过完整的样例测试,可能存在一些细节问题,请见谅。

问题描述

给定一个字符串和一个包含通配符 *? 的模版,判断给定的模版和字符串是否是可匹配的。其中 * 可以匹配 0 个或任意多个字符,? 可以匹配 0 个或 1 个字符。

样例

text = "readme.txt"
pattern = "r*e.t?t"

此时:
* ==> "eadm"
? ==> "x"
所以字符串和模版是可匹配的,返回 True

问题分析

首先分析 corner case

  1. 字符串和模版都为空,直接返回 True
  2. 字符串和模版存在一个为空,另一个不为空,直接返回 False

剩下就是考虑字符串和模版都不为空的情况,可以发现字符串的匹配是无后效性的,即如果当前字符串子串和模版子串是匹配的,后续的字符并不会影响这两个子串的匹配情况。因此,我们可以采用动态规划来对问题进行求解,dp[i][j] 表示以模版的第 i 个字符结尾,以字符串的第 j 个字符结尾的两个子字符串是否匹配,则一共有三种情况:

  1. pattern[i] == text[j] ,此时 dp[i][j] = dp[i-1][j-1]
  2. pattern[i] == "?" ,此时可以匹配 0 或 1 个字符, dp[i][j] = dp[i-1][j] or dp[i-1][j-1]
  3. pattern[i] == "*" ,此时可以匹配 0 或任意多个字符,则有 dp[i][j] = dp[i-1][j] or dp[i-1][j-1] or ... dp[i-1][0]

这里为了省去画图的麻烦,就不用闫神那种集合划分的来解释了。

问题求解

Python 版本

def match(text, pattern):
    if not text and not pattern:
        return True
    elif not text or not pattern:
        return False
    else:
        n = len(text)
        m = len(pattern)
        text = "0" + text
        pattern = "0" + pattern
        dp = [[False] * (n+1) for i in range(m+1)]
        dp[0][0] = True
        for i in range(1, m+1):
            for j in range(1, n+1):
                if pattern[i] == text[j]:
                    dp[i][j] = dp[i-1][j-1]
                elif pattern[i] == "?":
                    # 匹配 0 或 1 个字符
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-1]
                elif pattern[i] == "*":
                    dp[i][j] = dp[i-1][j]  # 匹配 0 个字符
                    for k in range(j, -1, -1):
                        dp[i][j] = dp[i][j] or dp[i-1][k]  # 匹配多个字符
        return dp[m][n]

if __name__ == "__main__":
    text = "readme.txt"
    pattern = "r*e.t?t"
    print(match(text, pattern))

求解优化

由于 dp 中任意的状态都仅与上一层的一侧的状态有关,所以可以对上述问题进行空间压缩,优化后的代码如下:

def match2(text, pattern):
    if not text and not pattern:
        return True
    elif not text or not pattern:
        return False
    else:
        n = len(text)
        m = len(pattern)
        text = "0" + text
        pattern = "0" + pattern
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(1, m+1):
            for j in range(n, -1, -1):
                if pattern[i] == text[j]:
                    dp[j] = dp[j-1]
                elif pattern[i] == "?":
                    dp[j] = dp[j] or dp[j-1]
                elif pattern[i] == "*":
                    for k in range(j, -1, -1):
                        dp[j] = dp[j] or dp[k]
        return dp[n]

------------------------------------许愿分割线------------------------------------------------
最后求一波微软的 offer ....




肆十一
7个月前

原文发表于个人博客:剑指offer 36:二叉搜索树与双向链表


问题描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点,只能调整树中结点指针的指向。

注意

  • 需要返回双向链表最左侧的节点。

例如,输入下图中左边的二叉搜索树,则输出右边的排序双向链表。


问题分析

我们知道二叉搜索树满足以下性质:

  • 根节点的值大于左孩子节点,小于右孩子节点;
  • 中序遍历得到的值数组是有序数组

而我们最终需要的恰好是排序好的双向链表,且双向链表和二叉树搜索相似,每个节点都存在两个指针。因此,最直观的方法是采用中序遍历的思想来解决该问题。

方案一:中序遍历

可以发现,在将二叉搜索树转化为双向链表的过程中,实际上就是在中序遍历时,将当前节点的左指针指向前一个节点,同时前一个节点的右指针指向当前节点。

由于需要在遍历的过程中进行指针的变换,我们这里采用非递归的中序遍历来解决该问题。

from collections import deque

def convert(root):
    if (not root) or (not root.left and not root.right):
        return root
    # 采用中序遍历的思想
    prev = TreeNode(0)
    head = prev  # 增加一个哨兵节点
    stack = deque()
    while root or stack:
        if root:
            stack.append(root)  
            root = root.left  # 遍历左孩子节点
        else:
            root = stack.pop()
            cur = root
            cur.left = prev  # 当前节点的左指针指向前一个节点
            prev.right = cur # 前一个节点的右指针指向当前节点
            prev = cur  # 当前节点变为前一个节点
            root = root.right  # 处理右孩子节点
    ans = head.right
    ans.left = None
    return ans

方案二:递归

我们可以将二叉搜索树转化为双向链表的过程看出三部分:根节点、左子树和右子树

则双向链表的构建实质上就是将左子树的最大节点与根节点相连,右子树的最小节点与根节点相连,然后递归处理左右子树。

针对每棵子树,我们需要该子树的最左侧的节点,以及最右侧的节点,因此递归函数 dfs(root) 返回的就应该是以 root 为根节点的子树的最小节点和最大节点 pair(lside, rside)

def convert(root):
    if not root:
        return None
    sides = dfs(root)
    return sides[0]

def dfs(root):
    if not root.left and not root.right:  # 无子节点
        return [root, root]

    if root.left and root.right:
        lside = dfs(root.left)  # 递归左子树,最右侧节点与根节点相连
        lside[1].right = root
        root.left = lside[1]

        rside = dfs(root.right) # 递归右子树,最左侧节点与根节点相连
        rside[0].left = root
        root.right = rside[0]
        return [lside[0], rside[1]]  # 最终返回最小和最大的节点

    # 只有左子树或者只有右子树的情况,最终同样范围最小和最大的节点
    if root.left: 
        lside = dfs(root.left)
        lside[1].right = root
        root.left = lside[1]
        return [lside[0], root]    
    if root.right:
        rside = dfs(root.right)
        rside[0].left = root
        root.right = rside[0]
        return [root, rside[1]]        



活动打卡代码 AcWing 23. 矩阵中的路径

肆十一
7个月前
class Solution(object):
    def hasPath(self, matrix, string):
        """
        :type matrix: List[List[str]]
        :type string: str
        :rtype: bool
        """
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if self.dfs(matrix, string, 0, i, j):
                    return True
        return False

    def dfs(self, matrix, string, u, x, y):
        if matrix[x][y] != string[u]:
            return False
        if u == len(string) - 1:
            return True
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        temp = matrix[x][y]
        matrix[x][y] = "*"
        for i in range(4):
            a = x + dx[i]
            b = y + dy[i]
            if 0 <= a < len(matrix) and 0 <= b < len(matrix[0]):
                if self.dfs(matrix, string, u+1, a, b):
                    return True
        matrix[x][y] = temp
        return False




肆十一
7个月前

个人博客:动态规划第二讲:线性DP


线性 DP 问题是指递推方程具有明显的线性关系,有一维线性和二维线性。

数字三角形

问题描述

给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入样例:

5  # 三角形的行数
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例:

30

问题分析

我们从集合的角度来对该问题进行分析:

注意

在进行状态计算的时候有两个关键点:

  1. 每行的第一个元素只能从右上转移过来;
  2. 每行的最后一个元素只能从左上转移过来。

因此需要单独将这两种情况拿出来考虑。

问题求解

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
inf = float("-inf")
dp = [[inf] * (n) for i in range(n)]
dp[0][0] = a[0][0]
for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] + a[i][j]
        elif j == i:
            dp[i][j] = dp[i-1][j-1] + a[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
print(max(dp[n-1]))

最长上升子序列

问题描述

给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。

输入样例

7
3 1 2 1 8 5 6

输出样例

4

问题分析

从集合的角度来进行分析:

我们按照第 i 个元素结尾的上升子序列的前一个元素来进行集合的划分,前一个元素可以是空,也可以是第 1 个元素,一直到第 i-1 个元素,因此一共划分为 i 个集合。状态转移方程为:

dp[i] = 1 # 前一个元素为空
for j in range(1, i):
    if a[j] < a[i]:
        dp[i] = max(dp[i], dp[j]+1)

问题求解

n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

最长公共子序列

问题描述

给定两个长度分别为 N 和 M 的字符串 A 和 B ,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入样例:

4 5
acbd
abedc

输出样例:

3

问题分析

由于涉及到两个字符串,所以需要用二维状态表示 f[i, j] ,其分析图如下:

本题的重点是在集合的划分,假定两个字符串分别为 ab ,则可以根据子序列是否包含 a[i]b[j] 将集合划分为四种情况:

  1. 子序列不包含 a[i]b[j] ,用 00 表示,其对应了状态表示 f[i-1, j-1]
  2. 子序列包含 b[j] ,但不含 a[i] ,用 01 表示;
  3. 子序列包含 a[i] ,但不含 b[j] ,用 10 表示;
  4. 子序列包含 a[i]b[j] ,用 11 表示,其对应了状态表示 f[i-1, j-1]+1

关键点是如何计算中间两种的状态表示,因为 f[i-1, j] 表示的集合是包含 01 部分的集合,且被整个集合 f[i, j] 包含的,而且我们是求 f[i, j 中的最大值,因为我们完成可以将 01 部分的集合放大为 f[i-1, j] ,并不影响我们的最大值。同理,10 部分的集合就对应了状态表示 f[i][j-1]

同时我们可以发现 f[i-1, j] 是包含 f[i-1, j-1] 的,且 11 成立的条件是 a[i] == b[j]

动态规划问题求最大值和最小值是集合可重复的,但不能漏元素。

问题求解

n, m = map(int, input().split())
a = input()
b = input()

dp = [[0] * (m+1) for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # 01 和 10 的情况
        if a[i-1] == b[j-1]:  # 11 的情况
            dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
print(dp[n][m])




肆十一
7个月前
n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if a[j] < a[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))


活动打卡代码 AcWing 898. 数字三角形

肆十一
7个月前
n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
inf = float("-inf")
dp = [[inf] * (n) for i in range(n)]
dp[0][0] = a[0][0]
for i in range(1, n):
    for j in range(i+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] + a[i][j]
        elif j == i:
            dp[i][j] = dp[i-1][j-1] + a[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
print(max(dp[n-1]))


活动打卡代码 AcWing 9. 分组背包问题

肆十一
7个月前
from collections import defaultdict
N, V = map(int, input().split())
items = defaultdict(list)
for i in range(1, N+1):
    s = int(input())
    for j in range(s):
        v, w = map(int, input().split())
        items[i].append((v, w))
dp = [[0] * (V+1) for i in range(N+1)]

for i in range(1, N+1):
    for j in range(1, V+1):
        dp[i][j] = dp[i-1][j]
        k = 0
        while k < len(items[i]):
            if items[i][k][0] <= j:
                v_ik = items[i][k][0]
                w_ik = items[i][k][1]
                dp[i][j] = max(dp[i][j], dp[i-1][j-v_ik]+w_ik)
            k += 1
print(dp[N][V])