LeetCode

发布日期: 2021-08-16

作者: M

文章字数: 3.5k

阅读时长: 18 分

热度:

输入输出

将向量以特定的分隔符输出到屏幕中

#include <vector>
#include <stack>
#include <iostream>
#include <sstream>
using namespace std;

//方法1：用stringstream
int main() {
    vector<int> v{1, 2, 3};
    stringstream ss;
    for (auto &i :v) {
        if (i != v[0]) {
            ss << '|';
        }
        ss << i;
    }
    cout << ss.str() << endl;// 1|2|3
}
//方法2: 用输出流迭代器
#include <iterator>
int main() {
    vector<int> nums = {1, 2, 3};
//    将结果给stream
    ostringstream stream;
    copy(nums.begin(), nums.end(), ostream_iterator<int>(stream, "|"));
//    去掉最后一个分隔符
    string s=stream.str();
    s.erase(s.length()-1);
    cout << s << endl;
}


// 方法3：用for_each 和lambda函数的组合
// 捕获列表[]中放置局部变量,这样才能在lambda函数中使用该变量，num为lambda自己的参数
#include <iostream>
#include <map>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
    vector<int> v{1,2,3};
    for_each(v.begin(), v.end(), [v](const int &num) {
        if (num != *(v.end() - 1)) {
            cout << num << "|";
        } else
            cout << num;
    });
}

C++根据’,’将string数据进行分隔

方法1：使用stringstream进行split,用 while (getline(ss, word, delim)){...}将数据分隔

#include <iostream>
#include <string>
#include <vector>

using namespace std;

////方法1：
//添加下面的库：万金油式的库，但比较费时间
#include <bits/stdc++.h>

//delim 用来记录分隔符
vector<string> split(string s, char delim) {
    stringstream ss(s);
    string word; // 分隔符之间的内容
    vector<string> vec;
    while (getline(ss, word, delim)) {
        vec.push_back(word);
    }
    return vec;
}

int main() {
    string s("1,2,3,4,5,6,66");
    vector<string> v = split(s, ',');

    for (auto &vv:v) {
        cout << vv << endl;
    }
}

方法2：for循环（供参考）

#include <iostream>
#include <string>
#include <vector>

using namespace std;

//方法2：
vector<string> split(string s) {
    vector<string> vec;
    int start = 0;
    for (int i = 0; i <= s.size(); ++i) {
        if (i == s.size() || s[i] == ',') {
            vec.push_back(s.substr(start, i - start));
            start = i + 1;
        }
    }
    return vec;
}

int main() {
    string s("1,2,3,4,5,6,66");
    vector<string> v = split(s);

    for (auto &vv:v) {
        cout << vv << endl;
    }

}

数据类型

字典

python字典

普通字典常用的操作

字典按键或值排序
- 注：经过sorted()函数后，字典变成了存放元组的列表

d = {1: 2, 3: 4, 2: 1, 5: 3}
# 按键排序
d_k = sorted(d.items(), key=lambda x: x[0])
print(d_k) # [(1, 2), (2, 1), (3, 4), (5, 3)]
# 按值排序
d_v = sorted(d.items(), key=lambda x: x[1])

#取出排序后的键
print([i[0] for i in d_k]) # [1, 2, 3, 5]
# 把键按空格输出
res=" ".join(map(str,[i[0] for i in d_k]))
print(res)
# 取出排序后的值
print([i[1] for i in d_k]) # [2, 1, 4, 3]

defaultdict 字典

常用的defaultdict字典操作

defaultdict接受一个工厂函数作为参数：dict =defaultdict( factory_function). 这个factory_function可以是list、set、str、int等等。作用是当key不存在时，返回的是工厂函数的默认值。比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0

取出字典中的信息

import collections
s = [('yellow', 6), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
d = collections.defaultdict(list) # d的键对应的值默认为列表

for k, v in s:
    d[k].append(v)
print(d)# defaultdict(<class 'list'>, {'yellow': [6, 3], 'blue': [2, 4], 'red': [1]})
# 按键排序
print(sorted(d.items())) # [('blue', [2, 4]), ('red', [1]), ('yellow', [6, 3])]
# 打印字典
print(d.items()) # dict_items([('yellow', [6, 3]), ('blue', [2, 4]), ('red', [1])])
# 打印某键对应的值
print(d["blue"]) # [2, 4]
# 打印键
print(d.keys()) # dict_keys(['yellow', 'blue', 'red'])
# 打印值
print(d.values()) # dict_values([[6, 3], [2, 4], [1]])
# 把值以列表的形式输出
print(list(d.values())) # [[6, 3], [2, 4], [1]]

from collections import defaultdict
dic=defaultdict(list)
dic[1]=[1,2,3]
dic[1].append([7,8,9])
dic[2]=[2,3,4]
print(dic) # defaultdict(<class 'list'>, {1: [1, 2, 3, [7, 8, 9]], 2: [2, 3, 4]})
# 也可以直接取字典中的元素
keys=[i for i in dic.keys()]
values=[i for i in dic.values()]
print(keys) # [1, 2]
print(values) # [[1, 2, 3, [7, 8, 9]], [2, 3, 4]]

列表按字典序输出结果

a=['1', '11', '2', '3', '12']
# 按字符串排序，并输出
print(sorted(a)) # ['1', '11', '12', '2', '3']

# 将 ['1', '11', '12', '2', '3'] 转化成 [1, 11, 12, 2, 3]
a=['1', '11', '2', '3', '12']
b=list(map(int,a))
print(b)
# 或者凑出来： print('['+', '.join(sorted(a))+']')

# 经过上面处理后，a字符变成了b这样的
b=[1,11,2,3,12]
# 按数字大小排序，并输出
print(sorted(b)) # [1, 2, 3, 11, 12]

C++字典

按键或值排序
将字典转换成向量。如果是按键排序，则用默认的sort(vec.begin(), vec.end())即可。如果是按值排序，则构建bool函数（或者用lambda函数），将该函数传到sort函数的参数中 sort(vec.begin(), vec.end(), sortByVal) （或者将sortByVal函数用lambda函数代替）

#include <iostream>
#include <map>
#include <vector>
#include <algorithm> // for sort function

using namespace std;


int main()
{
    // create the map
    map<string, int> mymap = {
            {"coconut", 10}, {"apple", 5}, {"peach", 30}, {"mango", 8}
    };

    //默认的按键排序
    cout << "The map, sorted by keys, is: " << endl;
    map<string, int> :: iterator it;
    for (it=mymap.begin(); it!=mymap.end(); it++)
    {
        cout << it->first << ": " << it->second << endl;
    }
    cout << endl;


//    // 直接将map分配到vector中
   vector<pair<string, int>> vec(mymap.begin(), mymap.end());
    ////    或者可以一一推进vector中
//    // create a empty vector of pairs
//    vector<pair<string, int>> vec;
//    // copy key-value pairs from the map to the vector
//    map<string, int> :: iterator it2;
//    for (it2=mymap.begin(); it2!=mymap.end(); it2++)
//    {
//        vec.push_back(make_pair(it2->first, it2->second));
//    }


//    将map转成vector后，按值排序 sort the vector by increasing order of its pair's second value
    sort(vec.begin(), vec.end(), [](auto &left, auto &right) {
        return left.second < right.second; // left和right的类型为pair<string, int>
    });

    // print the vector
    cout << "The map, sorted by value is: " << endl;
    for (int i = 0; i < vec.size(); i++)
    {
        cout << vec[i].first << ": " << vec[i].second << endl;
    }
    return 0;
}
//结果：
//The map, sorted by keys, is:
//apple: 5
//coconut: 10
//mango: 8
//peach: 30
//
//The map, sorted by value is:
//apple: 5
//mango: 8
//coconut: 10
//peach: 30

找到multimap中的相同键对应的值，并计算其数量

count(): multimap::count(k)统计键值k对应的元素数量
equal_range(): multimap::equal_range(k)Returns the bounds of a range that includes all the elements in the container which have a key equivalent to k.

#include <iostream>
#include <map>
using namespace std;

int main(){
    multimap<char, int> mm;
    mm.insert(make_pair('x',50));
    mm.insert(make_pair('y',100));
    mm.insert(make_pair('y',150));
    mm.insert(make_pair('y',200));
    mm.insert(make_pair('z',250));
    mm.insert(make_pair('z',300));

    for(char c='x';c<='z';c++){
        cout<<c<<"\t"<<mm.count(c)<<":"<<"\t";
        multimap<char,int>::iterator it;
        for (it =mm.equal_range(c).first;it!=mm.equal_range(c).second;it++){
            cout<<(*it).second<<" ";
        }
        cout<<endl;
    }
}
//x    1:    50
//y    3:    100 150 200
//z    2:    250 300

multimap

Multimap is similar to map with an addition that multiple elements can have same keys. Also, it is NOT required that the key value and mapped value pair has to be unique in this case. One important thing to note about multimap is that multimap keeps all the keys in sorted order always. These properties of multimap makes it very much useful in competitive programming.

可以借助multimap的特性，将map的键值互换，使map按值排序

#include <map>
#include <iostream>

int main()
{
    std::map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
    std::multimap<int, int> mm;

    for(auto const &kv : m)
        mm.insert(std::make_pair(kv.second, kv.first));

    for(auto const &kv : mm)
        std::cout << "m[" << kv.second << "] = " << kv.first << std::endl;

    return 0;
}
// 结果：
// m[6] = 1
// m[2] = 5
// m[4] = 6
// m[1] = 10

可以将map转化成vector of pairs，然后使用vector的特性，使map按值排序

#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    map<int, int> m = {{1, 10},
                       {2, 5},
                       {4, 6},
                       {6, 1}};
    using mypair = pair<int, int>;


    vector<mypair> v(m.begin(), m.end());

    sort(v.begin(), v.end(), [](const mypair &a, const mypair &b) { return a.second < b.second; });

    for (auto const &p : v)
        cout << "m[" << p.first << "] = " << p.second << endl;

    return 0;
}
//结果：
//m[6] = 1
//m[2] = 5
//m[4] = 6
//m[1] = 10

向量

一维二维升序降序排列

比如信封有宽度高度。先对宽度（第一个数）进行升序排序，宽度相同时，对高度（第二个数）降序排序

envelopes=sorted(envelopes,key=lambda x:(x[0],-x[1]))

// 用到了lambda表达式
sort(envelopes.begin(), envelopes.end(), [](vector<int> &a, vector<int> &b) {
    if (a[0] == b[0]) {
        return a[1] > b[1];// 如果宽度相同，则高度降序排列
    }
    return a[0] < b[0]; // 宽度升序排列
});

返回最大元素及其索引

a=[1,2,3,4,1]
print(max(a))
print(a.index(max(a)))

vector<int> v{ 3, 1, -14, 1, 5, 9 }
int res=*max_element(v.begin(), v.end()); //最大元素
std::distance(v.begin(), result) // 最大元素对应的索引位置

移除重复元素

Just using vector, sort + unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

Convert to set (using a constructor)

set<int> s( vec.begin(), vec.end());
vec.assign( s.begin(), s.end() );

正则表达式

正则表达式速查

What does ‘r’ mean before a Regex pattern?

The R or r means that the string is to be treated as a raw string, which means all escape codes will be ignored.

Modern C++正则表达式用法示例

根据加减号将字符串分隔，匹配结果的结尾不包括分隔符: regex re("(?=[-+*/])")
- x(?=y)向前断言: x 被 y 跟随时匹配 x。例如，对于/Jack(?=Sprat)/，“Jack”在跟有“Sprat”的情况下才会得到匹配．/Jack(?=Sprat|Frost)/ “Jack”后跟有“Sprat”或“Frost”的情况下才会得到匹配。不过，匹配结果不包括“Sprat”或“Frost”。
- sregex_token_iterator的-1含义：Returns the value represented by the digit c in base radix. If c is not a valid digit character, the function returns -1.
- 注意：这里有一个非常隐蔽的bug。通过re("(?=[-+*/])") 分隔字符时，若一开始就是符号，则也会提取符号前面的内容。如”-1+2”会分成””,”-1”,”+2”（注意这里有一个””）。所以迭代器要用if ((*it)=="") it++; 跳过这个空的，从下一个开始算起

#include <vector>
#include <string>
#include <iostream>
#include <regex>
using namespace std;

int main() {
    string s{"5+4-3*2/1"};
    regex re("(?=[-+*/])"); // 或者regex re(R"((?=[\+\-\*\/]))");
    sregex_token_iterator it{s.begin(),s.end(),re,-1},end;
    if ((*it)=="") it++; // 注意这句话
    vector<string> v(it,end);
    for (auto i:v){
        cout<<i<<"\t";   // 5    +4    -3    *2    /1
    }
}

根据加减号将字符串分隔，匹配结果不要任何分隔符: regex re("[-+*/]")

#include <vector>
#include <string>
#include <iostream>
#include <regex>
using namespace std;

int main() {
    string s{"5+4-3*2/1"};
    regex re("[-+*/]");  // 或者regex re(R"([\+\-\*\/])");
    sregex_token_iterator it{s.begin(),s.end(),re,-1},end;
    if ((*it)=="") it++; // 注意这句话
    vector<string> v(it,end);
    for (auto i:v){
        cout<<i<<"\t";   //  5    4    3    2    1
    }
}

与$相关的正则表达式
- $& - 正则表达式匹配的文本
- $` - 匹配文本的左侧内容
- $’ - 匹配文本的右侧内容

var text = "abc123def", total, left, right;
total = text.replace(/\d+/g, "[$&]");   // abc[123]def
left = text.replace(/\d+/g, "[$`]");     // abc[abc]def
right = text.replace(/\d+/g, "[$']");   // abc[def]def

按不同的字符分隔字符串。即实现string1.Replace("-", "#-").Split("#");: 符号前面加#，然后按#进行分隔
- 添加一个dummy的标志，$&获取当前内容 -1+2*3/4 -> #-1#+2#*3#/4
- 使用stringstream，通过dummy标志分隔 #-1#+2#*3#/4 -> -1 +2 *3 /4
  - 如果只替换一个字符（//replace all occurances of ‘x’ with ‘y’），则用s.replace( s.begin(), s.end(), 'x', 'y'); 即可。不必用正则
  - 向量也可以用replace函数进行局部替换

#include <vector>
#include <string>
#include <iostream>
#include <regex>

using namespace std;

int main() {
    string test = "-1+2*3/4";
    regex reg("(?=[-+*/])"); // 或者regex re(R"((?=[\+\-\*\/]))");
    test = regex_replace(test, reg, "#$&");
    cout << test;// #-1#+2#*3#/4

    vector<string> v;
    string item = "";
    stringstream ss(test);
    while (getline(ss, item, '#')) {
        v.push_back(item);
    }

    for (auto &i:v) {
        cout << i << "\t"; // -1    +2    *3    /4
    }
}

Difference between ?:, ?! and ?=
- The difference between ?= and ?! is that the former requires the given expression to match and the latter requires it to not match. For example a(?=b) will match the “a” in “ab”, but not the “a” in “ac”. Whereas a(?!b) will match the “a” in “ac”, but not the “a” in “ab”.
- The difference between ?: and ?= is that ?= excludes the expression from the entire match while ?: just doesn’t create a capturing group. So for example a(?:b) will match the “ab” in “abc”, while a(?=b) will only match the “a” in “abc”. a(b) would match the “ab” in “abc” and create a capture containing the “b”.
\\ 含义
- If “.” matches any character, how do you match a literal “.”? You need to use an “escape” to tell the regular expression you want to match it exactly, not use its special behaviour. Like strings, regexps use the backslash, \, to escape special behaviour. So to match an ., you need the regexp \.. Unfortunately this creates a problem. We use strings to represent regular expressions, and \ is also used as an escape symbol in strings. So to create the regular expression \. we need the string “\\.“.

heap

import heapq
a=[(3,"1"),(4,"2")]
heapq.heapify(a)
heapq.heappush(a,(10,"11"))
b,c=heapq.heappop(a)
print(a) # [(4, '2'), (10, '11')]
print(b) # 3
print(c) # 1

Find the largest and smallest elements from Heap in Python

# Python code to demonstrate working of
# nlargest() and nsmallest()

# importing "heapq" to implement heap queue
import heapq

# initializing list
li1 = [6, 7, 9, 4, 3, 5, 8, 10, 1]

# using heapify() to convert list into heap
heapq.heapify(li1)

# using nlargest to print 3 largest numbers
# prints 10, 9 and 8
print("The 3 largest numbers in list are : ", end="")
print(heapq.nlargest(3, li1))

# using nsmallest to print 3 smallest numbers
# prints 1, 3 and 4
print("The 3 smallest numbers in list are : ", end="")
print(heapq.nsmallest(3, li1))

# Output：
# The 3 largest numbers in list are : [10, 9, 8]
# The 3 smallest numbers in list are : [1, 3, 4]

Binary Search (bisect) in Python

返回左或右索引：

# Python code to demonstrate the working of
# bisect(), bisect_left() and bisect_right()

# importing "bisect" for bisection operations
import bisect

# initializing list
li = [1, 3, 4, 4, 4, 6, 7]

# using bisect() to find index to insert new element
# returns 5 ( right most possible index )
print ("Rightmost index to insert, so list remains sorted is : ",
    end="")
print (bisect.bisect(li, 4))

# using bisect_left() to find index to insert new element
# returns 2 ( left most possible index )
print ("Leftmost index to insert, so list remains sorted is : ",
    end="")
print (bisect.bisect_left(li, 4))

# using bisect_right() to find index to insert new element
# returns 4 ( right most possible index )
print ("Rightmost index to insert, so list remains sorted is : ",
    end="")
print (bisect.bisect_right(li, 4, 0, 4))

根据顺序，在合适的地方插入值

# Python code to demonstrate the working of
# insort(), insort_left() and insort_right()

# importing "bisect" for bisection operations
import bisect

# initializing list
li1 = [1, 3, 4, 4, 4, 6, 7]

# initializing list
li2 = [1, 3, 4, 4, 4, 6, 7]

# initializing list
li3 = [1, 3, 4, 4, 4, 6, 7]

# using insort() to insert 5 at appropriate position
# inserts at 6th position
bisect.insort(li1, 5)

print ("The list after inserting new element using insort() is : ")
for i in range(0, 7):
    print(li1[i], end=" ")

# using insort_left() to insert 5 at appropriate position
# inserts at 6th position
bisect.insort_left(li2, 5)

print("\r")

print ("The list after inserting new element using insort_left() is : ")
for i in range(0, 7):
    print(li2[i], end=" ")

print("\r")

# using insort_right() to insert 5 at appropriate position
# inserts at 5th position
bisect.insort_right(li3, 5, 0, 4)

print ("The list after inserting new element using insort_right() is : ")
for i in range(0, 7):
    print(li3[i], end=" ")