Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit60e34d1

Browse files
add 517
1 parente297dd0 commit60e34d1

File tree

2 files changed

+62
-0
lines changed

2 files changed

+62
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -110,6 +110,7 @@ Your ideas/fixes/algorithms are more than welcome!
110110
|522|[Longest Uncommon Subsequence II](https://leetcode.com/problems/longest-uncommon-subsequence-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_522.java)| O(x*n^2) (x is average length of strings)|O(1)| Medium|
111111
|521|[Longest Uncommon Subsequence I](https://leetcode.com/problems/longest-uncommon-subsequence-i/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_521.java)| O(max(x,y)) (x and y are length of strings)|O(1)| Easy|
112112
|520|[Detect Capital](https://leetcode.com/problems/detect-capital/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_520.java)| O(n)|O(1)| Easy|
113+
|517|[Super Washing Machines](https://leetcode.com/problems/super-washing-machines/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_517.java) | | | Hard| DP
113114
|516|[Longest Palindromic Subsequence](https://leetcode.com/problems/longest-palindromic-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_516.java) | O(n^2) |O(n^2) | Medium| DP
114115
|515|[Find Largest Value in Each Tree Row](https://leetcode.com/problems/find-largest-value-in-each-tree-row/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_515.java) | O(n) |O(k) | Medium| BFS
115116
|514|[Freedom Trail](https://leetcode.com/problems/freedom-trail/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_514.java) | O(?) |O(?) | Hard | DP
Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
packagecom.fishercoder.solutions;
2+
3+
/**
4+
* 517. Super Washing Machines
5+
*
6+
* You have n super washing machines on a line. Initially, each washing machine has some dresses or is empty.
7+
8+
For each move, you could choose any m (1 ? m ? n) washing machines, and pass one dress of each washing machine to one of its adjacent washing machines at the same time .
9+
10+
Given an integer array representing the number of dresses in each washing machine from left to right on the line, you should find the minimum number of moves to make all the washing machines have the same number of dresses. If it is not possible to do it, return -1.
11+
12+
Example1
13+
14+
Input: [1,0,5]
15+
16+
Output: 3
17+
18+
Explanation:
19+
1st move: 1 0 <-- 5 => 1 1 4
20+
2nd move: 1 <-- 1 <-- 4 => 2 1 3
21+
3rd move: 2 1 <-- 3 => 2 2 2
22+
Example2
23+
24+
Input: [0,3,0]
25+
26+
Output: 2
27+
28+
Explanation:
29+
1st move: 0 <-- 3 0 => 1 2 0
30+
2nd move: 1 2 --> 0 => 1 1 1
31+
Example3
32+
33+
Input: [0,2,0]
34+
35+
Output: -1
36+
37+
Explanation:
38+
It's impossible to make all the three washing machines have the same number of dresses.
39+
Note:
40+
The range of n is [1, 10000].
41+
The range of dresses number in a super washing machine is [0, 1e5].
42+
43+
*/
44+
publicclass_517 {
45+
/**Reference: https://discuss.leetcode.com/topic/79938/super-short-easy-java-o-n-solution*/
46+
publicintfindMinMoves(int[]machines) {
47+
inttotal =0;
48+
for(inti :machines) {
49+
total+=i;
50+
}
51+
if(total %machines.length !=0) {
52+
return -1;
53+
}
54+
intavg =total/machines.length,cnt =0,max =0;
55+
for(intload:machines){
56+
cnt +=load-avg;//load-avg is "gain/lose"
57+
max =Math.max(Math.max(max,Math.abs(cnt)),load-avg);
58+
}
59+
returnmax;
60+
}
61+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp