Re: [閒聊] 每日leetcode
今天這題第一個想法是有bubble sort的既視感
不過想說應該有更快的方法
觀察後發現可以簡單的動態規劃一下
假設S[i]是 0在左邊 1在右邊 已經排好的字串
那根據下個讀到的字元是0還是1就可以計算新的S[i+1]所需要交換的次數
class Solution {
public:
long long minimumSteps(string s) {
long long one_num = 0;
long long sum = 0;
bool flag = false;
for (long long i = 0; i < s.length();i++) {
if (!flag && s[i] != '1') continue;
else {
if (s[i] == '1') {
flag = true;
one_num += 1;
}
else
sum += one_num;
}
}
return sum;
}
};
好像就這樣
--
https://i.imgur.com/7bQdjkb.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.135.214 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728975875.A.54B.html
推
10/15 15:06,
1年前
, 1F
10/15 15:06, 1F
→
10/15 15:08,
1年前
, 2F
10/15 15:08, 2F
推
10/15 15:34,
1年前
, 3F
10/15 15:34, 3F
討論串 (同標題文章)
完整討論串 (本文為第 989 之 1548 篇)：