LeetCode #888 FairCandySwap. Algorithm,알고리즘,LeetCode,Codefights,CodeSignal,코드파이트,코드시그널,예제,그래프,Graph,example,c++,java,재귀,recursive,datastructure,techinterview,coding,코딩인터뷰,기술면접
Runtime: 1244 ms, faster than 5.02% of C++ online submissions for Fair Candy Swap.
Memory Usage: 12.3 MB, less than 80.00% of C++ online submissions for Fair Candy Swap.
최대개수 사탕 동적테이블 만들면 퍼포먼스/메모리 뒤집을 수 있을 듯함
I think it could be changed performance / memory if I use dynamic table of candies
LeetCode #888
Q.
Alice and Bob have candy bars of different sizes: A[i] is the size of the i-th bar of candy that Alice has, and B[j] is the size of the j-th bar of candy that Bob has.
Since they are friends, they would like to exchange one candy bar each so that after the exchange, they both have the same total amount of candy. (The total amount of candy a person has is the sum of the sizes of candy bars they have.)
Return an integer array ans where ans[0] is the size of the candy bar that Alice must exchange, and ans[1] is the size of the candy bar that Bob must exchange.
If there are multiple answers, you may return any one of them. It is guaranteed an answer exists.
앨리스와 밥은 각자 다른 개수의 캔디바들을 갖고 있다. A[i] 는 앨리스가 가지고 있는 캔디바의 i 번째 개수이고, B[j] 는 밥이 가지고 있는 캔디바의 j 번째 캔디바 개수이다.
그들은 친구이기 때문에, 캔디바 한개를 교환해서 둘이 갖고 있는 전체 캔디 개수를 맞추고 싶어한다.
정수배열 ans 를 반환하는데, ans[0] 은 앨리스가 바꿔야하는 캔디바의 사이즈이고, ans[1] 은 밥이 바꿔야하는 캔디바의 사이즈이다.
답이 여러개면, 그중 아무거나 1개만 리턴해라. 답은 무조건 있다고 보장한다.
Example 1:
Input: A = [1,1], B = [2,2]
Output: [1,2]
Example 2:
Input: A = [1,2], B = [2,3]
Output: [1,2]
Example 3:
Input: A = [2], B = [1,3]
Output: [2,3]
Example 4:
Input: A = [1,2,5], B = [2,4]
Output: [5,4]
Note:
- 1 <= A.length <= 10000
- 1 <= B.length <= 10000
- 1 <= A[i] <= 100000
- 1 <= B[i] <= 100000
- It is guaranteed that Alice and Bob have different total amounts of candy.
- It is guaranteed there exists an answer.
Process
// Process
//1. Input Alice's candies and Bob's candies
//2. Get total candy each and get fair amount of candy
//3. Find changingNumber
//4. Return change number
// 처리과정
//1. 앨리스와 밥의 캔디바 배열을 입력받는다.
//2. 각자의 전체 개수와 바뀌어야 하는 캔디수를 구해둔다.
//3. 각자의 바뀌게 되는 캔디바를 구한다.
//4. 결과 반환한다.
Code.. lemme see example code!!!
코드.. 예제코드를 보자!!!
class Solution {
public:
vector<int> fairCandySwap(vector<int>& A, vector<int>& B) {
vector<int> resultVector;
// 2.
int sumA = 0;
for (int i = 0; i < A.size(); ++i) {
sumA += A[i];
}
int sumB = 0;
for (int i = 0; i < B.size(); ++i) {
sumB += B[i];
}
// 3.
int fairDiff = abs(sumA - (sumA + sumB) / 2);
// 4.
bool isDone = false;
if (sumA > sumB) {
for (int i = 0; !isDone && i < A.size(); ++i) {
for (int j = 0; !isDone && j < B.size(); ++j) {
if (A[i] - B[j] == fairDiff) {
resultVector.push_back(A[i]);
resultVector.push_back(B[j]);
isDone = true;
}
}
}
} else {
for (int i = 0; !isDone && i < B.size(); ++i) {
for (int j = 0; !isDone && j < A.size(); ++j) {
if (B[i] - A[j] == fairDiff) {
resultVector.push_back(A[j]);
resultVector.push_back(B[i]);
isDone = true;
}
}
}
}
return resultVector;
}
};
Something else you might like...?
2019/02/19 - [Life/Health care] - Lysine 라이신 usage/side effects/dosage 효과/효능/부작용/성인,소아 용법, 복용법
2019/02/28 - [Life/Health care] - Vitamin K, 비타민 K usage/side effects/dosage 효능/부작용/성인,소아 용법