来看这个题,https://leetcode.com/problems/…,要求常数空间,想了想,没想到,找了答案,是这样
class Solution {
public:
void connect(TreeLinkNode *root) {
if (!root) {
return;
}
TreeLinkNode dummy(-1);
for (TreeLinkNode *prev = &dumm…… 阅读全文
Tag Archives: 数据结构
Linked List Cycle
所谓拳不离手曲不离口,算法和基础不能丢。
话说三藏师徒四人辞别女儿国,再上西行路,今天来到。。。啊呸,扯远了。。
今天来看这个,https://oj.leetcode.com/proble…,题目是这么说的
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
这题原…… 阅读全文
tr1 的 unorderd_map
#include <tr1/unordered_map>
#include <stdio.h>
#include <string>
int main() {
typedef std::tr1::unordered_map<std::string, int> HashMap;
HashMap mapNumber;
mapNumber["one"] = 1;
mapNumber["two"] = 2;
std::tr1::hash<st…… 阅读全文
练手代码白板
先来一个简单的 list
#include <stdio.h>
class ListNode {
public:
ListNode(int n) {
this->n = n;
this->pNext = NULL;
}
int n;
ListNode* pNext;
};
class List {
public:
ListNode* pHead;
List(ListNode* pHead) {
this->pHead = pHead;
}
List* add(ListNod…… 阅读全文
STL set 的一些实现差异
侯捷大师在 STL 源码剖析中说道,set 的迭代器的值是不可改变的,这个本来很好理解,但是我神奇的在 visual studio 2005 上发现,神奇的事情总是会发生
#include <stdio.h>
#include <map>
#include <string>
#include <set>
int main() {
std::set<int> setInt;
setIn…… 阅读全文
二级指针删除单向链表
今晚在这里看到一篇文章,http://coolshell.cn/articles/8…,原文给的是代码片段,本着动手实践的原则,另外顺便复习一下链表,写了下代码
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int n;
struct _node *next;
} node;
typedef int (* remove_fn)(node const *…… 阅读全文
出栈次序问题
昨天笔试,见到一个题
一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
写代码模拟的结果如下
#include <iostream>
#include <stack>
#include <queue>
#include <set>
using namespace std;
set<queue<int>> total;
void print(queue<int> q)
{
total.i…… 阅读全文
生成可重集的排列
刘汝佳在算法竞赛入门经典,http://book.douban.com/subject…,的 118 页提到生成一个可重集的全排列问题,跟上次的 生成一个字符串的全排列 很相像,但是写法却巧妙很多
#include <stdio.h>
void quick_sort(int a[], int left, int right)
{
int i=left, j=right;
int povit = a[(i+j)/2];
while (i …… 阅读全文
简单枚举的除法
今天看到一个简单枚举的题目
除法
输入正整数n,按从小到大的顺序输出所有形如abcde/fghij=n的表达式,其中a~j恰好为数字0~9的一个排列,2 阅读全文
栈结构练习
今天从刘汝佳的书上看到一个简单的栈的题目
有n节车厢从A方向驶入车站,按进站顺序编号1~n。现让这些火车按照某种特定的顺序进入B方向的铁轨并驶出车站。为了重组车厢,可以借助中转站C。C是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢,一旦从A移入C,就不能再…… 阅读全文