Pistachio's Blog

Later equals never.

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

全排列

全排列涉及循环和递归。递归由递归关系式和递归出口组成。在每一次循环中，可以从左到右确定一个数字，然后通过递归让剩下k-1个数进行全排列。也可以从右到左，先确定最后一个数字，然后把前面k-1个数字进行全排列。 Leetcode 输入: [1,2,3] 输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 思路一......

Posted by Liao on 2020-02-24

摩尔投票算法

摩尔投票算法(Boyer-Moore majority vote algorithm) 该算法是一种在线性时间O(n)和空间复杂度的情况下，在一个元素序列中查找包含最多的元素，是典型的流算法。 Leetcode 主要元素如果数组中多一半的数都是同一个，则称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。 123456789101112131415161718int......

Posted by Liao on 2020-02-23

字符串知识总结

读入有空格的字符串1、getline 123#include <string>string str;getline(cin,str); 2、将句子中每个单词读入队列中 1234567891011 // sentence1 = "My name is Haley"; sentence2 = "My Haley"string w; strin......

Posted by Liao on 2020-02-23

KMP

1.求前缀表next[]为什么要求前缀表？如果用暴力的双指针，在失配的时候又从模式串的开头重新匹配，增加了回溯的次数，效率低，复杂度为O(m*n)。前面已经匹配上的不用再搜索，通过next[]数组，在失去匹配的地方找到该元素的前后缀个数n，移动到模式串的下标n。复杂度时O(m+n)。通俗来说，next数组存放每个元素之前的字符串，最长公共前后缀的个数。如何求next[]呢？Text......

Posted by Liao on 2020-02-19

今天博客又搬回hexo啦～

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Qu......

Posted by Liao on 2020-02-18

二分查找

前言日常刷LeetCode的时候，用暴力解决了一道困难级别的题目，其时间限制是log(m+n)，才发现真正做法是用二分查找，因此补补相关知识。题目中有序、时间复杂度要求logn、最大值最小等，可以考虑二分查找。一、基本思想二分查找也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的......

Posted by Liao on 2020-02-11