当前位置：首页 > article >正文

算法题常用的STL（Java与C++）(90%)

article 2024/9/22 14:43:00

1.数组（vector/ArrayList）

C++:

vector

vector<int> v;

//插入操作
v.push_back();

//清空操作
v.clear(); 

//求长度操作
int len=v.size();
v.empty();//判断是否为空

//删除字符串操作
v.pop_back(); // 删除向量末尾的元素
v.erase(v.begin() + n); // 删除索引为n的元素

//离散化操作+去重
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());

*在前面还有加上查找：
int find(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}


//翻转函数
v.reverse(v.begin(),v.end());

//查找函数 用的较少
auto it = find(v.begin(), v.end(), target);
if (it != v.end()) {
    cout << distance(v.begin(), it) << endl;
}


//自定义排序函数 lambda表达式
sort(v.begin(), v.end(), [](int a, int b) {
        return a > b; // 左升序 右降序
    });

也可以：
bool cmp(int x,int y){
    return x>y;  //降序
}
bool cmp(int x,int y){
    return x<y;//升序
}

还可以：
sort(v.begin(), v.end(),greater<int>();//降序
sort(v.begin(),v.end(),less<int>());//升序

java

ArrayList

List list = new ArrayList();

// 添加元素
list.add(n);
list.add(index, n);// 在指定位置插入元素
list.set(index,n);// 更新元素
// 获取元素
list.get(index);

// 删除元素
list.remove(n);
list.remove(index);// 删除指定位置的元素

// 检查元素是否存在
list.contains(n); 

// 获取ArrayList的大小
list.size();

// 清空ArrayList
list.clear();

// 遍历ArrayList
for (int n : list) {
    System.out.println(n);
}

// 使用迭代器遍历
Iterator<Interger> iterator = list.iterator();
while (iterator.hasNext()) {
    int n = iterator.next();
    System.out.println(n);
}

LinkedList（双向链表）

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

import java.util.LinkedList;
// 创建一个空的LinkedList
LinkedList<String> list = new LinkedList<String>();
// 添加元素到列表末尾
list.add("Apple");
// 添加元素到列表开头
list.addFirst("Banana");
// 在指定位置插入元素
list.add(1, "Cherry");
// 获取第一个元素
String first = list.getFirst();
// 获取最后一个元素
String last = list.getLast();
// 删除第一个元素
String removedFirst = list.removeFirst();
// 删除最后一个元素
String removedLast = list.removeLast();
// 删除指定位置的元素
String removed = list.remove(1);
// 检查元素是否存在
boolean contains = list.contains("Cherry");
// 获取LinkedList的大小
int size = list.size();
// 清空LinkedList
list.clear();
// 遍历LinkedList
for (String fruit : list) {
    System.out.println(fruit);
}

HashSet（不重复元素的集合）

// 添加元素
set.add(n);

// 删除元素
set.remove(n);

// 检查元素是否存在
boolean contains = set.contains(n);

// 获取HashSet的大小
int size = set.size();

// 清空HashSet
set.clear();

// 遍历HashSet
for (String fruit : set) {
    System.out.println(fruit);
}

2.Map

C++：

map

map<E,E> m;

//map中使用较多1，存储  2，遍历  3，排序 4，查找

//存储,m[key]=value；
m[E]=E;

//查找
auto it = m.find(n); // 查找key为n的元素
if (it != m.end()) {
    cout<<it->second<<endl;//输出value值
}

//删除
m.erase(n); // 删除key为n的元素
m.erase(m.begin()); // 删除映射中的第一个元素

//统计key个数
m.count("key");
//遍历
for(auto k:m) {
    cout<<k.first<<' '<<k.second<<endl;
}

//排序 默认按照key值升序排序
//在声明的时候添加:greater<int>  就变成降序排序
map<E,E,greater<E>> //默认按照key降序排序

//自定义排序主要用于按照value进行排序的情况
bool cmp(const pair<int, string>& a, const pair<int, string>& b) {// 自定义比较函数，用于比较map的value
    return a.second < b.second; // 按照value的字典序排序
}

vector<pair<E, E>> v(m.begin(), m.end());//直接把map当作pair类型存到vector中，key->first  value-seond

sort(v.begin(),v.end(),cmp);//现在直接输出v即可
/*简易测试代码
    m[0]="1";
    m[2]="11";
    m[1]="22";
    vector<PII> v(m.begin(),m.end());
    sort(v.begin(),v.end(),cmp);
    for(auto k:v) cout<<k.first<<' '; //输出的是key 
    输出:0 2 1  正常输出应该是默认升序0 1 2
*/

unordered_map

unordered_map<int,int> data;

插入：
    // 方式1: 使用下标运算符[]，如果键不存在，则插入新元素
    data["apple"] = 5;
    // 方式2: 使用insert()函数插入一个pair类型的对象
    data.insert(pair<string, int>("banana", 3));
    // 方式3: 使用insert()函数插入一个make_pair()生成的键值对
    data.insert(make_pair("orange", 7));
    // 方式4: 使用insert()函数插入一个初始化列表表示的键值对
    data.insert({"grape", 2});
    // 方式5: 使用emplace()函数直接构造键值对并插入
    data.emplace("pear", 4);

//从容器中删除。
//key
data.erase("orange");
//迭代器
auto it = data.find("grape");
if (it != data.end()) {
    data.erase(it);
}

clear()：清除容器中的所有元素。

//通过key查找元素
auto it = data.find("apple");
if (it != data.end()) {
    // 找到元素，进行操作
}
//判断key是否存在
if (data.count("banana")) {
    // 键存在
}

遍历：
for (const auto& pair : data) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}
for (auto it = data.begin(); it != data.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

Java：

Hashmap

Map<String, Integer> map = new HashMap<String, Integer>();

// 添加键值对
map.put(n, m);

// 获取值
map.get(n);

// 检查键是否存在
map.containsKey(n);//如果有值就用原来的值  没有赋新值(记不得那个操作了)
map.containsKey(n) ? map.put(n,map.get(n)+x) : m;  //三元运算符实现

// 删除键值对
map.remove(n);
map.clear();// 清空HashMap

// 获取HashMap的大小
map.size();

// 遍历HashMap的键
for (String key : map.keySet()) {
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

// 遍历HashMap的条目
for (HashMap.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

// 添加元素
set.add(n);

// 删除元素
set.remove(n);

// 检查元素是否存在
boolean contains = set.contains(n);

// 获取HashSet的大小
int size = set.size();

// 清空HashSet
set.clear();

// 遍历HashSet
for (String fruit : set) {
    System.out.println(fruit);
}

3.栈与队列

C++：

队列queue

queue<int> q

//入队
q.push(n);
    
//获取对头
q.front();
q.back();//获取队尾

//对头出队
q.pop();

//大小
q.size();
q.empty();//非空判断

优先队列 priority_queue：（插入一个数就排序的队列）

priority_queue<int, vector<int>, less<int>/greater<int>> pq;

//入队
pq.push(n);
    
//获取对头
pq.top();
pq.back();//获取队尾

//对头出队
pq.pop();

//大小
pq.size();
pq.empty();//非空判断

栈stack

stack<int> s;

//入栈
s.push();

//访问
s.top();
s.pop(); //出栈

//大小
s.size();
s.empty();//非空判断

java：

Queue

Queue queue = new LinkedList<>();

在Java中，Queue 是一个先进先出（FIFO）的数据结构，它通过接口来实现，常用的实现类有 LinkedList 和 PriorityQueue。

// 入队操作
queue.offer(1);

// 出队操作
int head = queue.poll(); // 移除并返回队头元素

// 查看队头元素（不出队）
int peek = queue.peek();

// 获取队头元素（如果队列为空，则抛出NoSuchElementException）
int element = queue.element();

// 获取Queue的大小
queue.size();

// 检查Queue是否为空
queue.isEmpty();

// 清空Queue
queue.clear();

// 遍历Queue
while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

// 使用迭代器遍历
Iterator<Integer> iterator = queue.iterator();
while (iterator.hasNext()) {
    Integer element = iterator.next();
    System.out.println(element);
}

优先队列：

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(10, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return a - b; //if a>b 则交换，so这是递增序列
}
});

// 入队操作
queue.offer(1);

// 出队操作
int head = queue.poll(); // 移除并返回队头元素

// // 获取队头元素（不出队）
int peek = queue.peek();


// 获取Queue的大小
queue.size();

// 检查Queue是否为空
queue.isEmpty();

// 清空Queue
queue.clear();

// 遍历Queue
while (!queue.isEmpty()) {
    System.out.println(queue.poll());
}

Stack

Stack stack = new Stack<>();

在Java中，Stack 是一个后进先出（LIFO）的数据结构，它是通过扩展 Vector 类来实现的。

// 压栈操作
stack.push(1);

// 出栈操作
int top = stack.pop(); // 移除并返回栈顶元素

// 查看栈顶元素（不出栈）
int peek = stack.peek();

// 搜索元素，返回元素在栈中的位置（距离栈顶的距离）
int index = stack.search(n);

// 获取Stack的大小
int size = stack.size();

// 检查Stack是否为空
boolean isEmpty = stack.isEmpty();

// 清空Stack
stack.clear();

// 遍历Stack
while (!stack.isEmpty()) {
    System.out.println(stack.pop());
}

// 使用迭代器遍历
Iterator<Integer> iterator = stack.iterator();
while (iterator.hasNext()) {
    Integer element = iterator.next();
    System.out.println(element);
}

查看全文

http://www.kler.cn/news/284265.html