求第一个缺失的整数问题： 给定一个数组A[0...N-1]，找到从1开始，第一个不在数组中的正整数。 例如：3，5，1，2，-3，7，14，8；返回： 4。 问题分析： 可以将找到的数放在正确的位置上，如果最终发现某个元素一直没有找到，则该元素即为所求。 假设前 i-1 个数已经找到，并已经正确存放在前 i-1 位。则可以分下面几种情况：  A[i] = i, i++; 1<A[i]<i, 丢弃； i<A[i]<N, 当A[i] = A[A[i]], 丢弃；当不等于的时候，交换； A[i]>N, 丢弃。  程序实现：   1 /******************...

最小编辑代价问题： 对于两个字符串A和B，我们需要进行插入、删除和修改操作将A串变为B串，定义c0，c1，c2分别为三种操作的代价，请设计一个高效算法，求出将A串变为B串所需要的最少代价。 给定两个字符串A和B，及它们的长度和三种操作代价，请返回将A串变为B串所需要的最小代价。保证两串长度均小于等于300，且三种代价值均小于等于100。  测试样例：  "abc",3,"adc",3,5,3,100 返回：8 问题分析：看到这道题，首先想到的是编辑距离问题，可以说是有异曲同工之处，但需要注意的是要将增删改的代价考虑进去。 注意：（1）增删的操作只能是在A...

编辑距离问题： 给定两个字符串，对两个字符串进行增删改操作，使用最少的次数使得两个字符串相同，使用的最少次数即为编辑距离。 程序实现：   1 /***************************************  2 FileName EditDistance.cpp  3 Author : godfrey  4 CreatedTime : 2016/5/1  5 ****************************************/  6 #include <iostream>  7 #include <cstring>  8 #includ...

字符串的全排列问题： 给定字符串S[0...N-1]，设计算法，枚举字符串的全排列。 1、无重复字符串全排列非递归算法 程序实现：   1 //无重复字符串的全排列递归算法  2 void Permutaion(int* a,int size,int index){  3 if(index == size-1){  4  Print(a,size);  5 return;  6  }  7 for(int i=index;i<size;i++){  8  swap(a[i],a[index]);  9 Permutaion(a,size,index+1); 10  swap(a[i],a...

最长公共子序列： 求两个序列中最长的公共子序列算法，要区别于最长公共子串（其要求连续）。 如：字符串acdfg与adfc的最长公共子序列为adf。 假设c(i,j)记录序列Xi和Yj的最长公共子序列的长度，满足下列公式：  程序实现：   1 /***************************************  2 FileName LongestCommonSubsequence.cpp  3 Author : godfrey  4 CreatedTime : 2016/5/1  5 ****************************************/  6 #i...

字符串循环左移： 给定一个字符串，要求把S的前k个字符移动到S的尾部，如把字符串"abcdef"前面的2个字符'a'，'b'移动到字符串的尾部，得到新字符"cdefab"，即字符串循环左移k位。 程序实现：   1 /***************************************  2 FileName ReverseString.cpp  3 Author : godfrey  4 CreatedTime : 2016/5/1  5 ****************************************/  6 #includ...

哈希表实现： 使用BKDRHash作为基础的哈希函数，同时使用拉链法作为冲突处理方法，实现哈希表的插入和查找操作。 哈希函数BKDRHash实现如下：  1 //映射方法，BKDRHash方法 2 static int32_t BKDRHash(const string& str){ 3 int32_t hash=0,seed = 131; 4 for(uint32_t i=0;i<str.length();i++){ 5 hash = hash * seed + str[i]; 6  } 7 return (hash & 0x7fffffff); 8 }  处理冲突的方...

直方图收集雨水问题： 给定n个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度假定都为1，若这样形状的容器收集雨水，可以盛多少雨水。 如：输入0,1,0,2,1,0,1,3,2,1,2,1；返回为6. 如图所示：  程序实现：   1 #include <iostream>  2 using namespace std;  3  4 int TrappingRainWater(int A[],int n){  5 int SecHight = 0;//当前找到的第二大数  6 int left = 0;  7 int right = n-1;  8 int trap = 0;...

直方图最大矩阵面积法： 给定n个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度假定都为1，找出直方图中最大的矩形面积。 如：给定高度为：2，1，5，6，2，3，最大面积为10.  程序实现：   1 #include <iostream>  2 #include <stack>  3 #include <algorithm>  4 #include <cstring>  5 using namespace std;  6  7 int LargestRectangleArea(vector<int>& height){...

逆波兰表达式： 计算给定的逆波兰表达式的值，有效操作只有加减乘除，每个操作数都为整数。 如： "2"，"1"，"+"，"3"，"*" ： 9；---------（2+1）*3 "4"，"13"，"5"，"/"，"+" ： 6；---------4+（13/5） 程序实现：   1 #include <iostream>  2 #include <stack>  3 #inc...

最长括号匹配： 给定字符串，仅包含左括号'('和右括号')'，它可能不是括号匹配的，设计算法找出最长匹配的括号子串，返回该字串的长度。 如： (() : 2 ()() : 4 ()(()) : 6 ()(())) : 6 (((()())) : 8 1、首先采用栈的存储方式来解决这个问题： 假设起始匹配位置为start = -1，最大匹配长度为MaxLen，考虑第i位字符c： 如果c是左括号，则进行压栈； 如果c为右括号，它一定与栈顶左括号匹配： （1）如果栈为空，表示没有匹配左括号，start = i，为下一次匹配做准备； （2）如果栈不空，出栈。再判断栈是否为空，若为空，MaxLen = ...

    “绘图室”(PaintOffice)可以设计各个图形对象，每个图形对象包括坐标信息，并且可以通过构造函数初始化图形信息；每个图形对象提供Draw()函数，已完成自身的绘制，同时提供SetPos()成员函数来改变成员位置。本次设计中图形对象包括直线、椭圆、矩形三种，如果有兴趣的可以自行添加其他图形。每个类提供构造函数完成信息的初始化，类内没有系统能源申请，可以不要析构函数。Draw()、SetPos()函数可以看成类的成员函数。直线的坐标可用起点和终点的坐标来定位；矩形的坐标用左上角和右下角的坐标定位；椭圆的坐标可用椭圆的外接矩形来定位。     下面列出其中一个图形对象(直线)的相关程...

      每一个计算机程序都是现实中的或者精神中的某个过程的一个模型，通过人的头脑孵化处理啊。这些过程出现在人们的经验或者思维之中，数量数不胜数，详情琐碎繁杂，任何时候人们都只能部分地理解它们。我们很少能通过自己的程序将这种过程模拟到永远令人满意的程度。计算机程序设计领域之令人兴奋的源泉，就在于它引起连绵不绝的发现，在我们的头脑之中，在由程序所表达的计算机机制之中，以及在由此所导致的认识爆炸之中。如果说艺术解释了我们的梦想，那么计算机就是以程序的名义执行着它们。        除了通过编程语言进行表达，程序员还要做些什么？恩，这是一个更深入的问题，大多数程序员在解释他们所作的事情这个问题上都...

      编程是一种技艺，用最简单的话语描述。作为程序员，你就是倾听者，又是顾问；既是解释者，又是发号施令者。设法捕捉难以琢磨的需求，并找到它合适的表达方式；设法使你的工作模块化，使他人在你的基础上进行构建。无论你是开发者，还是项目团队中的一员，相信自己每天创造小小的奇迹。       编程是需要不断练习的，小编博客中会不断发表一些关于程序编程中的编程思想和实践指导，希望能够给予帮助，同时关于编程的一些思维和算法研究，欢迎指导和相互交流。今天我主要介绍2个程序，侧重C++编程基础。 1、 求解1-1/2+1/3-1/4+......+1/99-1/100 编程思想：从算式中可以看出，有明显的...