Pistachio's Blog

Later equals never.

二叉树

无论是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

STL之vector

一、vector的特性 vector封装了数组，拥有连续的内存空间，并且起始地址不变，能够高效地进行存取，时间复杂度为O(1) 但由于其内存空间是连续的，在进行插入或删除操作时，会造成内存块拷贝，时间复杂度为O(n)；另外，在数组内存空间不够时，也会重新申请一块内存空间进行内存拷贝。（与list数据结构相反，用于不同的场景）二、初始化12345vector<int>vec(......

Posted by Liao on 2020-03-05

双指针

LeetCode题目总结LeetCode 合并两个排序的数组 1234567891011121314151617181920212223242526272829303132333435363738394041void merge(vector<int>& A, int m, vector<int>& B, int n) { ve......

Posted by Liao on 2020-03-03

二进制的总结

LeetCode 求二进制数中1的个数这是一种更高效的思路，把整数减1，再与原来的数做与运算，会把原来的二进制数最右边的1去掉。计算有多少次去掉1的操作，即可知道1的个数。 n = n & (n-1) 123456789int hammingWeight(uint32_t n) { int cnt = 0; while(n) ......

Posted by Liao on 2020-02-25

位运算题目总结

LeetCode 求二进制数中1的个数这是一种更高效的思路，把整数减1，再与原来的数做与运算，会把原来的二进制数最右边的1去掉。计算有多少次去掉1的操作，即可知道1的个数。 n = n & (n-1) 123456789int hammingWeight(uint32_t n) { int cnt = 0; while(n) ......

Posted by Liao on 2020-02-25