資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時裝研究
法律研究使用 JavaScript 尋找二進位制字串中的最小翻轉次數
單調遞增字串
一個只包含『0』和『1』的字串是單調遞增的，前提是它由一些（可能為 0）個『0』和一些（可能為 0）個『1』組成。
問題
我們需要編寫一個 JavaScript 函式，它以二進位制字串 str 作為第一個也是唯一的引數。
我們可以將字串中任何『0』翻轉為『1』或將任何『1』翻轉為『0』。我們的函式應該返回使 S 單調遞增所需的最小翻轉次數。
例如，如果輸入函式的內容為
輸入
const str = '00110';
輸出
const output = 1;
輸出說明
因為如果我們將最後一個『0』翻轉為『1』，剩下的字串就是『00111』。
示例
const str = '00110';
const countFlips = (str = '') => {
const map = {}
const helper = (index, prev) => {
map[index] = map[index] || {}
if (map[index][prev] !== undefined) {
return map[index][prev]
}
if (index >= str.length) {
return 0
}
if (prev === '0') {
if (str[index] === '0') {
map[index][prev] = Math.min(helper(index + 1, '0'), helper(index + 1, '1') + 1)
} else {
map[index][prev] = Math.min(helper(index + 1, '1'), helper(index + 1, '0') + 1)
}
} else if (str[index] === '0') {
map[index][prev] = helper(index + 1, '1') + 1
} else {
map[index][prev] = helper(index + 1, '1')
}
return map[index][prev]
}
return helper(0, '0')
};
console.log(countFlips(str));輸出
1
更新時間：2021-04-23
146 次瀏覽
廣告