Commit6fbf025

authored

Add files via upload

1 parent68afba7 commit6fbf025Copy full SHA for 6fbf025

File tree

+77

-0

lines changed

+77

-0

lines changed

Lines changed: 64 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,64 @@`
	`1`	`+// 根据题目说明，两者都是正数`
	`2`	`+// 基本思路是使用广度优先搜索，但是很明显的超时了`
	`3`	`+// 明显超时`
	`4`	`+`
	`5`	`+classSolution`
	`6`	`+{`
	`7`	`+public:`
	`8`	`+intbrokenCalc(int start,int end)`
	`9`	`+ {`
	`10`	`+if (start >= end)`
	`11`	`+ {`
	`12`	`+return start - end;`
	`13`	`+ }`
	`14`	`+`
	`15`	`+ queue<int> memo;`
	`16`	`+ memo.push(start);`
	`17`	`+`
	`18`	`+int layer =0;`
	`19`	`+while (!memo.empty())`
	`20`	`+ {`
	`21`	`+for (int i = memo.size(); i >0; --i)`
	`22`	`+ {`
	`23`	`+int temp = memo.front();`
	`24`	`+ memo.pop();`
	`25`	`+`
	`26`	`+if (temp == end)`
	`27`	`+ {`
	`28`	`+return layer;`
	`29`	`+ }`
	`30`	`+`
	`31`	`+if (temp >1) memo.push(temp -1);`
	`32`	`+if (temp < end) memo.push(temp *2);`
	`33`	`+ }`
	`34`	`+ ++layer;`
	`35`	`+ }`
	`36`	`+`
	`37`	`+return -1;`
	`38`	`+ }`
	`39`	`+};`
	`40`	`+`
	`41`	`+// 改成递归贪心`
	`42`	`+// Runtime: 0 ms, faster than 100.00% of C++ online submissions for Broken Calculator.`
	`43`	`+// Memory Usage: 8.2 MB, less than 80.00% of C++ online submissions for Broken Calculator.`
	`44`	`+`
	`45`	`+classSolution`
	`46`	`+{`
	`47`	`+public:`
	`48`	`+intbrokenCalc(int start,int end)`
	`49`	`+ {`
	`50`	`+if (start >= end)`
	`51`	`+ {`
	`52`	`+return start - end;`
	`53`	`+ }`
	`54`	`+`
	`55`	`+if (end %2 ==0)`
	`56`	`+ {`
	`57`	`+returnbrokenCalc(start, end /2) +1;`
	`58`	`+ }`
	`59`	`+else`
	`60`	`+ {`
	`61`	`+returnbrokenCalc(start, end +1) +1;`
	`62`	`+ }`
	`63`	`+ }`
	`64`	`+};`

Lines changed: 13 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,13 @@`
	`1`	`+# Runtime: 40 ms, faster than 27.06% of Python3 online submissions for Broken Calculator.`
	`2`	`+# Memory Usage: 14 MB, less than 50.00% of Python3 online submissions for Broken Calculator.`
	`3`	`+`
	`4`	`+classSolution:`
	`5`	`+defbrokenCalc(self,start:int,end:int)->int:`
	`6`	`+`
	`7`	`+ifstart>=end:`
	`8`	`+returnstart-end`
	`9`	`+`
	`10`	`+ifend%2is0:`
	`11`	`+returnself.brokenCalc(start,end//2)+1`
	`12`	`+else:`
	`13`	`+returnself.brokenCalc(start,end+1)+1`

Comments

(0)