某公司常见题刷题笔记

LeetCode搞起来，虽说和实际业务没啥联系，但现在就卷起来了，没办法被迫卷起来。

1，滑动平均值，官网

给定窗口大小size，然后每次增加一个值value放入窗口，求此窗口内的平均值

class MovingAverage:
    def __init__(self, size: int):
        self.size = size
        self.sum = 0
        self.q = deque()
    def next(self, val: int) -> float:
        if len(self.q) == self.size:
            self.sum -= self.q.popleft()
        self.sum += val
        self.q.append(val)
        return self.sum / len(self.q)

2，正则匹配，力扣网

用*可以表示与前面的字母相同的字母，比如a*与aa是匹配的；用.可以表示任意字符，比如a.与ab是匹配的。由于要匹配的字符串长度是未知的，匹配字段长度与前者长度可存在差异，所以dp无疑

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)#s是字符串长度
        def matches(i: int, j: int) -> bool:
            if i == 0:
                return False
            if p[j - 1] == '.':
                return True
            return s[i - 1] == p[j - 1]
        f = [[False] * (n + 1) for _ in range(m + 1)]
        f[0][0] = True
        for i in range(m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    f[i][j] |= f[i][j - 2]
                    if matches(i, j - 1):
                        f[i][j] |= f[i - 1][j]
                else:
                    if matches(i, j):
                        f[i][j] |= f[i - 1][j - 1]
        return f[m][n]

3,有效的数独，网页

判断9*9的数组是否是有效的数独，9*9分成3*3的大网格，每个网格都是3*3,1~9在此网格中只能出现一次，在9*9的每一行和每一列也只能出现一次。给定的.是空值（空白的），给定的数字是已知的，判断给定的数字是否是有效的数独。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][9];
        int[][] columns = new int[9][9];
        int[][][] subboxes = new int[3][3][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

4，买卖股票的最大利润，link

给定数组prices，其中数字是当天收盘价格，可选择买入和卖出。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}

5，盛水最多，web link

此题不同于接雨水，给定边缘高度heights，找出其中两个边，使其满足其中盛水最多。

 6，整数转罗马数字，website link

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
 
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

class Solution:
 
    THOUSANDS = ["", "M", "MM", "MMM"]
    HUNDREDS = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
    TENS = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
    ONES = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
 
    def intToRoman(self, num: int) -> str:
        return Solution.THOUSANDS[num // 1000] + \
            Solution.HUNDREDS[num % 1000 // 100] + \
            Solution.TENS[num % 100 // 10] + \
            Solution.ONES[num % 10]

7，吃糖果，link

n个糖果，其中类型在candyType中，其长度为n，set()后得到的个数即为类型个数，医生建议最多吃n/2个，其中n为偶数，那么最多吃到的类型有几个？这不是最简单的么，果然是。

class Solution:
    def distributeCandies(self, candyType: List[int]) -> int:
        length=len(candyType)
        types=set(candyType)
        type_num=len(types)
        return min(length//2,type_num)

8，最长递增子序列，link

此题是最长递增子序列而非枚举所有的递增子序列

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

愿我们终有重逢之时，而你还记得我们曾经讨论的话题