轮转数组

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

进阶：

尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

题解

系统 api

1
2
3
4
5
6
7

// rust api
impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let len = nums.len();
        nums.rotate_right(k as usize % len);
    }
}

直觉实现，效率低到难以接受

1
2
3
4
5
6
7
8

impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        for _i in 0..(k as usize % nums.len()) {
            let v = nums.pop().unwrap();
            nums.insert(0, v)
        }
    }
}

优化后，仍效率不太高

1
2
3
4
5
6
7
8
9
10
11

impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let mut rotate_len = k as usize;
        if nums.len() < rotate_len {
            rotate_len = rotate_len % nums.len();
        }
        println!("{:?}", rotate_len);
        let mut v: Vec<i32> = nums.splice(0..(nums.len() - rotate_len), vec![]).collect();
        nums.append(&mut v)
    }
}

来源

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

题目

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

题解

直觉解法（最快）

1
2
3
4
5
6
7

impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut v = nums.iter().map(|x| x * x).collect::<Vec<i32>>();
        v.sort();
        v
    }
}

双指针，插入（最慢）

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

impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut left = 0;
        let mut right = nums.len() - 1;
        let mut result = Vec::new();
        while left <= right {
            let left_suqare = nums[left].abs().pow(2);
            let right_suqare = nums[right].abs().pow(2);
            if left_suqare < right_suqare {
                result.insert(0, right_suqare);
                right = right - 1;
            } else {
                result.insert(0, left_suqare);
                left = left + 1;
            }
        }
        result.reverse();
        result
    }
}

双指针后插入后，翻转

impl Solution {
    pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
        let mut left = 0;
        let mut right = nums.len() - 1;
        let mut result = Vec::new();
        while left <= right {
            let left_suqare = nums[left].abs().pow(2);
            let right_suqare = nums[right].abs().pow(2);
            if left_suqare < right_suqare {
                result.insert(0, right_suqare);
                right = right - 1;
            } else {
                result.insert(0, left_suqare);
                left = left + 1;
            }
        }
        result.reverse();
        result
    }
}

来源

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

时至今日，你依然是我心中的光。

em，可惜了。

太难了啊。。

我已经好像 em 太少了会em

想的太多了

太计较得失

很难再去全力做那样一件事

em

时至今日啊

好像从来没有过

内心

自卑啊

em

确实挺卑微的

嗨

不知道脑子再想什么

突然就是觉得应该写点什么

老样子，想到哪写到哪

有时候会觉得有些孤单啊

想找个人陪着

但好像em

都木有什么好结果啊

是不是得忍受一些寂寞

稍微对你好一点

内心就开始躁动

你应该知道，什么是正确的选择

em

确实需要

不应该

已经决定了

不

俺也不知道

迷茫的很啊

什么是对的

内心坚持的

对的吗

不知道

嗯，能让自己舒服点

克制

没有完全克制

还是有骚动

却不敢

君子论迹不论心？

不

只是我

直面自己的想法

她

冬天了吧

没有可能 再次

确实很好

我

有问题

犹豫不决

嗯

可能

不知道

就这样子吧

也挺好

理一下思路

初恋

我不成熟，她对我有好感，可能是刚好，我也是？嗯，应该是喜欢的，刚好，念念不忘那么多年，应该是第一份感情的原因吧，放下了。

高中的那个女孩子

笑起来特别好看，可惜。

大学的那个人

em

刚好吧，已经回忆不起来当时的感觉了，她很努力，也尽力了，她应该这么做，不值得。做的是对的，哪怕后来，不明白她的想法，愧疚。。还是其他？不明白。说我心太狠了，确实。我已经没有留恋的地方了。从什么时候开始？记不清楚了，不应该再次联系的，可能她也很辛苦吧，嗯，应该是很辛苦，不然不会这样子。嗯，我变了吗。不，可能一直是这样子，只是不再是她。确实有点人渣 ，不知道是不是对的。不，对的。不应该再继续了，保留那些美好的记忆吧。

大学

哈哈，一个。二。em，是的。单纯的二，了解不深，当时确实蛮喜欢？应该是了，不然不会那么在意，祝福她吧，写到这里的时候，竟然没想起来她，看来，不应该。。不应该，希望她也幸福，她值得。不怪什么，木有再来一次，况且真的再来一次，会是好的吗。

她，我比较变态？确实变态，男人啊，都是管不住下半身的动物，傻逼。如果真的有，你，em，可能还是，真特么是头牲口，直面内心，如果有机会你会继续吗？会，嗯，甚至每次都有一些期望。。。你果然是一头。。。对吗？不知道，大概率不对吧。。em算了，过去了。。决定一些事情，不摇再有期望，不要再当牲口了。

花？我也不知道，可能，只是单纯的寂寞了，刚好的出现了，em，太多次了，男人啊，克制住你的寂寞，确实有点狗，谁不是呢，应该也结婚了吧。开心的走下去吧

emmmm，下次不要当神经病了，傻逼，玩玩吗，她也是吧？em，两颗焦动的心啊，凑一起了，真的狗。。你也太狗了，太狗了

做了一个正确的决定，em

她，那么多的坏脾气，你，那么多的受气包。。。喜欢吗。喜欢啊，可爱的妹子。。她应该，em，刚好我出现了吧。后面，不知道。。也许有一些依赖吧，只是我当了牲口。对吗，对我来说对的。对她来说呢，对的。决定正确吗，正确。她好，我也好。她知道的，她做的决定，em，但是你知道，你的内心得不到安宁，这些有你的原因。曾经想过就她了，可。。 em她是，我也是，财迷。。。挺好的，应该是正确的决定吧。她值得更好的。哪天结束了，。。em，还是有些难过，回忆又涌了上来。。。你尽力了吗？没有。你对她好吗？自认没有亏欠。有愧疚吗？有一些。这个排比不通顺，你尽力了吗，应该放最后面。做到了一部分吧，果然我已经很难去全力em，是的。。。做了一半吧。100分打多少？不重要了，没有愧对她，某一些方面，你活该。活该，活该。。你做的那些事情，只有你自己知道，哪怕是她自己选的，哪怕是对的。这会是你心里的一根刺。。

小姑娘？只是你内心开始骚动了，是骚动了。是不对的，也没有可能的。为什么还这么做呢？快乐？是快乐吧。为什么？耐不住寂寞。结果是什么，木有结果。你应该怎么做，嗯，不越线，做该做的事情。。不要再有期望，哪怕你内心依然。好像哪里怪怪的。你依然管不住你骚动的内心啊。。牲口。。。就这样子吧。。不要越线，不主动，不负责，傻逼。。。哈哈哈哈，你配吗。 膨胀的一批。傻逼。傻逼。傻逼。知道应该做什么了吗。em，决定点什么？？yeah，不可能。只是因为开心。有个好心情。可以，很合理。

她，对的，牲口当一次就够了。。希望她能好起来。。。希望她以后不要在受苦了。。已经那么难了。。照顾好自己啊。。照顾好自己。。已经这么难了，不要再为难她了好不好。。。。 em，。你这个人啊。。。自我感动的样子真是太傻逼了。

我能做些什么吗。。

em 陪她聊聊天吧。可是她好像。。。我应该问问

大概就这样子了吧

可能还有一些骚动的经历，啊。。。。

高中时候的你，还真是。。。狗啊。。。

狗啊。。。

真的狗。。

难道那就是我喜欢的类型？emm，不不不。。。你什么都不知道。谈什么喜欢？你知道自己喜欢什么吗。没有。。。

甚至脑子里面连一幅画都没有，也许。。。她出现的那天？画里面的人就是她？？

可能吧。。。

梦里那个人的样子一直没有记忆，只是温馨。。

长大后再也没做过这种梦了吧。。

如果哪天，我能遇到，。

不了。

不再有期望了

我不配

人心深处的黑暗，太可怕了。。。

估计我再也不能理直气壮的对未来的她讲起我的过往了

就这样子吧

我知道，也许不只是我。。。

嗨，不要去窥探。。。

希望明天是美好的一天，see you。

对了，

你要耐得住寂寞，骚动的心啊，是时候开始缓一缓了。。

不知道

也不要再期望了。

希望有一天啊

…………有一天啊。。。

对的，猜猜这时候你再想什么。

题目

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

假设你有 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）
• 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。