http://www.lintcode.com/zh-cn/…
给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数。
注意事项
一个数可以在组合中出现多次。
数的顺序不同则会被认为是不同的组合。
样例
给出 nums = [1, 2, 4], target = 4
可能的所有组合有：
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2,…… 阅读全文
背包问题
Reply
Tag Archives: 算法
36 进制
看到同事桌上有一份面试题，有一个 36 进制运算的题目，手贱敲了一下，不调真的不好做啊
#include <stdio.h>
#include <string>
#include <algorithm>
#include <math.h>
int convert_36_10(std::string strNum) {
std::reverse(strNum.begin(), strNum.end());
int n = 0;
for (…… 阅读全文
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?
这题原…… 阅读全文
Jon Bently 一种快排的写法
看到知乎上有这个讨论，程序员能20分钟徒手写出一个没bug的快速排序吗？
void quicksort(int l, int u){
int i, m;
if(l >= u) return;
m = l;
for(i = l+1; i<= u; i++)
if(x[i] < x[l]) // buggy!
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
…… 阅读全文
练手代码白板
先来一个简单的 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…… 阅读全文
基于 AC 自动机的多模匹配的 map
昨天写了一个 AC 自动机的模版题，现在，我们需要基于这个模版，实现一个多模匹配的 map，具体是这样的，我们给一个 map<string, int>，然后给一个串，要求在这个串里面，把 map 中含有的 key 的 value 都返回出来。
注意到昨天的模版题的实现，是会去改动树本身的，同时也没有做一些内存管理方面的处理，另外的区…… 阅读全文
AC 自动机
hdu 2222 题。。（这题号。。。）http://acm.hdu.edu.cn/showprob…
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <string>
#include <queue>
#define CHAR_COUNT 26
class Node {
public:
Node() {
memset(this, 0, sizeof(*t…… 阅读全文
std unique 的实现
接触到 std 的 unique 这个函数，看了一下实现，自己也写了一下。在读默认的实现的时候发现代码真是的比较坑爹的，缩进啊，花括号啊，之类的，都是不按规范来的。
自己照着写了一个如下
#include <iostream>
#include <vector>
template<class It>
It myUnique(It itBegin, It itEnd) {
f…… 阅读全文
找出第一个不重复的字母
今天笔试，遇到一个题目要找出一个字符串中第一个不重复的字母，简单写了一下
#include <stdio.h>
void find(const char *str, char *result)
{
int count[128]={0}, pos[128]={0};
for (int i=0; str[i]!='\0'; i++)
{
int ascii = (int)(str[i]);
count[ascii]++;
if (pos[ascii] == 0)
{
…… 阅读全文
蛇形填数
之前因为家里的原因，回乡下一个星期，期间都没有机会，也没有心情写代码，一个星期就这么毫无长进，罪过。
看到一个蛇形填数的题目，搞了搞，代码如下
#include <stdio.h>
#include <stdlib.h>
void print(int **a, int n)
{
for (int y=0; y<n; y++)
{
for (int x=0; x<n; x++)
{
printf…… 阅读全文