编程语言(3)—数据结构和算法

数据结构(容器)库和算法库是最基础的库之一。字符串是人类语言的记录，是计算机处理的主要对象。

C和C++

由于C语言不提供数据结构和算法库，这里专指C++的STL stand template library。

数据结构

std::array，静态数组，编译时确定数组长度，数组创建在栈。相当于C语言的int[2] = {1,2}

std::vector，动态数组，可动态扩展大小。当 size() 即将超过 capacity() 时，vector 会自动分配更大的内存空间（一般是翻倍），并将原有元素移动或复制到新空间。
因此std::vector会有迭代器失效的问题，需要及时重新获取迭代器。

数组随机访问和更新效率高，为O(1)，但随机插入删除低。适合大量访问少量插入删除的场景。vector建议使用.at(x)索引元素，具有边界检查，如果越界会抛出异常。

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6);

    for (int val : vec) {
        std::cout << val << " ";  // 输出：1 2 3 4 5 6
    }
    std::cout << std::endl;

    std::cout << vec[2] << std::endl;  // 访问元素 3
    return 0;
}

std::list 是双向链表，能高效插入或删除元素，但随机访问效率低。适合维护不需要大量随机访问和更新的结构（即不需要用vector的都建议上链表）。例如队列，环形buffer等。

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    lst.push_back(6);  // 在末尾插入元素
    lst.push_front(0); // 在头部插入元素

    for (int val : lst) {
        std::cout << val << " ";  // 输出：0 1 2 3 4 5 6
    }
    return 0;
}

std::deque 是双端队列，使用链接起来的若干内存块构成。deque的头部和尾部可以进行高效的插入和删除操作，同时也提供随机访问接口，但随机访问比vector慢。deque实现复杂，实际应该少用。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> deq = {1, 2, 3, 4, 5};
    deq.push_back(6);   // 在尾部添加元素
    deq.push_front(0);  // 在头部添加元素

    for (int val : deq) {
        std::cout << val << " ";  // 输出：0 1 2 3 4 5 6
    }
    return 0;
}

std::stack是可以传入底层容器的配接器，默认底层容器是std::deque，但可以指定底层容器为std::vector。同样std::queue也是个配接器，默认底层容器是std::deque，但可以指定底层容器为std::list。

std::stack<T> s;                   // 默认使用 deque
std::stack<T, std::vector<T>> s;    // 显式指定 vector 作为底层容器


std::stack<int> s1;
s1.push(1);                     // 压栈
int top = s1.top();             // 访问栈顶（1）
s1.pop();                       // 弹栈

// 使用 list 作为底层容器
std::queue<int, std::list<int>> q2;
q2.push(2);                     // 入队
q2.pop();                       // 出队

std::set 是一个有序关联容器，基于红黑树（平衡二叉搜索树）实现，元素会自动排序且不允许重复，CRUD复杂度都是O(logn)。unordered_set 是一个不排序的集合，基于哈希表实现, 复杂度为O(1)，但会面临哈希碰撞和rehash的问题。

std::set 创建需要传入comparator (operator <，即Less<T>升序排列)。而std::unordered_set需要提供hash function和operator==。

// 按字符串长度排序
struct LengthCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};
std::set<std::string, LengthCompare> s;
auto comp = [](const std::string& a, const std::string& b) { return a < b; }
std::set<T, decltype(comp)> my_set(comp);

s.insert("apple");
s.insert("banana"); // "apple"（长度 5）排在 "banana"（长度 6）之前

struct Person {
    std::string name;
    int age;
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);
    }
};

struct PersonEqual {
    bool operator()(const Person& a, const Person& b) const {
        return a.name == b.name && a.age == b.age;
    }
};

std::unordered_set<Person, PersonHash, PersonEqual> s2;

auto hash = [](const T& key) { /* 返回哈希值 */ };
auto equal = [](const T& a, const T& b) { /* 返回是否相等 */ };
std::unordered_set<T, decltype(hash), decltype(equal)> s3(hash, equal);

哈希表的元素个数除以哈希表长度是哈希表的负载因子load factor。当负载超过负载因子时，哈希表会自动进行扩容。

计算新桶数量：新桶数量通常为不小于 size() / max_load_factor() 的质数。
重新分配桶数组：分配新桶数组
重新哈希所有元素：将所有元素重新插入到新桶中
最后释放旧桶数组
rehash期间hash表会停止工作, rehash完毕后旧的迭代器会失效

数组和unorder_set/unorder_map使用时建议预分配空间（reserve）以减少重新分配。

map类似set，只是元素是键值对pair，根据键进行排序。unordered_map类似unordered_set，是一个无序映射，使用哈希表进行存储。

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> um = {{1, "one"}, {2, "two"}, {3, "three"}};

    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

C++ STL使用迭代器来标识容器中的元素，以及实现容器中元素的访问。迭代器支持重载*和->运算符来解引用或访问元素成员变量

随机访问迭代器 (Random Access Iterator)，类似指针，通过加减算数提供随机访问。对应容器std::vector、std::deque、std::array。支持随机访问迭代器作为参数的算法函数，一般也支持指针作为参数。
双向迭代器(Bidirectional Iterator)，允许在容器中向前和向后移动。对应容器std::list、std::set、std::map。

迭代器是使用继承结构组织的，随机访问迭代器也是一种双向迭代器

.begin(), .end() 分别代表首尾迭代器

算法库algorithm

std::sort 对容器中的元素进行排序，默认升序。sort可以用std::less和std::greater 进行降序和升序排序。


#include <functional>
std::sort(v.begin(), v.end()); // 默认使用 std::less<int>
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // 降序

std::sort 内部实现原理,

快速排序（Quicksort）：作为主要排序算法，处理大规模数据。
堆排序（Heapsort）：在快速排序递归深度过大时触发，避免最坏情况下的 O(n²) 时间复杂度。
插入排序（Insertion Sort）：在小规模子数组（通常 ≤16 个元素）时使用，减少递归开销。

常见排序算法的稳定性

排序算法	最佳时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	原地排序	备注
冒泡排序	O(n)	        O(n²)	    O(n²)	    O(1)	        稳定	是	优化后可提前终止（如无交换时停止）。
选择排序	O(n²)	        O(n²)	    O(n²)	    O(1)	        不稳定	是	每次选择最小/最大元素交换。
插入排序	O(n)	        O(n²)	    O(n²)	    O(1)	        稳定	是	对部分有序数据效率高。
希尔排序	O(n log n)	    O(n^(3/2))	O(n²)	    O(1)	        不稳定	是	基于插入排序的改进，间隔序列影响性能。
归并排序	O(n log n)	    O(n log n)	O(n log n)	O(n)	        稳定	否	分治思想，需额外空间合并。
快速排序	O(n log n)	    O(n log n)	O(n²)	    O(log n) ~ O(n)	不稳定	是	基于分治和分区操作，平均性能最优。
堆排序	    O(n log n)	    O(n log n)	O(n log n)	O(1)	        不稳定	是	利用堆结构排序，适合大规模数据。
计数排序	O(n + k)	    O(n + k)	O(n + k)	O(n + k)	     稳定	否	适用于整数且范围较小的数据（k为数据范围）。
桶排序	    O(n + k)	    O(n + k)	O(n²)	    O(n + k)	     稳定	否	数据均匀分布时高效，依赖桶的数量和分布。
基数排序	O(d(n + k))	    O(d(n + k))	O(d(n + k))	O(n + k)	     稳定	否	按位排序（d为位数，k为基数大小），通常用于整数或字符串。

std::sort是不稳定的，std::stable_sort提供稳定排序，即保证相同元素的相对顺序。内部实现原理是基于归并排序（Merge Sort）的变体，并结合优化策略以优化空间。

std::find查找容器中的某个元素，返回第一个匹配元素的迭代器。

auto it = std::find(vec.begin(), vec.end(), 2);
if (it != vec.end()) {
    // 找到了元素
}
it == vec.end();  // 未找到元素

std::lower_bound，传入排序好的数组，返回第一个大于或等于指定元素的迭代器。
std::upper_bound：返回指向已排序数组中第一个大于指定元素的迭代器。
需要随机访问迭代器

1 2	auto it = std::lower_bound(vec.begin(), vec.end(), 3); auto it = std::upper_bound(vec.begin(), vec.end(), 3);

std::reverse, 反转容器中的元素顺序。

1	std::reverse(vec.begin(), vec.end());

std::fill, 将容器中的所有元素设置为指定值。

1	std::fill(vec.begin(), vec.end(), 0);

std::transform, 对容器中的每个元素应用指定的操作。

1	std::transform(vec.begin(), vec.end(), vec.begin(), [](int x) { return x * 2; });

std::copy：将容器中的元素复制到另一个容器。std::swap, 交换两个容器的内容。std::move, 移动容器，避免复制。

1
2
3

std::copy(vec, dest);
std::swap(vec, dest);
std::vector<int> new_vec = std::move(vec);

std::count, 统计容器中某个元素出现的次数。std::count_if：统计符合特定条件的元素的数量。

1 2	int count = std::count(vec.begin(), vec.end(), 2); int count = std::count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

std::accumulate, 对容器中的元素进行累加。

1	int sum = std::accumulate(vec.begin(), vec.end(), 0);

std::min_element, 返回容器中最小元素的迭代器。std::max_element：返回容器中最大元素的迭代器。

1 2	auto min_it = std::min_element(vec.begin(), vec.end()); auto max_it = std::max_element(vec.begin(), vec.end());

std::unique, 将容器中相邻的重复元素移动到末尾，返回新逻辑结尾的迭代器，不修改容器大小
unique需要和sort一起连用

1
2
3

std::vector<int> v = {1, 1, 2, 2, 3, 3, 3, 4};
auto last = std::unique(v.begin(), v.end());
// v 变为 {1, 2, 3, 4, 3, 3, 3, 4}，last 指向第5个元素（第一个3后的位置）

字符串处理函数

由于C++兼容C语言，因此支持C风格和C++风格的字符串处理算法。C风格字符串函数参数是指针，C++风格是随机访问迭代器。

C风格的字符串处理函数, 在C++中，需要#include <cstring>，C语言的字符串处理函数作为std namespace的全局函数。

C 语言字符串处理函数

strcpy(dest, src), strncpy(dest, src, n), 字符串拷贝
strcat(dest, src), strncat(dest, src, n), 字符串拼接
strcmp(s1, s2), strncmp(s1, s2, n), 字符串比较
strlen(s), 字符串长度
strchr(s, c), strrchr(s, c), 字符串查找

memset, memove, memcpy 内存赋值/移动/拷贝

// strcpy(dest, src), strncpy(dest, src, n), 字符串拷贝
char src[] = "Hello, World!";
char dest[20];
std::strcpy(dest, src);
std::strncpy(dest, src, 5);

// strcat(str1, str2) 将str2拼接到str1
std::strcat(str1, str2); 
std::strncat(str1, str2, 5);

// strlen(str)，返回 C 风格字符串的长度（不包括 \0 终止符）

// strcmp(str1, str2), strncmp(str1, str2, n) 如果str1 > str2, 返回大于0
std::strcmp(str1, str2)

// strchr(str, c)，查找字符c在字符串str中第一次出现的位置。如果找到了，返回指向该字符的指针；如果没找到，返回 nullptr。
char* ptr = std::strchr(str, 'o');

// strstr(str, sub), 查找子字符串sub在字符串str中的第一次出现。如果找到了，返回指向子字符串的指针；如果没找到，返回 nullptr。
const char* str = "Hello, World!";
const char* sub = "World";
char* ptr = std::strstr(str, sub);

// memset(str, c, n) 按字节为单位对内存初始化
char str[20];
std::memset(str, '*', 5);  // 将前 5 个字符设置为 '*'

memcpy(dest, src, n) 从src拷贝n个字节到dest
char src[] = "Hello";
char dest[10];
std::memcpy(dest, src, 6);

C++ string函数

append(xxx) 追加字符串
substr(start, length) 截取字符串, 需要拷贝
find(xxx) 查找子串
replace(start, length, xxx) 替换字符串
erase(start, length) 删除字符串, 是真正的删除（性能差）
stoi(xxx) 字符串转整数

std::string, .c_str()

// size() 或 length() 获取字符串长度

// append(string)，将内容追加
std::string str = "Hello";
str.append(", World!"); 

// push_back(c)，添加一个字符
str.push_back('!');

// insert(index, string), 指定位置插入字符串
str.insert(5, ", World");

// erase(index, length), 删除指定位置区间的字符串
str.erase(5, 7);  // 从位置 5 开始删除 7 个字符

// replace(index, length, newstring), 替换字符串中的指定部分。
str.replace(7, 5, "C++");

// resize(size) 改变字符串的大小，如果增加字符则填充，减少字符则截断。
str.resize(5);

// std::find(string) 查找子字符串首次出现的位置。如果找不到返回 std::string::npos。rfind, 从字符串末尾向前查找字符串
size_t pos = str.find("World");

// find_first_of(),find_last_of()
size_t pos = str.find_first_of("o");

// substr(index, length) 提取子字符串
std::string sub = str.substr(7, 5); 

// compare 字符串比较
std::string str1 = "Hello";
std::string str2 = "World";
int result = str1.compare(str2);

// stoi(), stol(), stoll() 字符串转为整型
int num = std::stoi(str);

// to_string()，转为字符串
std::string str = std::to_string(num);

// c_str(), data() 返回 C 风格字符串（const char*）。
const char* cstr = str.c_str();

string_view 是C++17的特性，旨在解决substr()字符串切片会导致拷贝造成性能损失的问题

string_view不管理内存，仅保存指向外部数据的指针和长度。不能通过string_view修改底层数据。
构造时不复制数据，可以直接传递字符串参数，避免临时对象的开销。

void process(std::string_view text) {
    // 处理 text，无需关心数据来源
}

process("Hello");       // C字符串
process(std::string("World")); // std::string
process(sv1);          // 另一个 string_view

JAVA

数据结构

静态数组，

固定长度：数组在初始化时指定长度，后续无法修改。
连续内存：元素在内存中连续存储，支持快速随机访问（时间复杂度 O(1)）。
数组本身也是对象（继承自 Object 类），存储在堆内存中。

java只有8种基本类型变量(byte, short, int, long, float, double, char, boolean)存放在栈里，数组不是

int[] numbers;       // 声明一个整型数组,  此时 arr = null
String[] names;      // 声明一个字符串数组

numbers = new int[5]; // 初始值为 [0, 0, 0, 0, 0]

names = new String[] {"Alice", "Bob", "Charlie"};

numbers[1] = 10;             // 修改第二个元素
int length = numbers.length; // 获取数组长度（非方法，是字段）

ArrayList，等于C++的vector，动态数组。JAVA的List是一个接口，实现了动态数组和链表。

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
System.out.println(list);  // 输出: [Apple, Banana, Cherry]

int first = list.get(0);       // 获取索引 0 的元素
int last = list.get(list.size() - 1); // 获取最后一个元素
list.set(0, 20); // 将索引 0 的元素修改为 20
list.addAll(otherList); // 添加另一个集合的所有元素

LinkedList，双向链表，相当于C++的list

1
2
3

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();

HashSet, 基于哈希表实现，不保证元素的顺序。

LinkedHashSet, 基于哈希表和链表实现，能够保证元素的插入顺序。

TreeSet, 基于红黑树实现，元素按自然顺序或自定义顺序排列。

HashMap，基于哈希表实现，允许 null 键和值。

LinkedHashMap，基于哈希表和链表实现，保持插入顺序（或访问顺序）

TreeMap，基于红黑树实现，键按自然顺序或自定义顺序排序。

PriorityQueue，基于堆实现的队列，元素按优先级顺序排列

LinkedList 也实现了 Queue 接口，支持双端队列操作。

import java.util.LinkedList;
import java.util.Queue;

Queue<String> queue = new LinkedList<>();
queue.add("Apple");
queue.add("Banana");
queue.add("Cherry");
System.out.println(queue.poll());  // 输出: Apple（出队）
System.out.println(queue);  // 输出: [Banana, Cherry]

算法

Arrays用于操作数组，例如.sort() 用于对静态数组进行排序，数组是基本类型数组int[] arr ，或对象数组new Integer[10].
java的.length用于获取静态数组长度

int[] arr = {5, 3, 1, 4, 2};
Arrays.sort(arr); // 数组变为 [1, 2, 3, 4, 5]
Arrays.sort(arr, (a, b) -> b - a); // 降序排序 → [5, 4, 3, 2, 1]
// 二分查找
int index = Arrays.binarySearch(arr, 3); // 返回 2（索引）

// 填充
int[] arr = new int[5];
Arrays.fill(arr, 10); // [10, 10, 10, 10, 10]

Collections用于容器算法，.sort() 用于对集合（如 List）进行排序

import java.util.*;

public class SortExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 3));
        Collections.sort(list);
        System.out.println(list);  // 输出: [1, 2, 3, 5, 8]

        int index = Collections.binarySearch(list, 5);
        System.out.println(index);  // 输出: 3

        Collections.fill(list, 10);
        System.out.println(list);  // 输出: [10, 10, 10, 10, 10]

        Collections.shuffle(list);
        System.out.println(list);  // 输出: 随机打乱后的结果
    }
}

字符串处理

JAVA的字符串操作类主要是String, StringBuilder, StringBuffer。

String一旦创建，内容不可修改。任何修改操作（如拼接、替换）都会生成新对象。（如果固定内存的字符串需要修改，用字符数组更好）

// 创建
String str1 = "Hello"; // 字符串字面量
String str2 = new String("Hello"); // 使用构造函数

// length() 获得长度
int length = str.length();

s.charAt(0)  // 访问字符
String sub = s.substring(0, 5);  // 切片
String result = s1 + " " + s2;  // 使用 + 拼接

StringBuilder sb = new StringBuilder();  // 利用StringBuilder
sb.append("Hello");
sb.append(" ");

String trimmed = s.trim();  // 去除两端空白字符

String s = "Hello, World!";
int index = s.indexOf("World");  // 查找子字符串的索引位置

String upper = s.toUpperCase();  // 转为大写
String formatted = String.format("My name is %s and I am %d years old.", name, age);  // 字符串格式化
String s = "apple,banana,cherry";
String[] fruits = s.split(",");  // 按逗号分割字符串

// 字符数组可以修改某位置字符
String str = "Hello";
char[] charArray = str.toCharArray();
charArray[1] = 'a';
String modifiedStr = new String(charArray);
System.out.println(modifiedStr);  // 输出: Hallo

StringBuilder 和 StringBuffer 是用于可变字符串的类。StringBuilder只能用于单线程环境, 直接修改内部字符数组，避免频繁创建新对象。StringBuffer 所有方法均用synchronized修饰, 性能低于StringBuilder, 但多线程安全。

修改字符串某位置的字符

// String 字符串不可修改某位置字符，可以利用stringBuilder
StringBuilder sb = new StringBuilder("Hello");
sb.setCharAt(1, 'a');
System.out.println(sb.toString());  // 输出: Hallo

sb.insert(5, " World"); // "Hello" → "Hello World"
sb.deleteCharAt(4); // "Hello" → "Hell"

int length()  // 长度
String result = sb.toString();

Go

数据结构

golang 用语言关键字提供了容器，不必额外导入包

静态数组, 固定大小的同一类型的元素。Go 数组的大小在声明时确定并且内容不可更改。

var arr [5]int // 定义一个长度为 5 的整型数组
arr[0] = 1
arr[1] = 2
fmt.Println(arr) // 输出: [1 2 0 0 0]

切片slice，动态数组。[]byte表示动态字符串。slice 的切片截取操作无须拷贝,

// 创建切片
slice := []int{1, 2, 3, 4, 5}
s := make([]int, 3, 5) // 长度3，容量5

slice = append(slice, 6)
slice = slice[:len(slice)-1]  // 删除最后一个元素
s = s[:0] // 清空元素（容量不变）

for i, v := range slice { fmt.Printf("Index: %d, Value: %d\n", i, v) }

fmt.Println(len(s)) // 3 获取长度
fmt.Println(cap(s)) // 5 获取容量

sub := s[1:3] // 截取切片, 包含索引1，不包含索引3 → [1, 2]

// 删除元素, 将删除位置后的元素前移，时间复杂度为 O(n)
// 会拷贝 slice[i+1:] 的元素到 slice[i:] 的位置。
slice = append(slice[:i], slice[i+1:])
// 删除元素还可以用最后一个元素覆盖删除位置
s[i] = s[len(s)-1]
s = s[:len(s)-1]

// 直接用数组创建切片
arr := [5]int{10, 20, 30, 40, 50}
s2 := arr[1:4] // [20, 30, 40]

map，哈希表实现的容器。map底层实现和C++的unorder_map、JAVA的hashmap不同
map的底层结构体是hmap，hmap里维护着若干个bucket数组 (即桶数组)。

每个桶存储固定数量的键值对（通常为 8 对），如果超过8个键值对了, 会先把多余的pair放到一个溢出桶中
map负载因子的定义是map中元素的个数 / map中当前桶的个数。当装载因子 > 6.5, 或溢出桶的数量过多，就会执行哈希表扩容。扩容非一次性完成, 每次对map进行删改操作时，会触发从oldbucket中迁移到bucket的操作, 在扩容没有完全迁移完成之前，每次get或者put遍历数据时，都会先遍历oldbuckets，然后再遍历buckets。

myMap := map[string]int{
    "apple":  5,
    "banana": 3,
}
m := make(map[string]int)
m3 := make(map[string]int, 100) // 预分配约 100 元素的容量

// 插入或更新元素
myMap["orange"] = 7

value, exists := m["key"] // exists 为 bool 类型，表示是否存在

for k, v := range myMap { fmt.Printf("Key: %s, Value: %d\n", k, v) }

value, exists := m["key"]
if exists {
    // 处理 value
}

length := len(m)   // 获取键值对数量

链表，使用container/list

package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    l.PushBack(1) // 在链表尾部插入
    l.PushFront(0) // 在链表头部插入

    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value) // 输出: 0 1
    }
}

channel，channel可认为是一个线程安全的协程间任务队列，内部通过链表和环形链表实现，这个可以在并发编程处详细展开。

算法

排序，import “sort”标准库

golang自定义struct的排序比较麻烦, 需要对自定义的struct实现Len() int , Less(i, j int) bool, Swap(i, j int) 三个接口

package main

import (
	"sort"
)

func main() {
	numbers := []int{5, 2, 9, 1, 5, 6}

	sort.Ints(numbers) // 排序，可以选择Ints, Strings, Stable等
}

// 自定义类型排序
type Person struct {
	Name string
	Age  int
}

type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	people := []Person{
		{"Alice", 25},
		{"Bob", 20},
		{"Charlie", 30},
	}

	sort.Sort(ByAge(people)) // 排序
}

字符串处理函数

Go中，string是不可变的 UTF-8 编码字符串, 无法原地修改字符串（编译失败）。[]byte是字符序列切片，可原地修改字符串。

golang字符串处理函数strings，如果要修改字符串, 必然会有内存拷贝。

s := "Hello, World!"
b := []byte(s) // 将 string 转换为 []byte

b := []byte{72, 101, 108, 108, 111}
s := string(b) // 将 []byte 转换为 string

str := "Hello"
len(str)  // 返回长度
str[1]  // 根据索引查看字符

str1 := "Hello"
str2 := "World"
result := str1 + ", " + str2  // + 拼接字符串

strings.Index(str, "World")  // 查找字符串
strings.Contains(str, "World")

// 以下都有内存拷贝
strings.Split(str, ",")  // 字符串分割，返回字符串数组
strings.TrimSpace(str)  // 去掉两侧空白

strings.ToUpper(str)  // 字符串大小写
strings.ToLower(str)

// 格式化生成新字符串
result := fmt.Sprintf("Name: %s, Age: %d", name, age)

strconv.Atoi(numStr) // 字符串转整数

bytes 包处理 []byte


data := []byte("name:age:email")

// 分割操作（无拷贝，共享底层数组）
parts := bytes.Split(data, []byte(":"))

Python

数据结构

列表，动态数组。和go一样，python列表支持切片。

1
2
3

my_list = [1, 2, 3, 4, 5]
my_list[0] = 10
my_list.append(6)

元组Tuple，不可变，只可被访问。

1 2	my_tuple = (1, 2, 3) a, b, c = my_tuple

字典dict, 无序（Python 3.7 及以上版本中插入有序）、键值对、键唯一。

dict的内部实现基于开放寻址法的哈希表

python3.7之后, 字典内部新增一个双向链表（或紧凑数组），按插入顺序记录所有键值对。

my_dict = {"name": "Alice", "age": 25}
my_dict["age"] = 30

要求：对象必须实现__hash__和__eq__方法。
__hash__：返回唯一且不变的哈希值。
__eq__：判断键是否相等。

class User:
    def __init__(self, id):
        self.id = id
    
    def __hash__(self):
        return hash(self.id)
    
    def __eq__(self, other):
        return self.id == other.id

users = {User(1): "Alice", User(2): "Bob"}

集合set，无序、不重复。

1 2	my_set = {1, 2, 3, 4, 5} my_set.add(6)

有序字典, 保留键值对插入顺序

from collections import OrderedDict

ordered_dict = OrderedDict()
ordered_dict["a"] = 1
ordered_dict["b"] = 2

python的 str不可变, 任何修改生成新对象（原对象不变）


# 列表（可变）
lst = [1, 2, 3]
lst[0] = 10      # 直接修改 → [10, 2, 3]
lst.append(4)    # 追加元素 → [10, 2, 3, 4]

# 字符串（不可变）
s = "hello"
s[0] = "H"       # 报错：TypeError
new_s = s.replace("h", "H")  # 生成新对象 "Hello"

# 列表
lst = [1, 2, 3, 4]
sub_lst = lst[1:3]  # [2, 3]（浅拷贝）
# 字符串
s = "hello"
sub_s = s[1:3]     # "el"（新字符串）

算法

排序
sorted(iterable, key=None, reverse=False), 返回一个新的排序列表，不改变原列表。

nums = [5, 2, 9, 1]
print(sorted(nums))  # 升序: [1, 2, 5, 9]
print(sorted(nums, reverse=True))  # 降序: [9, 5, 2, 1]

words = ["apple", "banana", "cherry"]
print(sorted(words, key=len))  # 按字符串长度排序: ['apple', 'cherry', 'banana']

# list.sort(), 原地排序，直接修改列表
nums = [5, 2, 9, 1]
nums.sort()

# 字典排序
my_dict = {"b": 2, "a": 1, "c": 3}
sorted_keys = sorted(my_dict)  # 按键排序
sorted_items = sorted(my_dict.items(), key=lambda item: item[1])  # 按值排序

字符串处理

s = "Hello"
len(s)
s[1]
s[-1]
s[1:3]
s + " "  # 拼接
print(f"My name is {name} and I am {age} years old.")  # 格式化输出, python3支持
s.upper()，s.lower()
s.strip()  # 去除空格
s.find("World")
s.replace("World", "Python")

s.split(",")

对于python2, 还有个编码的问题。处理办法是，对于u开头的字符串或者unicode类型的字符串，都使用encode(“utf-8”) 编码为str类型后，再使用。

# coding=utf-8
unicode_str = u"中文"  # Unicode 字符串
byte_str = "byte"  # 字节字符串
print(type(unicode_str))  # <type 'unicode'>
print(type(byte_str))  # <type 'str'>

print(type(unicode_str.encode("utf-8")))  # <type 'str'>