Mind_V-CSDN博客

原创添加文件夹右键用VSCode打开

添加右键VSCode打开mark一下，后续使用。Windows Registry Editor Version 5.00[HKEY_CLASSES_ROOT\Directory\shell\VSCode]@="Open with VSCode""Icon"="C:\\Program Files\\Microsoft VS Code\\Code.exe"[HKEY_CLASSES_...

2018-12-27 10:21:45 7614

原创 Google MapReduce 总结

Google MapReduce 总结MapReduce 编程模型总的来讲，Google MapReduce 所执行的分布式计算会以一组键值对作为输入，输出另一组键值对，用户则通过编写 Map 函数和 Reduce 函数来指定所要进行的计算。由用户编写的Map 函数将被应用在每一个输入键值对上，并输出若干键值对作为中间结果。之后，MapReduce 框架则会将与同一个键 II 相关...

2018-06-10 12:18:15 1901

转载《深入理解计算机系统》｜处理器体系结构

《深入理解计算机系统》｜处理器体系结构目录学习事物是怎样工作的有其内在价值：处理器是如何工作的对于我们普通人来说一直是个秘密，我们将从零开始构建一个流水线处理器，为了实现这一处理器的软硬件，我们有大量的前提知识要学习，包括：指令系统、硬件设计背景知识（hcl）、以及流水线的通用原理。学习完这些内容以后我们才开始YY一个我们自己的86处理器。本章内容※ YY一个指令集Y8...

2018-05-17 15:26:19 1556

转载 Google File System 学习总结

趁着4月份找实习的契机，学习了MIT 6.824的课程推荐论文Google File System。篇幅很长，感觉不是完全理解了，先转载了一篇觉得整理得比较好的笔记，方便后续的进一步学习。GFS 的主要需求在学习 GFS 的原理前，首先我们应当了解 GFS 在设计时所面对的需求场景。简单概括，GFS 的设计主要基于以下几个需求：节点失效是常态。系统会构建在大量的普通机器上，这使得...

2018-05-03 21:03:16 4703

原创理解C++中引用的底层实现

1、C++ Primer提到：引用并非对象，相反的，它只是为一个已经存在的对象所起的另外一个名字。引用的定义必须伴随初始化，而且一旦定义了引用，就无法令其再绑定到另外的对象，之后每次使用这个引用都是访问它最初绑定的那个对象。2、何为对象？对于面向对象来说，对象就是类的实例，是抽象化的数据本身。更广义的来说，一个int型变量可以是对象，一个指针也可以是对象，但一个引用却又不是对象。

2017-11-23 21:19:31 2546

原创哈希表HashTable

哈希表概念哈希表（Hash Table），又称散列表，是字典结构的其中一种表达方式，可以根据数对的键值（Key value）映射到数组中的位置而对元素进行直接访问，时间复杂度为O(1)。其实现原理很简单，即使用一个哈希函数把键值转换成一个整型数字，数字对数组长度取余，即得到数组的索引。

2017-10-22 22:27:04 499

原创 Perfect Squares——动态规划

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.For example, given n = 12, return 3 because 12 = 4 + 4 + 4;

2017-10-18 10:14:28 423

原创二叉树前序、中序和后序的非递归遍历

把经典问题：二叉树的非递归遍历理了理，顺便做个笔记。核心思路就是节点的压栈和出栈。#include #include#includeusing namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x) {

2017-10-09 17:18:13 366

原创 Sort List —— 归并排序

Sort a linked list in O(n log n) time using constant space complexity.算法分析1、要求时间复杂度为 O(n log n)，可以考虑归并与快排；2、本文使用归并，每次将链表从中间位置切断，一分为二；3、递归2过程，直到链表长度为1；4、依次从小到大合并两个链表，最后返回排序好的链表。

2017-10-05 14:34:49 322

原创 Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).Example 1:nums1 = [1, 3]nu

2017-10-02 15:03:05 319

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does

2017-09-29 13:11:23 656 1

原创动态规划——0-1背包问题

问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问：应如何选择装入背包的物品，使得装入背包中物品的总价值最大？算法设计分析背包问题要求达到物品总价值的最优化，每一次选择作为一个阶段，根据前一个阶段的解可以求解出后一个阶段的解。定义状态F[i,y]，表示剩余容量为y，剩余物品为i, i+1, i+2 ,…, n的最优解。所以：（2）式便是状态转移方程，而（1）式则是边界

2017-08-31 08:55:50 2242

原创动态规划

算法思想dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.——维基百科动态规划的思想：将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任

2017-08-29 22:25:20 846 1

原创优化程序性能

一般来说，程序优化主要是以下三个步骤：　　1. 高级设计 —— 算法和数据结构选择　　2. 基本编码原则 —— 编码优化　　3. 低级优化 —— 代码结构化高级设计算法的选择是必须首要考虑的，也是最重要的一步。一般我们需要分析算法的时间复杂度，即处理时间与输入数据规模的一个量级关系，一个优秀的算法可以将算法复杂度降低若干量级，那么同样的实现，其平均耗时一般会比其他复杂度高的算法少（这里不代表任意输

2017-08-29 18:08:24 400

原创图——C++实现

基本概念图（graph）是用线连接在一起的顶点或节点的集合，即两个要素：边和顶点。每一条边连接个两个顶点，用（i，j）表示顶点为 i 和 j 的边。如果用图示来表示一个图，一般用圆圈表示顶点，线段表示边。有方向的边称为有向边，对应的图成为有向图，没有方向的边称为无向边，对应的图叫无向图。对于无向图，边（i， j）和（j，i）是一样的，称顶点 i 和 j 是邻接的，边（i，j

2017-07-25 14:45:27 14385

原创深入理解浮点数类型float和double

浮点数的表示浮点数格式首先看一下64位机器中的浮点数float和double格式：浮点数位表示有三个字段，分别对这些值进行编码：符号位s，阶码字段exp和小数字段frac。单精度float浮点格式中，s、exp和frac分别为1，8和23位，得到一个32位的表示；双精度double浮点格式中，s、exp和frac分别为1，11和52位，得到一个64位的表示。编码知道了浮点数的位表示，那如何对数值进行

2017-07-17 13:14:29 4170

原创分支定界法——旅行商(TSP)问题

问题描述给定一个n顶点网络（有向或无向），找出一个包含n个顶点且具有最小耗费的换路。任何一个包含网络所有顶点的换路称为一个旅行。旅行商问题（Traveling Salesman Problem，TSP）是要寻找一条耗费最少的旅行。图1 四顶点网络如图1是一个四顶点无向网络。这个网络的一些旅行：1,2,4,

2017-07-01 12:56:08 33015 5

原创回溯法——旅行商(TSP)问题

问题描述给定一个n顶点网络（有向或无向），找出一个包含n个顶点且具有最小耗费的换路。任何一个包含网络所有顶点的换路称为一个旅行。旅行商问题（Traveling Salesman Problem，TSP）是要寻找一条耗费最少的旅行。图1 四顶点网络如图1是一个四顶点无向网络。这个网络的一些旅行：1,2,4,3,1；1,3,2,4,

2017-06-28 18:16:49 8767 1

原创分支定界法——0-1背包问题

问题描述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?算法设计分析：和回溯法中的界定函数类似，对每一个活动节点N，计算收益的上限maxPossibleProfitInSubtree，使得以N为根的子树中，任何一个节点的收益都不可能超过这个值。活动节点使用大根堆maxHeap<heapNode>，按需构造解空间树

2017-06-27 16:01:23 9341 1

原创回溯法——0-1背包问题

问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大?算法设计分析从所有的物品中选取若干将它们装进背包，在满足限制条件的情况下，获得最大的收益。既然要选择一个对象的子集，解空间就应该组织成子集树结构。要设计的递归算法使用深度优先搜索子集树：对于左孩子，满足限制条件即可；对于右孩子，需要利用界定函数计算此节

2017-06-27 15:55:25 5939

原创回溯法和分支定界法

概述要求解一个问题，最可靠的方法是：列出所有候选解，然后逐个检查，理论上在遍历了所有的候选解之后，就能得到所需要的解。但是，对于实际运用中的问题，候选解的规模庞大，即使使用速度最快的计算机，也很难在合理的时间内解决。回溯法和分支定界法师对复杂问题进行系统检查的系统方法。通过使用限制条件和界定函数，可以省去对很大一部分候选解的检查。回溯法——深度优先搜索回溯法是一种选

2017-06-26 16:22:33 6328

原创分治算法

算法思想分治算法把一个问题实例分解成若干个小型而独立的实例，从而可以在并行计算机上执行；那些小型而独立的实例可以在并行计算机的不同处理器上完成。分治法的思想：将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，然后再合并这些子问题的解来建立原问题的解。分治算法的特征分治法所能解决的问题一般具有以下几个特征：1) 该问题的规模缩小到一定的程度就可以容易地解决；2) 该问题可以分解为

2017-06-21 16:31:39 589 1

原创贪心算法——拓扑排序

关于贪心算法介绍： http://blog.csdn.net/mind_v/article/details/72956707拓扑排序问题描述一个复杂的工程，经常可以分解成一组简单一些的任务，这些任务完成了，整个工程就完成了。例如汽车组装问题可以分解成：底盘安装、车轴安装、车轮安装、座位安装、喷漆、刹车安装、车门安装等。但是这些任务之间有个先后顺序，例如车轴安装之前先要进行底盘安装。类似的问题，可

2017-06-09 21:31:34 2088

原创贪心算法——单源最短路径（Dijkstra算法）

单源最短路径——Dijkstra算法问题描述对于给定的加权有向图G（加权邻接数组表示），它的每一条边（i，j）都有一个固定成本（权值）a[i][j]，一条路径的长度就是该路径上所有边的的成本之和。如下图所示，路径124的长度是8，路径125的长度是9。寻找一条从给定的一个源顶点出发到任意顶点的（目的顶点）的最短路径。如1到5的最短路径为1345。贪心法求解根据贪婪法，每一步生成一条当前顶点的最短

2017-06-09 21:22:36 3095

原创贪心算法

最优化问题定义：给定一组限制条件(constraint)和一个优化函数(optimization function)，求出一个可行解(feasible solution)，使得优化函数可能取得最优值，即最优解(optimal solution)，求解这样一个最优解的问题就称为最优化问题(optimization problem)。解决一个最优化问题有很多种方法：贪心算法、分治算法、动态规划、线性规划

2017-06-09 13:38:35 1352

原创红-黑树——C++实现

一、红-黑树基本概念红-黑树(Red-Black tree)是一种特殊的二叉查找树，因此具有二叉查找树的特征：任意一个节点所包含的关键字，大于左孩子的关键字，小于右孩子的关键字。树中每一个节点的颜色或者是黑色或者是红色，和AVL树一样具有平衡性。每一个空指针用一个外部结点来替代，红-黑树的性质可以描述为：RB1：根节点和外部节点都是黑色。 RB2：在根至外部节点路径上，没有连续两个节点是红色。

2017-05-27 10:56:44 687

转载 AVL树—— C++实现

AVL树的介绍AVL树的C实现AVL树节点AVL树接口旋转操作核心1 LL的旋转2 RR的旋转3 LR的旋转4 RL的旋转完整的实现代码AVL树的介绍二叉查找树的深度越小，那么查找所需要的运算时间越小。一个深度为log(n)的二叉查找树，查找算法的时间复杂度也是log(n)。然而，我们在二叉查找树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8，7，6，5，

2017-05-22 11:12:41 631

原创编写C++函数：识别一段string字符串是IPv4还是IPv6

今天做到Calix(南京凯易迅)的笔试题，其中有一题大致意思是：vector<string>中存有string字符串，识别每一个字符串是否是ip地址，三种可能：IPv4、IPv6、Neither，将每个字符串的识别结果依次存入一个vector<string>中返回。编写函数：vector<string> checkIP(vector<string> &ip_array{ } 如：输入：

2017-05-15 16:06:08 4647 1

原创常见排序算法——桶排序(箱子排序)bucket Sort

桶排序是一个经典的排序算法，特点是速度快，算法复杂度为O(n)，且是稳排，当然也是最耗空间的一种算法。例如： 1）排序一组数[7，3，19，11，6，8，1，15] 最大数是19，那首先创建20个空桶，接着就是把这些数依次放进对应的桶中； 2）有重复的元素，如[7，3，9，11，6，3，7，14]，这时候应该保证每个桶能放入多个元素，即最终保证排序稳定性，所以我选择用链表来存储每个桶中的元

2017-05-08 22:53:03 938

原创 error C4146: 一元负运算符应用于无符号类型，结果仍为无符号类型

在学习有符号类型整数运算时，会遇到溢出的可能：如下代码，tadd_ok函数能检测计算结果是否溢出#include<iostream>using namespace std;//判断是否溢出，返回1则不溢出，0则溢出int tadd_ok(int x, int y){ int sum = x + y; if ((x > 0 && y > 0 && sum < 0)

2017-05-08 17:30:10 3584 2

原创 C++中new一个动态数组(内置类型和自定义类型的区别)

在学习数据结构与算法的时候，T *p = new T[n]的算法复杂度为Θ(n)，而int *p = new int[n]的算法复杂度为Θ(1)。 C++ primer的动态内存的讲解没有关于这一点的解释，自己测试了一下：#include<iostream>using namespace std;struct myClass{ int i = 5;};ostream &operato

2017-04-25 15:41:38 5655 1

原创 C++模板类中声明友元函数重载输入和输出运算符时，提示无法解析的外部符号解决方案

在练习模板类的重载输入输出运算符时，编译器提示“无法解析的外部符号”，代码如下：template <typename T>class matrix{ friend ostream& operator<<(ostream &out, const matrix<T> &m); friend istream& operator>>(sstream &in, matrix<T> &m);

2017-04-18 14:51:39 5163 3

原创常见排序算法——选择排序、冒泡排序、插入排序和原地排序

#include<iostream>#include<algorithm>#include<iterator>using namespace std;//选择排序template<typename T>void SelectionSort(T a[], int n){ for(int size = n; size > 1; --size) int indexOfMax =

2017-03-23 22:44:52 843

Mind_V的博客