MichaelFu

好记性不如烂笔头

设计模式是软件设计中常见问题的典型解决方案。它们就像能根据需求进行调整的预制蓝图,可用于解决代码中反复出现的设计问题。

设计模式与方法或库的使用方式不同,很难直接在自己的程序中套用某个设计模式。模式并不是一段特定的代码,而是解决特定问题的一般性概念。可以根据模式来实现符合自己程序实际所需的解决方案。

人们常常会混淆模式和算法, 因为两者在概念上都是已知特定问题的典型解决方案。但算法总是明确定义达成特定目标所需的一系列步骤,而模式则是对解决方案的更高层次描述,同一模式在两个不同程序中的实现代码可能会不一样。

算法更像是菜谱:提供达成目标的明确步骤。而模式更像是蓝图:可以看到最终的结果和模式的功能,但需要自己确定实现步骤。

设计模式从分类上来讲,可以分为创建型、结构型和行为型。

阅读全文 »

SOLID 设计原则并非单纯的一个原则,它实际上包含5个设计原则:单一职责原则、开闭原则、里氏替换替换原则,接口隔离原则和依赖反转原则。

单一职责原则(SRP

SRP(Single Responsibility Principle) 这个原则的意思是一个类或者一个模块只负责完成一个功能。所以,这里有两种理解方式,一种理解是把模块看做比类更加抽象的概念,类也可以看做是模块。另一种理解是把类看做是比类更加粗粒度的代码块,模块中包含多个类。

单一职责原则定义非常简单,不难理解。一个类只负责完成一个职责或者功能,也就是说,不要设计大而全的类,要设计粒度小、功能单一的类。换个角度来讲就是,一个雷包含了两个或者两个以上业务不相干的功能,那我们就说它职责不够单一,应该将它拆分成多个功能更加单一、粒度更细的类。举例来讲,如果一个类包含了用户和订单的一些操作,而用户和订单又是独立的业务领域模型,我们将它们放到一起就违反了单一职责原则,我们就需要进行拆分。

不同的应用场景、不同阶段的需求背景、不同的业务层面,对于同一个类的职责是否单一,可能会有不用的判定结果。实际上,一些侧面的判断指标更具有指导意义和可执行性,比如,代码行数过度,函数或者属性过多都可能是违反单一职责原则的表象。

例如,下面的 UserInfo 类,这个类里面除了用户的基本信息,还有地址信息。或许一个观点是都属于用户的基本信息应该放在一起,另一个观点是可以拆分出 UserAddress 类,UserInfo 只保留除 Address 之外的其他信息,拆分之后两个类的职责更加单一。是否应该拆分,取决于具体情况,如果实际中地址信息和基本信息总是同时出现,那放在一起没有问题。但是如果地址信息单独在其他模块中使用,就应该单独抽象成 UserAddress

1
2
3
4
5
6
7
8
9
10
11
12
13
public class UserInfo {
private long userId;
private String username;
private String email;
private String telephone;
private long createTime;
private long lastLoginTime;
private String avatarUrl;
private String provinveOfAddress;
private String cityOfAddress;
private String regionOfAddress;
private String detailedAddress;
}

单一职责原则指导设计粒度较小的类,职责清晰的类,类的依赖以及被依赖的其他类也很会变少,从而降低代码的耦合性,实现高内聚、低耦合。但是如果拆分的过细,可能会适得其反,影响代码的可维护性。

阅读全文 »

几年前在面试的时候,还经常被面试官问 OOP 的四个特征是什么以及他们背后代表的意思,几年过去了,除了不支持面向对象的语言之外,面向对象编程思想已经深入到了每个开发者的灵魂,只是做的好与不好罢了。

面向对象编程中有两个非常基础的概念,类和对象,面向对象编程是一种编程范式或者说编程风格,它以类或者对象作为组织代码的基本单元,并将封装,继承,抽象,多态作为代码设计和实现的基石,不像面向过程编程语言,以函数为程序中的基本单元。

面向对象编程只是一种编程思想,可以用不同的语言进行实现,即使我们用面向对象语言,也完全可以写出面向过程风格的代码。至于什么是面向对象编程语言,并没有严格的定义,只要它能实现 OOP 的四大特性,那它就是面向对象编程语言,例如:RustC++GOJavaPython 以及 PHP 等,

面向对象编程的前提是面向对象分析(OOA)和面向对象设计(OOD),这样才能进行面向对象编程(OOP),具备完整的面向对象编程的思维。面向对象分析和设计两个阶段的产物应该是类的设计,包括应用程序应该被分为哪些类,每个类该有哪些属性和方法,类与类之间如何交互等等,它们比较贴近代码,非常具体,容易落地实现。

OOAOOD 的过程中,我们会经常用到 UML(Unified Model Language) 工具辅助我们进行工作。UML 是一种比较复杂的工具,除了包括我们常见的类图,还有用例图,顺序图,活动图,状态图,组件图等,即使是类图,类之间的关系就有泛化,实现,关联,聚合,组合以及依赖等,熟练掌握难度比较大,即便你掌握了,你同事不一定掌握,沟通成本依然很高,大多时候,我们会用草图实现我们的设计过程。

阅读全文 »

题目

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr],并返回其长度。如果不存在符合条件的子数组,返回 0

示例

示例 1

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2

输入:target = 4, nums = [1,4,4]
输出:1

示例 3

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

思路

这一题的解题思路是用滑动窗口。在滑动窗口 [i,j] 之间不断往后移动,如果总和小于 s,就扩大右边界 right,不断加入右边的值,直到 sum >= s,然后判断满足的子数组的长度,再缩小 left 左边界,直到 sum < s,这时候右边界又可以往右移动,寻找下一个满足的子数组。

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
fn min(a: i32, b: i32) -> i32 {
if a < b {
return a;
}
b
}

impl Solution {
pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
let mut left = 0usize;
let mut sum = 0;
let mut res = nums.len() as i32 + 1;
for right in 0..nums.len() {
let num = nums[right];
sum += num;
while sum >= target{
res = min(res, (right - left + 1) as i32);
sum -= nums[left];
left += 1;
}
}

if res == nums.len() as i32 + 1 {
return 0;
}
return res;
}
}

题目

DNA 序列 由一系列核苷酸组成,缩写为 'A''C''G' 和 'T'.。

例如,"ACGAATTCCG" 是一个 DNA 序列,在研究 DNA 时,识别 DNA 中的重复序列非常有用。

给定一个表示 DNA 序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例

示例 1

输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC","CCCCCAAAAA"]

示例 2

输入:s = "AAAAAAAAAAAAA"
输出:["AAAAAAAAAA"]

提示:

0 <= s.length <= 105
s[i]=='A'、'C'、'G' or 'T'

解法一

暴力解法,双层循环比较,结果可想而知,超时。

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
struct Solution;

impl Solution {
pub fn find_repeated_dna_sequences(s: String) -> Vec<String> {
let sub_strlen = 10;

if s.len() <= sub_strlen {
return vec![];
}

let s = s.into_bytes();
let end = s.len() - 10;
let mut set = std::collections::HashSet::new();

for i in 0..=end {
let tmp1 = &s[i..i + (sub_strlen as usize)];
for j in (i + 1)..=end {
let tmp2 = &s[j..j + (sub_strlen as usize)];
if tmp2 == tmp1 {
unsafe {
set.insert(String::from_utf8_unchecked(tmp1.to_vec()));
}
}
}
}
set.into_iter().collect()
}
}

fn main() {
let dna = "AAAAAAAAAAAAA".to_owned();
println!("{:?}", Solution::find_repeated_dna_sequences(dna));
}

解法二

O(n) 的时间复杂度,一次遍历将长度为 10 的所有子串放在 map 中,并且计数,最后将出现次数大于 1 的子串找出来返回。

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
use std::collections::HashMap;

struct Solution;

impl Solution {
pub fn find_repeated_dna_sequences(s: String) -> Vec<String> {
let sub_strlen = 10;

if s.len() <= sub_strlen {
return vec![];
}

let s = s.into_bytes();
let end = s.len() - 10;
let mut result = HashMap::new();

for i in 0..=end {
let tmp1 = &s[i..i + (sub_strlen as usize)];
let tmp1 = unsafe { String::from_utf8_unchecked(tmp1.to_vec()) };
result
.entry(tmp1)
.and_modify(|count| *count = *count + 1)
.or_insert(1);
}

let result: HashMap<&String, &i32> =
result.iter().filter(|(_, count)| **count > 1).collect();

let result = result
.into_keys()
.map(|key| key.to_owned())
.collect::<Vec<String>>();

result
}
}

fn main() {
let dna = "AAAAAAAAAAAAA".to_owned();
println!("{:?}", Solution::find_repeated_dna_sequences(dna));
}

接口是高级语言中的一个规约,是一组方法签名的集合。GoInterface 是非侵入式的,具体类型实现 Interface 不需要在语法上显式的声明,只需要具体类型的方法集合是 Interface 方法集合的超集,就表示该类实现了这一 Interface。编译器在编译时会进行 Interface 校验,Interface 和具体类型不同,它不能实现具体逻辑,也不能定义字段。

Go 语言中,Interface 和函数一样,都是第一公民,Interface 可以用在任何使用变量的地方。可以作为结构体内的字段,可以作为函数的形参和返回值,可以作为其他 Interface 定义的内嵌字段。Interface 在大型项目中常常用来解耦,在层与层之间用 Interface 进行抽象和解耦,使得抽象出来的代码特别简洁,这也符合 Go 语言设计之初的哲学。

先看一个易错的例子:

1
2
3
4
5
6
7
8
9
10
package main

import "fmt"

func main() {
var x interface{} = nil
var y interface{} = (*int)(nil)
fmt.Println(x == nil)
fmt.Println(y == nil)
}

这将输出:

true
false

Interface 实际上包含两部分,类型和值。对于 x 而言,它的类型和值都是 nil,所以 x == niltrue;对于 y,它的类型是 *int,值是 nil,所以 y == nilfalse。因此,我们在看 Interface 的时候,需要关注类型和值两部分。

阅读全文 »

题目

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符 ,但不需要考虑 words 中单词串联的顺序。

示例

示例 1

输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]

示例 3

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]

解法一

题目有两个要点:

  1. 字符串数组里面的字符串长度都是一样的;
  2. 要求字符串数组中的字符串都要连续连在一起的,前后顺序可以是任意排列组合;

假设,words 的长度是 nwords 中每个单词的长度是 w,所以我们每次可以从字符串 sn * w 长度来判断它是否是 words 的自由排列组合。

在判断时,我们先将 words 中每个单词的数量放在一个计数器中,可以用 map 表示,例如:["aaa", "bbb"] 表示成 {"aaa": 1, "bbb": 1}["aaa", "aaa", "ccc"] 表示成 {"aaa": 2, "ccc": 1};然后我们将 s 中每个 n * w 长度的子串每 w 个一组放在一个 map 中计数,最后和 words 的计数器比较是否相等,如果相等就是我们想要的子串。

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
use std::collections::HashMap;

impl Solution {
pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
let mut result: Vec<i32> = Vec::new();

let n = words.len();
if n == 0 {
return result;
}

let w = words[0].len();
if s.len() < n * w {
return result;
}

let mut counter = HashMap::new();
for i in 0..n {
counter
.entry(words[i].as_str())
.and_modify(|count| *count += 1)
.or_insert(1);
}

for i in 0..=(s.len() - n * w) {
let mut tmp_counter = HashMap::new();
for j in 0..n {
let start = i + j * w;
let tmp_str = &s[start..(start + w)];
tmp_counter
.entry(tmp_str)
.and_modify(|count| *count += 1)
.or_insert(1);
}
if tmp_counter == counter {
result.push(i as i32);
}
}

result
}
}

题目

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

示例

示例 1

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

思路

使用滑动窗口,它的右边界不断的右移,只要没有重复的字符,就持续向右扩大窗口边界。一旦探测到出现了重复字符,就需要右边界先停下,然后缩小左边界,直到重复的字符移出了左边界,然后继续移动滑动窗口的右边界。以此类推,每次移动需要计算当前长度,并判断是否需要更新最大长度,最终最大的值就是题目中的所求。

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
fn max(a: i32, b: i32) -> i32 {
if a >= b {
a
} else {
b
}
}

impl Solution {
pub fn length_of_longest_substring(s: String) -> i32 {
let mut result = 0;
let mut left = 0i32;
let mut right = -1i32;
let mut freq = [0; 127];
let s = s.into_bytes();

while (left as usize) < s.len() {
let right_index = (right + 1) as usize;
if right_index < s.len() && freq[s[right_index] as usize] == 0 {
right += 1;
freq[s[right_index] as usize] += 1;
} else {
freq[s[left as usize] as usize] -= 1;
left += 1;
}

result = max(result, right - left + 1);
}

result
}
}

题目

给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例

示例 1

输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.

示例 2

输入:l1 = [0], l2 = [0]
输出:[0]

示例 3

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]

思路

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
impl Solution {
pub fn add_two_numbers(
l1: Option<Box<ListNode>>,
l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
let mut head = Box::new(ListNode::new(0));
let mut n1 = 0;
let mut n2 = 0;
let mut carry = 0;
let mut current = &mut head;

let mut l1 = l1;
let mut l2 = l2;

loop {
if l1.is_none() && l2.is_none() && carry == 0 {
break;
}

if l1.is_none() {
n1 = 0;
} else {
n1 = l1.as_ref().unwrap().val;
l1 = l1.unwrap().next;
}

if l2.is_none() {
n2 = 0;
} else {
n2 = l2.as_ref().unwrap().val;
l2 = l2.unwrap().next;
}

current.next = Some(Box::new(ListNode::new((n1 + n2 + carry) % 10)));
current = current.next.as_mut().unwrap();
carry = (n1 + n2 + carry) / 10;
}

head.next
}
}

参考链接

  1. Add Two Numbers

题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

在数组中找到 2 个数之和等于给定值的数字,结果返回 2 个数字在数组中的下标。

示例

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

输入:nums = [3,2,4], target = 6
输出:[1,2]

输入:nums = [3,3], target = 6
输出:[0,1]

思路

这道题最优的做法时间复杂度是 O(n)。顺序扫描数组,对每一个元素,在 map 中找能组合给定值的另一半数字,如果找到了,直接返回 2 个数字的下标即可。如果找不到,就把这个数字存入 map 中,等待扫到另一半数字的时候,再取出来返回结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::collections::HashMap;

impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut positions = HashMap::<i32, usize>::new();
for i in 0..nums.len() {
if let Some(j) = positions.get(&(target - nums[i])) {
return vec![*j as i32, i as i32];
}
positions.insert(nums[i], i);
}
vec![]
}
}

参考链接

  1. Two Sum
0%