本题给你一个无向图，其中有n个顶点，n-1条边，因此取其中的任意某顶点作为根，都可以构建成一棵树。那么本题的问题就是在这些树中找出高度最小的树，返回树的根节点；如果有多棵树的高度相同，则返回多个根节点。

思路1：一开始，我认为最直白的解法就是遍历所有的顶点，以该顶点为根，求此树的高度。最后找出高度最小的树就是答案。此为暴力法，但是暴力一般往往会超时，本题也不例外。所以就得另辟蹊径咯。

思路2：先找到所有的叶子节点(该顶点只与一个顶点连接，即只有一条边)，再删除所有的叶子节点，再继续找目前的叶子节点，再删除掉。直到找不到叶子节点为止。那么最后一次找到的叶子节点就是所求的根节点。这题算是trick吧，自己多画几个图，或许可以发现这个规律。

好了，代码如下。

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:
3
/ \
2 3
\ \
3 1
Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
3
/ \
4 5
/ \ \
1 3 1
Maximum amount of money the thief can rob = 4 + 5 = 9.

本题是一道树形DP问题。
思路：
一颗二叉树可以返回两种结果，选取父节点的结果与未选取父节点的结果。
其中，选取了父节点，则左右孩子节点都不能被选取。即F0(root) = root->val + F1(root->left) + F1(root->right).
未选取父节点，则左右孩子节点可选可不选，视情况而定。
即F1(root) = max(F0(root->left),F1(root->left))+max(F0(root->right),F1(root->right)).
<！–more–>

本题要求将二叉树所有的路径输出，是一道简单题，深度优先遍历即可。
二叉树节点存储的是Int值，需要将其转化为字符串。

今天看了ICPC-2016WF，瞬间又燃起了刷题的兴趣。研一的时候玩了好几个月，后来由于忙其它的东西就不怎么刷题了。

这道题是判断链表是否是回文，需要0(N)时间复杂度，0(1)空间复杂度。
阶梯思路想到了比较简单，先翻转一半链表，再双指针判断即可。

例如：链表的如下
1->2->3->3->2->1，总共有6个元素，可以翻转最后三个元素，得到1->2->3->1->2->3。
设定两个指针分别指向前半部分的起点与后半部分的起点，再依次比较节点上的元素是否相同即可。

今天完成了人生中的第一次正规面试，貌似来的真的太晚了。本人半路出家，本科四年只学过C语言，考研那会才真正开始踏入CS专业的道路。
研一刚进来的时候，那叫一个菜啊，真的菜。连VS2010才从研一的时候开始用，以前都用VC6.0，真是呵呵哒了。自己的研究方向是图像处理，啥都不知道，先从Opencv自学开始，自己慢慢地摸索，虽然进度很慢，但是到现在为止自己感觉真的是进步蛮大的。
研一，自学了数据结构，Leetcode刷了一大半，那时只剩30道左右没又刷了。自学了MFC,写了一个图书馆管理系统。积累了一些图形图像的基本知识及相关机器学习的算法。
研二，重点学了Linux,深入C++的理解，看了《C++ Primer》，《Effective C++》,<<深度探索C++对象模型>>，《C和指针》。
通过网易云课堂，看了很多择善教育的Win32编程视频，随后自己开始Windows编程的学习，主要看了《Windows程序设计》上下版，《Windows核心编程》
对了，最重要的是着重了解Duilib开源框架，这个是用C++，在Win32上封装的一个UI库。写界面真的是比用原生Win32或MFC开发简单了很多倍，重点还更漂亮！

链表旋转

链表旋转有指定一段旋转，也有整个链表旋转。我这边讲述下整个链表旋转，因为核心的思想都是一样的。

核心思想

构建三个指针head,pre,cur。
其中，head->next指向我们待旋转链表的头结点。pre指向头结点。cur指向第二个结点。
每一次的操作都是一样的，如下

1
2
3
4
5

tmp = head->next;
pre->next = cur->next;
head->next = cur;
cur->next = tmp;
cur = pre->next;

理解了上面的核心代码，链表旋转就完成一大半了，剩下要做的就是让链表循环起来及一些边界条件的判断，如下

本文主要是对内核模式下的多线程机制进行讲述。与用户模式下的同步机制相比，使用内核对象的同步机制用途更加广泛。

内核对象包括以下几类

• 进程
• 线程
• 作业
• 事件
• 可等待的计时器
• 信号量
• 互斥量

等待函数

在使用内核对象的同步机制时，就要用到等待函数来判断内核对象是否已经触发，这样就可以确定调用线程是否可被调度。

WaitForSingleObject

1

DWORD WaitForSingleObject(HANDLE hObject, DWORD dwMilliseconds);

• hObject：表示要等待的内核对象
• dwMilliseconds：表示线程愿意花费多少时间来等待对象被触发（时间单位：毫秒），INFINITE表示无限等待

• 函数的返回值：如果线程等待的对象被触发了，则返回WAIT_object_0; 如果因为等待超时，返回WAIT_TIMEOUT; 如果给函数传入的是无限的句柄，则返回WAIT_FAILED;

  阅读全文 »

本文主要讲了用户模式下的线程同步机制，用户模式下的同步最大的好处是速度快。此外还有内核状态下的同步机制将放在写一篇博客中讲述！

原子访问

• 指的是一个线程在访问某个资源的同时能够保证没有其他线程会在同一时刻访问同一资源。
  Interlocked系列的函数可以保证是原子操作。

高级线程同步

• 当线程想要访问某一共享资源的时候，线程必须调用系统函数，将线程想要访问的东西作为参数传递给函数。如果操作系统检测到资源可以被访问，那么这个函数会立即返回。这样线程就编程可调度状态。如果无法访问该共享资源，那么系统会将线程切换到等待状态，使线程变得不可调度，从而避免线程浪费CPU的时间。

关键代码段

• 这种方式让多行代码以原子的方式对资源进行操控。

  1 2 3 4 5 6

  CRITICAL_SECTION g_cs //初始化关键代码段结构 InitializeCriticalSection(g_cs); //初始化 EnterCriticalSection(&g_cs); //进入关键代码段 ... LeaveCriticalSection(&g_cs); //离开关键代码段 DeleteCriticalSection(g_cs); //删除

阅读全文 »

New和Delete

• 内置类型对象或未提供默认构造函数的类类型对象必须显示初始化

  1 2	int* a = new int; //a未初始化 int* b = new int(); //b初始化为0

• delete后，应该将指针赋值为NULL，否则该指针成为“悬垂指针”，悬垂指针是指向曾经存放对象的内存，但该对象已经不再存在了。

• C++保证：删除0值的指针是安全的

显示类型转换

• 调用方式： cast-name(expression)

• static_cast
  编译器隐式的执行任何类型转换

  1 2	void* p = &d; double* dp = static_cast<double*>p;

• dynamic_cast

• const_cast
  转换掉表达式的const性质
• reinterpret_cast
  阅读全文 »