It_Ds_N_cpp-CSDN博客

原创时隔三年，我又回来了！

过去三年，一直忙于硕士论文 + 外出实习（百度 + 华为 + 网易游戏）一年 + 谈恋爱（现已拜拜）。毕业后，在中国电信IT研发中心工作了两年大数据平台相关的工作。现在在阿里做大数据相关工作。突然收到邮件说我的博客很久没更新了，然后我发现我居然登录不了，各种忘记密码，更改邮箱，手机号等。以后的博客都写关于big data相关的了。。 ...

2018-11-08 10:37:50 481 1

原创在由N个正整数的集合S中，找出最大元素M，满足M=A + B，其中A,B都是集合S中元素

思路：先对集合排序，时间复杂度nlogn，再把M从最大值开始遍历，A和B分别取小于M的最小值和最大值，测试A+B是否等于M，如果小则A右移，如果大则B左移。总的时间负责度为n*nint find(int S[], int n){ sort(S, S + n); for(int i = n - 1; i >=2; --i){ int left = 0, right = i - 1

2015-08-28 21:30:11 1015

原创查找数组中第二大的数字

#define ARRSIZE 10#define MINNUMBER 0xFFFFFFFF#define FIND_SUCESS 1#define FIND_FAIL 0int GetSecondMaxNumber(int buffer[],int *secondMax){ int i,max;

2015-08-28 16:37:06 1008

原创 windows下实现UDP

服务器端：SOCKET sockSrv = socket(AF_INIT, SOCK_DGRAM, 0); SOCKADDR_IN addrSrv; addrSrv.sin_addr.S_un.S_addr = htonl(INADDR_ANY); addrSrv.sin_family = AF_INIT; addrSrv.sin_port = htons(60

2015-06-18 21:05:40 701

原创 C语言实现TCP通信

服务器端：#include #include #include #include #include #include #include #include #define SERVPORT 3333#define BACKLOG 10#define MAX_CONNECTED_NO 10#define MAXDATASIZE 5int main() { str

2015-06-18 13:52:06 2952 1

原创几种典型的设计模式

//工厂模式#include using namespace std;static const double PI = 3.14;class Shape {public: virtual double Area() = 0; virtual ~Shape() {}};class Rectangle : public Shape {public: Rec

2015-05-22 22:02:57 472

原创 3.1.3 STL中list、map、vector的使用方法

（一）list的使用方法：代码：#include #include #include #include #include using namespace std;typedef list LISTINT;typedef list LISTCHAR;int main() { LISTINT listA; LISTINT::iterator it1;

2015-05-12 13:25:10 662

原创 3.1.2 函数模版与类模版

一、函数模版比较两个数的大小。代码：#include using namespace std;template inline int myCompare(const T &a, const T &b) { if(a > b) return 1; else if(a < b) return -1; else return 0;}int main()

2015-05-12 12:31:38 522

原创 4.7 蚂蚁爬杆

题目：有一根树枝，树枝很细，不能同时通过两只蚂蚁。开始时，蚂蚁的头朝左还是朝右是任意的，它们只会朝前走或调头，但不会后退。当两只蚂蚁碰头时，它们会同时调头朝反方向走。求所有蚂蚁都离开木杆的最短时间和最长时间。思想：虽然两只蚂蚁相遇后是调头往反方向走，但是，可以“看作”两个蚂蚁相遇后，擦身而过。也就是说，可以认为蚂蚁的运动是独立的，是否碰头并不是重点。

2015-05-09 11:10:37 918

原创 4.4 点是否在三角形内

题目：给定一个三角形和一个点，判断这个点是否在三角形内。。第一种方法：面积相等法如果点在三角形内部，则如果将三角形的三个顶点与这个点相连所得的三个小三角形的面积之和与原三角形的面积相等S(A,B,D) + S(A,C,D) + S(B,C,D) = S(A,B,C)第二种方法：向量叉积法判断点P3是否在向向P1P2的左边，只需要通过两个向量P1P2、

2015-05-09 10:45:57 691

原创 3.10 分层遍历二叉树

题目1:写一个函数，打印二叉树中某层次的节点（从左到右），其中根节点为第0层。思路：利用递归算法，思想是：要求访问二叉树中第k层的节点，那么其实就是要访问“以该二叉树根节点的左右子节点为根节点的两颗子树”中层次为k-1的节点代码：struct pNode { int data; pNode *lChild; pNode *rChild;};int

2015-05-07 11:48:36 520

原创 3.9 重建二叉树

题目：给定一颗树的先序遍历结果和中序遍历的结果，重建这颗树。例如：前序：a b d c e f中序：d b a e c fa是根节点。思路：根据前序，可以很快找出根节点a，然后根据中序，可以找出根节点a的左右子树，然后递归求a的左子树前序b d跟中序d b，a的右子树前序c e f跟中序e c f即可代码：struct pNode

2015-05-07 11:05:58 547

原创 3.8 求二叉树中节点的最大距离

题目：把二叉树看成一个图，父子节点之间的连线看成是双向的，定义“距离”为两个节点之间的边数。求一颗二叉树中的两个节点之间的距离的最大值。方法一：用书上写的方法：代码：struct node { node *left; node *right; int nMaxLeft; int nMaxRight; cha

2015-05-06 22:16:33 647

原创 3.7 队列中取最大值操作问题

问题：假设有这样一个拥有3个操作的队列：1. EnQueue(v): 将v加入队列中2. DeQueue(): 使队列中的队首元素删除并返回此元素3. MaxElement: 返回队列中的最大元素设计一种数据结构和算法，让MaxElement操作的时间复杂度尽可能地低。方法：用两个栈来模拟队列在代码中，maxStackItemIndex代表栈中dui

2015-05-06 18:04:44 750

原创 3.6 编程判断两个链表是否相交

（一）题目：输入一个单项链表，找出该链表的倒数第k个节点。解法：设立两个指针，先让第一个指针先往前走k步，然后第二个指针放到链表开头。然后两个链表一起往后走，当第一个链表到达链表尾部的时候，后面那个链表所在的位置就刚好是链表的倒数第k个节点！代码： struct node { int data; node *pNext;};node

2015-05-05 13:59:15 515

原创 3.5 最短摘要的声成

题目：Alibaba笔试题：给定一段产品的英文描述，包含M个英文字母，每个英文单词以空格分隔，无其他标点符号；再给定N个英文单词关键字，请说明思路并编程实现方法String extractSummary(String description,String[] key words)，目标是找出此产品描述中包含N个关键字（每个关键词至少出现一次）的长度最短的子串，作为产品简介输出。（不限编程语

2015-05-05 11:07:23 576

原创 C++ STL中的哈希表 hash_map

在定义hash_map容器的时候，不仅需要指定键和值的类型，还需要指定hash函数和相等函数（一）hash_map 的hash函数hash到底是什么样子？看看源码:struct hashint> { size_t operator()(int __x) const { return __x; }};原来是个函数对象。在SGI S

2015-05-04 22:55:39 1543

原创 3.4 从无头单链表中删除节点

题目：有一个单链表，没有头指针，现在有一个指针指向这个链表的中间的一个节点，要求删除这个节点。方法：由于没有办法寻求指针去找到要删除的这个节点的前一个节点。所以要另想办法。设立新的指针指向要删除的节点的后一个节点，然后把这两个节点里面的数据换一下！然后删除要删除节点的后一个节点！这样就ok了！代码：void DeleteRan

2015-05-04 20:29:40 605

原创 3.3 计算字符串的相似度

题目：定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：　　1.修改一个字符（如把“a”替换为“b”）;　　2.增加一个字符（如把“abdd”变为“aebdd”）;　　3.删除一个字符（如把“travelling”变为“traveling”）;　　给定任意两个字符串，你是否能写出一个算法来计算它们的距离呢？方法：　　　

2015-05-04 19:13:49 545

原创使用libspopc函数库实现POP访问

#include #include #include #include typedef struct _emaillist emaillist;struct _emaillist { // 定义结构体，用于保存邮件信息 int size; int sig; char head[500]; char msg[

2015-04-28 13:18:34 949

原创使用libESMTP函数库实现电子邮件的发送

书上P260#define _XOPEN_SOURCE // 定义系统环境，使符合X/Open标准#include #include #include #include #include #include #include #include #include #inc

2015-04-28 11:57:38 2951 2

原创使用libcurl实现简单的HTTP访问

使用简单的接口模式设计一个HTTP访问的应用程序，通过网络获得HTML文件。#include #include #include // 包含libcurl库FILE *fp;

2015-04-28 11:46:45 1431

原创多线程的实现

include #include #include #include #define NUM_THREADS 6 // 定义线程总素void *thread_function(void *arg);int main(){ int res; pthread_t a_thre

2015-04-27 21:07:23 374

原创线程操作－－－－取消线程

#include #include #include #include // 包含线程库void *thread_function(void *arg); // 定义线程函数原型

2015-04-27 21:07:15 362

原创线程间的同步－－－－利用互斥量来实现

#include #include #include #include #include // 包含线程库#include

2015-04-27 21:03:59 705

原创线程间的同步－－－－利用信号量来实现

#include #include #include #include #include #include sem_t bin_sem;void *thread_funtion(void *arg);char work_area[1024];int main() { pthread_t a_thread; int res; void *thread_result; r

2015-04-27 20:49:52 784

原创线程的基本操作，创建线程，结束线程，新线程跟原线程共享变量

#include #include #include #include // 包含线程库#include void *thread_function(void *arg);

2015-04-27 20:32:02 622

原创进程间通信－－－在父进程跟子进程之间利用管道进行通信。一个简单的例子

#include //提供open函数#include // 该头文件提供系统调用的标志#include // 该头文件提供系统状态信息和相关函数#include // 该头文件提供进程I/O操作的相关函数#inc

2015-04-27 20:26:29 2636

原创进程的基本操作，fork（），创建多进程。

fork用于新建一个子进程，简单的例子：#include //提供open函数#include // 该头文件提供系统调用的标志#include // 该头文件提供系统状态信息和相关函数#include // 该

2015-04-27 20:24:05 731

原创 C语言实现scoket通信。

服务器端：#include #include // 包含套接字函数库#include #include

2015-04-26 00:37:13 782

原创字符串高频面试题。

（一）题目：把一个01（只包含0和1的串）串进行排序。可以交换任意两个位置，求最少交换的次数。方法：仿造快速排序里面的partition的过程。。。最左边的0和1是没有意义的，从左到右扫到第一个1，从右到左扫到第一个0，然后交换，然后继续扫下去，就ok啦。。代码：#include #include #define MAXN 1000using namespace st

2015-04-23 10:21:28 657

原创 3.2 电话号码对应英语单词

原始问题如下：手机上面的数字键均对应了几个字符，譬如2对应了a,b,c。问题是当输入一段数字后，求出所有可能的字符组合第一种方法：假设电话号码是n个数字，那么就n个for循环。这方法果断不好第二个方法：#include #include using namespace std;char c[10][10] ={ "", "", "

2015-04-21 10:03:02 757

原创 3.1 字符串移位包含的问题

题目：给定两个字符串s1,s2，要求判定s2是否可以被s1循环移位后得到的字符串包含。思路：首先如果第一个字符串的长度比第二个更短的话，那么直接错误，没有比较的意义了。然后，因为循环移位的原因，如果s2可以被s1循环移位后的结果所包含，那么肯定可以被s1s1所包含。#include #include #include #define MAXN 1000using na

2015-04-20 21:12:46 662

原创 2.19 区间重合判断

问题：1. 给定一个源区间[x,y]和N个无序的目标区间[x1,y1] [x2,y2] ... [xn,yn]，判断源区间[x,y]是不是在目标区间内。2. 给定一个窗口区域和系统界面上的N个窗口，判断这个窗口区域是否被已有的窗口覆盖。1. 解法：先用区间的左边界值对目标区间进行排序O(nlogn)，对排好序的区间进行合并O(n)，对每次待查找的源区间，

2015-04-20 20:25:26 522

原创 2.17 数组循环移位

题目：把一个含有N个元素的字符串右移K位，要求时间复杂度为O(N)，且只允许使用两个附加变量。例子：字符串为：abcd1234，右移4位，结果变为：1234abcd思路：移动前跟移动后是有两段的顺序是不变的，所以可以把这两段看成两个整体右移K位的过程就是把数组的两部分交换一下。交换的过程：（1）逆序排列第一部分（2）逆序排列第二部分（3）再全部逆序！

2015-01-25 18:13:45 610

原创 2.16 求数组中最长递增子序列

题目：求一个一维数组(N个元素)中最长递增子序列的长度DP题代码如下：#include using namespace std;const int MAXN = 100000;const int INF = 10000000;int minV[MAXN], lis[MAXN], Array[MAXN];int n;//lis[i]表示从第i个元素开

2015-01-25 17:36:49 695

原创 2.15 子数组之和的最大值（二维）

题目：给定一个二维数组，求这个二维数组的子数组之和的最大值。分析：将二维降低到一维的情况。代码：#include const int MAXN = 10000;const int INF = 100000000;using namespace std;int B[MAXN][MAXN], PS[MAXN][MAXN];int n, m;int B

2015-01-25 11:33:12 649

原创 2.14 求数组的子数组之和的最大值

题目：给定一个一维数组，求这个数组的子数组之和的最大值。最佳方法：动态规划！一、可以将一个大问题（N个元素数组）转化为一个较小的问题（N-1个元素数组）。。假设已经知道（A[1],...A[n-1]）中最大的子数组的和为：All[1]并且已经知道（A[1],...A[n-1]）中包括A[1]的子数组的最大和为start[1]所以最终的解All[0]

2015-01-25 11:29:54 693

原创 2.13 子数组的最大乘积

题目：给定一个长度为N的整形数组，只允许用乘法，不能用除法。计算任意N-1个数的组合中乘积最大的一组。方法一：#include #define MAXN 10000using namespace std;int n, a[MAXN], s[MAXN], t[MAXN], p[MAXN];//s[i]表示数组前i个元素的乘积//t[i]表示数组后N-i个元素的乘

2015-01-18 21:18:47 728 1

原创 2.12 快速寻找满足条件的两个数

题目：一个数组，快速找出两个数的和，使得这个和等于给定的另外一个数思路：先排序，然后首尾两个指针，i.j，如果和等于给定的数，则找到，如果小于的话，则I++，如果大于的话，则J--代码：#include #include #define MAXN 10000using namespace std;int n, sum;int a[MAXN];int main

2015-01-18 12:04:23 674

空空如也

空空如也