用两个栈实现队列

题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
[“CQueue”,”appendTail”,”deleteHead”,”deleteHead”,”deleteHead”]
[[],[3],[],[],[]]
输出：[null,null,3,-1,-1]
示例 2：

输入：
[“CQueue”,”deleteHead”,”appendTail”,”appendTail”,”deleteHead”,”deleteHead”]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用

题解

原生方法

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

use std::collections::VecDeque;

struct CQueue {
    stack: VecDeque<i32>,
}

impl CQueue {
    fn new() -> Self {
        CQueue {
            stack: VecDeque::new(),
        }
    }

    fn append_tail(&mut self, value: i32) {
        self.stack.push_front(value);
    }

    fn delete_head(&mut self) -> i32 {
        let v = self.stack.pop_back();
        match v {
            Some(v) => v,
            None => -1,
        }
    }
}

双 vec

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

#[derive(Default)]
struct CQueue {
    stack1: Vec<i32>,
    stack2: Vec<i32>,
}

impl CQueue {
    fn new() -> Self {
        Self::default()
    }

    fn append_tail(&mut self, value: i32) {
        self.stack1.push(value);
    }

    fn delete_head(&mut self) -> i32 {
        if let Some(i) = self.stack2.pop() {
            return i;
        };
        while let Some(i) = self.stack1.pop() {
            self.stack2.push(i);
        }
        self.stack2.pop().unwrap_or(-1)
    }
}

思路

• 第一反应是找原生队列支持，确实有，引入标准库就可以了。
• 做完后发现跟题目不太符合，需要用两个栈来实现队列的功能。
• 栈是先进后出，队列是先进先出
• 原生 vec 可以实现栈的功能，pus- pop。
• 把出栈的内容 push 到第二个 vec 里面，然后 在第二 vec pop 出来，就实现了类似队列的功能
• 比如 stack1.push(1),stack1.push(2), stack1 = [1,2]; stack2 = [];
• stakc2.push(stack1.pop()),stack1 = [1];stack2= [2]
• stakc2.push(stack1.pop()),stack1 = [];stack2= [2,1]
• stack2.pop(),stack1 = [];stack2= [2],返回值 1
• stack2.pop(),stack1 = [];stack2= [],返回值 2

来源

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

做了一件不太聪明的事

当别人再向你陈述一件事的时候，你是这么认为的，她也是这么认为的，但是不能说出来，很奇怪

你知道，我知道，说出来，就不一样了。

又想起多年之前的一个事情，A、B是好朋友，有一天C说，你们俩关系并没有那么好

最后如C所说，确实慢慢就，em ，对。

不知道是C看出了什么，还是AB因为C的那句话，一些小的想法慢慢被放大了

em，有时候我在想，如果没有C的那句话，应该还是很好的朋友

是吧，有些话还是不能说的。

今天，我也犯了同样的错误

对，好像我的表达也有一些问题。

她说的是当下，我回答的是往后余生，往后余生这个词不太好，但是暂时没有想到其他的，先这样

朋友，都会离去的，大部分吧

em，应该这么说，如果没有人努力维持这种关系，应该都会离开的

我现在的想法是这样子

不知对错

看完活着以后，这种想法愈加强烈

嗨，认真思考一下，假如

朋友多年未联系，再次碰到会是什么感觉，应该还是能愉快的吹牛，回去以后，什么也没有改变。

他已经没有在你的生活里面，以后估计也不会有吧

好像是这样子

可能我本身就是一个心性薄凉的人

刚想到一句话，完整的记不清楚了，大概是倒向你的墙，离开你的人，手里的沙子

em

不知道别人是不是也会有这种想法

或者没有注意到

活在当下，开心就好，随遇而安

你自己最明白你在想什么

轮转数组

题目

给定一个整数数组 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);
}

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

正确性未确认