灯的个人博客

forever young,forever weeping.

0%

发表于 更新于 分类于

题目

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

假设你有 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
    }
}

思路

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

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

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

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

来源

发表于 更新于 分类于

##

给定一个 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 一个有符号，一个无符号，导致在第一个版本的时候，写了很多冗余代码处理这个问题。

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

来源

发表于 更新于 分类于

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

运算 二进制
x
x && y 0x01
x || y 0x01
x &&~y 0x01

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

1
2
3
4
int equal_val(int x, int y)
{
    return !(x ^ y);
}

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

x x x <<3 x <<3 x >>2(逻辑的) x >>2(逻辑的) x >>2(算术的) x >>2(算术的)
十六进制 二进制 二进制 十六进制 二进制 十六进制 二进制 十六进制
0xc3 11000011 00011000 0x18 00110000 0x30 11110000 0xf0
0x75 01110101 10101000 0xA8 00011101 0x1d 00011101 0x1d
0x87 10000111 00111000 0x38 00100001 0x21 11100001 0xe1
0x66 01100110 00110000 0x30 00011001 0x19 00011001 0x19

正确性未确认

发表于 更新于 分类于

给出位向量的布尔运算

运算 二进制
a [01101001]
b [01010101]
~a [10010110]
~b [10101010]
a&b [01000001]
a|b [01111101]
a^b [00111110]

发表于 更新于 分类于

题目

给定一个包含 [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
    }
}

来源

发表于 更新于 分类于

有效的括号

题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 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

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

链接

发表于 更新于 分类于
n 2^n 十进制 2^n 十六进制
9 512 0x200
19 524288 0x80000
14 16384 0x4000
16 65535 0x10000
17 131070 0x20000
5 32 0x20
7 128 0x80

卧槽，算错那么多

十进制 二进制 十六进制
0 0000 0000 0x00
167 1010 0111 0xA7
62 0011 1110 0x3E
188 10111100 0xBC
55 00110111 0x37
136 10001000 0x88
243 11110011 0xF3
82 01010010 0x52
172 10101100 0xAC
231 11100111 0xE7

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

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

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

完了，还是那么粗心。。

发表于 更新于 分类于

p-26-1

将 0x39A7F8 转换为二进制

16 2
3 0011
9 1001
A 1010
7 0111
F 1111
8 1000

001110011010011111111000

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

16 2
C 1100
9 1001
7 0111
B 1011

0xC97b

将 0xD5E4C 转换为二进制

16 2
D 1101
5 0101
E 1110
4 0100
C 1100

11010101111001001011

将 1001101110011110110101 转化为十六进制

16 2
2 0010
6 0110
E 1110
7 0111
B 1011
5 0101

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

其他

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

表结构

用户积分记录表

字段 类型 含义
id primary key 主键
uid bigint 用户 id
source_type tinyint 积分来源类型
source_id int 积分来源 id
socre int 分值
rest_score datetime 剩余积分
action_uid bigint 操作人
reason varchar 原因
exprie_time datetime 过期时间
create_time datetime 创建时间
update_time datetime 更新时间
delete_time datetime 删除时间

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

字段 类型 含义
id primary key 主键
uid bigint 用户 id
socre int 分值
create_time datetime 创建时间
update_time datetime 更新时间
delete_time datetime 删除时间