Commite0422c5

zhenyu zhang

committed

update LeetCode 441、907

1 parentcc45c07 commite0422c5Copy full SHA for e0422c5

File tree

+114

-0

lines changed

+114

-0

lines changed

Lines changed: 61 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,61 @@`
	`1`	`+packagecom.hadley;`
	`2`	`+`
	`3`	`+/*`
	`4`	`+2020.07.01`
	`5`	`+441 Arranging Coins`
	`6`	`+You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.`
	`7`	`+`
	`8`	`+Given n, find the total number of full staircase rows that can be formed.`
	`9`	`+`
	`10`	`+n is a non-negative integer and fits within the range of a 32-bit signed integer.`
	`11`	`+`
	`12`	`+Example 1:`
	`13`	`+`
	`14`	`+n = 5`
	`15`	`+`
	`16`	`+The coins can form the following rows:`
	`17`	`+¤`
	`18`	`+¤ ¤`
	`19`	`+¤ ¤`
	`20`	`+`
	`21`	`+Because the 3rd row is incomplete, we return 2.`
	`22`	`+Example 2:`
	`23`	`+`
	`24`	`+n = 8`
	`25`	`+`
	`26`	`+The coins can form the following rows:`
	`27`	`+¤`
	`28`	`+¤ ¤`
	`29`	`+¤ ¤ ¤`
	`30`	`+¤ ¤`
	`31`	`+`
	`32`	`+Because the 4th row is incomplete, we return 3.`
	`33`	`+ */`
	`34`	`+`
	`35`	`+publicclass_441 {`
	`36`	`+`
	`37`	`+//first try: when MAX_VALUE, time exceed limit fix: temp from int to long`
	`38`	`+publicintarrangeCoins(intn) {`
	`39`	`+intres =0;`
	`40`	`+longtemp =0;`
	`41`	`+`
	`42`	`+if(n ==0){`
	`43`	`+return0;`
	`44`	`+ }`
	`45`	`+if(n ==1){`
	`46`	`+res ++;`
	`47`	`+temp +=res;`
	`48`	`+returnres;`
	`49`	`+ }`
	`50`	`+`
	`51`	`+while(temp <=n){`
	`52`	`+`
	`53`	`+res ++;`
	`54`	`+temp +=res;`
	`55`	`+ }`
	`56`	`+`
	`57`	`+returnres -1;`
	`58`	`+ }`
	`59`	`+`
	`60`	`+//another two solution: Binary Search + Pure Maths solution`
	`61`	`+}`

Lines changed: 53 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,53 @@`
	`1`	`+packagecom.hadley;`
	`2`	`+`
	`3`	`+/*`
	`4`	`+2020.07.01`
	`5`	`+746、Sum of Subarray Minimums`
	`6`	`+`
	`7`	`+Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.`
	`8`	`+`
	`9`	`+Since the answer may be large, return the answer modulo 10^9 + 7.`
	`10`	`+`
	`11`	`+Example 1:`
	`12`	`+`
	`13`	`+Input: [3,1,2,4]`
	`14`	`+Output: 17`
	`15`	`+Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].`
	`16`	`+Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.`
	`17`	`+ */`
	`18`	`+`
	`19`	`+publicclass_907 {`
	`20`	`+`
	`21`	`+`
	`22`	`+//time exceed limit`
	`23`	`+publicintsumSubarrayMins(int[]A) {`
	`24`	`+longres =0;`
	`25`	`+int[]temp =newint[A.length];`
	`26`	`+if(A.length ==0)return0;`
	`27`	`+if(A.length ==1){`
	`28`	`+temp[0] =A[0];`
	`29`	`+res =res +temp[0];`
	`30`	`+returntemp[0];`
	`31`	`+ }`
	`32`	`+`
	`33`	`+for(inti =0;i <A.length;i++){`
	`34`	`+//在temp中存 i + 1个数 temp[0..i-1] A[i]`
	`35`	`+for(intj =0;j <i;j ++){`
	`36`	`+temp[j] =Math.min(temp[j],A[i]);`
	`37`	`+res +=temp[j];`
	`38`	`+ }`
	`39`	`+temp[i] =A[i];`
	`40`	`+res +=temp[i];`
	`41`	`+if(res >Integer.MAX_VALUE){`
	`42`	`+res =res % (1000000007);`
	`43`	`+ }`
	`44`	`+System.out.println(res);`
	`45`	`+ }`
	`46`	`+`
	`47`	`+if(res >Integer.MAX_VALUE){`
	`48`	`+return (int)(res % (1000000007));`
	`49`	`+ }`
	`50`	`+return (int)res;`
	`51`	`+ }`
	`52`	`+`
	`53`	`+}`

Comments

(0)