Array-3
Ref
/* Given a non-empty array, return true if there is a place to split the
* array so that the sum of the numbers on one side is equal to the sum of
* the numbers on the other side.
*/
public boolean canBalance(int[] nums) {
int first = 0;
int second = 0;
for(int i = 0; i < nums.length; i++)
second += nums[i];
for(int i = 0; i <= nums.length - 2; i++) {
first += nums[i];
second -= nums[i];
if(first == second)
return true;
}
return false;
}
/* Say that a "clump" in an array is a series of 2 or more adjacent elements
* of the same value. Return the number of clumps in the given array.
*/
public int countClumps(int[] nums) {
int count = 0;
int i = 0;
while(i < nums.length) {
int val = nums[i];
i++;
int length = 1;
while(i < nums.length && nums[i] == val) {
i++;
length++;
}
if(length > 1)
count++;
}
return count;
}
/* Return an array that contains exactly the same numbers as the given array,
* but rearranged so that every 3 is immediately followed by a 4. Do not move
* the 3's, but every other number may move. The array contains the same
* number of 3's and 4's, every 3 has a number after it that is not a 3 or 4,
* and a 3 appears in the array before any 4.
*/
public int[] fix34(int[] nums) {
int i = 0;
while(i < nums.length && nums[i] != 3)
i++;
int j = i + 1;
while(j < nums.length && nums[j] != 4)
j++;
while(i < nums.length) {
if(nums[i] == 3) {
int temp = nums[i+1];
nums[i+1] = nums[j];
nums[j] = temp;
while(j < nums.length && nums[j] != 4)
j++;
}
i++;
}
return nums;
}
/* Return an array that contains exactly the same numbers as the given array,
* but rearranged so that every 4 is immediately followed by a 5. Do not move
* the 4's, but every other number may move. The array contains the same
* number of 4's and 5's, and every 4 has a number after it that is not a 4.
* In this version, 5's may appear anywhere in the original array.
*/
public int[] fix45(int[] nums) {
int i = 0;
int j = 0;
while(j < nums.length && nums[j] != 5)
j++;
while(i < nums.length) {
if(nums[i] == 4) {
int temp = nums[i+1];
nums[i+1] = nums[j];
nums[j] = temp;
while((j < nums.length && nums[j] != 5) || j == i + 1)
j++;
}
i++;
}
return nums;
}
/* Given two arrays of ints sorted in increasing order, outer and inner,
* return true if all of the numbers in inner appear in outer. The best
* solution makes only a single "linear" pass of both arrays, taking
* advantage of the fact that both arrays are already in sorted order.
*/
public boolean linearIn(int[] outer, int[] inner) {
int i = 0;
int j = 0;
while(i < inner.length && j < outer.length) {
if(inner[i] > outer[j]) {
j++;
} else if(inner[i] < outer[j]) {
return false;
} else {
i++;
}
}
if(i != inner.length)
return false;
return true;
}
/* We'll say that a "mirror" section in an array is a group of contiguous
* elements such that somewhere in the array, the same group appears in
* reverse order. For example, the largest mirror section in
* {1, 2, 3, 8, 9, 3, 2, 1} is length 3 (the {1, 2, 3} part). Return the size
* of the largest mirror section found in the given array.
*/
public int maxMirror(int[] nums) {
int max = 0;
for(int i = 0; i < nums.length; i++) {
int count = 0;
for(int j = nums.length - 1; j >= 0 && i + count < nums.length; j--) {
if(nums[i + count] == nums[j]) {
count++;
} else {
max = Math.max(max, count);
count = 0;
}
}
max = Math.max(max, count);
}
return max;
}
/* Consider the leftmost and righmost appearances of some value in an array.
* We'll say that the "span" is the number of elements between the two
* inclusive. A single value has a span of 1. Returns the largest span found
* in the given array. (Efficiency is not a priority.)
*/
public int maxSpan(int[] nums) {
int max = 0;
for(int i = 0; i < nums.length; i++) {
int j = nums.length - 1;
while(nums[i] != nums[j])
j--;
int span = j - i + 1;
if(span > max)
max = span;
}
return max;
}
/* Given n>=0, create an array with the pattern
* {1, 1, 2, 1, 2, 3, ... 1, 2, 3 .. n} (spaces added to show the
* grouping).
*/
public int[] seriesUp(int n) {
int[] arr = new int[n*(n+1)/2];
int index = 0;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < i; j++) {
arr[index + j] = j + 1;
}
index += i;
}
return arr;
}
/* Given n>=0, create an array length n*n with the following pattern, shown
* here for n=3 : {0, 0, 1, 0, 2, 1, 3, 2, 1}
*/
public int[] squareUp(int n) {
int[] arr = new int[n*n];
if(n == 0)
return arr;
for(int i = n - 1; i < arr.length; i += n) {
for(int j = i; j >= i - i / n; j--)
arr[j] = i - j + 1;
}
return arr;
}
Last updated