哔哩哔哩-万诺 coding 城市旅游规划笔试题解析，涵盖滑动窗口、二分查找等算法

lq1995 发表于 2024-10-15 19:13:32

计算机科学领域，数组处理技能被视为根本且关键的技巧之一。本文旨在对数组内滑动窗口与二分搜索技术进行深入剖析，这两项技术在处理复杂数据结构问题时展现出卓越的效能。通过对这两种技术的原理、适用场合及编程实现进行详尽阐述，旨在助力读者深入理解和熟练掌握这些核心技巧。

滑动窗口的基本概念

<pre> <code class="prism language-python"># 输入处理
N, k = map(int, input().split(' '))
city_xy = dict()
for i in range(N):
x, y = map(int, input().split(' '))
city_xy[x] = y
# 对键进行排序
keys_sorted = sorted(city_xy.keys())
# 定义双指针
left = right = 0
happy_vals = 0
max_happy = 0
while right < len(keys_sorted):
happy_vals += city_xy[keys_sorted[right]]
# 两个城市之间的花费差值不小于k
# 左指针就要右移，同时要减去对应的开心值
if keys_sorted[right] - keys_sorted[left] >= k:
 happy_vals -= city_xy[keys_sorted[left]]
 left += 1
# 取当前较大的开心值
max_happy = max(max_happy, happy_vals)
right += 1
print(max_happy)
</code></pre>
滑动窗口技术是数组操作中的一种普遍应用手段，尤其擅长处理涉及连续子数组或子字符串的问题。其基本原理在于构建一个可移动的窗口，该窗口在数组中移动以高效解决相关任务。例如，在寻找特定和的连续子数组时，滑动窗口技术能有效降低计算复杂度。

<pre> <code class="prism language-python">N, M = map(int, input().split(' '))
room = list(map(int, input().split(' ')))
room.sort()
# 判断在当前间隔下，是否满足放下M条猪的情况
def check(mid):
pre = room[0]
count = 1
for i in range(1, len(room)):
 if pre + mid <= room[i]:
 count += 1
 pre = room[i]
return count >= M
# 二分查找间隔
maxGap = (room[-1] - room[0]) // (M - 1)
left, right = 0, maxGap
res = maxGap
while left <= right:
mid = (left + right) // 2
if check(mid):
 res = mid
 left = mid + 1
else:
 right = mid - 1
print(res)
</code></pre>
滑动窗口技术通常依赖两个关键指针，分别定位窗口的起始端和终结端。通过灵活调整这两个指针的位置，能够实现对窗口尺寸及位置的实时调整。此策略在处理大规模数据集时展现出卓越的效率，因为它有效减少了冗余的计算步骤。

二分查找的原理与应用

<pre> <code class="prism language-python">strInput = input()
# 为了避免初始化，attack和defender都扩充了一个元素
# attack扩充的是第一个元素
# defender扩充的是最后一个元素
attack = [0] * (len(strInput) + 1)
defender = [0] * (len(strInput) + 1)
# 从前往后遍历
for i in range(1, len(strInput)+1):
# 如果遇见0，则再前一个值的基础上加上当前下标
if strInput[i-1] == '0':
 attack[i] = attack[i-1] + i
else:
 attack[i] = attack[i-1]
# 从后往前遍历
for i in range(len(strInput)-1, -1, -1):
# 如果遇见1，则再前一个值得基础上加上前下标
if strInput[i] == '1':
 defender[i] = defender[i+1] + i+1
else:
 defender[i] = defender[i+1]
# 移除扩充元素
attack = attack[1:]
defender = defender[:-1]
res = float('inf')
for i in range(len(attack)):
res = min(res, abs(attack[i]-defender[i]))
print(res)
</code></pre>
二分搜索算法作为一种高效的信息检索技术，特别适用于对有序数组进行操作。其核心机制在于通过连续缩小查找区间的方式，迅速锁定目标数据。尽管这一算法在表面上看似直观易懂，但在具体问题解决中，它往往深藏于复杂问题的内部，需经过细致剖析方能准确把握并有效运用。

二分查找在编程实践中广泛用于处理查找插入点、定位峰值等任务，通过精心设计的算法，它能在对数时间复杂度内完成搜索，显著提升了程序的执行效能。

滑动窗口与二分查找的结合应用

在处理某些繁复问题时，滑动窗口技术与二分查找法可相辅相成，以实现更佳的解决策略。以动态调整的数组为例，往往需兼顾窗口的移动与元素的定位。运用此两种方法融合，可构建出既高效又适应性强的算法模型。

<pre> <code class="prism language-python">def demo(matrix):
# 最迟发生时间
ve = [0] * len(matrix)
que = [0] # 定义一个先进先出的队列
while que:
 index = que.pop(0) # 取出队列中第一个元素，即matrix中的第index行
 for i in range(len(matrix)): # 遍历matrix中的第index行
 if matrix[index][i]: # 如果当前matrix元素不为零
 # 判断从index到i的距离是否大于之前的距离
 ve[i] = max(ve[i], ve[index]+matrix[index][i])
 # 将i节点添加到队列中
 que.append(i)
print('ve={}'.format(ve))
# 最早发生时间
vl = [ve[-1]] * len(matrix)
for index in range(len(matrix)-1, -1, -1): # matrix从下往上遍历
 # 再从左往右遍历
 for i in range(len(matrix)):
 if matrix[index][i]: # 如果当前matrix元素不为零
 # 判断从i到index的距离是否小于之前的距离
 vl[index] = min(vl[index], vl[i]-matrix[index][i])
print('vl={}'.format(vl))
res = []
for i in range(len(ve)):
 if ve[i] == vl[i]:
 res.append("V" + str(i+1))
return res
matrix = [[0, 6, 4, 5, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 9, 7, 0],
 [0, 0, 0, 0, 0, 0, 0, 4, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 2],
 [0, 0, 0, 0, 0, 0, 0, 0, 4],
 [0, 0, 0, 0, 0, 0, 0, 0, 0]]
keyPoint = demo(matrix)
print('Key point: ' + ' '.join(keyPoint))
</code></pre>
确保该应用融合的核心要素是妥善协调窗口滑动与搜索区间的关系。常规做法是，对数组进行预处理，优化其适用于二分搜索，并在滑动窗口操作中灵活调整搜索策略。

<pre> <code class="prism language-python">def demo(matrix):
passed = [0]
nopass = [i for i in range(len(matrix)) if i != 0]
maxDis = matrix[0]
path = dict()
for i in range(len(maxDis)):
 if maxDis[i] != 0:
 path[i+1] = [1]
while nopass:
 index = nopass[0]
 for k in nopass:
 if maxDis[k] > maxDis[index]: index = k
 passed.append(index)
 nopass.remove(index)
 for k in nopass:
 if matrix[index][k] != 0:
 if maxDis[index] + matrix[index][k] > maxDis[k]:
 maxDis[k] = maxDis[index] + matrix[index][k]
 path[k+1] = path[index+1] + [index+1]
print('ve={}'.format(maxDis))
print('path(1->9): {}'.format(path[9]))
return maxDis
# ve=
# path(1->9): 
</code></pre>
代码实现与优化

在滑动窗口与二分查找算法中，代码的编写至关重要。对于程序员而言，掌握编写清晰、高效代码的能力是必备素养。针对滑动窗口，需特别注意边界条件的妥善处理及指针移动策略的合理运用；至于二分查找，必须保证每次搜索均能有效减少搜索区间。

<pre> <code class="prism language-python">def demo(matrix):
passed = [0] # 默认从第0个节点开始，以邻接矩阵的第0行为准
nopass = [i for i in range(len(matrix)) if i != 0]
minDis = matrix[0]
# 初始化起始路径
path = dict()
for i in range(len(minDis)):
 if minDis != float('inf'):
 path[i+1] = [1]
while nopass:
 # 取出nopass中在minDis中路径最小的节点
 index = nopass[0]
 for i in nopass:
 if minDis[i] < minDis[index]: index = i

 nopass.remove(index)
 passed.append(index)
 for i in nopass:
 if matrix[index][i] != float('inf'):
 if minDis[index] + matrix[index][i] < minDis[i]:
 minDis[i] = minDis[index] + matrix[index][i]
 path[i+1] = path[index+1] + [index+1]

print('minDis={}'.format(minDis))
print('path(1->6): {}'.format(path[6]))
return minDis
inf = float('inf')
matrix = [[0, 1, 12, inf, inf, inf],
 [inf, 0, 9, 3, inf, inf],
 [inf, inf, 0, inf, 5, inf],
 [inf, inf, 4, 0, 13, 15],
 [inf, inf, inf ,inf, 0, 4],
 [inf, inf, inf, inf ,inf, 0]]
keyPoint = demo(matrix)
# minDis=
# path(1->6): 
</code></pre>
代码的优化环节同样不容忽视。恰当运用数据结构与算法，可显著提升程序执行效率。以滑动窗口问题为例，运用双端队列可优化窗口内元素的管理；在二分查找过程中，通过预处理数组，可减少冗余的比较次数。

实际案例分析

为深入探究滑动窗口与二分查找技术的实践应用，我们可选取具体案例进行细致剖析。譬如，在股票交易平台中，常需运用滑动窗口技术对特定时段内的股价变动进行评估，并辅以二分查找法迅速锁定特定价位的相关交易数据。

这些案例表明，滑动窗口与二分查找算法不仅限于理论探讨，其在具体应用领域展现出显著的价值与重要性。

常见问题与解决方案

<pre> <code class="prism language-python">while True:
try:
 strInput = input()
 a, b = map(int, strInput.split('/'))
 res = []
 while a != 1 and b % a != 0:
 q = b // a + 1
 mod = b % a
 res.append('1/'+str(q))
 a -= mod
 b *= q
 if a == 1:
 res.append('1/'+str(b))
 else:
 res.append('1/'+str(b//a))
 print('+'.join(res))
except:
 break
</code></pre>
在具体操作过程中，滑动窗口与二分搜索算法常遭遇诸多难题，诸如边界条件处理失当、搜索区间设定错误等问题。针对此类问题，我们必须透彻掌握算法的基本原理，并在编码阶段进行详尽的测试与调试。

在处理滑动窗口时，务必关注窗口尺寸的适时调整，以维护算法的准确性与运行效率；至于二分查找，关键在于每次操作均需准确减少搜索区间，防止发生无限循环。

<pre> <code class="prism language-python">while True:
try:
 strInput = input()
 a, b = map(int, strInput.split('/'))
 res = []
 while True:
 if a == 1:
 res.append('1/'+str(b))
 break
 elif b % a == 0:
 res.append('1/'+str(b//a))
 break
 elif a == 3 and b % 2 == 0:
 res.append('1/'+str(b//2))
 res.append('1/'+str(b))
 break
 else:
 q = b // a + 1
 a -= b % a
 b *= q
 res.append('1/'+str(q))
 print('+'.join(res))
except:
 break
</code></pre>
总结与展望

<pre> <code class="prism language-python">def convert(a, b):
if a == 1:
 print('1/%d' % b)
elif b % a == 0:
 print('1/%d' % (b//a))
elif a == 3 and b % 2== 0:
 print('1/%d+1/%d' % (b//2, b))
else:
 q = b // a + 1
 print('1/%d' % q, end='+')
 a -= b % a
 b *= q
 convert(a, b)
while True:
try:
 strInput = input()
 a, b = map(int, strInput.split('/'))
 convert(a, b)
except:
 break
</code></pre>
滑动窗口与二分搜索构成处理数组问题的核心策略。对这两种方法进行深刻领悟与熟练运用，有助于我们在处理复杂数据结构时，实现更为自如与高效的应对。展望未来，伴随数据规模持续扩大与计算需求日益增长，这两种技术的战略地位将愈发显著。

针对编程实践，我们向公众提问：在处理复杂问题时，您是如何巧妙融合滑动窗口技术与二分查找算法的呢？热切期待您在评论区分享个人心得与观点，同时，请不要吝啬您的点赞与转发，以便让更多读者从中获益。

<pre> <code class="prism language-python">nums = list(map(int, input().split(' ')))
res = 0
for i in range(len(nums)):
for j in range(i):
 if nums[j] <= nums[i]:
 res += nums[j]
out = res % 1000000007
print(out)
</code></pre>

页: [1]

QQ前线乐园's Archiver

哔哩哔哩-万诺 coding 城市旅游规划笔试题解析，涵盖滑动窗口、二分查找等算法