# learnAlgorithm

**Repository Path**: dream_zhou/learn-algorithm

## Basic Information

- **Project Name**: learnAlgorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-05-29
- **Last Updated**: 2021-05-29

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 算法学习笔记

[TOC]

《labuladong 的算法小炒》作者 付东来(@labuladong)

## 语言基础

### C++

#### `vector`

 初始化

```c++
int n  = 7;
int m = 8;

// 初始化一个 `int` 型的空数组 nums
vector<int> nums;

// 初始化一个大小为 n 的数组，数组的默认值都是0
vector<int> nums(n);

// 初始化一个元素为 1、3、5 的数组
vector<int> nums{1, 3, 5};

// 初始化一个大小为n 的数组，其值全部为 2 
vector<int> nums(n, 2);

// 初始化一个二维int数组
vector<vector<int>> dp;

// 初始化一个大小为 m * n 的布尔数组
vector<vector<bool>> dp(m, vector<bool>(n, true));
```

成员函数

```c++
// 返回是否为空
bool empty();

// 返回数组的元素个数
size_type size();

// 返回数组最后一个元素的引用
reference back();

// 在数组尾部插入一个元素 val
void push_back(const value_type& val);

// 删除数组尾部的那个元素
void pop_back();
```

#### `string`

初始化方法

```c++
// 空字符串
string s;

// s 是字符串 "abc"
string s = "abc"
```

成员函数

```c++
// 返回字符串的长度
size_t size();

// 判断字符串是否为空
bool empty();

// 在字符串尾部插入一个字符 c
void push_back(char c);

// 删除字符串尾部的那个字符
void pop_back();

// 返回从索引 pos 开始，长度为 len 的子字符串
string substr(size_t pos, size_t len);
```

判断2个字符串的相等性可以直接用 `==`

#### 哈希表 `unordered_map`

初始化方法

```c++
// 初始化一个 key 为 int， value为int 的哈希表
unordered_map<int, int>mapping;

//初始化一个 key 为 string，value 为 int 数组的哈希表
unordered_map<string, vector<int>> mapping;
```

成员函数

```c++
// 返回键值对的个数
size_type size();

// 是否为空
bool empty();

// 返回哈希表中 key 出现的次数
// 因为 hashmap 不会出现重复的键，此函数只可能返回 0 或 1
size_type count(const key_type& key);

// 通过key 清除hasmap中的键值对
size_type erase(const key_type& key);

// 
unordered_map<int, int> counter;
// 插入

// 遍历键值对
for(auto& it : counter) {
    int key = it.first;
    int value = it.second;
    cout << key << ": " << val << endl;
```

**使用`[]`方位其中的键 `key`时，如果`key`不存在，则会自动创建key，值为值类型的默认值**

#### 哈希集合`unordered_set`

初始化方法

```c++
// 初始化一个存储int 的 哈希集合
unordered_set<int> visited;

// 初始化一个存储string的哈希集合
unordered_set<string> visited;
```

成员函数

```c++
// 个数
size_type size();

// 是否为空
bool empty();

// 出现的次数，存在 1，否则0
size_type count(const key_type& key);

// 向集合中插入一个元素 key
pair<iterator, bool> insert(const key_type& key);

// 删除哈希集合中的元素 key
// 删除成功返回 1， 不存在返回0
size_type erase(const key_type& key);
```

#### 队列`queue`

初始化方法

```c++
// 初始化一个存储int的队列
queue<int> q;

// 
queue<string> q;
```

成员函数

```c++
// 是否为空
bool empty();

// 个数
size_type size();

// 加入队尾
void push(const value_type& val);

// 队头的引用
value_type& front();

// 删除队头元素
void pop();
```

C++ `pop` 不返回删除的元素

```c++
int e = q.front();
q.pop();
```

#### 堆栈`stack`

初始化方法

```c++
stack<int> stk;
stack<string> stk;
```

成员函数

```c++
// 是否为空
bool empty();

// 个数
size_type size();

// 栈顶添加元素
void push(const value_type& val);

// 返回栈顶元素的引用
value_type& front();

// 移除栈顶元素
void pop()
```

### Java

#### 1. 数组

初始化方法

```java
int m = 5;
int n = 10;

// 大小10， 值为0
int[] nums = new int[n]

// m * n 二维数组
boolean[][] visited = new boolean[m][n];

// 以参数传入，先进行非空检查
if (nums.length == 0) {
    return;
}
for(int i = 0; i < nums.length; i++) {
    // ...
}
```

#### 2. 字符串 `String`

不支持`[]` 访问其中的字符，不能直接修改，要转为`char[]`类型后才能修改

```java
String s1 = "hello java";
char c = s1.charAt(2);

char[] chars = s1.toCharArray();
chars[1] = 'a';
String s2 = new String(chars);
System.out.println(s2);

// 使用 equals 方法判断字符串是否相同
if (s1.equals(s2)) {
    // balabala
} else {
    
}

// 可以 + 号拼接
String s3 = s1 + "!";
System.out.println(s3);

// 频繁进行字符串拼接，使用 StringBuilder
StringBuilder sb = new StringBuilder();
for(char c = 'a'; c <= 'f'; c++) {
    sb.append(c);
}

// append 方法支持拼接字符、字符串、数字
sb.append('g').append("hi").append(321);
String res = sb.toString();

```

#### 3. 动态数组 `ArrayList`

初始化

``` java
ArrayList<String> names = new ArrayList<>();
ArrayList<Integer> nums = new ArrayList<>();
```

常用方法 （E为元素类型）

```java
// 是否为空
boolean isEmpty();

// 个数
int size();

//
E get(int index);

// 尾部添加元素
boolean add(E e);
```

#### 4. 双链表 `LinkedList`

初始化

```java
LinkedList<Integer> nums = new LinkedList<>();
LinkedList<String> names = new LinkedList<>();
```

常用方法  （E为元素类型）

```java
// 是否为空
boolean isEmpty();

// 个数
int size();

// 是否存在 （复杂度 O(N)）
boolean contains(Object o);

// 尾部添加元素
boolean add(E e);

// 头部添加元素
boolean addFirst(E e);

// 删除头部的第一个元素
E removeFirst();

// 删除最后一个
E removeLast();
```

#### 5. 哈希表 `HashMap`

初始化方法

```java
HashMap<Integer, String> map = new HashMap<>();
HashMap<String, int[]> map = new HashMap<>();
```

常用方法 （K为键的类型， V为值的类型）

```java
// 是否存在
boolean contains(Object o);

// 获得key对应的值，如不存在，返回 null
V get(Object key);

// 将 key, value 存入哈希表
V put(K key, V value);

// 如果key 存在，删除key 返回对应的值
V remove(Object key);

// 获得 key 的值，如不存在返回 defaultValue
V getOrDefault(Object key, V defaultValue);

// 获得哈希表中的所有key
Set<K> keySet();
    
// 如果不存在，则插入
// 存在啥都不做
V putIfAbsent(K key, V value);  
```

#### 6. 哈希集合 `HashSet`

初始化方法

```java
Set<String> set = new HashSet<>();
```

常用方法  （E为元素类型）

```java
// 如不存在则插入
boolean add(E e);

// 是否存在
boolean contains(Object o);

// 如存在则删除
boolean remove(Object o);
```

#### 7.队列 `Queue`

初始化, Queue 是个接口

```java
Queue<String> q = new LinkedList<>();
```

常用方法  （E为元素类型）

```java
// 是否为空
boolean isEmpty();

// 个数
int size();

// 返回队头的元素
E peek();

// 删除并返回队头的元素
E poll();

// 将元素e 插入队尾
boolean offer(E e);
```

#### 8. 堆栈 `Stack`

初始化方法

```java
Stack<Integer> s = new Stack<>();
```

常用方法  （E为元素类型）

```java
// 是否为空
boolean isEmpty();

// 个数
int size();

// 压栈
E push(E item);

// 栈顶
E peek();

// 删除并返回栈顶元素
E pop();
```

### Python3

#### 列表 `list`

```python
# 数组
arr = [1, 2, 3, 4]
print(arr[2])
# 尾部添加
arr.append(5)
# -1 代表最后一个索引
print(arr[-1])

# 模拟堆栈
stack = []

# 把列表尾部作为栈顶
# 在栈顶添加元素
stack.append(1)
stack.append(2)
#删除栈顶元素并返回
e1 = stack.pop()
#查看栈顶元素
e2 = stack[-1]
```