灯的个人博客

forever young,forever weeping.

0%

发表于 更新于 分类于

给一个单向关系图，实现广度优先算法

题解

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
use std::collections::HashMap;
use std::collections::HashSet;

fn search_m<'a>(hashmap: HashMap<&str, Vec<&'a str>>) -> Option<&'a str> {
    let mut queue: Vec<&str> = Vec::new();
    let mut check_list = HashSet::new();
    if let Some(first) = hashmap.get("you") {
        for ele in first {
            queue.push(ele);
        }
    }
    while queue.len() > 0 {
        let c = queue.remove(0);
        if check_list.contains(c) {
            continue;
        }
        check_list.insert(c);
        if c.ends_with("m") {
            return Some(c);
        }
        if let Some(eles) = hashmap.get(c) {
            for ele in eles {
                queue.push(ele)
            }
        }
    }
    None
}

fn main() {
    let mut hashmap = HashMap::new();
    hashmap.insert("you", vec!["alice", "bob", "claire"]);
    hashmap.insert("bob", vec!["anuj", "peggy"]);
    hashmap.insert("alice", vec!["peggy"]);
    hashmap.insert("claire", vec!["you", "thom", "jonny"]);
    hashmap.insert("anuj", vec![]);
    hashmap.insert("peggy", vec![]);
    hashmap.insert("thom", vec![]);
    hashmap.insert("jonny", vec![]);

    let v = search_m(hashmap);
    match v {
        Some(i) => {
            println!("find mongoose! name {:?}", i);
        }
        None => {
            println!("not find mongoose");
        }
    }
}

思路

创建一个队列，把离自己最近的一层放在队列内
队列出队，检查当前元素是否符合要求，符合终止查找
不符合，把该元素的子集放入队列
这样子，只要队列不为空，就能把所有的内容检查一遍，且依照离原点最近的距离检查。

发表于 更新于 分类于

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fn q_srot(arr: &Vec<i32>) -> Vec<i32> {
    if arr.len() < 2 {
        return arr.clone();
    }
    let base = arr[0];
    let small: Vec<i32> = arr.into_iter().filter(|x| *x < &base).map(|x| *x).collect();
    let bigger: Vec<i32> = arr.iter().filter(|x| *x > &base).map(|x| *x).collect();
    let result: Vec<i32> = q_srot(&small)
        .into_iter()
        .chain(vec![base])
        .chain(q_srot(&bigger))
        .collect();
    return result;
}

理解思路

分治，就是把问题不断的分解，这个问题的最小解就是问题的答案。不是所有的问题都可以使用分治

递归是实现分治的方案

递归实现的两个重要条件

  • 基准条件，满足此条件相当于找到最小解，可以结束递归
  • 递归条件，如何递归能得到结果

草，写这个东西是真的很困难。

还是需要在理解一下分治

发表于 更新于 分类于

重要的两点

  • 如何找出基线条件
  • 如何缩小计算规模

示例

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * 计算元素的和
 */
function sum(arr: number[]) {
  if (arr.length === 0) {
    return 0;
  }
  if (arr.length === 1) {
    return arr[0];
  }
  let [c, ...rest] = arr;
  return c + sum(rest);
}

let a =  sum([2, 4, 6]);
console.log(a);

/**
 * 计算元素的长度
 */
function ArrayLength(arr: number[]) {
  if (arr.length === 0) {
    return 0;
  }
  let [i, ...rest] = arr;
  return 1 + ArrayLength(rest);
}

let a = ArrayLength([2, 4, 6]);
console.log(a);

/**
 * 找出元素中的最大值
 */
function maxNumber(arr: number[]) {
  if (arr.length === 0) {
    return -Infinity;
  }
  let [i, ...rest] = arr;
  let max = maxNumber(rest);
  return i > max ? i : max;
}

let a = maxNumber([-1]);
console.log(a);


/**
 * 二分查找，分治方法
 */
function midSearch(arr: number[], search: number) {
  if (arr.length === 0) {
    return -1;
  }
  if (arr[0] === search) {
    return arr[0];
  }
  let mid = (arr.length - 1) / 2;
  if (arr[mid] > search) {
    return midSearch(arr.slice(0, mid), search);
  } else {
    return midSearch(arr.slice(mid, arr.length), search);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 分治，二分查找，Rust版本
fn mid_search(arr: Vec<i32>, search: i32) -> i32 {
    if arr.len() == 0 {
        return -1;
    }
    if arr[0] == search {
        return arr[0];
    }
    let mid = (arr.len() - 1) / 2;
    if arr[mid] > search {
        return mid_search(arr[0..mid].to_vec(), search);
    } else {
        return mid_search(arr[mid..arr.len()].to_vec(), search);
    }
}

发表于 更新于 分类于

题目

写一个选择排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fn selection_sort(arr: Vec<i32>) -> Vec<i32> {
    let mut min = std::i32::MIN;
    let mut result = vec![];
    for _i in &arr {
        let c_min = find_small(&arr, min);
        min = c_min;
        result.push(c_min);
    }
    result
}
fn find_small(arr: &Vec<i32>, min: i32) -> i32 {
    let mut c_min = std::i32::MAX;
    for i in arr {
        if *i <= min {
            continue;
        }
        if *i < c_min {
            c_min = *i;
        }
    }
    c_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
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
use std::{f32::MIN, vec};

struct MinStack {
    stack_a: Vec<i32>,
    stack_b: Vec<i32>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MinStack {
    /** initialize your data structure here. */
    fn new() -> Self {
        return MinStack {
            stack_a: vec![],
            stack_b: vec![],
        };
    }

    fn push(&mut self, x: i32) {
        self.stack_a.push(x);
        if self.stack_b.len() == 0 {
            self.stack_b.push(x);
        } else if self.min() >= x {
            self.stack_b.push(x);
        } else {
            self.stack_b.push(self.min());
        }
    }

    fn pop(&mut self) {
        self.stack_a.pop();
        self.stack_b.pop();
    }

    fn top(&self) -> i32 {
        let top: i32 = self.stack_a.last().unwrap().clone();
        top
    }

    fn min(&self) -> i32 {
        let min: i32 = self.stack_b.last().unwrap().clone();
        min
    }
}

思路

  • emmm，没思路，对栈不熟悉，看了代码才知道应该用两个栈来存储数据。
  • 第一个栈正常存数据，第二个栈存数据的最小值，一一对应的

来源

发表于 更新于 分类于

用两个栈实现队列

题目

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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

来源

发表于 更新于 分类于

做了一件不太聪明的事

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

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

又想起多年之前的一个事情，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)
    }
}

来源

发表于 更新于 分类于

题目

给你一个按 非递减顺序 排序的整数数组 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
    }
}

来源