五月花

原创 win7 64位Ultimate 英文系统中，使用CAJViewer 7.2的方法

首先，打开控制面板，点击区域和语言，将 格式、位置、非Unicode程序语言编码设置均修改为中文，如下图所示。这只是做好了第一步。还差一步。如果此时打开CAJViewer 7.2，仍然会弹出 文件不存在或不能正常访问 错误提示。如下图所示。以前有人说用回7.1版本就可以打开了。我试了一下，7.1版本确实可以打开文档，但是界面有相当一部分字

转载 晶体三极管工作原理讲解方法探讨

补充内容。 原文作者分析的极妙，但是少了饱和区状态的分析。这里加上。三极管的输出特性曲线往往会误导初学者，给人一种先进入饱和区，之后才进入放大区的错觉。其实正确的状态阶段是，输入电压Ube很小，输入电流很小，三极管工作在截止区；加大Ube，发射结导通，输入电流加大，工作在放大区；继续加大Ube，输入电流进一步加大，导致Ic变大，从而Rc上的分压进一步加大，导致集电极所在点的电压降低，从而Uce

原创 64位Linux环境 编译32位汇编程序（外链C库函数）

使用的是gas命令如下 ：as --32 -o helloworld.o helloworld.sld -m elf_i386 -dynamic-linker /lib/i386-linux-gnu/ld-linux.so.2 -o helloworld helloworld.o /lib/i386-linux-gnu/libc.so.6编译、连接 两条命令完成。

原创 返回给定值在有序数组中的插入位置

注意，数组中的数值可能有重复。题目描述：给定一非降序数组，数值可能有重复。再给定一值key，请返回第一个大于key的数组元素的下标。如果没有，则返回数组的长度.int binary_search(int* array, int length, int key){ if(array[length - 1] < key) return length; int left = 0,

原创 【剑指offer】复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）/*struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL),

翻译 算法导论 主项定理

原创 逆序数的三种求法

逆序数：一个数列nums[N]，对任意两个数，如果前面的数大于后面的数，那么就称它们为一对逆序数。我们用一个数组存储逆序数的值，Reverse[i]表示nums[i]之后且比nums[i]小的数。下面我们用三种方法（第一种方法没有实际意义）来求Reverse数组。1. 完全暴力计数法先将Reverse[N]数组初始化为0.求Reverse[i]时，从nums[i]开始，依次向后

原创 树状数组(Binary Indexed Tree)

树状数组(Binary Indexed Tree)，又叫做Fenwick Tree，它能够高效地获取数组中连续N个数的和。传统数组(共n个元素)的元素修改和连续元素求和的复杂度分别为O(1)和O(N)。树状数组通过将线性结构转换成逻辑上的树状结构（线性结构只能逐个扫描元素，而树状结构可以实现跳跃式扫描），使得修改和求和复杂度均为O(lgN)，大大提高了整体效率。对于给定的数组A，我们创

原创 【leetcode】318. Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case

原创 【剑指offer】二叉搜索树的后序遍历序列

一看到后序遍历，就要反应出来：从后向前遍历数组，我可以找到该二叉树每棵子树的根。其实，这道题前序和后序遍历，解题方法是完全一样的，因为只要该遍历中包含了根的信息，就可以按照BST树的定义来检查。所以，中序遍历不行。因为中序遍历不显含根的位置信息。这样，检验该二叉树是否是BST，就可以根据定义来做了。

原创 二叉树的层次遍历+每一层单行输出

给定一棵二叉树，要求按层次遍历该二叉树，每一层将单独输出一行。难点就在于每一层的结点输出一行。本着鄙视递归的潜意识，先用迭代来做，递归的做法放在最后。类似于广度优先遍历，故采用队列 做为辅助记忆结构。/*struct TreeNode{ int val; struct TreeNode *left; struct TreeNode *right; TreeN

原创 【剑指offer】二叉树的镜像

题目描述操作给定的二叉树，将其变换为源二叉树的镜像。 举例：二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7

原创 【证明】加减法交换两个整数，过程可能会溢出，但结果依然正确

请对下面的代码做出判断：void swap_int(int *a,int *b){ if(a == b) return; *a=*a+*b; *b=*a-*b; *a=*a-*b;}以下说法正确的是：A.结果不正确，因为会溢出，用位与的方式就没问题B.结果正确，即使会溢出C.结果正确，不会溢出D.其他选项都不对答案是B 结果

转载 几种TCP连接中出现RST的情况

在TCP协议中RST表示复位，用来异常的关闭连接，在TCP的设计中它是不可或缺的。发送RST包关闭连接时，不必等缓冲区的包都发出去，直接就丢弃缓存区的包发送RST包。而接收端收到RST包后，也不必发送ACK包来确认。其实在网络编程过程中，各种RST错误其实是比较难排查和找到原因的。下面列出几种会出现RST的情况。1 端口未打开服务器程序端口未打开而客户端来连接。这种情况是最为常见和好理

原创 分解正整数的质因数

首先，由 算术基本定理可知，任何一个大于1的正整数，都可以分解成若干个质数的乘积，并且这种乘积的形式是唯一的。所以，对于整数分解，如果先从最小的质数n=2开始进行分解，如果能整除，就只取商，直到不能除时，n++，然后判断n是否大于现在的商。如果大于，结束程序。否则继续循环。核心代码很短，只有10行左右。void prim(unsigned long long m){ un

原创 第一眼你能看出这是函数声明吗

struct Foo{ Foo(){} Foo(int){} void fun(){}};int main(void){ Foo a(10); //语句1 a.fun(); //语句2 Foo b(); //语句3 b.fun(); //语句4 return 0;}上述四个语句，你认为去掉哪句后，可以通过编译器？答案是语句4.看到Foo b();

原创 【剑指offer】替换空格（把一个空格替换为三个字符）

题目很简单，book备忘一下。显然，把一个空格替换为三个字符，替换后原字符串要变长。本题，题目保证原字符串空间可以容纳变长后的字符串。因为替换后变长，所以如果从前往后扫描的话，替换后，会覆盖之后原有的字符。所以采用从后向前来替换。第一遍，从前向后扫描一次，获取有多少个空格以及原字符串的总长度。之后，计算出新字符串的长度。之后，从后向前扫描原字符串，把对应的字符直接放到新字符串对应的

原创 【leetcode】4. Median of Two Sorted Arrays

题目如下：已知两个已从小到大排序的数组nums1[M]和 nums2[N]，返回两个数组中所有数字从小到大排序后的中位数。两个数组中可能均有重复的数字。时间复杂度不允许超过log(N+M).分析：看到已排序的、可随机访问的数组，肯定用二分查找。估计还是有人不知道中位数是什么。中位数就是：若总数为偶数，则返回中间两个数字的平均值；否则返回中间的那个数字。二分查找的难点在于现在

原创 插入、删除、修改操作 代价不等的 最短编辑距离 动态规化求法

直接上干货。什么叫编辑距离？从字符串str1到字符串str2需要经过多少次编辑。每次编辑只能增加 / 删除 / 替换1个字符。计算出从str1到str2最小的编辑距离(Minimum Edit Distance)，用此可作为两个字符串之间的相似度的衡量。定义符号：对于两个字符串strA, strB，它俩的长度分别记为lenA, lenB.MED：最小的编辑距离(Minimu

原创 数据流中所有数排序之后的中位数

先来讲一下STL中make_heap   push_heap   pop_heap这三个模板函数的用法。template void make_heap (RandomAccessIterator first, RandomAccessIterator last); template void make_heap (RandomAccessIterator first, Ran

原创 最长公共子序列LCS 与最长公共子串 两个问题的动态规化 解法

一、最长公共子序列最长公共子序列的问题常用于解决字符串的相似度。最长公共子序列全称为Longest Common Sequence，LCS，注意与最长公共子串的区别。序列可以不连续，子串一定是连续的。下面我们先讨论子序列（不连续）。对于两个字符串str1, str2，它俩的长度分别记为m, n。如果使用蛮力法去查找两个字符串的LCS，则即使我们忽略两个子串的比较时间，单单来看任

原创 【编程之法习题】第一章 字符串

在

原创 【leetcode】3. Longest Substring Without Repeating Characters 三种方法

查找给定字符串的最长不重复子串。方法一：该方法很直接，依次从每一个字符开始，向后逐个遍历，直到遇到重复的字符为止。判断字符是否重复，用到了hash数组，可以在常数时间内判断当前字符在本次循环中是否访问过，由于针对的是ASCII字符集，故使用的hash数组大小为256.int lengthOfLongestSubstring(string& s){ int n = s.size();

原创 【leetcode】5.Longest Palindromic Substring >>Manacher算法

求指定字符串的最长回文子串。给定 std::string Str，采用manacher算法，在O(n)时间内，在O(n)空间下，解决该问题。字符串包括奇数长的和偶数长，同时其中所含的回文串也分奇数长和偶数长，如果分情况讨论的话，比较复杂。manacher想出了一个方法，可以统一各种情况。manacher算法需要花费O(n)的时间来计算以各个字符为中心的最长回文串的长度，用一个一维数

原创 【后缀数组系列】二、后缀数组的两种求法

待续。。。

原创 【后缀数组系列】一、基本概念

如果你没有听说过后缀数组，那么我敢肯定，你确实没怎么处理过字符串相关的算法问题。————题记对于解决字符串相关的问题，后缀数组是一把利器。它经常被用来解决字符串相关的各种复杂问题。下面开始介绍后缀数组。后缀数组 int SA[N]从后缀字符串开始。对于字符串S[9] = "aabaaaab"来说，字符串的长度为8，所以不包括空子串，共有8个后缀字符串，我们分别用suffix

原创 旋转打印矩阵、旋转存储矩阵、之字形打印矩阵

题目：输入一个矩阵，按照从外向里以顺时针顺序依次打印出每一个数字。例如：如果输入如下矩阵：1      2    3     45      6    7     89    10  11  1213  14  15  16有三问：1）如何实现转圈打印矩阵？ 2）如何实现顺时针旋转矩阵？3）如何实现“之”字形打印矩阵？

原创 AVL树的插入与删除，重点是四种旋转

本文不是入门篇，零基础请绕过。先用维基上的话来介绍一下基本概念。       在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M.

原创 不用栈，来实现二叉树的非递归中序遍历

如果要求只能用非递归方法，同时还不让用栈，来遍历完全二叉树，则每个结点必须有一个指向父结点的指针。题目：完全二叉树，采用三叉链表结构。要求 不用递归，中序遍历这棵树。要求空间复杂度是O(1).分析：题目不让用递归，那就用迭代，同时，空间复杂度是常量级，摆明了不让用栈。那就必须是三叉链表了。三叉链表是二叉树的另一种主要的链式存储结构。三叉链表与二叉链表的主要区别在

原创 二叉树的遍历（递归加迭代）

先定义树中结点的结构如下：//二叉树结点typedef struct BiTNode{ //数据 char data; //左右孩子指针 struct BiTNode *lchild,*rchild;}BiTNode,*BiTreePtr;后序遍历最难，先搞后序遍历。递归：//后序遍历void PostOrder(BiTreePtr T){ if(nullptr

原创 线性时间排序： 三种非基于比较的内部排序算法

一、基于比较的排序算法，在最坏情况下，最少都需要用O(nlgn)次比较。下面来证明一下。不妨我们假设 排序都是从小到大进行排序。说明： 用1、2、3来表示三个元素，用π(1)、π(2)、π(3)来表示该元素对应的值。用尖括号〈1,3,2〉表示π(1) ≤ π(3) ≤ π(2)。对于n个元素而言，由于写算法不知道 未来每个待排元素的大小，所以要使排序算法能正确地工作，其必要条件就是

原创 折纸问题 C++实现

题目描述：把纸条竖着放在桌面上，然后从纸条的下边向上对折，压出折痕后再展开。如果每次都从下边向上对折，对折N次。我们规定，对于每条折痕，如果突起的方向指向纸条的背面，那么这条折痕叫做“下”折痕 ；相反，突起的方向指向纸条正面的折痕叫做“上”折痕。请从上到下打印所有折痕的方向。分析：当纸条从下向上对折一次后打开，有一条折痕，向下，记为0。继续再向上对折一次，打开后，在

转载 什么是P问题、NP问题和NPC问题

你会经常看到网上出现“这怎么做，这不是NP问题吗”、“这个只有搜了，这已经被证明是NP问题了”之类的话。你要知道，大多数人此时所说的NP问题其实都是指的NPC问题。他们没有搞清楚NP问题和NPC问题的概念。NP问题并不是那种“只有搜才行”的问题，NPC问题才是。好，行了，基本上这个误解已经被澄清了。下面的内容都是在讲什么是P问题，什么是NP问题，什么是NPC问题，你如果不是很感兴趣就可以不看了。接

原创 NP完全问题

从浅入深来介绍相关的概念。一、时间复杂度       时间复杂度并不是表示一个算法解决问题需要花多少时间，而是当问题规模扩大后，算法需要的时间长度增长得有多快。不管数据有多大，如果算法处理数据所用的时间始终基本不变，我们就说这个算法很好，具有O(1)的时间复杂度，也称常数级时间复杂度。而当数据规模变得有多大，算法所花的时间也跟着变得有多长，这个算法的时间复杂度就是O(n)，比如找n个数中的

原创 说说std::endl函数

所谓std::endl，原来就是一个模板函数名，相当于函数指针啊。该函数以引用的方式接收一个输出对象，经过处理后，再以引用的方式返回该对象本身。#include <iostream>int main(void){ endl(std::cout << "Test 4 std::endl"); endl(std::cout << "Here is the 2nd Line!");}请不要对endl前面不加std命名空间限定符感到不解，请查看Koenig looup法则，或者叫ADL法

原创 求二进制数中1的个数

题目描述给定一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。方法一：直觉法。完全凭直觉。int BitCount(unsigned int n){ unsigned int c =0 ; // 计数器 while (n >0) { if((n &1) ==1) // 当前位是1 ++c ; // 计数

原创 矩形覆盖

如图，设n=3，设我们从最左边开始覆盖，一开始，我们有两种选择，竖着放或者横着放，若横着放第一块后，下一块必然要把4个格子填满。然后图像就分为已经填好的，和还没填好的。可以看到剩下还没填好的，其实是初始问题n的一个子问题。于是f(n) = f(n-1) + f(n-2),于是这又是一个斐波那契数列问题。用自底向上动态规划来做。当n为0时，f(0) = 1; 当n为1时，f(1) = 1; 当n为2时，f(2) = 2;

原创 跳台阶问题 + 变态跳台阶问题 解法（动态规划递归 + 非递归）

一、跳台阶问题题目描述： 一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。通过题目的描述，可以很清晰地看到，这就是一个Fibonacci数列。递归实现：unsigned long long solution(int stageNum){ //定义递归出口 if(stageNum <= 0) re

原创 等概率随机生成不重复的数

一、1到n n个数字随机全排序，或者说，随机生成1到n n个不重复的数字用空间换时间，需要空间复杂度为o(n)，时间复杂度为o(n)用一维数组顺序存储1到n这n个数字。然后先在1到n中随机生成一个下标，输出该下标对应的值，然后将数组最后一个交换。并将此时最后一个从逻辑上删除。倒数第二个成为最后一个。生成n次随机下标，问题解决。简单吧。void generate_N_Random

原创 linux下配置Qt5 开发环境

linux下的Qt安装程序自身不带有C++编译器、调试器、make程序等开发工具。安装者要确认自己的linux系统中已经存在了这些开发工具。同时，对于用Qt开发图形界面，Qt会用到openGL的相关库文件和头文件。虽然绝大多数的linux发行版中都没有预置安装这些开发工具，但是要安装它们，也是非常简单的。用一行安装命令即可安装完毕。