230421-图-广度优先
给一个单向关系图,实现广度优先算法
题解
1 | use std::collections::HashMap; |
思路
创建一个队列,把离自己最近的一层放在队列内
队列出队,检查当前元素是否符合要求,符合终止查找
不符合,把该元素的子集放入队列
这样子,只要队列不为空,就能把所有的内容检查一遍,且依照离原点最近的距离检查。
230407-分治-快排
实现
1 | fn q_srot(arr: &Vec<i32>) -> Vec<i32> { |
理解思路
分治,就是把问题不断的分解,这个问题的最小解就是问题的答案。不是所有的问题都可以使用分治
递归是实现分治的方案
递归实现的两个重要条件
- 基准条件,满足此条件相当于找到最小解,可以结束递归
- 递归条件,如何递归能得到结果
草,写这个东西是真的很困难。
还是需要在理解一下分治
230403-分治
重要的两点
- 如何找出基线条件
- 如何缩小计算规模
示例
1 | /** |
1 | // 分治,二分查找,Rust版本 |
230329--选择排序
题目
写一个选择排序
题解
1 | fn selection_sort(arr: Vec<i32>) -> Vec<i32> { |
230328-包含min函数的栈
题目
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.min(); –> 返回 -2.
题解
个人
1 | use std::{f32::MIN, vec}; |
思路
- emmm,没思路,对栈不熟悉,看了代码才知道应该用两个栈来存储数据。
- 第一个栈正常存数据,第二个栈存数据的最小值,一一对应的
来源
- 来源:力扣(LeetCode)
- 链接:https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
230323-用两个栈实现队列
用两个栈实现队列
题目
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 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 | use std::collections::VecDeque; |
双 vec
1 | #[derive(Default)] |
思路
- 第一反应是找原生队列支持,确实有,引入标准库就可以了。
- 做完后发现跟题目不太符合,需要用两个栈来实现队列的功能。
- 栈是先进后出,队列是先进先出
- 原生 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
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
20230315-移动0
20230311
做了一件不太聪明的事
当别人再向你陈述一件事的时候,你是这么认为的,她也是这么认为的,但是不能说出来,很奇怪
你知道,我知道,说出来,就不一样了。
又想起多年之前的一个事情,A、B是好朋友,有一天C说,你们俩关系并没有那么好
最后如C所说,确实慢慢就,em ,对。
不知道是C看出了什么,还是AB因为C的那句话,一些小的想法慢慢被放大了
em,有时候我在想,如果没有C的那句话,应该还是很好的朋友
是吧,有些话还是不能说的。
今天,我也犯了同样的错误
对,好像我的表达也有一些问题。
她说的是当下,我回答的是往后余生,往后余生这个词不太好,但是暂时没有想到其他的,先这样
朋友,都会离去的,大部分吧
em,应该这么说,如果没有人努力维持这种关系,应该都会离开的
我现在的想法是这样子
不知对错
看完活着以后,这种想法愈加强烈
嗨,认真思考一下,假如
朋友多年未联系,再次碰到会是什么感觉,应该还是能愉快的吹牛,回去以后,什么也没有改变。
他已经没有在你的生活里面,以后估计也不会有吧
好像是这样子
可能我本身就是一个心性薄凉的人
刚想到一句话,完整的记不清楚了,大概是倒向你的墙,离开你的人,手里的沙子
em
不知道别人是不是也会有这种想法
或者没有注意到
活在当下,开心就好,随遇而安
你自己最明白你在想什么
20230310-轮转数组
轮转数组
题目
给定一个整数数组 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 | // rust api |
直觉实现,效率低到难以接受
1 | impl Solution { |
优化后,仍效率不太高
1 | impl Solution { |
来源
- 来源:力扣(LeetCode)
- 链接:https://leetcode.cn/problems/rotate-array
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。