Pistachio's Blog

Later equals never.

单调栈

单调栈简介单调栈分为单调递增栈和单调递减栈，顾名思义就是栈内元素大小保持递增或递减。操作规则（以单调递增栈为例）如果新进来的元素比栈顶元素大，则进栈如果新进的元素比栈顶元素小，就把栈内元素出栈，直到找到第一个比新进元素要小的元素为止。代码模板123456789int MonotoneStack(vector<int>& height){ stack&......

Posted by Liao on 2020-03-24

动态规划

动态规划用于解决重叠子问题(overlap sub-problem)，已经计算过的不再重复计算，而是从内存中重新调出来使用。 LeetCode　按摩师（同打家劫舍系列）给定预约时长，找到最优的预约集合(时长最长)，且不能接收相邻的预约输入： [2,1,4,5,3,1,1,3]输出： 12解释：选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4......

Posted by Liao on 2020-03-24

Prime

一、试除法求素数（通常会超时） 1234567891011121314151617bool isPrime(int n){ for(int i = 2; i <= sqrt(n); i++){ if(n%i==0) return false; } return true; ......

Posted by Liao on 2020-03-22

幂集

幂集，也是原集合的所有子集位运算求幂集 1234567891011121314vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>>ans; for(int i = 0; i < (1<<......

Posted by Liao on 2020-03-22

二叉树

无论是LeetCode的题目还是竞赛题，很多都有关对二叉树的操作，因此有必要对做过的题目进行一番总结。二叉树的层次遍历 BFS方式实现（队列）要注意队列的结点类型！ 123456789101112131415161718192021222324vector<vector<int>> levelOrder(TreeNode* root) { ......

Posted by Liao on 2020-03-21

STL之unordered_map

定义该容器提供了Key-Value的存储和查找功能无序性：unordered_map中的元素根据哈希值存储到桶中，以允许通过键直接快速访问每个元素唯一性：unordered_map中每个元素的值是唯一的关联性：unorederd_map 是一个关联容器，其中的元素根据键来引用，而不是根据索引来引用。插入值 12345678910111213141516171819#inc......

Posted by Liao on 2020-03-21

扩展欧几里得算法的应用

LeetCode 水壶问题有两个容量分别为 x升和 y升的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升的水？如果可以，最后请用以上水壶中的一或两个来盛放取得的 z升水。你允许：装满任意一个水壶清空任意一个水壶从一个水壶向另外一个水壶倒水，直到装满或者倒空样例：　x=3, y=5, z=4 true,......

Posted by Liao on 2020-03-21

回文串

LeetCode 最长回文串在给定包含大小写的字符串中，找出这些字母构成的最长回文串，构造时注意区分大小写这道题目不同在于可以通过构造找出最长回文串，于是可以通过找规律求得。首先把每个字母出现的个数统计出来，放进vector中（方便处理）。查看vector中每个字母出现的次数，如果字母出现的个数时偶数，一定可以构成回文串，则可以把这些个数直接加起来；如果字母出现的个数是奇数，则......

Posted by Liao on 2020-03-19

快慢指针

快指针走两步，慢指针走一步，当它们相等时就是走了一个循环，为一个周期。在链表中，如果一个链表存在环，那么快慢指针必然会相遇 LeetCode 快乐数对于一个正整数，将这个数字替换为每个位置上的数字平方和，循环多次，如果能变为１则是快乐数，否则不是。这道题用递归做的话，若正整数很大，递归层次深一点，就会导致调用栈爆了。 12345678910111213141516171819int......

Posted by Liao on 2020-03-18

位运算总结

由于计算机存储数据都是以二进制的形式存储，位运算实质时对二进制数进行操作。在做题目的的时候，通过位运算处理数据速度很快，便能使缩短计算时间。 1. 位运算的种类含义运算符解释和例子左移 << 高位丢弃，低位补0。x<<n 相当于x乘2^n (0011 << 1 == 0110) 右移 >> 无符号......

Posted by Liao on 2020-03-06