Notebook
  • Study hard and make progress every day
  • Mouka
    • Windows Internal
      • Helper Functions(todo:)
      • Find Kernel Module Address
      • Patch Guard Oops
      • Hook SSDT(Shadow)
      • Restore SSDT(Shadow)
      • Misc
        • Volatile in C
    • AntiCheat
      • Inject Defense
      • Injection Method
    • DriverDevelopment
      • 20180625
      • 20180626-27
    • Python
      • Python Tricks
        • 内置 http 服务器
        • 函数作为变量
        • "is" vs "=="
        • 直接变量值交换
        • 计算代码执行时间
        • 函数参数分解
        • 打印Python字典
        • 命名元组代替class
        • get()方法访问字典
        • 字典排序
        • 一次检查多个标志
        • 合并两个字典
        • re.sub使用替换函数
    • Algorithms
      • Greedy
        • 使括号平衡的最小交换次数
        • 埃及分数
      • DynamicProgramming
        • 0-1 背包问题
      • LeetCode
        • Count Primes
  • Honey
    • Python笔记
      • lxml库
      • os库
      • json文件读写
      • Scrapy
        • Scrapy安装与开始项目
        • Scrapy-Xpath
Powered by GitBook
On this page
  • 描述:
  • 输入:
  • 输出:
  • 举例:
  • 思路
  • 实现
  1. Mouka
  2. Algorithms
  3. Greedy

使括号平衡的最小交换次数

描述:

给定 2N 长度的字符串,包含N个 '[' ,N个 ']',计算使字符串平衡的最小交换次数

平衡字符串定义:S1[S2], 其中 S1,S2均为平衡字符串

输入:

2N长度字符串

输出:

最小交换次数

举例:

Input : []][][

Output : 2

First swap: Position 3 and 4 [][]][

Second swap: Position 5 and 6 [][][]

Input : [[][]]

Output : 0

String is already balanced.

Solution is below

思路

顺序遍历字符串,当遇到不匹配的']'时(遇到相应的'['之前),将其与之后最接近它的']'交换位置

实现

def MinSwapBracketBalancing(Brackets: list):
	# 首先遍历字符串,获取所有左括号的位置
	leftBrackets = []
	leftBrackets.extend([ idx for idx, x in enumerate(Brackets) if x == '['])

	if len(leftBrackets) != len(Brackets) // 2:	
		return 0

	count = 0	# 当前还未平衡的左括号数量
	pos = 0		# 下一个左括号的位置
	sum = 0		# 总共移动次数

	i = 0
	while i < len(Brackets):
		if Brackets[i] == '[':
			# 当前遍历括号为左括号
			count += 1
			pos += 1
		else:
			# 当前括号为右括号
			count -= 1	# 不平衡左括号 - 1
			if count < 0:
				# 右括号在不平衡左括号之前出现
				# 交换两括号位置
				Brackets[i], Brackets[leftBrackets[pos]] = Brackets[leftBrackets[pos]],Brackets[i]

				sum += leftBrackets[pos] - i
				count = 0
				pos += 1
				i += 1
		i += 1

	return sum
int MinSwapsBracketBalancing(string Brackets) {
	vector<int> leftBrackets;

	// Get positions of all left brackets
	for (auto i = 0;i<Brackets.size(); i++) {
		if (Brackets[i] == '[')
			leftBrackets.push_back(i);
	}

	auto count = 0;	// Current unbalanced left brackets
	auto pos = 0;	// Next position of next left brackets
	auto sum = 0;	// Total moves to balance brackets

	for (auto i = 0; i < Brackets.size(); i++) {
		if (Brackets[i] == '[') {
			count++;
			pos++;
		}
		else if (--count < 0) {
			// Get unbalanced right bracket
			// Swap it with next left bracket
			swap(Brackets[i], Brackets[leftBrackets[pos]]);
			sum += leftBrackets[pos] - i;
		}
	}

	return sum;

}
PreviousGreedyNext埃及分数

Last updated 6 years ago