seek
BAN USERint MaxSum(const vector<int>& v, int& start, int& end)
{
int max = v[0];
int sum = v[0];
int j;
start = 0;
end = 0;
for (int i = 1; i < v.size(); ++i)
{
if (sum > 0) {
sum += v[i];
} else {
sum = v[i];
j = i;
}
if (sum > max) {
max = sum;
end = i;
start = j;
}
}
return max;
}
string Replace(const string& input)
{
string ret = "";
bool in_word = false;
for (int i = 0; i < input.size(); ++i) {
if (!in_word && input[i] != ' ') {
in_word = true;
ret += '(';
ret += input[i];
} else if (in_word && input[i] == ' ') {
ret += ')';
in_word = false;
} else if (in_word && input[i] != ' ') {
ret += input[i];
}
}
if (in_word) {
ret += ')';
}
return ret;
}
}
- seek January 23, 2012#include <deque>
#include <iostream>
using namespace std;
void PrintLevel(TreeNode* root)
{
if (root == NULL)
return;
deque<TreeNode*> q;
q.push_back(root);
while (!q.empty()) {
int n = q.size();
while (n != 0) {
TreeNode* p = q.front();
q.pop_front();
cout << p->data << " ";
if (p->left)
q.push_back(p->left);
if (p->right)
q.push_back(p->right);
--n;
}
cout << endl;
}
}
#ifndef SINGLETON_HPP
#define SINGLETON_HPP
#ifdef __GNUC__
#define HAS_THREAD_SAFE_STATICS 1
#endif
#if defined _MSC_VER
#include <intrin.h>
inline void MemoryWriteBarrier() { _WriteBarrier(); }
#elif __GNUC__
#if defined __i386__ || defined __x86_64__
inline void MemoryWriteBarrier() { __asm__ __volatile__("sfence" ::: "memory");
}
#else
#endif
#ifdef HAS_THREAD_SAFE_STATICS
template <class T>
class SingletonBase
{
private:
SingletonBase(const SingletonBase&);
void operator=(const SingletonBase&);
protected:
SingletonBase() {}
~SingletonBase() {}
public:
static T& Instance()
{
static T instance;
return instance;
}
};
#else
template <typename T>
class SingletonBase
{
private:
SingletonBase(const SingletonBase&);
void operator=(const SingletonBase&);
protected:
SingletonBase() {}
~SingletonBase() {}
public:
static T& Instance()
{
if (!m_instance)
{
ScopedLocker<Mutex> lock(m_lock);
if (!m_instance)
{
T* p = new T();
MemoryWriteBarrier();
m_instance = p;
atexit(Destroy);
}
}
return *m_instance;
}
private:
static void Destroy()
{
if (m_instance)
{
delete m_instance;
m_instance = NULL;
}
}
private:
static Mutex m_lock;
static T* volatile m_instance;
};
template <typename T>
Mutex SingletonBase<T>::m_lock;
template <typename T>
T* volatile SingletonBase<T>::m_instance;
#endif // HAS_THREAD_SAFE_STATICS
template <typename T>
class Singleton : public SingletonBase<T>
{
};
#endif // SINGLETON_HPP
string KeyStrokeParser(const string& keys) throw(std::runtime_error)
{
static const string mappings[] = {
"", "ABC2", "DEF3", "GHI4", "JKL5", "MON6", "PQRS7", "TUV8", "WXYZ9" };
size_t len = keys.size();
string ret = "";
char first_char = '1';
char curr_char;
bool need_recalc = false;
int rott_index = 0;
for (size_t i = 0; i < len; ++i) {
if ((keys[i] <= '1' || keys[i] > '9')
&& (keys[i] != '*') && (keys[i] != '#')) {
throw std::runtime_error("parser error");
}
curr_char = keys[i];
if (first_char != curr_char) {
first_char = curr_char;
need_recalc = true;
rott_index = -1;
} else {
need_recalc = false;
}
if (curr_char == '#') {
first_char = curr_char;
need_recalc = true;
rott_index = -1;
} else if (curr_char == '*') {
ret += " ";
} else {
int map_index = curr_char - '0' - 1;
++rott_index;
if (need_recalc) {
ret += mappings[map_index][0];
} else {
ret[ret.size() - 1] = mappings[map_index][rott_index % mappings[map_index].size()];
}
}
}
return ret;
}
time complexity is O(n), classical dynamic programming problem
- seek January 23, 2012