DSA 问题集第一章

发表于 更新于 分类于 阅读次数： 本文字数： 713 阅读时长 ≈ 3 分钟

邓俊辉数据结构第一章的问题集题选

DSA 问题集第一章

image-20260316142211595

failstone (3,5) 无限循环

image-20260316142830802

TM 转换函数 (q,c;d,L/R,p) 当前状态 q 且字符为此，则将当前字符改成的，转向 L/R，转入 p 状态

每次只能移动一步，直到进入 h 状态

image-20260316142957608

(<, 0; 1, L, <)

(<, 1; 0, L, <<)

(<<, #; #, R, >>)

(<<, 1; 1, R, > )

(<<, 0; 0, R, >)

(>>, 0; #, R, >)

(>, 1; 1, R, >)

(>, #; #, L, h)

image-20260316145115763

颠倒之后是从中间位置开始调换

没有区别，递归深度和 swap 次数依旧 n / 2

理论上不变，但是失去了尾递归优化可能。

image-20260316150321851 image-20260316150612572

从中间拆开看，左边右边的 GS 单独计算，跨线的 GS 用站在线上往左右探索就行，因为增加了过线的条件

1
2
3
4
5
6
7
8
9
10
11
12
13
/*DSA*/#include <algorithm>
/*DSA*/using namespace std;
/*DSA*/extern int s_lo, s_hi;
/*DSA*/
int gs_DC( int A[], int lo, int hi ) { //分治策略：O(n*logn)
   if ( hi - lo < 2 ) return A[lo];
   int mi = (lo + hi) / 2; int gsL = 0, gsR = 0; //前缀|后缀中的最大后缀|前缀
   for ( int s = 0, i = mi-1; lo <= i; i-- ) //枚举[lo,mi)的所有后缀
      gsL = max(gsL, s += A[i]); //择优更新
   for ( int s = 0, j = mi; j < hi; j++ ) //枚举[mi,hi)的所有前缀
      gsR = max(gsR, s += A[j]); //择优更新
   return max( gsL + gsR, max( gs_DC( A, lo, mi ), gs_DC( A, mi, hi ) ) ); //递归
} //gs_DC
image-20260316152321749

S [k,n)<0：任何以 n 为终点跨越 k 的序列不可能是 GS

S [k,n)>0：k 不可能是 GS 的终点，否则可以加上这段后缀变得更大

在 gs 可以被更新的时候更新一下左右区间，sum < 0 的时候改右边界，左边界随循环改变就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*DSA*/#include <algorithm>
/*DSA*/using namespace std;
/*DSA*/extern int s_lo, s_hi;
/*DSA*/
int gs_LS( int A[], int n ) { //减治策略：O(n)
   int gs = 0; //目前已知的最大和 = S[n,n) = 0
   /*DSA*/s_lo = n; s_hi = n;
   for ( int sum = 0, k = n-1; 0 <= k; k-- ) { //当前区间[k,n)
      sum += A[k]; //递增地更新后缀和
      /*DSA*/if ( gs < sum ) { s_lo = k; s_hi = n; }
      /*DSA*/if ( sum <= 0 ) { n = k; }
      gs = max( gs, sum ); //择优更新
      sum = max( sum, 0 ); //剪除总和非正的后缀
   } //for
   return gs;
} //gs_LS

image-20260316153608784

不变 nlogn

image-20260316154441441

对每个元素，记录从什么状态来的。保持不变。

Hirschberg 算法有线性空间复杂度。下辈子再学吧。