Skip to content

Instantly share code, notes, and snippets.

@liyonghelpme
Created December 22, 2019 00:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save liyonghelpme/6ece488247822bd52a9c11250d9f53fc to your computer and use it in GitHub Desktop.
Save liyonghelpme/6ece488247822bd52a9c11250d9f53fc to your computer and use it in GitHub Desktop.
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