|
|
楼主 |
发表于 2013-10-31 11:51
|
显示全部楼层
本帖最后由 lee1892 于 2013-10-31 12:03 编辑
参考解题：
首先考察最小字典顺序的查找逻辑：
1、比较前后两个字符（此后称左指针和右指针，左前右后）
初始：yzyx********************
2、左小则右向后移动继续比较（此处左要移到本次对比循环开始的位置）
左小：yzyx********************
3、左右相同则同时向后移继续比较
相同：yzyx********************
4、右小则左向后移动继续比较（新一轮的比较）
右小：yzyx********************
5、退出循环比较的机制则是：左到达末尾或是右转一圈追上左
于是就有下面这样的代码：
[code=vb]Function MinRot_1&(ByRef sStr$)
Dim nLen&, i&, iLetL%, iLetR%, nLeft&, nRight&, nRes&, bFlag As Boolean
nLen = Len(sStr)
For i = 1 To nLen
nLeft = i: nRight = i + 1: bFlag = False
Do
iLetL = Asc(Mid(sStr, nLeft, 1))
iLetR = Asc(Mid(sStr, (nRight - 1) Mod nLen + 1, 1))
If iLetL < iLetR Then
nRes = i: nLeft = i: nRight = nRight + 1
ElseIf iLetL = iLetR Then
nLeft = nLeft + 1: nRight = nRight + 1
Else
Exit Do
End If
If nLeft = nLen Then Exit Do
If (nRight - 1) Mod nLen + 1 = nLeft Then bFlag = True: Exit Do
Loop
If bFlag Then Exit For
Next
MinRot_1 = nRes - 1
End Function[/code]
上面这段代码对付基本随机的字符串是没什么大问题的，但如果字符大量重复，则会退化成 O(N^2) 的时间复杂度。为满足速度要求，势必要设计成 O(N) 的算法。
考察上述代码逻辑，其主要问题出现在左比右大的情况，此时会大步倒退到开始对比处的下一个（即执行Next i）重新开始对比。而实际上当前左指针左侧的字符已经都比较过了，完全可以从当前左指针的下一个开始下一轮对比，所以只需要在Exit Do 之前加一句 i=nLeft 即可大踏步的前进了。再重复一遍改进后的代码：
[code=vb]Function MinRot_2&(ByRef sStr$)
Dim nLen&, i&, iLetL%, iLetR%, nLeft&, nRight&, nRes&, bFlag As Boolean
nLen = Len(sStr)
For i = 1 To nLen
nLeft = i: nRight = i + 1: bFlag = False
Do
iLetL = Asc(Mid(sStr, nLeft, 1))
iLetR = Asc(Mid(sStr, (nRight - 1) Mod nLen + 1, 1))
If iLetL < iLetR Then
nRes = i: nLeft = i: nRight = nRight + 1
ElseIf iLetL = iLetR Then
nLeft = nLeft + 1: nRight = nRight + 1
Else
i = nLeft: Exit Do
End If
If nLeft = nLen Then Exit Do
If (nRight - 1) Mod nLen + 1 = nLeft Then bFlag = True: Exit Do
Loop
If bFlag Then Exit For
Next
MinRot_2 = nRes - 1
End Function[/code]
继续观察上述代码，可以发现外部的For循环其实并未起到什么太大的作用，仅仅是在给左指针赋初值。来作一下手术：
1、由于需要保留左指针的初始位置，不能在循环体内改变其值，引入偏移量变量，左右指针变量变为初始位置，比较的字符为左右指针加偏移量指向的字符。
2、循环的退出机制中，右指针转一圈追上左指针意味着偏移量等于字符串长度。
3、不再需要记录结果位置，因为左指针始终指向找到的最小字典顺序的第一个字符。
于是演变成如下代码：
[code=vb]Function MinRot_3&(ByRef sStr$)
Dim nLen&, i&, iLetL%, iLetR%, nLeft&, nRight& ', nRes&, bFlag As Boolean
Dim nOff&
nLen = Len(sStr)
'For i = 1 To nLen
nLeft = 1: nRight = 2 ': bFlag = False
nOff = 0
Do
iLetL = Asc(Mid(sStr, nLeft + nOff, 1))
iLetR = Asc(Mid(sStr, (nRight + nOff - 1) Mod nLen + 1, 1))
If iLetL < iLetR Then
'nRes = i: nLeft = i: nRight = nRight + 1
nRight = nRight + nOff + 1
nOff = 0
ElseIf iLetL = iLetR Then
'nLeft = nLeft + 1: nRight = nRight + 1
nOff = nOff + 1
Else
'i = nLeft: Exit Do
nLeft = nLeft + nOff + 1
nRight = nLeft + 1
nOff = 0
End If
k = k + 1
If nLeft + nOff = nLen Then Exit Do
'If (nRight - 1) Mod nLen + 1 = nLeft Then bFlag = True: Exit Do
If nOff = nLen Then Exit Do
Loop
'If bFlag Then Exit For
'Next
MinRot_3 = nLeft - 1 ' 左指针指向的即为最小字典顺序的第一个字符
End Function[/code]
如果再仔细考虑一下左大于右的时候，上述代码将左指针移到了当前对比左指针的后面一位，此时如果右指针的初始值在其右侧，那么就还可以向后移动至右指针（自行考虑一下原因）。
至此，算法优化完毕。再加一个加速技巧就是使用Byte数组以直接获得字符串的ASC码的数组，从而避免反复调用Mid函数。最终我准备的参考答案如下：
[code=vb]Function MinRot&(ByRef sStr$)
Dim t#
t = Timer
Dim aStr() As Byte, nLen&, nCurrent&, nOffset&, nLeft%, nRight%
aStr = sStr
nLen = Len(sStr)
MinRot = 0: nCurrent = 1: nOffset = 0
Do While nOffset < nLen And MinRot + nOffset + 1 < nLen
nLeft = aStr((MinRot + nOffset) * 2)
nRight = aStr(((nCurrent + nOffset) Mod nLen) * 2)
If nLeft = nRight Then
nOffset = nOffset + 1
ElseIf nLeft < nRight Then
nCurrent = nCurrent + nOffset + 1: nOffset = 0
Else
MinRot = MinRot + nOffset + 1
If nCurrent > MinRot Then MinRot = nCurrent
nCurrent = MinRot + 1: nOffset = 0
End If
Loop
Erase aStr
t = Timer - t
Debug.Print " ID: " & "Lee1892 - Byte Array"
Debug.Print "Answer is: " & MinRot
Debug.Print "Time used: " & Format(t, "0.000s")
End Function[/code]
最初准备的关于此题的一些参考：
[code=vb]'| ======================================================= |'
'| 最小旋转次数
'| By Lee1892 @ 2013.10.11
'| ------------------------------------------------------- |'
'| 算法逻辑：
'| 1、设置左、右两个指针，对应指向字符串左、右两个字
'| 符，供后续比较。初始设置为左指向第一个字符，右
'| 指向第二个字符。
'| 2、设置变量偏移量，初始值为 0，供后续循环使用。
'| 3、对比左指针+偏移量和右指针+偏移量指向的两个字符
'| 分为下述三种情况：
'| 3.1、如果两者相等，则偏移量右移一位，即当前比较的
'| 左右两指针加偏移量都向右移动一位；
'| 3.2、如果左指针+偏移量指向的字符较小，则右指针移动
'| 到当前比较字符右侧后面一位，偏移量设为 0，即
'| 当前比较左侧小，则右侧移到当前比较后一位；
'| 3.3、如果右指针+偏移量指向的字符较小，则左指针移动
'| 到当前比较字符右侧后面一位，偏移量设为0，参考
'| 3.2步的逻辑；此时对于右指针，如果此时左指针在
'| 右指针左侧，则将左指针移到右指针处。最后将右
'| 指针移到左指针后面一位，开始新一轮比较查找；
'| 4、退出循环3的机制：
'| 偏移量达到字符串长度 或
'| 左指针到达字符串末端
'| 5、退出循环后，左指针指向的为最小字符串的第一个字
'| 符，所以最小转动次数等于左指针-1
'| 参考代码 MinRotMid
'| ------------------------------------------------------- |'
'| 使用的技巧：
'| 1、MOD运算符计算指针超过字符串长度时对应原字符串的
'| 位置，或元素下标于数组中。
'| 1.1、对于以 0 开始计数，元素（或字符）个数为 n 个
'| 第 i 个（i > n）对应为 i MOD n
'| 1.2、对于以 1 开始计数，元素（或字符）个数为 n 个
'| 第 i 个（i > n）对应为 (i - 1) MOD n + 1
'| 2、使用 Byte 数组实现对字符串中字符的逐个操作，相
'| 较于 Mid 函数或语句而言，使用 Byte 数组的速度要
'| 快很多，4~5倍。其机制是直接复制字符串对应的内存
'| 块到数组的对应的内存块中，而后使用数组来循环操
'| 作，避免了大量的 Mid 函数或语句的寻址时间。
'| 2.1、数组取值，可直接采用 arrByte = strString
'| 2.2、同样的，改变了数组中的值后，可直接将其赋值给
'| 字符串，如 strString = arrByte
'| 2.3、Byte 数组每两个元素由前至后的对应字符串中的一
'| 个字符，两个元素中前者为低位ASC码后者为高位。
'| 2.4、如数组下标由 0 开始，则字符串中第 i 个字符对
'| 应于数组中的第 2 * (i - 1) 和 2 * i - 1 两个
'| 元素。
'| 2.5、对于“a”~“z”的26个字母而言，只需操作两元素中的
'| 前者，后者值为 0。
'| ======================================================= |'[/code] |
评分
-
1
查看全部评分
-
|
楼主: lee1892
[复制链接]
/1 
沪公网安备 31011702000001号 沪ICP备11019229号-2
发表于 2013-10-30 14:44
发表于 2013-11-7 20:12
