字符串

Java 字符串

 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
import java.nio.charset.StandardCharsets;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        String s1 = "hello"; // 字面量创建
        String S3 = String.valueOf(123); // 任意类型转字符串

        String s = "a" + "b" + 1; // "ab1" 少量拼接时使用

        StringBuilder sb = new StringBuilder(); // 高频拼接使用
        for (int i = 0; i < 5; i ++) {
            sb.append(i).append(",");
        }
        String res = sb.toString();
        
        // 拼接集合
        s = String.join("-", "a", "b", "c"); // "a-b-c"
        
        boolean a1 = s.isEmpty(); // 判空
        int length = s.length(); // 长度
        boolean a2 = s.startsWith("a"); // 开始
        boolean a3 = s.contains("a"); // 包含
        
        // 查找位置
        int i = s.indexOf("ab"); // 查找
        String sub = s.substring(1, 4); // 左闭右开
        String r1 = s.replace("a", "x"); // 直接替换，非正则
        String r2 = s.replaceAll("\\d+", "#"); // 正则替换
        
        // 分割
        String[] parts = "a,b,c".split(",");
        
        // 格式化
        String msg = String.format("id=%d, name=%s", 10, "tom");
        
        // 字符编码
        char c = s.charAt(0);
        char[] arr = s.toCharArray();
        byte[] bytes = s.getBytes(StandardCharsets.UTF_8);
        String back = new String(bytes, StandardCharsets.UTF_8);
        
        // 码点
        s.codePoints().forEach(cp -> {
            System.out.println(cp);
        });
    }
}

Go 字符串

 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
func main() {
	// 创建字符串
	s1 := "hello"
	fmt.Println(s1)
	
	// 字符串长度
	fmt.Println(len(s1))
	
	// 少量拼接
	s := "a" + "b" + "c";
	fmt.Println(s)
	
	// 大量拼接
	var b strings.Builder
	for i := 0; i < 10; i++ {
		b.WriteString("a")
	}
	res := b.String()
	fmt.Println(res)
	
	// 拼接切片
	parts := []string{"a", "b", "c"}
	res = strings.Join(parts, "-")
	fmt.Println(res)

    // string byte 互转
    bs := []byte("hello")
    s := string(bs)

}

Python

1
2
3
4
if __name__ == '__main__':
    s = "cbbc"
    print(sorted(s)) // b b c c 
    print("".join(sorted(s))) // bbcc

JS

1
2
3
4
5
let s = "adbc"
let t = s.split("").sort() // a b c d
console.log(t)
let res = t.join("-") // a-b-c-d
console.log(res)

数组/列表

Java 数组基本用法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public static void main(String[] args) {
    int[] arr = {1, 2, 3};
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
    arr = new int[]{3, 4, 5};
    for (int v : arr) {
        System.out.println(v);
    }
}

Java 有个奇怪的点就是可以使用字面量来在声明的位置初始化，但是在运行时其他位置时，只能使用 new int[] 这种格式来进行赋值。

访问和修改都可以通过下标 + [] 运算符的方式来赋值。

1
2
3
4
5
6
7
public static void main(String[] args) {
    int[] arr = {3, 2, 3};
    Arrays.sort(arr);
    System.out.println(Arrays.toString(arr));
    Arrays.fill(arr, 1);
    System.out.println(Arrays.toString(arr));
}

arr 提供了一些便捷的工具可以用来对数组进行排序，填充值，打印等等。

在数组之上，java 提供了 List 接口，可以用来访问顺序数据结构，相对于数组，它不需要提前分配空间，而是需要在用的时候动态分配。

 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
public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    Integer[] arr = list.toArray(new Integer[0]);
    list = new ArrayList<>(Arrays.asList(arr));

    list.add(2);
    list.add(1);
    list.add(3);

    System.out.println(list);
    Collections.sort(list);
    System.out.println(list);

    Iterator<Integer> it = list.iterator();
    while(it.hasNext()) {
        Integer v = it.next();
        if (v == 3) {
            it.remove();
        }
    }
    System.out.println(list);
    
    list.set(1, 1);
    System.out.println(list);

    System.out.println(list.subList(0,1));

}

// output:
// [2, 1, 3]
// [1, 2, 3]
// [1, 2]
// [1]

在执行删除操作的时候，建议还是调用迭代器的方法进行安全删除。

另外，在使用 subList 截取 list 的某一个部分时，实际上是截取视图，如果想要深拷贝，建议使用 ArrayList 的构造函数再包一层。

Go 中的用法

数组：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var a [3]int          // [0 0 0]
b := [3]int{1, 2, 3}  // 指定长度
c := [...]int{1, 2, 3, 4} // 编译器推导长度
d := [5]int{1: 10, 3: 20} // 指定下标初始化 => [0 10 0 20 0]


a := [3]int{1, 2, 3}
b := [3]int{1, 2, 3}
fmt.Println(a == b) // true

m := map[[3]int]string{}
m[a] = "ok" // 注意: 切片不能作为 map 的 key

Go 中的数组其实用的不多，一般使用的还是切片 (slice)。

切片的底层实际上是对数组的视图，因此在传参的时候使用的不是值拷贝，而是引用拷贝。

和 java 不一样的是，定义切面时，[] 符号在类型前面。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func main() {
	arr := []int{1, 2, 3}
	fmt.Println(arr)
	arr = make([]int, len(arr))
	arr = append(arr, 3)
	fmt.Println(arr)
	fmt.Println(arr[3:4])
}
// [1 2 3]
// [0 0 0 3]
// [3]

go 的切片操作和 python 类似，取值逻辑也是左闭右开。

在使用字面量进行初始化时，不能使用 {} 直接进行初始化，而是要在之前加上 []int。

从数组追加到切片：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
package main

import "fmt"

func main() {
	arr := [5]int{1, 2, 3, 4, 5}
	s := arr[1:3] // 元素: [2,3], len=2, cap=4（从 arr[1] 到 arr[4]）

	fmt.Println(s, len(s), cap(s)) // [2 3] 2 4

	s = append(s, 99) // cap 够，原地追加到 arr[3]
	fmt.Println("s:", s)           // [2 3 99]
	fmt.Println("arr:", arr)       // [1 2 3 99 5]
}

Python 的用法

 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
if __name__ == '__main__':
    list = [2]
    list.append(4)
    list.extend([3,1])
    print(list)
    list[2] = 3
    print(list)
    print(list[-1])
    print(list[1:3])
    for v in list:
        print(v)
    for i, v in enumerate(list):
        print(i, v)
    # 原地排序
    v.sort()
    # 不改变原有列表的排序
    v2 = sorted(v)

    squares = [x * x for x in range(5)]
    print(squares)
    
    # 浅拷贝
    print(list[:])
    # 步长
    print(list[::2])

python 中有两个比较好的语法糖是其他语言中没有的：

列表推导式，可以快速生成一个规律的列表
切片，python 的切片非常灵活，可以指定步长

JS

 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
const arr = [1, 2];
arr.push(3);     // [1,2,3]
arr.pop();       // 返回 3，arr -> [1,2]

arr.unshift(0);  // [0,1,2]
arr.shift();     // 删除并返回 0
const arr = [1, 2, 3, 4];

// 删除：从 index=1 开始删 2 个
arr.splice(1, 2);      // arr -> [1,4]

// 插入：从 index=1 插入
arr.splice(1, 0, 99);  // arr -> [1,99,4]

// 替换：删 1 个再插入
arr.splice(2, 1, 7, 8);
const arr = [10, 20, 30];

// for
for (let i = 0; i < arr.length; i++) {}

// for...of（遍历值）
for (const x of arr) {}

// entries（索引+值）
for (const [i, x] of arr.entries()) {}

const arr = [1,2,3,4];
arr.slice(1, 3); // [2,3]

const arr = [10, 2, 1];
arr.sort();              // [1,10,2]（字符串比较）
arr.sort((a, b) => a - b); // [1,2,10]（数值升序）

排序

Java 实现

 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
import java.util.Arrays;

class Person {
    String name;
    int age;
    int score;
    Person(String name, int age, int score) {
        this.name = name; this.age = age; this.score = score;
    }
}

public class Demo {
    public static void main(String[] args) {
        Person[] arr = {
            new Person("Tom", 20, 90),
            new Person("Amy", 20, 95),
            new Person("Bob", 18, 95)
        };

        // 规则：score 降序；score 相同 age 升序；再按 name 升序
        Arrays.sort(arr, (p1, p2) -> {
            int c = Integer.compare(p2.score, p1.score); // score 降序
            if (c != 0) return c;
            c = Integer.compare(p1.age, p2.age);         // age 升序
            if (c != 0) return c;
            return p1.name.compareTo(p2.name);           // name 升序
        });
    }
}

import java.util.*;

List<Integer> list = new ArrayList<>(Arrays.asList(5, 1, 3, 2));
list.sort((x, y) -> Integer.compare(y, x)); // 降序
System.out.println(list); // [5, 3, 2, 1]

Go 实现

go 的排序依赖 sort 包实现。

 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
package main

import (
	"fmt"
	"sort"
)

type Person struct {
	Name  string
	Age   int
	Score int
}

func main() {
	ps := []Person{
		{"Tom", 20, 90},
		{"Amy", 20, 95},
		{"Bob", 18, 95},
	}

	// 规则：Score 降序；Score 相同 Age 升序；再按 Name 升序
	sort.Slice(ps, func(i, j int) bool {
		if ps[i].Score != ps[j].Score {
			return ps[i].Score > ps[j].Score // 降序
		}
		if ps[i].Age != ps[j].Age {
			return ps[i].Age < ps[j].Age // 升序
		}
		return ps[i].Name < ps[j].Name
	})

	fmt.Println(ps)
}

队列

Java 实现

在 Java 中，常用的队列是 LinkedList

对我而言，offer（提供）/poll（轮询）/peek 相对来说比较难记，我更适应其他语言的 push/pop/top 方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        // 失败时返回 false
        deque.offer(2); // 等价 offerLast
        deque.offer(3); // 2 3
        System.out.println(deque.peek()); // 2 等价 peekFirst
        System.out.println(deque.peekLast());
        deque.poll();
        System.out.println(deque); // 3

        // 栈相关方法
        deque.push(6); // 等价 offerFirst
        deque.push(7);
        System.out.println(deque); // 7 6 3
    }
}

Go 实现

Go 中，可以通过引入 container/list 包来支持队列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func main() {
	dq := list.New()

	// 入队：两端都可以
	dq.PushBack(1)  // 尾部入
	dq.PushFront(0) // 头部入
	dq.PushBack(2)

	// 查看头/尾（不删除）
	front := dq.Front().Value.(int)
	back := dq.Back().Value.(int)
	fmt.Println("front =", front, "back =", back)

	// 出队：两端都可以
	v1 := dq.Remove(dq.Front()).(int) // 头部出
	v2 := dq.Remove(dq.Back()).(int)  // 尾部出
	fmt.Println(v1, v2)

	fmt.Println("len =", dq.Len())
}

Python

在 python 中，可以导入 collections/deque 来实现队列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from collections import deque

if __name__ == '__main__':

    dq = deque()

    dq.append(1)  # 右端入队
    dq.appendleft(0)  # 左端入队
    dq.append(2)

    print(dq)  # deque([0, 1, 2])

    x = dq.popleft()  # 左端出队 -> 0
    y = dq.pop()  # 右端出队 -> 2
    print(x, y, dq)  # 0 2 deque([1])

JS

js 没有高效的队列实现，建议自己使用 list 实现环形队列。

优先级队列

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import java.util.PriorityQueue;

public class Demo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(5);
        pq.offer(1);
        pq.offer(3);

        System.out.println(pq.peek()); // 1（查看最小值，不删除）

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 1, 3, 5（依次弹出最小）
        }
    }
}

自定义排序规则：

 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
import java.util.PriorityQueue;

class Task {
    int priority;
    String name;
    Task(int priority, String name) {
        this.priority = priority;
        this.name = name;
    }
}

public class Demo2 {
    public static void main(String[] args) {
        PriorityQueue<Task> pq = new PriorityQueue<>(
            (t1, t2) -> Integer.compare(t1.priority, t2.priority)
        );

        pq.offer(new Task(2, "B"));
        pq.offer(new Task(1, "A"));
        pq.offer(new Task(3, "C"));

        while (!pq.isEmpty()) {
            Task t = pq.poll();
            System.out.println(t.priority + " " + t.name);
        }
    }
}

HashMap

Hashmap 基本用法

 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
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();

        // 新增/更新
        map.put("apple", 3);
        map.put("banana", 5);
        // 覆盖 apple 的值
        map.put("apple", 2);

        // 查询
        // 存在的值
        System.out.println(map.get("apple"));
        // 不存在的值
        System.out.println(map.get("pea"));
        // 判断是否存在
        System.out.println(map.containsKey("apple"));

        // 删除
        System.out.println(map.remove("apple"));

        // 安全查询
        int cnt = map.getOrDefault("pea", 0);
        System.out.println(cnt);
    }
}
// output
// 2
// null
// true
// 2
// 0

Java 的容器类往往放在 java.util 包中。
Java 中用 put 来往容器中设置值，为什么使用 put:
1. put 在 Map 中代表“放入/放置“的意思，就是将一个 k-v 关系放入映射结构中。
2. 有一个 put 的小知识点，就是 put 会返回设置之前的旧值
3. put 会替换掉之前已经设置的值，没有就插入，有就替换。
4. 为什么不用 set，set 只有赋值，但是不涉及新增，它是对已有字段的修改
5. 为什么不用 add/insert，因为他们的语义是只添加不覆盖。
Java 只能用 get 系列方法从 map 中取值，像其他语言中直接使用 [] 的方式是不合法的，这一点就很不方便。
Java 对于集合类的常见操作就是用接口访问，实际上这个是推荐的方式，在项目中，也应该先定义接口，用接口去访问对象信息。
关于 map 的操作，put/get/containsKey/remove 就最为常见，使用这几个方法能解决大部分问题。

map 接口

实际使用中，往往采用 map 接口访问对应的 map 实现类。

map 中接口中有两个方法很常用，分别是 size() 和 isEmpty()，这两个方法经常被用作判空，但是要注意空指针问题。

1
2
3
int size();

boolean isEmpty();

map 接口中，关于 put 方法的定义可以看作泛型使用的教科书：

1
2
3
public interface Map<K,V> {
    V put(K key, V value);
}

如果想在一个 map 中完全 put 另外一个 map 的值，可以使用 putAll 方法，这个也挺常用，不用自己写 for 循环了：

1
void putAll(Map<? extends K, ? extends V> m);

如果想要遍历 k-v 对，map 提供了三种可以用到的方法：

 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
public static void main(String[] args) {
    Map<String, Integer> map = new HashMap<>();

    // 新增/更新
    map.put("apple", 3);
    map.put("banana", 5);
    // 覆盖 apple 的值
    map.put("apple", 2);

    for (String key : map.keySet()) {
        System.out.println(key);
    }

    for (Integer value : map.values()) {
        System.out.println(value);
    }

    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());
    }
}

// Output:
// banana
// apple
// 5
// 2
// banana:5
// apple:2

Go 中的 map

Go 中的 map 构建相对简单些，通常，我们会使用下面的写法 2，需要注意的是在使用字面量初始化的时候，不需要带 make，以及所有的 k-v 对，包括最后一个 k-v 对都要加 , 结尾。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func main() {
    // 写法 1
	var mp map[string]int
	mp = make(map[string]int)
    // 写法 2
	mp2 := make(map[string]int)
	mp3 := map[string]int {
		"test": 3,
		"test4": 3,
	}
}

和 Java 相比，更新/访问 map 中的某个值不需要通过繁琐的 put/get 方法，只需要用 [] 运算符即可完成，同时遍历 map 中的元素也只需使用简单的 for-range 语法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func main() {
	mp := make(map[string]int)
	mp["apple"] = 3
	mp["banana"] = 5
	mp["apple"] = 2

	fmt.Println(mp["apple"])
	_, ok := mp["apple"]
	fmt.Println(ok)

	for k, v := range mp {
		fmt.Println(k, v)
	}
}

// Output:
// 2
// true
// apple 2
// banana 5

Go 中另外一个常见的用法是将 map[string]struct{} 结构用作集合，因为 Go 中并没有对应 Java 中的 Set 结构，例如:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func main() {
	set := make(map[string]interface{})
	set["a"] = struct{}{}
	_, ok := set["a"]
	fmt.Println(ok)
	delete(set, "a")
	_, ok = set["a"]
	fmt.Println(ok)
}

// Output:
// true
// false

Python 中的 map

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
if __name__ == '__main__':
    d = {"apple": 5, "banana": 4}
    d["apple"] = 3
    print(d["banana"])
    print(d.get("pea", 0))
    print("pea" in d)

    for k, v in d.items():
        print(k, v)

    print(d.keys())
    print(d.values())

python 中的 map 结构被称为 dict，dict 和 go 一样，可以通过 [] 运算符来判断，但是需要注意的是，如果值不存在，会抛出异常，所以更推荐使用 get 来为缺省值提供默认值。

dict 可以使用 for-in 语法进行遍历，这可以参考 go 中的 for-range 语法。

js 中的 map

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
var m = new Map()
m.set("banana", 1)
m.set("apple", 2)
console.log(m.get("banana"))
console.log(m.has("key"))

m = new Map([
    ["banana", 3],
])

console.log(m.get("banana"))

for (const [k, v] of m) {
    console.log(k, v)
}

js 中，可以通过 new Map 来创建一个 map，和 java 类似，需要通过 get/set 方法来设置值，不过 Java 用的 put，js 用的 set。

有点特殊的是，js 需要通过数组的字面量形式来初始化 map。

有些情况下，m.get("pea") === undefined 可以取代 has，但是要注意，如果存在 pea，且 pea 的值就是 undefined 则无法取代。

1
2
3
4
5
6
7
let mp = new Map()
mp.set('a', 1)
console.log(mp.values());
console.log(Array.from(mp.values()));

// [Map Iterator] { 1 }
// [ 1 ]

需要注意的是，values 返回的是一个迭代器，而不是真正的 array，需要zhuan

Map 的 LeetCode

这道算法的核心就是空间换时间，如果不使用 map 数据结构，需要通过两层 for 循环来找到最终的答案，使用 map 数据结构可以快速找到上一个和这个元素互补（和为 target）的元素的位置。

这道题涉及的 Java 的几个基本语法有：

初始化一个 map
for 循环遍历数组
返回一个数组
map 的 put 和 get 用法
判断是否存在某个 key

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i ++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target-nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return new int[]{0,0};
    }
}

Go 语言也是类似，无非是判断 key 存在的方式更加简洁了一点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func twoSum(nums []int, target int) []int {
    mp := make(map[int]int, 0)
    for i, v := range nums {
        targetV := target - v
        if targetI, ok := mp[targetV]; ok {
            return []int{targetI, i}
        }
        mp[v] = i
    }
    return []int{0, 0}
}

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mp = {}
        for i, v in enumerate(nums):
            targetV = target - v
            if targetV in mp:
                return [i, mp[targetV]]
            mp[v] = i
        return [0,0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
var twoSum = function(nums, target) {
    mp = new Map();
    for (let i = 0; i < nums.length; i ++) {
        let num = nums[i];
        let targetNum = target - num;
        if (mp.has(targetNum)) {
            return [mp.get(targetNum), i]
        }
        mp.set(num, i);
    }
    return [0,0]
};

字符串#

Java 字符串#

Go 字符串#

Python#

JS#

数组/列表#

Java 数组基本用法#

Go 中的用法#

Python 的用法#

JS#

排序#

Java 实现#

Go 实现#

队列#

Java 实现#

Go 实现#

Python#

JS#

优先级队列#

Java#

HashMap#

Hashmap 基本用法#

map 接口#

Go 中的 map#

Python 中的 map#

js 中的 map#

Map 的 LeetCode#

字符串

Java 字符串

Go 字符串

Python

JS

数组/列表

Java 数组基本用法

Go 中的用法

Python 的用法

JS

排序

Java 实现

Go 实现

队列

Java 实现

Go 实现

Python

JS

优先级队列

Java

HashMap

Hashmap 基本用法

map 接口

Go 中的 map

Python 中的 map

js 中的 map

Map 的 LeetCode