#
其實這個題目也很簡單 有很多種做法...
就是給一個array你 然后你找出 i,j使從第i個加到第j個最大就好了啊
最簡單的算法就是兩個for 算下來不到n^2的時間復雜度 可是還有更快的算法哦
首先 可以使用分治算法 這樣的算法大概時間復雜度是 n*lg n， 但是這樣還不是最好的
最好的其實是把前一個狀態儲存下來然后進行比較 這個算法時間復雜度只有n哦 很快的呢
先不要看 給個 int a[10] = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 }
求它的最大子串有多大哦
inline int
max( int a, int b)
{
return a > b ? a : b;
}
/*****************************************************************************
* This Function count a array find the largest string count max *
* Function : CountMax *
* int *a : the array of int *
* int n : the range of array *
* return : the sum of max this function find *
*****************************************************************************/
int
CountMax ( int *a, int n )
{
int sum = 0, tmp = 0;
for( int i = 0; i < n; i++ )
{
tmp = max( 0, tmp + a[i] );
sum = max( sum, tmp );
}
return sum;
}
/* ----- end of function CountMax ----- */
template<typename T>
void prefix(T* p, int m, int* next)
{
int i, j;
i = 0;
j = next[0] = -1;
while (i < m) {
while (j > -1 && p[i] != p[j])
j = next[j];
i++;
j++;
if (p[i] == p[j])
next[i] = next[j];
else
next[i] = j;
}
}
/* ---------- end of function prefix ---------- */
/*****************************************************************************
* Function : KMP *
* T *t : The string need be matching *
* int n : The length of the string *
* T *p : The sub string to matching *
* int m : The length of the p *
* int *out : An array mark the string match where ( max length is m - n ) *
*****************************************************************************/
template<typename T>
int KMP(T* t, int n, T* p, int m, int* out)
{
int c = 0;
int i, j, next[m];
prefix(p, m, next);
i = 0;
j = 0;
while(i < n)
{
while( j > -1 && p[j] != t[i])
j = next[j];
i++; j++;
if( j >= m )
{
out[c++] = i - m;
j = next[j];
}
}
return c;
}
/* ---------- end of function KMP ---------- */
// 這個算法 也研究了很久了。對于他的原理 我早已經清楚，但是快速的寫出他還是不是那么順利。也是因為我寫的程序太少了吧 呵呵。 理解中記憶。 嗯 不能死記硬背啊 呵呵。
#ifndef _BIGNUM_HPP_
#define _BIGNUM_HPP_
#include <vector>
#include <string>
#include <iostream>
using namespace std;
class BigNum;
BigNum operator+(const BigNum& lhs, const BigNum& rhs);
ostream& operator<<(ostream& os, const BigNum& rhs);
void Add(const BigNum& lhs, const BigNum& rhs, BigNum& res);
class BigNum
{
public:
BigNum(int n) : value(n){}
BigNum(const string& s);
friend BigNum operator+(const BigNum& lhs, const BigNum& rhs);
friend ostream& operator<<(ostream& os, const BigNum& rhs);
friend void Add(const BigNum& lhs, const BigNum& rhs, BigNum& res);
private:
vector<char> value;
};
#endif
#include "BigNum.hpp"
BigNum::BigNum(const string& s):value(s.length())
{
int j = value.size();
for(string::const_iterator it = s.begin(); it != s.end(); it++)
{
j--;
value[j] = *it;
}
}
ostream& operator<<(ostream& os, const BigNum& rhs)
{
size_t i = rhs.value.size();
bool zero = false;
if( i == 1)
return os << rhs.value[0];
if(rhs.value[ i - 1 ] == '0')
zero = true;
while( i > 0 )
{
i--;
while(zero == true)
{
i--;
if(rhs.value[i] != '0')
zero = false;
}
os << rhs.value[i];
}
return os;
}
void Add(const BigNum& lhs, const BigNum& rhs, BigNum& res)
{
int carry = 0;
char c = 0;
char tmp = 0;
size_t i = 0;
for( ; i < rhs.value.size(); i++)
{
tmp = lhs.value[i] + rhs.value[i] + carry - '0';
if( tmp > '9' )
{
carry = 1;
tmp -= 10;
}
else
{
carry = 0;
}
res.value[i] = tmp;
}
while( carry != 0 && i < lhs.value.size() )
{
tmp = lhs.value[i] + carry;
if( tmp > '9' )
{
carry = 1;
tmp = '0';
}
else
{
carry = 0;
}
res.value[i] = tmp;
i++;
}
if( carry > 0)
res.value[i] = '1';
}
BigNum operator+(const BigNum& lhs, const BigNum& rhs)
{
size_t lsize, rsize;
lsize = lhs.value.size();
rsize = rhs.value.size();
size_t n = lsize > rsize ? lsize : rsize;
BigNum res(n + 1);
res.value[0] = '0';
if( lsize > rsize )
{
Add(lhs, rhs, res);
}
else
{
Add(rhs, lhs, res);
}
return res;
}
//我自己實現的大數的加法的程序。。 終于驗證可以使用了 呵呵
這個程序寫好了 也算可以了了我的心愿了的
去年的某個時候 在杭州的UT斯達康面試 上機題就是這一道 我死活沒有憋出來，當時就很后悔 為什么不好好的看看論壇上的帖子 對上面的問題做做呢？那樣子的話 也許我就不會這么悲慘了，老是在哪里自怨自唉。
總結起來
我其實是眼高手低，然后從來都被寵著沒有認清過自己。小學初中，老媽老師都說我數學學的還不錯，其實是有點小聰明，分數還是那么可憐的一點點；到高中，因
為學校比較一般，考的名次看起來很美，被假象迷惑了；大學，因為自己有點基礎，被給哥封為軟件最好，也有點沾沾自喜；到了這個公司，也許因為我身體的原
因，也有點面試時做題速度超快的原因，被經理說我程序不錯，還是沒有擺正自己的位子。
受點挫折才好。嗯
呵呵， 心態 ， 心態才是一切。
不要眼高手低
// 給一個鏈表 list 將 list 倒置
// 有很多種做法
// 1 遞歸 (速度最慢)
// 2 用個棧 (速度慢)
// 3 三個指針遍歷 (大部分的做法)
//
// 具體就是一個 node*的數組 有三個元素
// 每次都將 a[1]的放入a[0] a[2]的放入a[1] a[2]->next放入a[2]
// 再將a[1]->next = a[0];
//
void resv_Linklist(Node* head)
{
Node* a[3];
a[0] = a[1] = NULL;
a[2] = head;
while(a[2]->next)
{
a[0] = a[1];
a[1] = a[2];
a[2] = a[2]->next;
a[1]->next = a[0];
}
*head = *(a[2]);
}
給一個數組 a[n] = {0, 1, 2, 3, 4, 5, 6} 一個k=3 // 將 a[n]變為 a[n] = {3, 4, 5, 6, 0, 1, 2}
// 給一個數組 a[n] = {0, 1, 2, 3, 4, 5, 6} 一個k=3
// 將 a[n]變為 a[n] = {3, 4, 5, 6, 0, 1, 2}
// 具體的算法是
// 先將 a[n] 變為{2, 1, 0, 6, 5, 4, 3}
// 再把 a[n] 逆轉了
void swap(int *a, int *b)
{
int t = *a;
*a = *b;
*b = t;
}
void resv(int* a, int start, int end)
{
end = end-1;
while(start < end)
{
swap(a+start, a+end);
start--, ed--;
}
}
void resver(int *a, int size, int k)
{
resv(a, 0, k);
resv(a, k, size);
resv(a, 0, size);
}
// 給一個數組a[n]求其中 第k大的數值的算法
// 基本的思想就是 使用quicksort的一個變種
// 每次進行完part后 判斷它的返回值 是否為k
// 如果為k 返回
// 如果大于k 則在返回的位置的前面找
// 如果小于k 則在返回的位置的后面找
int part(int* a, int start, int end)
{
int t = a[end-1];
int e = -2;
while(start < e)
{
while(a[start]<t) start++;
while(a[e]>t) e--;
int tmp = a[e];
a[e] = a[start];
a[start] = tmp;
}
return start;
}
int findK(int* a, int start, int end, int k)
{
int i = part(a, start, end);
int rtn;
if(i < k-1)
{
rtn = findK(a, i+1, end);
}
else if(i > k-1)
{
rtn = findK(a, start, i-1);
}
else
{
rtn = a[i];
}
return rtn;
}
#ifndef _LINKEDLIST_H_
#define _LINKEDLIST_H_
#include <stdexcept>
using namespace std;
class EmptyListException : public logic_error {
public:
EmptyListException(const string& what_arg ) throw() :
logic_error ("Empty list exception: " + what_arg) {}}
;
template <class T>
class Node {
private:
T data;
Node* next;
public:
Node(T d, Node* n = NULL) : data(d), next(n) {}
T& getData() { return data;}
Node*& getNext() { return next;}
};
template <class T>
class LinkedList {
protected:
Node<T>* head; // Beginning of list
Node<T>* tail; // End of list
int count; // Number of nodes in list
public:
LinkedList(void) : head(NULL), tail(NULL), count(0) {}
LinkedList(const LinkedList<T>& src); // Copy constructor
virtual ~LinkedList(void); // Destructor
virtual T& front(void) {
if (head == NULL) {
throw EmptyListException("front()");
}
return head->getData();
}
virtual T& back(void) {
if (tail == NULL) {
throw EmptyListException("back()");
}
return tail->getData();
}
virtual int size(void) {
return count;
}
virtual bool empty(void) {
return count == 0;
}
virtual void push_front(T); // Insert element at beginning
virtual void push_back(T); // Insert element at end
virtual void pop_front(void); // Remove element from beginning
virtual void pop_back(void); // Remove element from end
virtual void dump(void); // Output contents of list
};
// Copy constructor
template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& src) :
count(0), head(NULL), tail(NULL) {
Node<T>* current = src.head;
while (current != NULL) {
this->push_back(current->getData());
current = current->getNext();
}
}
// Destructor
template <class T>
LinkedList<T>::~LinkedList(void) {
while (!this->empty()) {
this->pop_front();
}
}
// Insert an element at the beginning
template <class T>
void LinkedList<T>::push_front(T d) {
Node<T>* new_head = new Node<T>(d, head);
if (this->empty()) {
head = tail = new_head;
}
else {
head = new_head;
}
count++;
}
// Insert an element at the end
template <class T>
void LinkedList<T>::push_back(T d) {
Node<T>* new_tail = new Node<T>(d, NULL);
if (this->empty()) {
head = new_tail;
}
else {
tail->getNext() = new_tail;
}
tail = new_tail;
count++;
}
// Remove an element from the beginning
template <class T>
void LinkedList<T>::pop_front(void) {
if (head == NULL) {
throw EmptyListException("pop_front()");
}
Node<T>* old_head = head;
if (this->size() == 1) {
head = NULL;
tail = NULL;
}
else {
head = head->getNext();
}
delete old_head;
count--;
}
// Remove an element from the end
template <class T>
void LinkedList<T>::pop_back(void) {
if (tail == NULL) {
throw EmptyListException("pop_back()");
}
Node<T>* old_tail = tail;
if (this->size() == 1) {
head = NULL;
tail = NULL;
}
else {
// Traverse the list
Node<T>* current = head;
while (current->getNext() != tail) {
current = current->getNext();
}
// Unlink and reposition
current->getNext() = NULL;
tail = current;
}
delete old_tail;
count--;
}
// Display the contents of the list
template <class T>
void LinkedList<T>::dump(void) {
cout << "(";
if (head != NULL) {
Node<T>* current = head;
while (current->getNext() != NULL) {
cout << current->getData() << ", ";
current = current->getNext();
}
cout << current->getData();
}
cout << ")" << endl;
}
#endif
#ifndef _ENHANCELINKLIST_H_
#define _ENHANCELINKLIST_H_
#include "LinkedList.h"
template<typename T>
class EnhancedLinkedList: public LinkedList<T>
{
public:
T& find_first (const T& key);
//Method find_first should search the EnhancedLinkedList for the first
//occurrence of an item that matches the value in the parameter key.
//It should return a reference to the first matching item.
//If the invoking EnhancedLinkedList object is empty or no item is found
//that matches the parameter, a ListItemNotFoundException should be thrown.
//You will have to define this exception
//(Hint: define this exception much the same way that the
//EmptyListException exception is defined in LinkedList.h).
EnhancedLinkedList find_all (const T& key);
//Method find_all should search the invoking EnhancedLinkedList
//for all elements that match the value in the parameter key.
//It should return an EnhancedLinkedList object containing
//copies of all the items that match the parameter key.
//If the invoking EnhancedLinkedList object is empty or
//no item is found that matches the parameter,
//this function should return an empty EnhancedLinkedList.
void remove_first (const T& key);
//Method remove_first should remove the first element from the
//invoking EnhancedLinkedList whose data item matches the parameter key.
//If the invoking EnhancedLinkedList object is empty or no item is found
//that matches the parameter, this function should do nothing.
//Remember to leave no memory leaks.
void remove_all (const T& key);
//Method remove_all should remove all elements from the invoking
//EnhancedLinkedList whose data items match the parameter key.
//If the invoking EnhancedLinkedList object is empty or no item is found
//that matches the parameter, this function should do nothing.
//Remember to leave no memory leaks.
};
template<typename T>
T& EnhancedLinkedList<T>::find_first(const T& key)
{
Node<T>* temp = this->head;
if(temp == NULL)
throw EmptyListException("Find first emptylist");
while(NULL != temp->getNext())
{
if(temp->getData()==key)
return temp->getData();
else
temp=temp->getNext();
}
throw EmptyListException("Find first not found");
}
template<typename T>
EnhancedLinkedList<T>
EnhancedLinkedList<T>::find_all(const T& key)
{
EnhancedLinkedList<T> resualt;
Node<T>* temp = this->head;
while(NULL != temp)
{
if(temp->getData()==key)
resualt.push_back(temp->getData());
temp=temp->getNext();
}
end:
return resualt;
}
template<typename T>
void
EnhancedLinkedList<T>::remove_first(const T& key)
{
EnhancedLinkedList<T> list;
while(NULL!=this->head)
{
if(this->head->getData()!=key)
list.push_front(this->head->getData());
else{
T* temp = this->front();
this->pop_front();
delete temp;
break;
}
this->pop_front();
}
while(list.head!=NULL)
{
this->push_front(list.front());
list.pop_front();
}
}
template<typename T>
void
EnhancedLinkedList<T>::remove_all(const T& key)
{
EnhancedLinkedList<T> list;
while(NULL!=this->head)
{
if(this->head->getData()!=key){
list.push_front(this->head->getData());
this->pop_front();
}
else{
T* temp = this->front();
this->pop_front();
delete temp;
}
}
while(list.head!=NULL)
{
this->push_front(list.front());
list.pop_front();
}
}
#endif //_ENHANCELINKLIST_H_
/////////////////////////////////////////////////////////////////////////////////
// The Sort //
// //
/////////////////////////////////////////////////////////////////////////////////
#ifndef _SORT_H_
#define _SORT_H_
/////////////////////////////////////////////////////////////////////////////////
// The QuickSort //
// //
/////////////////////////////////////////////////////////////////////////////////
template<typename T>
int Quick(T* a, int s, int e)
{
T t = a[e];
int i = s - 1;
for(int j = s; j < e; j++ )
if(a[j] <= t)
{
i++;
swap(a[j],a[i]);
}
swap(a[i+1], a[e]);
return i+1;
}
template<typename T>
void QuickSort(T* a, int s, int e)
{
if( s < e )
{
int i = Quick(a, s, e);
//int i = part(a, s, e);
QuickSort(a, s, i-1);
QuickSort(a, i+1, e);
}
}
/////////////////////////////////////////////////////////////////////////////////
// The HeapSort //
// //
/////////////////////////////////////////////////////////////////////////////////
inline int left(int i)
{
return 2*i+1;
}
inline int right(int i)
{
return 2*i+2;
}
template<typename T>
void HeapHy(T* a, int n, int i)
{
int big = i;
//first find the lage of i, left(i),right(i)
if(left(i) < n)
{
big = a[i]>a[left(i)]?(i):(left(i));
if(right(i) < n)
big = a[big]>a[right(i)]?(big):(right(i));
}
//and if the i not the biggest change pos i with the bigest
if(i!=big)
{
swap(a[i], a[big]);
//then HeapHy(a, n, bigest)
HeapHy(a, n, big);
}
}
template<typename T>
void BuildHeap(T* a, int n)
{
for(int i = n/2; i > -1; i--)
HeapHy(a, n, i);
}
template<typename T>
void HeapSort(T* a, int n)
{
BuildHeap(a, n);
for(int i=n-1; i>0; i--)
{
swap(a[0], a[i]);
HeapHy(a, i, 0);
}
}
/////////////////////////////////////////////////////////////////////////////////
// The ShellSort //
// //
/////////////////////////////////////////////////////////////////////////////////
template<typename T>
void ShellSort(T* a, int s)
{
T t;
int i,j,k;
for(i=s/2; i>0; i=i/3)
{
for(j=i; j<s; j++)
{
t = a[j];
for(k=j-i; k>-1; k-=i)
{
if(a[k]>t)
a[k+i] = a[k];
}
a[k+i] = t;
}
}
}
#endif //_SORT_H_