stt2019-CSDN博客

原创海量数据处理

海量数据处理基本方法针对海量数据的处理，可以使用的方法非常多，常见的方法有Hash法、Bit-map法、Bloom filter法、数据库优化法、倒排索引法、外排序法、Trie树、堆、双层桶法以及MapReduce法。Hash法Hash也被称作散列，它是一种映射关系，即给定一个数据元素，其关键字为key，按一个确定的哈希函数Hash计算出hash（key)，把hash（ke...

2018-08-19 23:06:18 447

原创【剑指offer】（33~36）

33：二叉树的后序遍历序列题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 bool VerifySquenceOfBST(vector<int> sequence) { int size=sequence.size(); if(si...

2018-08-05 15:52:07 369

原创【剑指offer】（29~32）

29：顺时针打印矩阵输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 vector&lt;int&gt; printMatrix(vector&lt;vector&lt;int&gt; &gt; matrix) { int row = matrix.size(); int col = matrix[0].size()...

2018-08-02 00:01:39 235

原创【剑指offer】（25~28）

25：合并两个排序的链表输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 //非递归 ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1==nullptr) return pHead2; ...

2018-07-31 22:59:27 232

原创【剑指offer】（21~24）

21：调整数组顺序使奇数位于偶数前面题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。void Reorder(int *pData, unsigned int length, bool (*func)(int)){ if(pData == nullptr || length == 0) ...

2018-07-27 23:00:37 205

原创【剑指offer】（17~20）

17：打印从1到最大的n位数题目：输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，打印出1、2、3一直到最大的3位数999。难点：当n极大的情况，因此借助字符串模拟数字加//方法一void Print1ToMaxOfNDigits_1(int n){ if (n &lt;= 0) return; char *number = ne...

2018-07-22 16:34:33 191

原创【剑指offer】（13~16）

13：机器人的运动范围题目：地上有一个m行和n列的方格。一个机器人从坐标（0,0）的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？//回溯法in...

2018-07-21 18:49:45 176

原创【剑指offer】（9~12）

9：两个栈实现队列class Solution{public: void push(int node) { stack1.push(node); } int pop() { if(stack2.empty()) while(!stack1.empty()) { stack2...

2018-07-21 13:46:37 164

原创【剑指offer】（5~8）

5：空格替换题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。//my resolutionvoid replaceSpace(char *str,int length) { int i = 0; queue<string> q...

2018-07-17 22:18:20 141

原创【剑指offer】（1~4）

1：赋值运算符函数题目：如下类型为CMyString的声明，请为该类型添加赋值运算符函数。class CMyString{public: CMyString(char* pData=nullptr); CMyString(const CMyString& str); ~CMyString(void);private: char* m_pData;}注意...

2018-07-15 16:39:33 224

条款29：为“异常安全”而努力是值得的当异常抛出时，带有异常安全的函数会：不泄露任何资源（条款13：资源管理类）不允许数据败坏异常安全函数提供以下三个保证之一：基本承诺：如果异常被抛出，程序内的任何事物仍然保持在有效状态下。没有任何对象或数据结构会因此而败坏，所有对象都处于一种内部前后一致的状态。然而程序的现实状态不可预料。强烈保证：如果异常被抛出，程序状态不改变。不抛掷保证：承诺绝不抛出异常...

2018-06-29 16:02:04 201

原创【Effective C++】第五章实现(上)

第五章实现条款26：尽可能延后变量定义式的出现时间只要你定义了一个变量而其类型带有一个构造函数或析构函数，那么当程序的控制流到达这个变量定义式时，你便得承受构造成本；当这个变量离开其作用域时，你便得承受析构成本。即使这个变量最终并为被使用，仍需耗费这些成本，所以应该尽量避免这种情形。考虑下面这个函数，它计算同学密码的加密版本后而返回，前提是密码够长。如果密码短，函数会丢出一个异常，类型为log...

2018-06-27 22:26:46 171

原创【Effective C++】第四章设计与声明(下)

条款22：将成员变量声明为private如果成员变量不是public，客户唯一能够访问对象的办法就是通过成员函数。如果public接口内的每样东西都是函数，客户就不需要再打算访问class成员时迷惑地试着记住是否该使用小括号。使用函数可以让你对成员变量的处理有更精确的控制。如果你令成员变量为public，每个人都可以读写它，但如果你以函数取得或设定其值，你就可以出现“不准访问”、“只读访问”以及...

2018-06-18 22:21:01 185

原创【STL源码剖析】第五章关联式容器之 hash_set、hash_map、hash_multiset和hash_multimap

hash_sethash_set以hashtable为底层实现机制。由于hash_set所供应的操作接口，hashtable都提供了，所以几乎所有的hash_set操作行为，都只是转调用hashtable的操作而已。运用set目的是能够快速搜寻元素，这一点，不论底层是RB-tree或是hashtable都可以达成任务。但是，RB-tree有自动排序功能而hashtable没有，反应出来的结果就是，...

2018-06-18 16:19:00 274

原创【STL源码剖析】第五章关联式容器之 hashtable底层实现

hashtable二叉搜索树具有对视平均时间的表现，但这种的表现构造在一个假设上：输入数据有足够的随机性。这一节介绍一种名为hastable（散列表）的数据结构，这种结构在插入、删除、搜寻等操作上也具有“常数平均时间”的表现，而这种表现是以统计为基础的，不需仰赖输入元素的随机性。hashtable概述hashtable通过hash function将元素映射到不同的位置，但当不同的元素通过hash...

2018-06-16 21:57:40 494

原创【STL源码剖析】第五章关联式容器之 set、map、multiset和multimap

set所有的元素都会根据元素的键值自动被排序。set的元素不像map那样可以同时拥有实值（value）和键值（key），set元素的键值就是实值。set不允许两个元素有相同的键值。不可以通过set的迭代器改变set的元素值。因为set元素值就是其键值，关系到set元素的排列规则。如果任意改变set元素值，会严重破坏set组织。set源码中，set<T>::iterator被定义为底层R...

2018-06-15 17:40:23 280

原创【STL源码剖析】第五章关联式容器之 RB-tree（红黑树）

RB-treeRB-tree不仅是一个二叉搜索树，而且必须满足一些规则：每个节点不是红色就是黑色（图中深色代表黑，浅色代表红）根节点为黑色如果节点为红，其子节点必须为黑任一节点至NULL(树尾端)的任何路径，所含之黑节点数必须相同根据规则4，新增节点不许为红；根据规则3，新增节点之父节点必须为黑。当新节点根据二叉搜索树的规则到达其插入点，却未能符合上述条件时，就必须调整颜色并旋转树形。插入节点在图...

2018-06-14 21:44:16 469

原创【STL源码剖析】第五章关联式容器之树的导览

第五章关联式容器标准的STL关联式容器分为set（集合）和map（映射表）两大类，以及这两大类的衍生体multiset（多建集合）和multimap（多键映射表）。这些容器的底层实现极值均以RB-tree（红黑树）完成。RB-tree也是一个独立容器，但并不开放给外界使用。此外，SGI STL还提供了一个不在标准规格之列的关联式容器：hash table（散列表），以及以此hash table为...

2018-06-13 20:23:20 322

原创【Effective C++】第四章设计与声明(上)

第四章设计与声明条款18：让接口容易被正确使用，不易被误用考虑客户可能做出什么样的错误。除非有好理由，否则应该尽量令你的types的行为与内置types一致。 tr1::shared_ptr有一个特别好的性质是：它会自动使用它的“每个指针专属的删除器”，因而消除另一个潜在的客户错误：所谓的“cross-DLL problem”。这个问题发生于“对象在动态连接程序库（DLL）中被new创建，却在另...

2018-06-10 22:31:41 180

原创【STL源码剖析】第四章序列式容器之 heap和priority_queue底层实现

heapheap概述heap并不归属于STL容器组件，它扮演priority queue的助手。binary max heap是priority queue的底层机制。binary heap是一种complete binary tree（完全二叉树），也就是说，整棵binary tree除了最底层的叶节点(s)之外，是填满的，而最底层的叶节点(s)由左至右不得由空隙。complete binary...

2018-06-08 17:09:12 490

原创【STL源码剖析】第四章序列式容器之 stack和queue底层实现

stackstack概述stack是一种先进后出的数据结构。它只能有一个出口。stack允许新增元素、移除元素、取得最顶端元素。但除了最顶端元素外，没有任何其他方法可以存取stack的其他元素。换言之，stack不允许有遍历行为。将新元素推入stack的操作称为push，将元素推出stack的操作称为pop。stack定义完整列表以某种既有容器作为底部结构，将其接口改变，使...

2018-05-31 22:22:53 1987 2

原创【STL源码剖析】第四章序列式容器之 deque底层实现

dequedeque概述vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操所。vector当然也可以在头尾端进行操作（从技术观点），但是其从头部操作效率奇差，无法被接受。deque和vector的最大差异，一在于deque允许常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓的容量概念，因为它...

2018-05-31 20:34:02 6314 2

原创【STL源码剖析】第四章序列式容器之 list底层实现

listlist概述list是双向链表，相比于vector的连续线性空间，list就显得复杂许多，她的好处是每次插入或删除一个元素，就配置或释放一个元素空间。list对空间的运用绝对的精准，一点儿也不浪费。而且，对任何位置的元素插入或元素移除，list永远是常数时间。list的节点list本身和list节点是不同的结构，需要分开设计。以下是STL list的节点结构： template...

2018-05-29 22:31:14 974

原创【STL源码剖析】第四章序列式容器之 vector底层实现

第四章序列式容器（sequence containers）vectorvector概述vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变；vector的动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。vector的实现技术，关键在于对其大小的控制以及重新配置时的数据移动效率。vector迭...

2018-05-25 16:24:01 464

原创【STL源码剖析】第三章迭代器(iterators)概念与traits编程技法

第三章迭代器(iterators)概念与traits编程技法迭代器设计思维——STL关键所在STL的中心思想在于：将数据容器（containters）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂撮合在一起。迭代器是一种smart pointer迭代器是一种行为类似指针的对象，而指针的各种行为中最常见也最方便的便是内容提领（dereference）和成员访问（member ...

2018-05-24 22:09:05 391

原创【Effective C++】第三章资源管理

第三章资源管理条款13：以对象管理资源假设我们使用一个用来塑模投资行为的程序库，其中各式各样的投资类型继承自一个root class Investment： class Investment{……}；进一步假设，这个程序库通过一个工厂函数供应我们某特定Investment对象： Investment* createInvestment();createInvestment的调用端使用了函数返...

2018-05-23 15:49:10 160

原创【STL源码剖析】第二章空间配置器（allocator）

第二章空间配置器（allocator）具备次配置力（sub-allocation）的SGI空间配置器SGI标准的空间配置器 SGI定义了一个符合部分标准，名为allocator的配置器，效率不高，只把c++的::operator new和::operator delete做了一层薄薄的包装，SGI没有用过。SGI特殊的空间配置器，std::alloc allocator只是基层内存配置/释放行...

2018-05-22 21:21:29 710

原创 Linux vim相关操作

移动光标的方法vim命令功能[Ctrl]+[f]屏幕向下移动一页，相当于[Page Down]按键[Ctrl]+[b]屏幕向上移动一页，相当于[Page Up]按键0或功能键[Home]移动到这一行最前面字符处$或功能键[End]移动到这一行最后面字符处G移动到这个文件最后一行nG移动到这个文件的第n行gg移动到这个文件的第一行，相当于1GN[enter]n为数字，光标向下移动n行u复原前一个操作...

2018-05-22 15:22:01 192

原创【STL源码剖析】第一章概论与版本介绍

第一章概论与版本介绍STL六大组件：容器（containers）:各种数据结构，如vector,list,deque,set,map，用来存放数据。从实现角度来看STL容器是一种class template。算法（algorithms）:各种常用的算法如sort,search,copy,erase… 从实现角度来看STL算法是一种function template。迭代器（iterators）:...

2018-05-22 14:51:53 321

原创【Effective C++】第二章构造/析构/赋值运算(下)

条款09：决不在构造和析构过程中调用virtual函数本条款重点：你不应该在构造函数和析构函数期间调用virtual函数，因为这样的调用不会带来你预想的效果。如下例，假如有个class继承体系，用来塑造股票交易如买进、卖出的订单等等，这样的交易一定要经过审计，所以每当创建一个交易对象，在审计日志中也需要创建一笔适当的记录: class Transaction{ ...

2018-05-21 22:43:40 177

原创【Effective C++】第二章构造/析构/赋值运算(上)

第二章构造/析构/赋值运算条款05：了解C++默默编写并调用哪些函数什么时候empty class（空类）不再是个empty class？当C++处理过它后。如果没自己的声明，编译器就会为它声明一个copy构造函数、一个copy assignment操作符和一个析构函数。如果没有声明任何构造函数，编译器也会为你声明一个default构造函数。所有这些函数都是public且inline。因此，如果...

2018-05-21 10:08:16 215

原创装饰模式 C++实现

装饰模式装饰模式（Decorator），动态地给一个对象添加一些额外的职责，就增加功能来说，装饰者模型比生成子类更为灵活。 #include <iostream> #include<string> using namespace std; //"Person"类（concretetcomponent） class Person { pub...

2018-05-21 09:16:43 338

原创适配器模式 C++实现

适配器模式适配器模式（Adapter），将一个类的接口转换成客户希望的另一个接口。Adapter模式使得原本接口不兼容而不能一起工作的那个类可以一起工作。适用场景：系统的数据和行为都正确，但接口不符时，考虑使用适配器，目的是使控制范围之外的一个原有对象与某个接口匹配。适配器模式主要应用于希望一些现存的类，但是接口又与复用环境要求不一致的情况。分类：类适配器模式和对象适配器模式 ...

2018-05-21 09:15:42 336

原创观察者模式 C++实现

观察者模式观察者模式又叫做发布-订阅（Publish/Subsribe）模式。观察者模式定义了一种一对多的依赖关系，让多个观察者对象同时监听某一个主题对象。这个主题对象在状态发生变化时，会通知所有观察者对象，使他们能够自动更新自己。在以下任一情况下都可以使用观察者模式：当一个抽象模型有两个方面，其中一个方面依赖于另一方面。将这二者封装在独立的对象中以使它们可以各自独立的改变和复用；当对一个...

2018-05-21 09:10:34 251

原创单例模式 C++实现

单例模式概念：单例模式是一种常的软件设计模式。它的核心结构只包含一个被称为单例的特殊类。它的目的是保证一个类仅有一个实例，并提供一个访问它的全局访问点，该实例被所有程序模块共享。应用场景：有一些对象只需要一个，如：对话框、系统日志、显卡等设备的驱动程序对象、一台PC连接一个键盘。单例模式有3种实现方式：懒汉式、饿汉式和双重锁的形式。懒汉：第一次用到类的实例的时候才回去实例化。饿汉：单例类定义的时候...

2018-05-20 22:43:56 19955 6

原创工厂模式 C++实现

工厂模式简单工厂模式所谓简单工厂模式，是一种实例化对象的方式，只要输入需要实例化对象的名字，就可以通过工厂对象的相应工厂函数来制造你需要的对象。简单工厂模式的核心是，对于一个父类的多个继承子类，工厂对象的工厂函数根据用户输入，自动new出一个子类对象并返回其父类的指针，这样利用父类的指针执行父类的虚函数，就可以动态绑定子类的重写函数，从而实现多态。对于一个只拥有加减乘除运算的简单计算器...

2018-05-20 22:39:44 285 1

原创数据库相关基础

数据库引擎MyISAM与InnoDB1.区别MySQL默认是MyISAM;（1）事务处理：MyISAM不支持事物处理，InnoDB支持事务处理；（2）锁机制不同：MyISAM是表级锁，而InnoDB是行级锁；（3）select ,update ,insert ,delete 操作：MyISAM：如果执行大量的SELECT，MyISAM是更好的选择InnoDB：如果你的数据执行大量的INSERT或U...

2018-05-20 20:41:15 208

原创 SQL语句

SQL语句SQL是结构化查询语句（Structured Query Language）的缩写，其功能包括数据查询（DQL）、数据定义（DDL）、数据操作（DML）和数据控制（DCL）4个部分。DQL（Data Query Language）：数据查询语言，用来查询记录（数据）。DDL（Data Definition Language）：数据定义语言，用来定义数据库对象：库、表、列等； CREATE...

2018-05-20 20:03:12 202

原创【Effective C++】第一章让自己习惯C++

第一章让自己习惯C++条款01：视C++为一个语言联邦为了理解C++，你必须人生的主要次语言：C。说到底C++仍以C为基础。区块（blocks）、语句（statements）、预处理器（preprocessor）、内置数据类型（built-in data types）、数组（arrays）、指针（pointers）等都来自C。许多时候C++对问题的揭法其实不过就是高级C的解法，但当你以C++内的...

2018-05-20 17:00:51 186

原创常用排序算法C++实现

排序算法排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n^2)O(n)O(n^2)O(1)稳定简单选择排序O(n^2)O(n^2)O(n^2)O(1)稳定直接插入排序O(n^2)O(n)O(n^2)O(1)稳定希尔排序O(nlogn)~O(n^2)O(n^1.3)O(n^2)O(1)不稳定堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定归并排序O(nlogn)O(n...

2018-05-20 12:55:17 261

空空如也

空空如也