Toto je nová série, kde dokumentuji svůj boj s otázkami leetcode a doufám, že jakkoli malé publikum mi dá motivaci pokračovat.
Tato otázka mě trochu rozhodila, protože se má jednat o střední obtížnost a otázku DP. To ve skutečnosti není ani lol ...
Každopádně můj myšlenkový proces byl takový:
1.) naším cílem je pouze porovnat levé a pravé jedinečné číslo postavy
2.) můžeme použít sady pro udržení počtu jedinečných znaků
3.) To by ale nefungovalo pro pravou stranu, protože musíme počítat, kolik z každého, když dosáhne 0, odstraníme.
4.) takže použijeme mapu, abychom získali to nejlepší z obou světů.
5.) teď je to jen otázka rozdělení řetězce a iterace!
níže je skutečný kód:
var numSplits = function(s) {
const sSplit = s.split('');
const leftSet = new Set();
const rightMap = sSplit.reduce(function(map, letter){
map[letter] = map[letter] ? map[letter]+1 : 1;
return map;
},{});
let goodNum = 0;
sSplit.forEach(function(letter){
leftSet.add(letter);
rightMap[letter]--;
if(rightMap[letter] == 0) { delete rightMap[letter]; }
if(leftSet.size === Object.keys(rightMap).length) {
goodNum++;
}
});
return goodNum;
};
výkon je opravdu dobrý, protože je to jen O(n), zdá se, že v tom není žádný trik, protože několik příspěvků v diskusi je v podstatě stejných.
Po přečtení tohoto článku mi dejte vědět, co vás napadne, DÍKY!