编程知识大杂烩

    impl Solution {
        pub fn length_of_longest_substring(s: String) -> i32 {
            use std::collections::HashMap;

            let chars = s.as_bytes();
            let mut ri = 0;
            let mut max_lenght = 0;
            for _ in 0..chars.len() {
                let mut h:HashMap<u8, u8> = HashMap::new();

                while ri < chars.len() {
                    if h.contains_key(&chars[ri]) {
                        break;
                    } else {
                        h.insert(chars[ri], chars[ri]);
                    }
                    ri = ri + 1;
                }
                max_lenght = std::cmp::max(max_lenght, h.len());

            }
            max_lenght as i32
        }
    }

待完成

4.2. 双指针

4.2.1. 557. 反转字符串中的单词 III

    impl Solution {
        pub fn reverse_words(s: String) -> String {
            use std::iter::FromIterator;
            let mut revert_string:Vec<String> = vec!();
            let mut tmp:Vec<char> = vec!();
            for (_, c) in s.char_indices() {
                if ' ' != c {
                    tmp.push(c);
                } else {
                    tmp.reverse();
                    revert_string.push(String::from_iter(tmp.clone()));
                    tmp.clear();
                }
            }
            tmp.reverse();
            revert_string.push(String::from_iter(tmp.clone()));
            revert_string.join(" ")
        }
    }

使用rust iter简写

    pub fn reverse_words(s: String) -> String {
        let revered:Vec<String> = s.split_whitespace()
                                   .map(|w| w.chars().rev().collect())
                                   .collect();
        revered.join(" ")
    }

4.2.2. 344. 反转字符串

    impl Solution {
        pub fn reverse_string(s: &mut Vec<char>) {
            let mut left = 0;
            let mut right = s.len() - 1;
            while left < right {
                s[left] = (s[left]  as u8 ^ s[right]  as u8) as char; (1)
                s[right] = (s[left]  as u8 ^ s[right]  as u8) as char;
                s[left] = (s[left]  as u8 ^ s[right]  as u8) as char;
                left = left + 1;
                right = right - 1;
            }
        }
    }

1	通过异或运算实现无额外空间交换两个数

4.2.3. 167. 两数之和 II - 输入有序数组

    impl Solution {
        pub fn two_sum(numbers: Vec<i32>, target: i32) -> Vec<i32> {
            use std::collections::HashMap;

            let mut h:HashMap<i32, i32> = HashMap::new();
            for i in 0..numbers.len() {
                if let Some(other_index) = h.get(&numbers[i]) {
                    return vec!(*other_index + 1, 1 + i as i32);
                } else {
                    h.insert(target - numbers[i], i as i32);
                }

            }
            vec!()
        }
    }

这里没有使用双指针，待实现

4.2.4. 283. 移动零

    impl Solution {
        pub fn move_zeroes(nums: &mut Vec<i32>) {
            let mut non_zero_vec = vec!();
            for i in 0..nums.len() {
                if nums[i] != 0 {
                    non_zero_vec.push(nums[i]);
                }
            }

            for i in 0..non_zero_vec.len() {
                nums[i] = non_zero_vec[i];
            }

            for i in non_zero_vec.len()..nums.len() {
                nums[i] = 0;
            }
        }
    }

笨方法，待优化

4.2.5. 977. 有序数组的平方

    impl Solution {
        pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> {
            let mut left = 0 as usize;
            let mut right = nums.len() - 1 as usize;
            let mut sorted:Vec<i32> = vec!();
            while left <= right { (1)
                let sqrt_left = nums[left] * nums[left];
                let sqrt_right = nums[right] * nums[right];
                if sqrt_left >= sqrt_right {  (2)
                    sorted.push(sqrt_left); (3)
                    // sorted.insert(0, sqrt_left);
                    left = left + 1;
                } else {
                    sorted.push(sqrt_right);
                    // sorted.insert(0, sqrt_right);
                    right = right - 1;
                }
            }
            sorted.reverse();
            sorted
        }
    }

1	边界必须是等于，不然会遗漏最后一个
2	usize必须大于0，否则0:usize - 1 是无穷大的一个数；等号写这即0的时候做加法不做减法
3	这边用push，执行速度会比用insert快很多,但是内存消耗相对多一点

vec 的push和insert的区别

4.3. leetcode

4.3.1. 606. 根据二叉树创建字符串

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public String tree2str(TreeNode root) {
            if (Objects.isNull(root)) {
                return "";
            }
            if (Objects.isNull(root.left) && Objects.isNull(root.right)) {
                return Integer.toString(root.val);
            }
            return root.val +
            Stream.concat(Stream.of(root.left), Stream.of(root.right).filter(Objects::nonNull))
            .map(r -> String.join(tree2str(r), "(", ")"))
            .collect(Collectors.joining(""));
        }
    }

4.4. 二分搜索

4.4.1. 704. 二分查找

java使用内存40M，耗时0ms

    class Solution {
        public int search(int[] nums, int target) {
            int right = nums.length - 1;
            int left = 0;
            int middle;
            do {
                middle = (left + right) / 2;
                if (target > nums[middle]) {
                        left = middle + 1; (1)
                    } else if (target < nums[middle]) {
                        right = middle - 1; (1)
                    } else {
                        return middle;
                    }
            } while(left <= right) ;
            return -1;
        }
    }

1	写成等于，反而不利于边界判断且多余

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0 as i32;
        let mut right = (nums.len() - 1) as i32;
        let mut middle = 0 as i32;
        while left <= right {
            middle = (right - left) / 2 + left;
            if target > nums[middle as usize] {
                left = middle + 1;
            } else if target < nums[middle  as usize] {
                right = middle - 1;
            } else {
                return middle as i32;
            }
        }
        return -1 as i32;
    }
}

rust使用内存2.1M,但是耗时4ms；耗时待优化

4.4.2. 278. 第一个错误的版本

    // The API isBadVersion is defined for you.
    // isBadVersion(version:i32)-> bool;
    // to call it use self.isBadVersion(version)

    impl Solution {
        pub fn first_bad_version(&self, n: i32) -> i32 {
                    let mut left = 1;
            let mut right = n;
            let mut mid = 0;
            while left < right {
                mid = (right - left) / 2 + left;
                if self.isBadVersion(mid) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    }

内存消耗问题怎么优化

35. 搜索插入位置

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0 as i32;
        let mut right = nums.len() as i32;
        let mut middle = 0 as i32;
        while left < right {
            middle = ((right - left) >> 1) + left; (1)
            if target > nums[middle as usize] {
                left = middle + 1;
            } else {
                right = middle;
            }
        }
        return right as i32;
    }
}

1	`(right - left) / 2` 使用 `((right - left) >> 1)` 节约内存占用

4.5. 动态规划

https://zhuanlan.zhihu.com/p/93857890 - 动态规划之背包问题系列

题目描述: 某公司购买了长钢条, 将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道出售一段长为i英寸的钢条的价格为pi, 钢条的长度均为整英寸。给出一个价格表的样例如下:

长度

1

2

3

4

5

6

7

8

9

10

价格pi

1

5

8

9

10

17

17

20

24

30

解题步骤: 由于每款长度的钢条数量无限, 所以采用无限背包的方法。
1、 状态定义:dp[i]表示切割长度为i的钢条的最大收益
2、 状态转移方程: dp[i] = max(dp[i],dp[i-len[j]]+price[j]) (i >= len[j])
3、 初始化:  dp[i] = 0;
4、 输出: dp[i]

4.6. 排序算法

4.6.1. 归并排序(Merge Sort)

参考文章【算法】排序算法之归并排序

^归并排序是一种分而治之的思想，常用来解决大文件排序的场景；通过切分成小文件分别排序，然后两两归并排序，从而实现对大文件排序

4.6.2. 快速排序(Quick Sort)

4.6.3. 冒泡排序(Bubble Sort)

4.6.4. 插入排序(Insertion Sort)

4.6.5. 希尔排序(Shell Sort)

4.6.6. 选择排序(Selection Sort)

4.6.7. 堆排序(Heap Sort)

4.6.8. 计数排序(Counting Sort)

4.6.9. 桶排序(Bucket Sort)

4.6.10. 基数排序(Radix Sort)

5. ETL

ETL是英文Extract-Transform-Load 的缩写，用来描述将数据从来源端经过抽取(extract)、转换(transform)、加载(load)至目的端的过程。

5.1. 数据抽取工具

kafka
flume
sync

5.2. 数据清洗

hive/tez
pig/tez
storm
spark

5.3. 其它工具

数据存储: hadoop、hbase, ES、redis
任务管理: azkaban、oozie
数据同步: datax、sqoop、 github:datax-web、 gitee:datax-web

5.4. 开发工具

Datastage
Congos
Kettle [a]
Apache NiFi
otter
dataX
Apache Airflow

编排工具: TASKCTL

References

博客

6. rust

trust: Travis CI and AppVeyor template to test your Rust crate on 5 architectures and publish binary releases of it for Linux, macOS and Windows
Lemmy: 一个自托管的社交链接聚合和讨论平台
Rust 开源：24个绝佳框架、项目及资料库
polars -Lightning-fast DataFrame library for Rust and Python

7. kafka

7.1. kafka connect

7.1.1. 概览

Kafka Connect 是一种用于在 Apache Kafka 和其他系统之间可扩展且可靠地流式传输数据的工具。它使快速定义将大量数据移入和移出 Kafka 的连接器变得简单。 Kafka Connect 可以摄取整个数据库或从所有应用程序服务器收集指标到 Kafka 主题中，使数据可用于低延迟的流处理。导出作业可以将数据从 Kafka 主题传送到二级存储和查询系统或批处理系统进行离线分析。

8. 分布式

8.1. 开源的分布式事务解决方案

Seata

Seata 是一款开源的分布式事务解决方案，致力于提供高性能和简单易用的分布式事务服务。Seata 将为用户提供了 AT、TCC、SAGA 和 XA 事务模式，为用户打造一站式的分布式解决方案

长度	1	2	3	4	5	6	7	8	9	10
价格pi	1	5	8	9	10	17	17	20	24	30