daily 10 problems

• worthy: of59-I of58-I

今天每日一题是括号匹配，1. 回溯+剪枝 2. bfs 个人感觉我自己写前一种方法太容易出错了，不是减错了枝就是少剪了TLE，相比之下，官方题解的利用unordered_set实现bfs的操作还是很有意思的，至少我个人挺受用，之前想到bfs只能想到队列这种数据结构
今天模拟周赛做出了三道题，第二道题pq数据结构不熟吃了大亏，后面看题解才知道map很多时候有相同的功效，仔细想想也合理，甚至因为需要修改非排序关键元素，map效率反而高一些。但是我仔细想了想，如果需要修改排序元素的话，可能pq是一种更好的选择？(好吧也应该不会)，所以感觉pq好没用啊，单元素有set双元素有map，都不知道它能拿来干什么了。

of59-I 有multiset和priority_queue两种思路，比较有意思的是学习了一下emplace_back的用法，比push_back少调用了一次拷贝构造函数。
of59-II 实现含max函数的队列，思想神似单调辅助栈，这一题中用到的辅助数据结构是双端队列
of60 二维dp，还是挺有意思
of61 水
of62 约瑟夫问题原来是一个数学问题！之前一直用的链表模拟，本质上是一个dp问题，

f(n,m) = (f(n-1,m) + m) % n

of63 一维dp
of64 递归模拟乘法，短路运算模拟if else
of65 经典位运算问题 必背

 int add(int a, int b){
    return b == 0 ? a : add(a^b, (unsigned int)(a&b)<<1);
}

of66 上三角下三角，感觉意义不大，确实不好想
of67 经典转化题，难点在于对overflow的判断，INT_MIN,INT_MAX分别表示最大值和最小值
of68 本质上就是简单dfs

study tags

• HTML