C++ algorithm算法库 acm常用函数统计

---

转载注明出自bestsort.cn,谢谢合作

---

函数统计

字符串相关

• substr()

  substr 方法将返回一个包含从 start 到最后（不包含 end ）的子字符串的字符串。
  string sub2 = s.substr(5, 3); //从下标为5开始截取长度为3位：sub2 = “567”
  string sub1 = s.substr(5); //只有一个数字5表示从下标为5开始一直到结尾：sub1 = “56789”

求gcd

• __gcd(a,b).(两个下划线开头)

  int a=34,b=4;
  cout << __gcd(a,b)<<endl;
  

注：部分oj可能不支持调用__gcd;

求全排列

• 求数组a的上一个排列prev_permutation（a，a+a.size（））

  int a[] = {1,4,2,3};

  prev_permutation(a,a+4);
  for(int i=0;i<4;i++)
      cout << a[i] << endl;
  return 0;
  

• 求数组a的下一个排列next_permutation(a,a+.size())

  int a[] = {1,4,2,3};

  next_permutation(a,a+4);
  for(int i=0;i<4;i++)
      cout << a[i] << endl;
  return 0;
  

二分

此类目下两个函数都是返回的地址，所以要求下标则需要减去初始地址a - 查找大于或等于x的第一个位置 lower_bound（a,a+a.size(),x）

int a[] = {1,3,5,7,9,11};
cout << a[lower_bound(a,a+6,7)-a] << endl;

-查找第一个大于x的数字的位置upper_bound(a,a+a.size(),x)。用法同上

初始化

• 将a数组中前n项填充数字x：fill（a,a+n,x）
• cstring中，将a数组前n个内容初始化为bmemset（a，b，n<<2），b只能0，-1，0x3f，初始化的结果分别为0，-1，0x3f3f3f3f(无穷大)，用于做题时推荐写memset(a,b,(n+3)<<2)防止出错

其他

• 翻转a[x]-a[y]之间的内容：reverse（a+x,a+y）翻转区间[x，y)
• 交换a，b的值`swap（a，b）
• x转化为二进制中1的个数__builtin_popcount(x)