1 Coding style and STL

STL

Category	Container	Expression	Notes
Sequence Containers	string, vector, deque, list	a.front()/a.back()	Equivalent to a.begin(),(--a.end())
		a[n]	list not apply
		void push_front(t)/void pop_front()	deque, list
		void push_back(t)/void pop_back()	All
(Unordered)Associative Containers	set, map, multiset, multimap(unordered_set, unordered_map, unordered_multiset, unordered_multimap)	size_type count( const Key& key ) const;	All
(Unordered)Associative Containers		bool contains( const Key& key ) const	All
Container adaptors	stack, queue, priority_queue	void push( value_type&& value )/void pop()	All
		reference top()	stack, priority_queue
		reference front()/back()	queue(begin(),(--end())

算法	类型	Structure	function	备注
Non-modifying sequence operations O(n)	Sequence Containers && Associative containers		iterator min_element(iterator first, iterator last[,Pred op])
			iterator max_element(iterator first, iterator last[,Pred op])
			int count(iterator first, iterator last,const T& val)
			iterator find(iterator first, iterator last,const T& val)
插入算法第一个被插入元素的迭代器first	Single element	vector	iterator insert (const_iterator position, const value_type& val);
		set	pair<iterator,bool> insert (const value_type& val);	pair::second inserted(1)or existed(0)
		string	string& insert (size_t pos, const char* s);
	Fill	vector	iterator insert (const_iterator position, size_type n, const value_type& val);	长度
	Fill	string	string& insert (size_t pos, size_t n, char c);	长度
	Range	vector, string	iterator insert (const_iterator position, InputIterator first, InputIterator last);
	Buffer	string	string& insert(size_t pos, const string& str, size_t subpos, size_t sublen);	个数
删除算法return iterator points at the element that was pointed by last prior to any erasure, or a.end() if no such element exists	Single element	Sequence containers && (Unordered)Associative containers	iterator erase (const_iterator position);
	Unfill	Associative containers	size_type erase(const value_type& val);	个数
	Range	Sequence containers && (Unordered)Associative containers	iterator erase(const_iterator first, const_iterator last);
变序算法O(n)	Sequence Containers		void reverse(iterator first, iterator last)
变序算法O(n)	Sequence Containers		void reverse(iterator first, iterator newFirst, iterator last)	Performs a left rotation on a range of elements so that newFirst becomes the first element of the new range

Coding Style

1.字符串处理

输入方式

getline(cin,str):

std::basic_istream& getline(std::basic_istream&is, std::cxx11::basic_string& __str);

//解析一个字符的三种方式
scanf("%c",&ch);
ch=cin.get();
ch=getchar();
//解析一个字符串的方式
char m[20];
gets(m);//gets函数如果读取了换行符会将其自动转换成字符串结束符'\0'
cin.getline(m,5);//多了一个参数，可以加结束符
cin.get(m,20);//多了一个参数，可以加结束符

tip

%2d就是将数字按照宽度为2 采用右对齐方式输出，若数据位数不到2位，则左边补空格
%02d和%2d差不多只不过左边补0
toupper,tolower的使用

字符串函数

basic_string& operator+=( const basic_string& str );
basic_string& operator+=( const CharT* s );
basic_string& erase( size_type index = 0, size_type count = npos )//number of characters to remove

2.初始化

等值

//vector
vector<vector<int>>v(8,vector<int>(8,0));
//e[][]
fill(e[0],e[0]+510*510,0);

不等值

void iota(iterator first,iterator last,T val) [first,last)从val连续赋值

3."对应"的处理

[易错点]0/1开头

1开头好处:避免map、lchild、rchild问题

`法1:建表`

char c[14] = {"0123456789ABC"};
printf("#");
for(int i = 0; i < 3; i++) {
    int num;
    scanf("%d", &num);
    printf("%c%c", c[num/13], c[num%13]);
}
return 0;

`法2:直接函数输出`

4. 排序题

cmp的写法(since C++11)

Lambda Structure

capture clause
- & (implicitly capture the used automatic variables by reference)
- = (implicitly capture the used automatic variables by copy).
parameter list Optional
lambda body.

sort(v.begin(),v.end(),[&](node&a, node&b)->bool{
    if ((a.de1 + a.cai) != (b.de + b.cai))        
        return (a.de + a.cai) > (b.de + b.cai);//技巧:以求和代替求平均值
    else if (a.de != b.de) return a.de > b.de;
    else return strcmp(a.name, b.name) < 0;//char name[9]
        //还可以string a.name<b.name;
})

并列排名问题

for(flag = 0; flag <= 2; flag++) {
   sort(ans.begin(), ans.end(), cmp1);
   for(int i = 0; i < n; i++) {
      ans[i].rank[flag] = i;
      if(i>0&&ans[i].grade[flag] == ans[i-1].grade[flag])
      ans[i].ans[flag] = ans[i-1].rank[flag];
   }
}

多维排序-->找参考系

1比较时间实际可以t[j]-t[i](从0:0:0开始)

2求连续字符串和满足一定条件-->sum[j]-sum[i]

易错点

多余链表、记录的问题
sum有n+1个(还有0)

夹逼题:[a,b]!c

for(j=temp;st[j].time<=cal(c)&&j<st.size();++j)
    if(st[j].status==0)sum++;
    else sum--;

5.输出格式

Basic

for (int i = 0; i < 4; i++) {
    sort(v[i].begin(), v[i].end(), cmp);
    for (int j = 0; j < v[i].size(); j++){//小技巧:利用顺序条件，如求一串码中只出现一次的元素
        if(j!=0)printf(" ");
        printf("%d", v[i][j].num);
    }
    printf("\n");
}

flag设置问题

Leetcode98 指针空间复杂度O(1)

int* last = NULL;//flag
bool isValidBST(TreeNode* root) {
   if (root){
         if(!isValidBST(root->left)) return false;
         if (last && *last>=root->val) return false;//第一次智慧执行下面
         last = &root->val;
         if(!isValidBST(root->right)) return false;
         return true;
   }else return true;
};

条件补零问题

Eg:保留n位小数(temp.size可大可小)

while(temp.size()<N)//有效数字位数小于N
temp+="0";//在字符串末尾加足够的0保证有N位有效数字

求模

sum+=(r-mid+1);
sum%=1000000007;

字符串

return mini==m+1?"":s.substr(cap,mini);//注意substr第二个参数是长度

6.Time Limit Exceed

循环内套了一个大函数:如循环内sort(>1000),或是一个大数组( $10^5$ )的cin-->scanf
- Eg:i<strlen(s),每次求长度
外循环与内循环条件对换，可以减少重复

7.Runtime Error

for:scanf()循环加了求sum或者列表问题,但还没sort呢
while和for的取舍,关键在于更新语句,一定要事先考虑update是否在所有结构均存在

while(){
    if(){update;}
    else(){update;}
}

1 Coding style and STL

STL​

Coding Style​

1.字符串处理​

输入方式​

字符串函数​

2.初始化​

等值​

不等值​

3."对应"的处理​

法1:建表​

法2:直接函数输出​

4. 排序题​

cmp的写法(since C++11)​

多维排序-->找参考系​

夹逼题:[a,b]!c​

5.输出格式​

Basic​

flag设置问题​

条件补零问题​

求模​

字符串​

6.Time Limit Exceed​

7.Runtime Error​

STL