230506-demo

发表于 2023-05-06

230421-图-广度优先

发表于 2023-04-21 更新于 2023-05-06

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

题解

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");
        }
    }
}

思路

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

230407-分治-快排

发表于 2023-04-07 更新于 2023-05-06

实现

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;
}

理解思路

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

递归是实现分治的方案

递归实现的两个重要条件

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

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

还是需要在理解一下分治

230403-分治

发表于 2023-04-03 更新于 2023-05-06

重要的两点

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

示例

/**
 * 计算元素的和
 */
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);
  }
}

// 分治，二分查找，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);
    }
}

230329--选择排序

发表于 2023-03-29 更新于 2023-05-06

题目

写一个选择排序

题解

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
}

230328-包含min函数的栈

发表于 2023-03-28 更新于 2023-05-06

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.

题解

个人

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，没思路，对栈不熟悉，看了代码才知道应该用两个栈来存储数据。
第一个栈正常存数据，第二个栈存数据的最小值，一一对应的

来源

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

230323-用两个栈实现队列

发表于 2023-03-23 更新于 2023-05-06

用两个栈实现队列

题目

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

题解

原生方法

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

#[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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

20230315-移动0

发表于 2023-03-15 更新于 2023-05-06

20230311

发表于 2023-03-11 更新于 2023-05-06

做了一件不太聪明的事

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

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

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

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

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

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

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

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

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

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

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

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

我现在的想法是这样子

不知对错

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

嗨，认真思考一下，假如

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

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

好像是这样子

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

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

em

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

或者没有注意到

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

你自己最明白你在想什么

20230310-轮转数组

发表于 2023-03-10 更新于 2023-05-06

轮转数组

题目

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

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

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

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)
        }
    }
}

优化后，仍效率不太高

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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。