刷题心得

读题关键字

• 注意总结解题模版！！！
• 满足条件的最小整数
• 涉及到存储长度类似的：[如果最小的不是32位整数，也返回-1]
• 局部变量一定要初始化

编程脑子-变迟钝

• 双重循环中，错误使用相同的计数变量，导致程序出现问题
• if (key[i] = 'T') -> 注意啊，还真出现了这种错误
  • == 不是 = -> 写判断时一定要注意
  • 写判断，把数值写到==左边==
• 不要忘记对循环的尾部进行输出处理: 例如将连续数字替换为平方和
  • 例如“avc12vd” -> 在循环中碰到新的字母时才对之前的数字进行处理、输出
  • “zvc123” -> 这样就忘记了最后一次的处理
• 循环中更新数组，用错循环下标
  • for (int i = l; i < r; ++i) nums[l] = tmp[i-l];
  • 这里nums[l] 应该为 nums[i]

两个区别

• sort(nums.begin(), nums.end(), greater<int>());
  • 这里传入对象
• map<int, int, greater<int>>mp;
  • 这里传入类型声明，传入类型即可，如果是自定义的比较，需要传入对象给构造函数: 可能是因为要传入的类型为函数对象，且有成员变量；如果没有的话，应该可以不用显示传入对象

    set<item, decltype(dcompare)>st(dcompare)

• 自定义sort排序函数时需要注意
  1. 对于任意元素a，需满足 comp(a, a) == false
  2. 对于任意两个元素a和b，若 comp(a, b)==true 则要满足 comp(b, a)==false
  3. 对于任意三个元素a、b和c，若 comp(a, b)==true 且 comp(b, c)==true 则需要满足 comp(a, c)==true

常用编程技巧

• (long long)(m-1) * (m-2) -> 强制类型转换的优先级高于加减乘除

• 使用std::greater<int>带入sort或者构造声明map

  #include<functional>
  
  sort(nums.begin(), nume.end(), greater<int>())
  
  map<int, int, greater<int>>
  // 注意它们两个不一样，map声明时需要传入一个类型；而sort需要传入一个函数	

• 使用lambda表达式自定义sort的比较函数，并使用decltype()传给map声明时的自定义key比较函数

  vector<vector<int>>>points;
  sort(points.begin(), points.end(), [](const auto& l, const auto& r) -> bool {
      return l[0] < r[0];
  });

• 使用程序块为变量赋值，要注意函数块需要使用()包裹起来：

  double sum = ({
          double tmp = 0;
          for (int j = 0; j < k; j++) tmp += nums[j];
          tmp;
      });

• 代码行压缩时，如果有多条语句，必须用{}包围起来，如果只有一条语句不用

  if (x != 1) {y = 10; z = 100;}
  while (s[i] != 'a' && i < m) {s[i] -= 1; flag = true; i++;}
  while(s[i] == 'a') s[i] -= 1; 

• 在while循环里写额外的for/while循环时，一定要记得在内层循环判断越界问题

• 两字符串字典序比较时要注意：循环判断，相等的才会继续，小于或者大于时都会结束判断！！！复习一下这个题目，注意提交错误的几个。可以直接使用string类的</>/>=运算符，或者compare成员函数进行字典序号的比较

• 体会如何写二叉树的递归：先转化为局部问题，考虑局部root, root->left, root->right的递归问题；先不用纠结于前/中/后的递归顺序，结合这个题目[114.二叉树展开为链表]。

• 判断一个数是否为质数

  • daiding

• 计算整数各个位上数字之和：可以先从个位数加起：

  int sumOfTheDigitsOfHarshadNumber(int x)
  {
      int s = 0;
      for (int v = x; v; v /= 10) {
          s += v % 10;
      }
      return s;
  }

• double, long, int, long long等类型表示的数据范围

  • double是双精度浮点型，可以表示小数，在64位系统上占8Bytes。采用的数据表示方法和另外几种数据类型不同，能表示的数据范围是最大的。此外还有float[单精度浮点型], long double[精确度更高]
  • 其余都是整数类型
  • 浮点型，牺牲了表示精度，但是增大了数据表示范围
  • 参考题目：152. 乘积最大子数组

个别题目复习

• 数的前/中/后遍历的迭代方法要熟悉

• 找数字规律的题目，先找到“主干规律”，再找次要规律，结合题目[6. Z字型变换]

• 二叉树层序遍历不一定非得用queue，也可以用vector实现一些重复遍历的操作，结合[2641.]

常用数据结构及其方法

vector

• erase()
• rbegin() -> 最右侧的那个节点
• front()/back() -> 用于查看元素
• pop_back()
• push_back() -> 可以用来模拟栈
• rend() -> 第一个节点前面，不在vector中
• insert(pos, start, end)，从pos处插入[start, end)，注意这样的话target[pos] = src[start]
• vector<int> ids(ids.begin()+1, ids.begin()+10) -> 使用迭代器从一个数组构造另一个数组

string

• <string>

• insert(pos, char *, size)

• string (size_t n, char c)

• size_t find(string& str, size_t pos = 0)

  • 五种原型

    // string (1) 
    size_t find (const string& str, size_t pos = 0) const noexcept;
    // c-string (2)    
    size_t find (const char* s, size_t pos = 0) const;
    // buffer (3)    
    size_t find (const char* s, size_t pos, size_type n) const;
    // character (4)    
    size_t find (char c, size_t pos = 0) const noexcept;

  • pos参数：指示原字符串的开始查询位置，而且包括pos指示的位置

  • 返回值：

    • size_t类型
    • the pos of the first character of the first match
    • string::nposif no match find

  • delimiter划分

      // for string delimiter
      std::vector<std::string> split(std::string s, std::string delimiter)
      {
       size_t pos_start = 0, pos_end, delim_len = delimiter.length();
    std::string token;
       std::vector<std::string> res;
      
    while ((pos_end = s.find(delimiter, pos_start))
    	  != std::string::npos)
    {
    	token = s.substr (pos_start, pos_end - pos_start);
    	pos_start = pos_end + delim_len;
    	res.push_back (token);
    }
      
    res.push_back (s.substr (pos_start));
    return res;
      }

• find_first_of() -> 类似于find()，但是匹配str中的任一个字符

• substr(start, len) ❗️ 注意这个方法的第二个参数为长度

• operator > / < -> string 类重载了这两个运算符，可以直接用于字典序的比较

• compare(const string& str)，返回值如下：

  • 0, equal
  • -1, lf < rf
  • 1, lf > rf

• erase(start_idx, len) -> 利用索引和长度删除指定范围的字符

• erase(iterator start, iterator end) -> 利用迭代器删除指定范围内的字符，[start, end)

• delimeter划分

  • 借助find进行划分；但是也只能跳过整体的string
  • 借助getline(string) 和 istringstrem(sstream)对字符串进行划分

    string str="She is a girl."; // istringstream 默认以空格进行划分
       istringstream is(str);
       string buf;
       while(is>>buf)
       {
         cout<<buf<<endl;
       }
       
       // 借助getline -> 缺点是只能delimeter只能为单个字符
       // istream& getline ( istream &is , string &str , char delim );
       char del = ' ';
       while(getline(is,buf,del))
       {
         if(buf.size()) cout<<buf;
       }

  • 使用strtok()进行划分 -> 可以忽略很多字符

    // in <string.h> or <cstring>
    // char* strtok( char* str, const char* delim );
    
    int main() 
    {
      char input[] = "one + two * (three - four)!";
      const char* delimiters = "! +- (*)";
      char* token = std::strtok(input, delimiters);
      while (token)
      {
          // token may do not have '\0' at the end
          std::cout << string(token) << ' ';
          token = std::strtok(nullptr, delimiters);
      }
    
      std::cout << "\nContents of the input string now:\n\"";
      for (std::size_t n = 0; n < sizeof input; ++n)
      {
          if (const char c = input[n]; c != '\0')
              std::cout << c;
          else
              std::cout << "\\0";
      }
      std::cout << "\"\n";
    }

• c_str()

  • 返回值为const char *

  • 可以使用const_cast<char *>剥除const符号

  • 但是要注意cout << char *，char* 后面可能没有’\0’，因此程序会有bug

  • 可以尝试使用string来装载这个char*，string会在尾部添加’\0’

stack

• <stcak>
• push()
• pop() -> 注意返回值为 void，因此取元素只能用top()方法 ❗️
• top()
• empty()
• begin() ❌ -> 没有这个方法
• size()
• swap() -> 交换两个栈的内容

queue

• <queue>
• push()
• pop() ❗️ -> 注意返回值为 void，因此取元素只能用front()方法
• top() ❌ -> 没有这个方法，要使用front()
• front() -> 查看队列头部的元素[先插入的]
• back() -> 查看队列尾部的元素[后插入的]
• empty()
• begin() ❌ -> 没有这个方法
• size()
• swap() -> 交换两个栈的内容

set

• set有一个cmp函数，当cmp(l, r)为false且当cmp(r, l)也为false时，说明l与r为相同的元素

• 自定义cmp函数:

  auto cmp = [](const auto& l, const auto& r) -> bool {
      return l[0]*l[0] + l[1]*l[1] <= r[0]*r[0] + r[1]*r[1];
  };
  set<vector<int>, decltype(cmp)> st(cmp);

• erase() ❗️ multiset在使用这个方法删除某个key时，会把所有相同的key删除；如果想要删除一个，需要先使用find返回迭代器，并将迭代器作为该方法的参数

• 注意：无法使用迭代器获取有序set中某个元素在set中的序号可以先将其转为vectorset迭代器+n的方法

• 迭代器加法可以使用advance

  • advance(it, 5);
  • 要注意该函数返回值为void
  • 且第二个参数可以为负值

• 可以使用distance(begin, end)计算两个迭代器之间的距离，注意end一定要在begin的后面

  • 是的，必须

map

• <map>

• lower_bound/upper_bound

• erase() -> 参数可以为 iterator；key；也可以为范围参数’[first it, last it)’

• 大 -> 小排列 map<int, multiset<int>, std::greater<int>>

• 定义map型对象时，如何自定义key比较函数：注意只能定义key的比较函数：也可以定义lambda表达式，并使用decltype

  struct cmp_key
  {
      // 注意，函数的参数需要于map的key的参数类型相同
      bool operator()(const key_t &k1, const key_t &k2)const
      {
          if(k1.dwBussID != k2.dwBussID)
          {
              return k1.dwBussID < k2.dwBussID;
          }
  
          if(k1.dwVersion != k2.dwVersion)
          {
              return k1.dwVersion < k2.dwVersion;
          }
          if(k1.dwHashUrl != k2.dwHashUrl)
          {
              return k1.dwHashUrl < k2.dwHashUrl;
          }
  　　　　　　　　  return false;
      }
  };

priority_queue

• <queue>
• 需要指定底层使用什么容器类型存放元素：默认为vector，也支持deque。也可以自定义容器
• top() -> 查看尾部元素
• push()/pop()

deque

• <deque>
• 元素存储不是连续的
• 支持[]下标索引操作
• front/back -> 查看元素
• puah_back/push_front
• pop_back/pop_front

常用库函数运算

lower_bound(iterator_start, iterator_end, value) ->

• 返回第一个迭代器it，其值不满足 (*it) < value
• 即找到第一个迭代器，其值满足 value <= (*it)
• 参数可以为&arr[i]，返回值也为该类型，参考

upper_bound(start, end, value) ->

• 返回第一个迭代器，其值满足 (*it) > value

gcd/lcm

• <numeric>
• gcd: 最大公因数
• lcm: 最小公倍数

iota

• <numeric>
• iota(foreard_iterator start, forward_iterator end, init_val)
• 序列化[start, end)，第一个值为init_val

atan2() -> double

• 求坐标(x, y)到x轴的极角，范围为[-pi, pi]。这里要注意坐标上的点在-x轴上时，其极角可能为-pi，也可能为pi，但只能为一个值
  • 1610. 可见点的最大数目

next_permutation

• <algorithm>
• 返回数组的全排列
• 使用前需要对数组进行小->大的排序

浮点数保留指定长度小数

• 设置标准输出保留指定位数

  #include <iomanip>
  #incude <sstream>
  // ios::fixed -> 防止0.2000仍然输出0.2
  cout << setiosflags(ios::fixed) << std::setprecision(2);
  // 只需设置一次，后续都是这样打印
  // 或者这样设置
  cout.setf(ios::fixed);
  cout.precision(2);
  
  cout << 0.2000 << endl; /* 输出为0.20 */

• 运算过程中保留两位小数

  #incude <cmath> // for floor
  /*采用数学计算的方式*/
  float a = 0.0239102;
  a = floor(a*1000 + 0.5)/1000  /* + 0.5 是为了四舍五入*/

• floor/ceil/round -> 头文件：cmath
  • 这三个函数都是给浮点型数据使用的
• lround/llround -> 头文件：cmath
  • 用于将浮点数四舍五入为long/long long