/** wenbin Reverse the list **/
/*
逆转单链表，没什么技巧，用3个指针即可
*/
#include <cstdio>
#define LL __int64
using namespace std;
/* .................................................................................................................................. */
const int M = 100100;
const int INF = 2139062143;
const int mod = 1000000007;
int __ = 0;
#define BIAOJI printf("yes%d
",++__);
class node
{
public:
int val;
node* next;
};
void PRINTLIST(node *root)
{
while(root)
{
printf("%d ",root->val);
root = root->next;
}
printf("
");
}
node *Reverse(node *root)
{
if( root == NULL )return NULL;
if( root->next== NULL )return root;
node *p1,*p2,*p3;
p1 = root;
p2 = p1->next;
p3 = p2->next;
p1->next = NULL;
while( p2 )
{
p3 = p2->next;
p2->next = p1;
p1 = p2;
p2 = p3;
}
return p1;
}
int main()
{
int a[6] = {4,5,6,7,8,9};
int n = 6;
node *root = new node();
node *p = root;
p->val = a[0];
p->next = NULL;
for(int i = 1; i < n; ++i)
{
p->next = new node();
p = p->next;
p->val = a[i];
p->next = NULL;
}
printf("initial list is :
");
PRINTLIST(root);
printf("
resverse list is :
");
PRINTLIST(Reverse(root));
return 0;
}
/** wenbin **/
/*
在m*n的矩阵中找M存在不
从左下角开始找，这样就有判断的方向了。。。面试过说了后才恍然大悟。。。这种技巧题真是。。。
回来要想想的是这种算法的正确性，一开始会怀疑这种算法正确性，但是模拟一下后发现还真是对的。。。
*/
#include <cstdio>
#define LL __int64
using namespace std;
/* .................................................................................................................................. */
const int M = 100100;
const int INF = 2139062143;
const int mod = 1000000007;
int __ = 0;
#define BIAOJI printf("yes%d
",++__);
int main()
{
int m = 5;
int n = 3;
int M = 8;
int a[5][3] = {{1 , 2 , 3 },
{4 , 5 , 6 },
{7 , 8 , 9 },
{10, 11, 12},
{13, 14, 15} };
printf("the matrix a is:
");
for( int i = 0; i < m; ++i )
{
for( int j = 0; j < n; ++j )
printf("%-3d",a[i][j]);
printf("
");
}
printf("
the M is:%3d
",M);
int i = m-1,j = 0;
while( i >= 0 && j < n )
{
if( a[i][j] == M )
{
printf("
find M! location is a[%d][%d]%3d
",i,j,M);
break;
}
else if( M < a[i][j] )i--;
else j++;
}
if( i < 0 || j >=n )printf("
not find the M %d
",M);
return 0;
}
/** wenbin **/
/*
已知a[i]
b[i] = a[0]*..*a[i-1]*a[i+1]*..*a[n-1]
不能用除法，求b[i]
这种脑经急转弯的题还真不会。。。我还是百度了才知道这个技巧。。。
*/
#include <cstdio>
#define LL __int64
using namespace std;
/* .................................................................................................................................. */
const int M = 100100;
const int INF = 2139062143;
const int mod = 1000000007;
int __ = 0;
#define BIAOJI printf("yes%d
",++__);
int main()
{
int a[10] = {1,2,3,4,5,6,7,8,9};
int b[10] = {0};
int n = 9;
printf("array a is :
");
for( int i = 0; i < n; ++i )printf("%d ",a[i]);
printf("
");
b[0]=1;
for( int i = 1; i < n; ++i )//b[n-1] will ok
b[i]=b[i-1]*a[i-1];
b[0]=1;
for( int i = n-1; i > 0; --i )//b[0] will ok
{
b[i]=b[i]*b[0];
b[0]*=a[i];
}
printf("
array b is :
");
for( int i = 0; i < n; ++i )printf("%d ",b[i]);
printf("
");
return 0;
}
/** wenbin **/
#include <cstdio>
#define LL __int64
using namespace std;
/* .................................................................................................................................. */
const int M = 100100;
const int INF = 2139062143;
const int mod = 1000000007;
int __ = 0;
#define BIAOJI printf("yes%d
",++__);
/* 最大连续子串和 经典dp吧
定义b[i]为包含a[i]的最大连续子串和
即b[i] = max(b[i-1]+a[i],a[i]);
那sum = max(b[i]);
由于求sum是遍历b[i]一遍，故可以将b[]优化为b降低空间复杂度
时间复杂度O(n) 空间复杂度O(1)
*/
int SUM1(int *a, int n)
{
int sum = 0 - INF;
int b = 0;
for( int i = 0; i < n; ++i)
{
if( b > 0 ) b += a[i];
else b = a[i];
if( sum < b ) sum = b;
}
return sum;
}
/*
这个dp以前没遇到过，但是貌似和连续的有类似的感觉。试着优化吧
最大非连续子串和
定义b[i]为包含a[i]的最大非连续子串和
即b[i] = max( b[j]+a[i], a[i] ) 0<=j<i-1
时间复杂度O(n^2) 空间复杂度O(n)
*/
int SUM2(int *a,int n)
{
int sum = 0 - INF;
int b[20] = {0};
for( int i = 0; i < n; ++i)
{
int k = 0 - INF;
for(int j = 0; j < i-1; ++j)
{
if( k < b[j] ) k = b[j];
}
if( i-2 >= 0 && k > 0) b[i] = k + a[i];
else b[i] = a[i];
if( sum < b[i] ) sum = b[i];
}
return sum;
}
/*
最大非连续子串和 优化一 去掉内存循环
定义b[i]为包含a[i]的最大非连续子串和
即b[i] = max( b[j]+a[i], a[i] ) 0<=j<i-1
时间复杂度O(n) 空间复杂度O(n)
*/
int SUM3(int *a,int n)
{
int sum = 0 - INF;
int b[20] = {0};
int k = 0 - INF;
for( int i = 0; i < n; ++i)
{
if( i-2 >= 0 && k < b[i-2] )k = b[i-2];
if( i-2 >= 0 && k > 0) b[i] = k + a[i];
else b[i] = a[i];
if( sum < b[i] ) sum = b[i];
}
return sum;
}
/*
最大非连续子串和 优化二 去掉内存循环，使用b[3]的循环数组优化空间
定义b[i]为包含a[i]的最大非连续子串和
即b[i] = max( b[j]+a[i], a[i] ) 0<=j<i-1
时间复杂度O(n) 空间复杂度O(1)
*/
int SUM4(int *a,int n)
{
int sum = 0 - INF;
int b[3] = {0};
int k = 0 - INF;
for( int i = 0; i < n; ++i)
{
if( i-2 >= 0 && k < b[(i-2+3)%3] )k = b[(i-2+3)%3];
if( i-2 >= 0 && k > 0) b[i%3] = k + a[i];
else b[i%3] = a[i];
if( sum < b[i%3] ) sum = b[i%3];
}
return sum;
}
int main()
{
int a[13] = {1,-2,3,-4,5,-3,7,8,-9,11,-6,7,12};
int n = 13;
printf("最大连续子串和为: %d
",SUM1(a,n));
printf("最大非连续子串和为: %d
",SUM2(a,n));
printf("优化一 最大非连续子串和为: %d
",SUM3(a,n));
printf("优化二 最大非连续子串和为: %d
",SUM4(a,n));
return 0;
}