- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我有一个字符串 s
包含不同类型的括号:()
和 []
。我怎样才能平衡这种类型的字符串与尽可能少的反转次数?我可以用任何其他支架替换任何支架。
例如:[)(]
的成本是 2,它变为 [()]
。[]((
的成本是1、变成了[]()
。[(])
不平衡。
一个更复杂的例子:)[)([)())]
可以在 4 个变化中变成 ([])[(())]
,但也可以分 3 步转为 [()(()())]
,这是使它平衡的最少修改次数。
我该如何解决这个问题?
最佳答案
我想到的第一个方法是 O(n^3)
动态规划。
让match(i, j)
是为了制作 s[i]
必须进行的替换次数和 s[j]
作为()
或 []
.所以match(i, j)
可以是 0
, 1
或 2
.
考虑 dp[i][j] = the minimum cost to balance the subsequence from i to j in your brackets array
.现在您将定义 dp[i][i + 1]
作为:
dp[i][i + 1] = match(i, i + 1)
现在一般规则是我们取 dp[i + 1][j - 1] + match(i, j)
之间的整体最小值和 min(dp[i][j], dp[i][p] + dp[p + 1][j])
对于任何 i < p < j
.显然,结果将保存在dp[1][n]
中。 .有一个 C++ 解决方案(我也会在大约 15 分钟内上传一个 python 程序,当我完成它时 - python 不是那么强大:P)。
#include <iostream>
#include <string>
using namespace std;
int dp[100][100];
string s;
int n;
int match(char a, char b) {
if (a == '(' && b == ')') {
return 0;
}
if (a == '[' && b == ']') {
return 0;
}
if ((a == ')' || a == ']') && (b == '(' || b == '[')) {
return 2;
}
return 1;
}
int main() {
cin >> s;
n = s.length();
s = " " + s;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
dp[i][j] = 0x3f3f3f3f;
}
}
for (int i = 1; i < n; ++i) {
dp[i][i + 1] = match(s[i], s[i + 1]);
}
for (int k = 3; k <= n; k += 2) {
for (int i = 1; i + k <= n; ++i) {
int j = i + k;
dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + match(s[i], s[j]));
for (int p = i + 1; p <= j; p += 2) {
dp[i][j] = min(dp[i][j], dp[i][p] + dp[p + 1][j]);
}
}
}
cout << dp[1][n] << '\n';
/*for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cout << dp[i][j] << ' ';
}
cout << '\n';
}*/
return 0;
}
编辑:
给你 Python :)
s = input()
n = len(s)
inf = 0x3f3f3f3f
def match(x, y):
if x == '(' and y == ')':
return 0
if x == '[' and y == ']':
return 0
if (x == ')' or x == ']') and (y == '(' or y == '['):
return 2
return 1
# dp[i][j] = min. cost for balancing a[i], a[i + 1], ..., a[j]
dp = [[inf for j in range(n)] for i in range(n)]
for i in range(n - 1):
dp[i][i + 1] = match(s[i], s[i + 1])
for k in range(3, n, 2):
i = 0
while i + k < n:
j = i + k
dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + match(s[i], s[j]))
for p in range(i + 1, j, 2):
dp[i][j] = min(dp[i][j], dp[i][p] + dp[p + 1][j])
i += 1
print(dp[0][n - 1])
#for i in range(n):
# for j in range(n):
# print(dp[i][j], end = ' ')
# print()
关于string - 翻转算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40504845/
如果您想使用 String.Concat() 连接 5 个或更多字符串,则它会使用 Concat(String[])。 为什么不一直使用 Concat(String[]) 而不再需要 Concat(S
今天在使用 String 时,我遇到了一种我以前不知道的行为。我无法理解内部发生的事情。 public String returnVal(){ return "5";
似乎在我所看到的任何地方,都有一些过时的版本,这些版本不再起作用。 我的问题似乎很简单。我有一个Java类,它映射到derby数据库。我正在使用注释,并且已经成功地在数据库中创建了所有其他表,但是在这
一、string::size_type() 在C++标准库类型 string ,在调用size函数求解string 对象时,返回值为size_type类型,一种类似于unsigned类型的int 数据
我正在尝试将数据保存到我的 plist 文件中,其中包含字符串数组的定义。我的plist - enter image description here 我将数据写入 plist 的代码是 -- let
我有一个带有键/值对的 JavaScript 对象,其中值是字符串数组: var errors = { "Message": ["Error #1", "Error #2"], "Em
例如,为了使用相同的函数迭代 List 和 List> ,我可以编写如下内容: import java.util.*; public class Test{ public static voi
第一个Dictionary就像 Dictionary ParentDict = new Dictionary(); ParentDict.Add("A_1", "1")
这是我的 jsp 文件: 我遇到了错误 The method replace(String, String, String) in the type Functions is not appl
我需要一些帮助。我有一个方法应该输出一个包含列表内容的 txt 文件(每行中的每个项目)。列表项是字符串数组。问题是,当我调用 string.Join 时,它返回文字字符串 "System.Strin
一位同事告诉我,使用以下方法: string url = "SomeURL"; string ext = "SomeExt"; string sub = "SomeSub"; string s
给定类: public class CategoryValuePair { String category; String value; } 还有一个方法: public
我正在尝试合并 Stream>>对象与所有 Streams 中的键一起映射到单个映射中. 例如, final Map someObject; final List>> list = someObjec
在这里使用 IDictionary 的值(value)是什么? 最佳答案 使用接口(interface)的值(value)始终相同:切换到另一个后端实现时,您不必更改客户端代码。 请考虑稍后分析您的代
我可以知道这两个字典声明之间的区别吗? var places = [String: String]() var places = [Dictionary()] 为什么当我尝试以这种方式附加声明时,只有
在 .NET 4.0 及更高版本中存在 string.IsNullOrWhiteSpace(string) 时,在检查字符串时使用 string.IsNullOrEmpty(string) 是否被视为
这个名字背后的原因是什么? SS64在 PowerShell 中解释此处的字符串如下: A here string is a single-quoted or double-quoted string
我打算离开 this 文章,尝试编写一个接受字符串和 &str 的函数,但我遇到了问题。我有以下功能: pub fn new(t_num: S) -> BigNum where S: Into {
我有一个结构为 [String: [String: String]] 的多维数组。我可以使用 for 循环到达 [String: String] 位,但我不知道如何访问主键(这个位 [String:
我正在尝试使用 sarama(管理员模式)创建主题。没有 ConfigEntries 工作正常。但我需要定义一些配置。 我设置了主题配置(这里发生了错误): tConfigs := map[s
我是一名优秀的程序员,十分优秀!