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

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

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

#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<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();                       // 出队

// 按字符串长度排序
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);

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

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

排序算法	最佳时间复杂度	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性	原地排序	备注
​​冒泡排序​​	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为基数大小），通常用于整数或字符串。

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

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

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

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

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

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

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

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

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

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后的位置）

// 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); 

// 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();

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

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

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; // 获取数组长度（非方法，是字段）

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); // 添加另一个集合的所有元素

import java.util.LinkedList;

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

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]

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]

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);  // 输出: 随机打乱后的结果
    }
}

// 创建
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

// 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();

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

// 创建切片
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]

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)   // 获取键值对数量

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

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)) // 排序
}

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) // 字符串转整数

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

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

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

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

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

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

# 列表（可变）
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"（新字符串）

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(",")

# 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'>