Skip to content

Instantly share code, notes, and snippets.

@dkyang
dkyang / candy.cpp
Last active December 24, 2015 15:39
N个孩子站成一排,每个人分给一个权重。按照如下的规则分配糖果: 每个孩子至少有一个糖果;所分配权重较高的孩子,会比他的邻居获得更多的糖果。 问题是,最少需要多少个糖果?
#include <iostream>
#include <vector>
using namespace std;
void Candy(int weight[], vector<int>& result, int len)
{
int i = 0;
while (i < len) {
int j;
int count = 0;
@dkyang
dkyang / find_number_once.cpp
Created June 23, 2013 12:42
《剑指OFFER》面试题40:数组中只出现一次的数字
#include <iostream>
using namespace std;
void FindNumOnce(int pArray[], int nLength,
int* pNum1, int* pNum2);
int FindFirstBit1(int nNum);
bool IsBit1(int nNum, int nPos);
void FindNumOnce(int pArray[], int nLength,
@dkyang
dkyang / lcs.cpp
Last active December 17, 2015 13:29
几道常见的动态规划面试题
//http://www.ahathinking.com/archives/124.html
#include <iostream>
#include <string>
using namespace std;
int LCS(const string& str1, const string& str2, string& longest_seq)
{
int len1 = str1.size();
@dkyang
dkyang / sort.cpp
Last active December 17, 2015 12:49
各种排序算法,实现方法参见《数据结构与算法分析——C语言描述》第七章。
//来自《数据结构与算法分析——C语言描述》,Mark Allen Weiss,第7章,排序
//todo: 桶排序
#include <iostream>
using namespace std;
typedef int ElementType;
static const int QS_CUT_OFF = 5;
@dkyang
dkyang / transpose.cpp
Last active December 17, 2015 10:39
增强代码局部性,加快矩阵转置速度
#include <iostream>
#include <ctime>
using namespace std;
//dim==10000------1.406s
//最直接的方法
void transpose1(int* dst, int* src, int dim)
{
int i, j;
@dkyang
dkyang / TopK.cpp
Last active December 16, 2015 23:58
寻找前K大的数的几种解法,来自《编程之美》2.5
//寻找前K大的数的几种解法
//来自《编程之美》2.5
#include <iostream>
#include <limits>
#include <cstdlib>
using namespace std;
//解法一,排序
void Method1(float array[], int len, int K);