Created
December 22, 2019 00:08
-
-
Save liyonghelpme/6ece488247822bd52a9c11250d9f53fc to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
enum OpType { | |
None, | |
Remove, | |
Add, | |
Replace, | |
} | |
class MethodDetail { | |
method : OpType | |
num : number | |
} | |
enum ProblemT { | |
Less, | |
More, | |
Same, | |
MisUp, | |
MisLow, | |
MisNum | |
} | |
class SNode { | |
// start : number | |
len : number = 0 | |
// char : string | |
// solved : boolean = false | |
// removeNum : number = 0 | |
// addNum : number = 0 | |
// replaceNum : number = 0 | |
} | |
class ProblemDetail { | |
type : ProblemT | |
lessNum : number | |
moreNum : number | |
sameNode :SNode = null | |
solved : boolean = false | |
// needAddNum : number = 0 | |
} | |
function IsUpper(c : string){ | |
return c.toUpperCase() == c && c.toLowerCase() != c | |
} | |
function IsLower(c : string) { | |
return c.toLowerCase() == c && c.toUpperCase() != c | |
} | |
function IsNum( c : string) { | |
return !isNaN(Number(c)) | |
} | |
class StrP{ | |
password : string | |
problems : ProblemDetail[] = [] | |
//从操作角度分析 | |
//解决哪些问题 | |
//寻找所有问题 | |
//执行某个操作 问题解决了一部分 没有 解决所有问题 | |
//复杂在于 过多的if 判断逻辑 | |
//列出问题 | |
//Remove Add Replace 确定步骤解决方案 | |
//解决部分问题 确定问题的解决进度 | |
//接着进入下一个循环 | |
Check() { | |
this.CollectProblem() | |
return this.FixProblem() | |
} | |
CollectProblem(){ | |
if(this.password.length < 6){ | |
let p = new ProblemDetail(); | |
p.type = ProblemT.Less | |
p.lessNum = 6-this.password.length | |
this.problems.push(p) | |
} | |
if(this.password.length > 20) { | |
let p = new ProblemDetail() | |
p.type = ProblemT.More | |
p.moreNum = this.password.length-20 | |
this.problems.push(p) | |
} | |
let misUp = true | |
for(let i = 0; i < this.password.length;i++){ | |
let pc = this.password[i] | |
// if(pc == pc.toUpperCase()){ | |
if(IsUpper(pc)) { | |
misUp = false | |
break | |
} | |
} | |
if(misUp){ | |
var p = new ProblemDetail() | |
p.type = ProblemT.MisUp | |
this.problems.push(p) | |
} | |
let mislow = true | |
for(let i = 0; i < this.password.length;i++){ | |
let pc = this.password[i] | |
// if(pc == pc.toLowerCase()){ | |
if(IsLower(pc)) { | |
mislow = false | |
break | |
} | |
} | |
if(mislow){ | |
var p = new ProblemDetail() | |
p.type = ProblemT.MisLow | |
this.problems.push(p) | |
} | |
let misNum = true | |
for(let i = 0; i < this.password.length;i++){ | |
let pc = this.password[i] | |
// if(!isNaN(Number(pc))) | |
if(IsNum(pc)) | |
{ | |
misNum = false | |
break | |
} | |
} | |
if(misNum){ | |
let p = new ProblemDetail() | |
p.type = ProblemT.MisNum | |
this.problems.push(p) | |
} | |
let curChar : string = null | |
let newNode = new SNode() | |
// newNode.start = 0 | |
newNode.len = 0 | |
// newNode.char = curChar | |
for(let i = 0; i < this.password.length; i++) | |
{ | |
let pc = this.password[i] | |
if(pc != curChar) | |
{ | |
if(newNode.len > 1) { | |
// this.sameNodes.push(newNode) | |
let p = new ProblemDetail() | |
p.type = ProblemT.Same | |
p.sameNode = newNode | |
newNode = new SNode() | |
// newNode.start = i | |
newNode.len = 1 | |
// newNode.char = pc | |
this.problems.push(p) | |
}else { | |
// newNode.start = i | |
newNode.len = 1 | |
// newNode.char = pc | |
} | |
curChar = pc | |
} | |
else { | |
newNode.len++; | |
} | |
} | |
if(newNode.len > 1) { | |
let p = new ProblemDetail() | |
p.type = ProblemT.Same | |
p.sameNode = newNode | |
this.problems.push(p) | |
} | |
} | |
//每个问题有最优解 如果满足这个最优解的话则使用对应的解法来解决问题 | |
AddSolve() { | |
let addOpNumber = 0 | |
let toHanderProblem : ProblemDetail[] = [] | |
for(let i = 0; i < this.problems.length; i++){ | |
let p = this.problems[i] | |
if(!p.solved){ | |
switch(p.type) { | |
case ProblemT.Less: | |
case ProblemT.MisLow: | |
case ProblemT.MisNum: | |
case ProblemT.MisUp: | |
case ProblemT.Same: | |
toHanderProblem.push(p) | |
break | |
} | |
} | |
} | |
//列出所有可以当前通过Add解决的问题 | |
//对问题排序列出最优解是Add的问题 | |
if(toHanderProblem.length > 0) { | |
//Add最多能解决多少问题 | |
//Add 需要的数量 | |
let addMaxNum = 0 | |
toHanderProblem.forEach(element => { | |
switch(element.type){ | |
case ProblemT.Less: | |
addMaxNum = element.lessNum; | |
element.solved = true | |
break; | |
} | |
}); | |
addOpNumber = addMaxNum | |
let missProblems : ProblemDetail[] = [] | |
toHanderProblem.forEach(element => { | |
switch(element.type){ | |
case ProblemT.MisLow: | |
case ProblemT.MisNum: | |
case ProblemT.MisUp: | |
missProblems.push(element) | |
break | |
} | |
}) | |
//解决部分Miss问题 | |
let minAddMis = Math.min(missProblems.length, addMaxNum) | |
for(let i = 0; i < minAddMis; i++){ | |
missProblems[i].solved = true | |
} | |
//剩下的MissProble在Replace的时候处理 | |
let allSameProblem : ProblemDetail[] = [] | |
let totalAddNum = 0 | |
toHanderProblem.forEach(element => { | |
switch(element.type){ | |
case ProblemT.Same: | |
let addNum = Math.floor((element.sameNode.len-1)/2) | |
totalAddNum += addNum | |
allSameProblem.push(element) | |
// let repNum = Math.floor(element.sameNode.len/3) | |
// //len > 3 add消耗更多元素 | |
// if(repNum < addNum) { | |
// } | |
// if(addMaxNum >= addNum){ | |
// element.solved = true | |
// addMaxNum -= addNum | |
// }else { // | |
// } | |
break | |
} | |
}) | |
//差值小优先处理 | |
allSameProblem.sort((a, b)=>{ | |
let len = a.sameNode.len | |
let an = Math.floor((len-1)/2) | |
let rn = Math.floor(len/3) | |
let delta1 = an - rn | |
let len2 = b.sameNode.len | |
let an2 = Math.floor((len2-1)/2) | |
let rn2 = Math.floor(len2/3) | |
let delta2 = an2-rn2 | |
return delta1-delta2 | |
}) | |
//add此处无法结局所有Same问题 | |
if(totalAddNum > addMaxNum) { | |
let leftAdd = totalAddNum-addMaxNum | |
let curAdd = addMaxNum | |
//按照AddNum - RepNum 差最小的排序 | |
for(let i = 0; i < allSameProblem.length; i++){ | |
let p = allSameProblem[i] | |
let len = p.sameNode.len | |
let an = Math.floor((len-1)/2) | |
if(curAdd >= an) { | |
p.solved = true | |
curAdd -= an | |
}else { | |
p.sameNode.len -= curAdd * 2 //部分解决问题 | |
break | |
} | |
} | |
}else {//小于等于 addMaxNum | |
addMaxNum -= totalAddNum | |
//解决了所有same问题 再额外Add解决Less问题 | |
allSameProblem.forEach(element => { | |
element.solved = true | |
}); | |
} | |
} | |
return addOpNumber | |
} | |
//移除解决问题 | |
RemoveSolve() { | |
let rmOpNum = 0 | |
// let toHanderProblem : ProblemDetail[] = [] | |
let allSameProblem : ProblemDetail[] = [] | |
let rmMaxNum = 0 | |
for(let i = 0; i < this.problems.length; i++){ | |
let p = this.problems[i] | |
if(!p.solved){ | |
switch(p.type) { | |
case ProblemT.More: | |
rmMaxNum = p.moreNum | |
p.solved = true | |
break | |
case ProblemT.Same: | |
// toHanderProblem.push(p) | |
allSameProblem.push(p) | |
break | |
} | |
} | |
} | |
rmOpNum = rmMaxNum | |
let totalRmNum = 0 | |
allSameProblem.forEach(element=>{ | |
let rmN = element.sameNode.len-2 | |
totalRmNum += rmN | |
}) | |
//RMNum 和 ReplaceNum 差值最小的排序 | |
//余0 和 余1的优先处理 | |
// allSameProblem.sort((a, b)=>{ | |
// let len1 = a.sameNode.len | |
// // let rn1 = len1-2 | |
// // let rpN1 = Math.floor(len1/3) | |
// // let delta1 = rn1 - rpN1 | |
// let len2 = b.sameNode.len | |
// // let rn2 = len2 - 2 | |
// // let rpN2 = Math.floor(len2/3) | |
// // let delta2 = rn2 - rpN2 | |
// let m1 = len1 % 3 | |
// let m2 = len2 % 3 | |
// // return delta1 - delta2 | |
// return m1 - m2 | |
// }) | |
//先解决mod = 0 mod = 1 然后再处理mod == 2 的元素 | |
let mod0 : ProblemDetail[] = [] | |
let mod1 : ProblemDetail[] = [] | |
let mod2 : ProblemDetail[] = [] | |
//最后再mod2 按照长度排序 | |
//所有same问题解决 | |
if(totalRmNum <= rmMaxNum) { | |
allSameProblem.forEach(element => { | |
element.solved = true | |
}); | |
}else { //rm解决前面的问题 | |
allSameProblem.forEach(element => { | |
let len = element.sameNode.len | |
let mod = len % 3 | |
if(mod == 0) mod0.push(element) | |
if(mod == 1) mod1.push(element) | |
if(mod == 2) mod2.push(element) | |
}); | |
let curRmNum = rmMaxNum | |
for(let i = 0; i < mod0.length; i++){ | |
let p = mod0[i] | |
if(curRmNum > 0) { | |
p.sameNode.len-- | |
curRmNum-- | |
if(p.sameNode.len < 3) p.solved = true | |
// else mod2.push(p) | |
}else { | |
break | |
} | |
} | |
for(let i = 0; i < mod1.length; i++){ | |
let p = mod1[i] | |
if(curRmNum >= 2) { | |
curRmNum -= 2 | |
p.sameNode.len -= 2 | |
if(p.sameNode.len < 3) p.solved = true | |
// else mod2.push(p) | |
}else { | |
break | |
} | |
} | |
//剩余 mod0 mod1 mod2 问题解决 | |
// let curRmNum = rmMaxNum | |
for(let i = 0; i < allSameProblem.length; i++){ | |
let p = allSameProblem[i] | |
if(!p.solved) { | |
let rn = p.sameNode.len-2 | |
if(rn <= curRmNum){ | |
curRmNum -= rn | |
p.solved = true | |
}else { | |
p.sameNode.len -= curRmNum //部分解决问题 | |
break | |
} | |
} | |
} | |
} | |
return rmOpNum | |
} | |
ReplaceSolve() { | |
let repOpNum = 0 | |
let allMiss : ProblemDetail[] = [] | |
let allSame : ProblemDetail[] = [] | |
for(let i = 0; i < this.problems.length; i++){ | |
let p = this.problems[i] | |
if(!p.solved){ | |
p.solved = true | |
switch(p.type) { | |
case ProblemT.MisLow: | |
case ProblemT.MisNum: | |
case ProblemT.MisUp: | |
allMiss.push(p) | |
break | |
case ProblemT.Same: | |
allSame.push(p) | |
break | |
} | |
} | |
} | |
let totalRepNum = 0 | |
allSame.forEach(element=>{ | |
let n = Math.floor(element.sameNode.len/3) | |
totalRepNum += n | |
}) | |
let totalMisNum = allMiss.length | |
return Math.max(totalRepNum, totalMisNum) | |
} | |
SolveUse(method : OpType){ | |
let ret = 0 | |
//寻找删除的数量 解决相关问题 | |
if(method == OpType.Add) { | |
ret = this.AddSolve() | |
} | |
if(method == OpType.Remove){ | |
ret = this.RemoveSolve() | |
} | |
if(method == OpType.Replace){ | |
ret = this.ReplaceSolve() | |
} | |
return ret | |
} | |
FixProblem(){ | |
let solveNum = 0 | |
while(true) { | |
let method = OpType.None | |
for(let i = 0; i < this.problems.length; i++){ | |
let p = this.problems[i] | |
if(!p.solved){ | |
switch(p.type){ | |
case ProblemT.Less: { | |
method = OpType.Add | |
break | |
} | |
case ProblemT.More: { | |
method = OpType.Remove; | |
break | |
} | |
case ProblemT.MisLow: | |
case ProblemT.MisNum: | |
case ProblemT.MisUp: | |
case ProblemT.Same: { | |
method = OpType.Replace | |
break | |
} | |
default: { | |
method = OpType.None | |
break | |
} | |
} | |
} | |
if(method != OpType.None) break | |
} | |
// console.log("Method", method, this.problems.length) | |
//寻找当前解决问题的方法 | |
if(method != OpType.None){ | |
let rn = this.SolveUse(method) | |
solveNum += rn | |
// console.log("SolveNum", rn, solveNum, this.problems.length) | |
// console.log(this.problems) | |
// break | |
}else { | |
break | |
} | |
} | |
return solveNum | |
} | |
} | |
var password = "aaabbbbcccdddeeeffffff" | |
var password = "aA123456" | |
var password = "ABABABABABABABABABAB1" | |
var password = "111111111111111111111" | |
var password = "AAAAAABBBBBB123456789a" | |
var password = "1234567890123456Baaaa" | |
let sp = new StrP() | |
sp.password = password | |
let n = sp.Check() | |
console.log(n) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment