小编Lui*_*igo的帖子

我试图解决Cormem的算法导论第3版(第405页)中的动态编程问题,该问题如下:

回文是一些字母表上的非空字符串,它向前和向后读取相同的字符串.回文的实例是长度为1的所有字符串,civic,racecar,和aibohphobia (回文的恐惧).

给出一个有效的算法来找到作为给定输入字符串的子序列的最长回文.例如,给定输入 character,您的算法应该返回carac.

好吧,我可以通过两种方式解决它:

第一解决方案

字符串的最长回文子序列(LPS)只是其自身及其反向的最长公共子序列.(我在解决了另一个要求序列的最长增加子序列的相关问题后构建了这个解决方案).由于它只是一个LCS变体,它还需要O(n²)时间和O(n²)存储器.

二解决方案:

第二个解决方案稍微详细一点,但也遵循一般的LCS模板.它来自以下重现:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

用于计算lps长度的伪代码如下:

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // …

我正在做一个小房子设计项目,其中一个最重要的部分是用户可以提供一些关于他如何想要他的房间的信息(例如,一个10 x 10米的房子,有一个3x3的起居室,一个3x3厨房,两个4 x 5卧室和一个4x2浴室),然后该程序根据所做的requeriments生成房子的地图.

现在,我并不担心绘制地图,只是以不重叠的方式安排房间(是的,输出可能非常难看).我已经做了一些搜索,发现我想要的东西与打包问题非常相似,它有一些算法可以很好地处理这个问题(尽管这是一个NP完全问题).

但后来又有了一个限制:用户可以指定房间之间的"链接",例如,他可能希望房间必须有一个"门"到浴室,客厅可以直接到厨房等(也就是说,房间必须并排放置,这就是事情变得复杂的地方.

我很确定我想要的是配置NP问题,所以我要求提供一些好的,但不一定是最佳实现的技巧.我的想法是使用图表来表示房间之间的关系,但我无法找到如何调整现有的打包算法以适应这个新的限制.谁能帮我？

今天我正在寻找当地信息学奥林匹克运动会的最新考试,我发现了一个有趣的问题.简而言之,它要求给定一个整数数组,计算它有多少个反转,其中反转是一对指标i,j例如i > j和A[i] < A[j].非正式地,反转的数量是无序的对的数量.最初我做了一个O(n²)解决方案(是的,天真的),但看到它不适合输入的大小,我想到了更多的问题,然后我意识到可以O(n log n)通过一个变体在一段时间内做到这一点合并排序,处理好输入的大小.

但是看到输入约束(n整数之间1 and M,没有重复),我想知道我的解决方案是否是最优的,或者你知道是否有任何其他解决方案来解决O(n log n)运行时问题？

我需要通过逻辑列过滤表(或者更确切地说,通过它的否定),但列的名称可能会有所不同.我事先知道他们的名字很容易:

tb = tibble(
  id = 1:4, 
  col1 = c(TRUE, TRUE, FALSE, FALSE), 
  col2 = c(TRUE, FALSE, TRUE, FALSE)
)

tb
## # A tibble: 4 x 3
##      id  col1  col2
##   <int> <lgl> <lgl>
## 1     1  TRUE  TRUE
## 2     2  TRUE FALSE
## 3     3 FALSE  TRUE
## 4     4 FALSE FALSE

colname = quo(col1)

tb %>% 
  filter(!!colname) # rows where col1 is true
## # A tibble: 2 x 3
##      id  col1  col2
## …

我正在使用Qt及其样式表开发GUI.在主窗口样式表上我放了以下样式:

QLineEdit:focus { border: 2px solid #006080; }

但是当我使用它时,风格并没有像我预期的那样真正改变.但是,如果我将相同的样式表直接放在所需的组件上,它就像魔术一样!但是,将样式表放在我可能想要的每个LineEdit上并不是一个好主意(这会大大增加添加新组件或更改样式表所需的工作量),也不会通过添加代码行来重新应用样式表setStyleSheet(styleSheet()).

有谁知道如何解决这个问题？