1.向量旋转
将一个具有n个元素的一维向量左旋i位。
1.1使用i个额外空间
void left_rotate(string &s,int i){ string s2(s,0,i);//将前i个字符复制到s2 int j=0; //将剩余n-i个元素左移i个位置 for(;i<s.size();i++){ s[j++] = s[i]; } //将s2复制到s的后面部分 for(int k=0;k<s2.size();k++){ s[j++] = s2[k]; } }
1.2定义一个函数将向量左旋1位，然后i次调用该函数
//左旋一位 void one_left_rotate(string &s){ char ch = s[0]; for(int i=0;i<s.size()-1;i++){ s[i] = s[i+1]; } s[s.size()-1] = ch; } //i次调用左旋一次函数 void left_rotate(string &s,int i){ for(int j=0;j<i;j++){ one_left_rotate(s); } }
1.3先转置前i位，再转置后n-i位，最后转置整个向量
void left_rotate(string &s,int i){ reverse(s.begin(),s.begin()+i);//reverse()函数不访问后一个迭代器所指元素，需#include<algorithm> reverse(s.begin()+i,s.end()); reverse(s.begin(),s.end()); }
1.4杂技算法
void left_rotate3(string &s,int rotdist){ int n = s.size(); int m = gcd(n,rotdist); for(int i=0;i<m;i++){ int t=s[i]; int j = i; while(true){ int k = j+rotdist; if(k>=n){ k -= n; } if(k==i){ break; } s[j] = s[k]; j = k; } s[j] = t; } }
gcd(m,n)是求m和n的最大公约数。有如下几种实现方法：
//1.辗转相除求最大公约数 ，n为0终止 int gcd(int m,int n){//需保证m>n int r; while(n!=0){ r = m%n; m = n; n = r; } return m; } //2.辗转相除的递归实现 int gcd(int m,int n){//需保证m>n return n==0?m:gcd(n,m%n); } //3.更相减损术 ,m==n终止 int gcd(int m,int n){ while(m!=n){ if(m>n){ m -= n; } else{ n -= m; } } return m; }
1.5块交换算法
//swap s[a..a+m-1] with s[b..b+m-1] void swap(string &s,int a,int b,int m){ for(int i=0;i<m;i++){ swap(s[a+i],s[b+i]); } } //块交换算法 void left_totate(string &s,int rotdist){ int n = s.size(); rotdist = rotdist%n;//rotdist>=n时，只需旋转 rotdist%n位 if(rotdist==0){ return; } int i = rotdist; int p = rotdist; int j = n-p;//number of elements in right while(i != j){ if(i>j){ swap(s,p-i,p,j); i -= j; } else{ swap(s,p-i,p+j-i,i); j -= i; } } swap(s,p-i,p,i); }
1.6STL中的rotate()
Defined in header <algorithm> template< class ForwardIt > void rotate( ForwardIt first, ForwardIt n_first, ForwardIt last ); (until C++11) template< class ForwardIt > ForwardIt rotate( ForwardIt first, ForwardIt n_first, ForwardIt last ); (since C++11) Parameters first - the beginning of the original range n_first - the element that should appear at the beginning of the rotated range last - the end of the original range Return value (none) (until C++11) The iterator equal to first + (last - n_first) (since C++11)//point to previous first element after rotate // simple rotation to the left rotate(v.begin(), v.begin() + 1, v.end()); // simple rotation to the right rotate(v.rbegin(), v.rbegin() + 1, v.rend());
1.7拓展
左旋i位等价于右旋n-i位。
2.变位词
给定一本英语词典，找出所有的变位词类。
- 签名:按字母顺序排序单词中的字母作为签名
- 排序:按签名将单词排序
- 挤压:将签名相同的单词按行输出
#include<iostream> #include<map> #include<string> #include<algorithm> using namespace std; int main(){ multimap<string,string> A; string s,s0; while(cin>>s){ s0 = s; sort(s.begin(),s.end()); A.insert({s,s0}); } string lastkey = A.begin()->first; for(auto iter=A.begin();iter != A.end();++iter){ if(iter->first !=lastkey){ cout<<endl; } cout<<iter->second<<ends; lastkey = iter->first; } return 0; }
3.第6题解答
- 签名:将按钮编码作为姓名的签名
- 排序:按签名(按钮编码)将姓名排序
查询时用二分查找找到所查询的按钮编码，将按钮编码对应的姓名全部输出。
4.二分查找与排序
排序最明显的用法就是给元素排序，这既可作为系统规范的一部分，也可作为二分查找程序的准备条件。
二分查找算法：
//循环实现 int binary_search(const vector<int> &iv,int key){ int low = 0; int high = iv.size()-1; while(low <= high){ int mid = low+(high-low)/2; if(key == iv[mid]){ return mid; } else if(key<iv[mid]){ high = mid-1; } else{ low = mid+1; } } return -(low+1);//查询的关键字不存在,low是key应该插入的位置 } //递归实现 int binary_search( const vector<int> &iv, int low, int high, int key) { int mid = low + (high - low) / 2; // Do not use (low + high) / 2 which might encounter overflow issue if (low > high) return -(low+1); //low是key应该插入的位置 else { if (iv[mid] == key) return mid; else if (iv[mid] > key) return binary_search(iv, low, mid-1, key); else return binary_search(iv, mid+1, high, key); } }