题目

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 231 - 1

解法

个人解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn first_bad_version(&self, n: i32) -> i32 {
        let mut left = 0;
        let mut right = n;
        let mut first_false = n;
        while left < right {
            let mid = left + (right - left) / 2;
            let is_bad = self.isBadVersion(mid);
            if is_bad {
                right = mid;
                if first_false > mid {
                    first_false = mid;
                }
            } else {
                left = mid + 1;
            }
        }

        first_false
    }
}

示例解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

impl Solution {
    pub fn first_bad_version(&self, n: i32) -> i32 {
        let mut left = 1;
        let mut right = n;
        while left < right {
            let mid = left + (right - left >> 1);
		    if self.isBadVersion(mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        left
    }
}

思路

写完后看示例解题，发下思路还不是很清晰

查找到的数据跟自己想的补太一样

还一个是处理越界的方案，最开始没有处理好。

然后除以二，可以用位移实现

来源

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/first-bad-version
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

##

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

题解

笨比版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        if nums.len() == 0 {
            return -1;
        }
        let mut left = 0;
        let mut right = nums.len() - 1;
        let mut mid = nums.len() / 2;
        while left <= right {
            if left == right {
                if nums[left] == target {
                    return left as i32;
                } else {
                    return -1;
                }
            }
            let c = *nums.get(mid).unwrap();
            if c == target {
                return mid as i32;
            } else if c < target {
                left = mid + 1;
                mid = (left + right) / 2
            } else {
                right = mid - 1;
                mid = (left + right) / 2
            }
        }
        -1
    }
}

优化过后版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left: usize = 0;
        let mut right: usize = nums.len() - 1;
        while left < right {
            let mid = (left + right) / 2;
            if nums[mid] < target {
                left = mid + 1;
            } else if nums[mid] > target {
                right = mid;
            } else {
                return mid as i32;
            }
        }
        -1
    }
}

思路

最主要的困难点在于边界问题的处理

以前一直有这个问题，不过是用的弱类型的语言，所以一直没啥问题

这次用 rust 写，i32 跟 usize 一个有符号，一个无符号，导致在第一个版本的时候，写了很多冗余代码处理这个问题。

然后发现边界处理，可以在循环外层解决，左闭右开的方式

来源

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/binary-search
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

x=0x66 y = 0x39 计算下列值

用位运算与逻辑运算，实现一 x==y

1
2
3
4

int equal_val(int x, int y)
{
    return !(x ^ y);
}

位移运算，假设只有只有八位的位移情况

正确性未确认

给出位向量的布尔运算

题目

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

思路

看到题目的时候靠直觉去写，就是循环 0-n，然后判断 n 在不在，不在就抛出，循环完后，还没找到，返回数组的长度

时间复杂度 n^2

发现可以用等差数列去做，计算等差数列的和，然后去掉数组内的数，最终的结果为缺失的数

还一个是用异或的方案

数组的数与0-n的数，全部进行异或，最终的数据为缺失的数

题解

自己实现的

1
2
3
4
5
6
7
8
9
10
11
12

impl Solution {
    pub fn missing_number(nums: Vec<i32>) -> i32 {
        for i in 0..nums.len() as i32 {
            if nums.contains(&i) {
                continue;
            } else {
                return i;
            }
        }
        nums.len() as i32
    }
}

看到别人题解后优化

1
2
3
4
5
6
7
8
9
10

impl Solution {
    pub fn missing_number(nums: Vec<i32>) -> i32 {
        let num_size: i32 = nums.len().try_into().unwrap();
        let mut total = (1 + num_size) * num_size / 2;
        for i in nums.iter() {
            total -= i;
        }
        total
    }
}

来源

• 作者：力扣 (LeetCode)
• 链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnj4mt/
• 来源：力扣（LeetCode）
• 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

有效的括号

题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

题解

个人题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = Vec::new();
        for c in s.chars() {
            if c == '{' {
                stack.push('}')
            } else if c == '[' {
                stack.push(']')
            } else if c == '(' {
                stack.push(')')
            } else {
                if let Some(i) = stack.pop() {
                    if i == c {
                        continue;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        stack.is_empty()
    }
}

官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#[allow(dead_code)]
impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut res: Vec<char> = Vec::with_capacity(s.len());
        let mut pre: Option<&char>;
        for c in s.chars() {
            pre = res.last();
            match (pre, c) {
                (Some('{'), '}') | (Some('['), ']') | (Some('('), ')') => {
                    res.pop();
                }
                _ => res.push(c),
            }
        }
        res.is_empty()
    }
}

思路

原本也没啥思路，就想着怎么处理字符串

然后发现解答里面有关于栈的问题，看了别人的解体思路后，比较明朗

匹配到左括号，向栈推入右括号

如果匹配到右括号，就把栈顶的括号推出，判断是不是为当前的右括号，如果是，代表括号闭合，如果不是，直接失败

匹配到右括号空栈也直接失败

最后判断栈的长度是不是为 0，如果为 0，代表完全匹配

emm

示例的代码写的比较精简，感觉可以复现一次

链接

• 作者：力扣 (LeetCode)
• 链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnbcaj/
• 来源：力扣（LeetCode）
• 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

卧槽，算错那么多

草，还是得用计算器？？？？

• 0x503c + 0x8 = 0x5044
• 0x503c - 0x40 = 0x50FC(0x4FFC)
• 0x503c + 64 = 0x507c
• 0x50ea - 0x503c = 0x50Ae(0xAE)

别做卷子了，废物，这都能错俩，还特么检查，你有脸检查？？？

完了，还是那么粗心。。

p-26-1

将 0x39A7F8 转换为二进制

001110011010011111111000

将二进制 1100100101111011 转化为十六进制

0xC97b

将 0xD5E4C 转换为二进制

11010101111001001011

将 1001101110011110110101 转化为十六进制

0x26e7B5

积分表结构设计

需求

• 记录积分行为来源
• 允许撤销用户积分
• 个人中心有展示总积分
• 未来积分可以兑换商品
• 未来积分逐条过期机制

分析

记录积分行为来源

• 需要增加行为枚举类，并且记录该行为对应的表主键，比如发帖需要对应发帖的内容 id
• 行为增加的分数，考虑到变动很少，可以放在代码中。如果后期确认该需求经常变动，需要建立对应的表结构，映射该枚举数据

1
2
3
4
5
6
7
8
9
10
11
12

// 积分枚举
enum ScoreSourceTypeEnum {
  LIKE = 1,
  COMMENT = 2,
  // ...
}
// 积分对应分数
const ScoreSourceTypeMap = new Map({
  [ScoreSourceTypeEnum.LIKE]: { score: 5, title: "点赞" },
  [ScoreSourceTypeEnum.COMMENT]: { score: 10, title: "评论" },
  // ...
});

允许撤销用户积分

• 撤销用户积分不能修改原始数据，应增加一条新纪录记录该行为，积分记录表允许负值或新建一个表记录数据(先采用允许负值方案)
• 撤销用户积分需要增加操作人，撤销的原因两个字段
• 增加一个撤销用户积分的行为，行为对应的主键为对应的积分记录 ID

积分逐条过期机制

• 积分记录表增加剩余积分字段，默认等于当前积分
• 用户消费积分时，判断剩余积分字段相加是否满足需求，如果满足，按时间倒序挨个去扣除剩余积分字段，直到扣除完毕
• 统计用户积分时，SUM（剩余积分）
• 每天跑一次定时任务，每次用户积分过期，剩余积分字段设置为 0

个人中心展示总积分

• 每次查询用户的积分数据，都需要 sum 方法，如果数据量多，性能会比较差
• 是否需要直接统计用户的积分，每次插入或删除去修改该数据
• 如果需要用户总积分，应独立于用户模块，新建一张表，统计用户总积分，以及用户积分相关数据

未来积分可以兑换商品

• 积分记录表增加商品兑换的行为，并记录订单 id

其他

• 并发问题（如果用户同时访问数据，一边增加一边消费，是否需要在数据库加锁，或使用单个消息队列来实现）
• 积分异常（如果突然出现大批量积分发放，每天应有积分监控功能，每日发放积分、扣减积分，总积分数据）

表结构

用户积分记录表

用户积分表(暂时不使用，数据库无法支撑再考虑)

不知道应该写点什么。

想到哪 写到哪吧。

都会有一段令人铭记在心的记忆，随着时间的流逝，逐渐变淡

已经感觉到了

最开始

后来

现在

嗯，这种情况也许不会持续很久。

也许到了说再见的时候

不知道是不是最坏的结果

但应该不是最好的

但

总是有些东西，在夜深人静的时候会想起来

想起来 就一阵难过

为什么当时热恋的两个人

到现在

em，可能分离两地的结果就是这样子吧

自己也没想着尝试改变什么

按班就不

一步步走到那个阶段

是你自己选择的

不应该埋怨什么

你当时做这件事情的时候 已经预见到了结果

这不是如你所愿

感性吗

不应该

应该是活该

晚上总是瞎J8想

就这吧

还有吗

木有了，就这。

希望她有更好的生活