免费下载时尚笔记A-Z# Fashion - 美丽时尚
S*2
1 楼
Given an array with length at least 1 and not more than 100. write a
function which returns total pair of (a, b) in the array. Any pair start
looping till they are equal. when a < b, a double itself. then b decrease
by a.
Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
Therefore,(1,4)
count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
a, b < 2^30 -1.
code总是TLE, 请问有效率的判断方法,谢谢!
下面是我的code总是超时
public class solution{
public static int solution(int[] arr) {
int len = arr.length;
int cnt = 0;
for (int i = 0; i < len-1; i++) {
for (int j = i+1; j < len; j++) {
if (isPairable(arr[i],arr[j])) cnt++;
}
}
return cnt;
}
private static boolean isPairable(int i, int j) {
if (i == j) return false;
if ((i+j)%2 == 1 || ((i+j)/2)%2 == 1) return true;
if (j < i) {i = i-j; j =j+i; i = j-i;}
Set set = new HashSet();
int mid,t;
mid = (i+j)/2;
t = mid/i;
if (mid%i == 0 && (t == (t & -t))) return false;
while (i < j) {
if (set.contains(i)) return true;
set.add(i);
j = j - i;
i = i+i;
if (i > j) {
i = i-j; j = j+i; i = j-i;
t = mid/i;
if (mid%i == 0 && (t == (t & -t))) return false;
}
}
return false;
}
}
function which returns total pair of (a, b) in the array. Any pair start
looping till they are equal. when a < b, a double itself. then b decrease
by a.
Vice versa. For example, 1,4 -> 2, 3 ->4, 1 -> 3, 2 -> 1, 4 and so on.
Therefore,(1,4)
count for a pair. 3,5 -> 6,2 -> 4,4, stop at 4== 4. so (3,5) is not a pair.
a, b < 2^30 -1.
code总是TLE, 请问有效率的判断方法,谢谢!
下面是我的code总是超时
public class solution{
public static int solution(int[] arr) {
int len = arr.length;
int cnt = 0;
for (int i = 0; i < len-1; i++) {
for (int j = i+1; j < len; j++) {
if (isPairable(arr[i],arr[j])) cnt++;
}
}
return cnt;
}
private static boolean isPairable(int i, int j) {
if (i == j) return false;
if ((i+j)%2 == 1 || ((i+j)/2)%2 == 1) return true;
if (j < i) {i = i-j; j =j+i; i = j-i;}
Set
int mid,t;
mid = (i+j)/2;
t = mid/i;
if (mid%i == 0 && (t == (t & -t))) return false;
while (i < j) {
if (set.contains(i)) return true;
set.add(i);
j = j - i;
i = i+i;
if (i > j) {
i = i-j; j = j+i; i = j-i;
t = mid/i;
if (mid%i == 0 && (t == (t & -t))) return false;
}
}
return false;
}
}