编程面试题

17 Mar 2025 | 58 分钟阅读

仅仅了解 Java 的理论知识是不够的，无法通过面试。对于想成为 Java 开发人员的人来说，最重要的环节之一是编程环节，在此环节中，面试官会要求应聘者进行编码。编写优化代码是成为 Java 开发人员的必备条件。在本教程中，我们将讨论一些高级编程面试题。

1) 给定一个大小为 s 的整数数组 arr。现在，检查是否存在至少一个元素，该元素严格小于其右侧的所有元素，并且大于其左侧的所有元素。如果存在，则返回 true；否则，返回 false。忽略给定数组的边界元素。

示例：1

arr[] = {3, 4, 5, 1, 6, 10, 9, 7, 8}; s = 9

答案: true

解释: 6 之前的所有数字都小于 6，而 6 之后的所有元素都大于 6。因此，答案是 true。

示例：2

arr[] = {4, 5, 1}; s = 3

答案: false

解释: 没有一个数字符合给定的条件。因此，答案是 false。

文件名: PeakElement.java

// import statement
import java. util. Arrays;

public class PeakElement
{
boolean isPeak(int a[], int s)
{
boolean []l = new boolean[s];
boolean []r = new boolean[s];

int max = a[0];
l[0] = false;

// a loop to find those elements 
// that are greater than elements that are left of it
for (int j = 1; j < s; j++) 
{
if (a[j] > max) 
{
max = a[j];
l[j] = true;
} 
else 
{
l[j] = false;
}
}
int min = a[s - 1];
r[s - 1] = false;
for (int j = s - 2; j >= 0; j--) 
{

if (a[j] < min) 
{
r[j] = true;
min = a[j];
} 
else 
{
r[j] = false;
}
}

// a loop to find those elements 
// that are greater than elements that are right of it
for (int j = 0; j < s; j++) 
{
if (l[j] && r[j]) 
{
return true;
}
}
return false;
}
// main method
public static void main(String argvs[])
{
// creating an object of the class PeakElement
PeakElement obj = new PeakElement();

// input array 1
int arr[] = { 10, 2, 3, 4, 5, 4, 3, 2, 3, 10 };
int size = arr.length;

if(obj.isPeak(arr, size))
{
System.out.println("The array " + Arrays.toString(arr) + " has got a peak element.");
}
else
{
System.out.println("The array " + Arrays.toString(arr) + " has not got a peak element."); 
}

// input array 2
int arr1[] = {3, 4, 5, 1, 6, 10, 9, 7, 8}; 
size = arr1.length;

if(obj.isPeak(arr1, size))
{
System.out.println("The array " + Arrays.toString(arr1) + " has got a peak element.");
}
else
{
System.out.println("The array " + Arrays.toString(arr1) + " has not got a peak element."); 
}
}
}

输出

The array [10, 2, 3, 4, 5, 4, 3, 2, 3, 10] has not got a peak element.
The array [3, 4, 5, 1, 6, 10, 9, 7, 8] has got a peak element.

2) 给定一个只读数组 arr，大小为 s，使得数组中的每个元素都不超过 s。此外，在数组中，除了 a1 以外，每个元素都只出现一次，a1 出现了两次，因此 a2 丢失了。找出 a1 和 a2 的值。注意，只读意味着不允许修改输入数组。

示例：1

arr[] = {1, 3, 5, 2, 3}; s = 5

答案: a1 = 3, a2 = 4

解释: 重复的数字是 3，丢失的数字是 4。

示例：2

arr[] = {1, 2, 1}; s = 3

答案: a1 = 1, a2 = 3

解释: 重复的数字是 1，丢失的数字是 3。

文件名: MissingAndRepeatingElement.java

// import statement
import java. util. Arrays;

public class MissingAndRepeatingElement
{
void findEle(int a[], int s)
{

// finding sum of n natural numbers (n * (n + 1)) / 2
long nsum = (s * (s + 1)) / 2;

// finding sum of square of n natural numbers (n * (n + 1) * (2 * n + 1)) / 6
long nsqrsum = (nsum * ( 2 * s + 1)) / 3;


long sqrsum = 0, sum = 0;

for(int i = 0; i < s; i++)
{
// find sum of elements present in the array
sum = sum + a[i];

// finding sum of square of elements presenet in the array
sqrsum = sqrsum + ((long) a[i] * a[i]);
}

// finding a1^2 - a2^2
long sqrdiff = sqrsum - nsqrsum;

// finding a1 - a2
long diff = sum - nsum;

// finding a1 + a2 using mathematical identity
// a1^2 - a2^2 = (a1 + a2)(a1 - a2)
sum = sqrdiff/diff;

// finding a1 using a1 + a2 and a1 - a2
long a1 = (sum + diff)/2;

// finding y
long a2 = sum - a1;

System.out.println("For array: " + Arrays.toString(a) + "\n");
System.out.println("a1 is: " + a1);
System.out.println("a2 is: " + a2);

return;
}

public static void main(String argvs[])
{
// creating an object of the class MissingAndRepeatingElement
MissingAndRepeatingElement obj = new MissingAndRepeatingElement();

int arr[] = {1, 3, 5, 4, 1};
int size = arr.length;

obj.findEle(arr, size);

int arr1[] = {1, 3, 5, 2, 3};
size = arr1.length;

System.out.println();
obj.findEle(arr1, size);

}
}

输出

For array: [1, 3, 5, 4, 1]

a1 is: 1
a2 is: 2

For array: [1, 3, 5, 2, 3]

a1 is: 3
a2 is: 4

3) 给定一个只读数组 arr，大小为 s。找出可以将数组 arr 分成 3 个部分的方法，使得每个部分的总和相等。

示例：1

arr[] = {0, 1, -1, 0}; s = 4

答 1

解释: 只有一种方法可以将数组分成三个总和相等的部份。{0}, {1, -1}, {0}

示例 2

arr[] = {2, 2, 4, 0, 4}; s = 5

答 2

解释: 有两种方法可以将数组分成三个总和相等的部份。

{2, 2}, {4, 0}, {4}

{2, 2}, {4}, {0, 4}

文件名: ParititionArray.java

// import statement
import java. util. Arrays;

public class PartitionArray
{
// A method that returns the number of ways
// the array arr can be partitioned into 3 parts
// such that sum of each part is equal
int countWays(int arr[], int size)
{

int pre[] = new int[size + 1];
pre[0] = 0;;
for (int j = 0; j < size; j++) 
{
// Creating a prefix array for retrieving the sum in O(1)
pre[j + 1] = pre[j] + arr[j]; 
}

int ans = 0;
  
// Sum of all the elements of the array must be divisible 
// by 3; otherwise, it is not possible to partition the array
if(pre[size] % 3 == 0) 
{
// partition happen at two points at 1 / 3 and 2 / 3
int u = pre[size] / 3;
int v = 2 * pre[size] / 3;   
// Count for first partition
int count = 0;                  
for (int j = 1; j < size; j++) 
{
if (pre[j] == v)
{
// If the sum is of 2 partitions, then add the count to answer
ans = ans + count; 
}

if (pre[j] == u)
{
 // If sum is of 1 partition then increase the count by 1
count = count + 1; 
}
}
}
return ans;   
}
public static void main(String argvs[])
{
// creating an object of the class PartitionArray
PartitionArray obj = new PartitionArray();

int arr[] = {2, 2, 4, 0, 4};
int size = arr.length;

int ways = obj.countWays(arr, size);


System.out.println("For array: " + Arrays.toString(arr));
System.out.println("The number of ways to it partition is: " + ways + "\n");

int arr1[] = {-1, 1, 0, 0, -1, 1};
size = arr1.length;

ways = obj.countWays(arr1, size);

System.out.println("For array: " + Arrays.toString(arr1));
System.out.println("The number of ways to it partition is: " + ways + "\n");


int arr2[] = {4, 6, 8, 9, -13, 9};
size = arr2.length;

ways = obj.countWays(arr2, size);

System.out.println("For array: " + Arrays.toString(arr2));
System.out.println("The number of ways to it partition is: " + ways);

}
}

输出

For array: [2, 2, 4, 0, 4]
The number of ways to it partition is: 2

For array: [-1, 1, 0, 0, -1, 1]
The number of ways to it partition is: 3

For array: [4, 6, 8, 9, -13, 9]
The number of ways to it partition is: 0

4) 给定一个由 N 个整数 X1, X2, X3, ...., Xn 组成的数组 arr。你必须返回 f(a1, a2) 的最大值，其中 0 ≤ a1, a2, < N。给定 f(a1, a2) = |arr[a1] - a[a2]| + |a1 - a2|，其中 |y| 表示 y 的绝对值。

示例：1

arr[] = {1, -1, 3};

答 5

说明

f(0, 0) = f(1, 1) = f(2, 2) = 0

f(0, 1) = f(1, 0) = 3

f(0, 2) = f(2, 0) = 4

f(1, 2) = f(2, 1) = 5

我们看到最大值是 5。因此，答案是 5。

示例：2

arr[] = {2, -1, -1, 3};

答 6

说明

f(0, 0) = f(1, 1) = f(2, 2) = f(3, 3) = 0

f(0, 1) = f(1, 0) = 4

f(0, 2) = f(2, 0) = 5

f(0, 3) = f(3, 0) = 4

f(1, 2) = f(2, 1) = 1

f(1, 3) = f(3, 1) = 6

f(2, 3) = f(3, 2) = 5

我们看到最大值是 6。因此，答案是 6。

文件名: AbsoluteValue.java

// import statement
import java. util. Arrays;

public class AbsoulteValue
{
public int maxVal(int arr[], int s)
{
int max1 = Integer.MIN_VALUE;
int max2 = Integer.MIN_VALUE;
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;

// loop for finding the maximum and minimum value of
// arr[i] + i and arr[i] - i
for(int i  = 0; i < s; i++)
{
max1 = Math.max(max1, arr[i] + i);
min1 = Math.min(min1, arr[i] + i);
min2 = Math.min(min2, arr[i] - i);
max2 = Math.max(max2, arr[i] - i);

}

// finding the maximum between
// max(arr[i] + i) - min(arr[i] + i) &
// max(arr[i] - i) - min(arr[i] - i)
int ans = Math.max(max1 - min1, max2 - min2);
return ans;
}

// main method
public static void main(String argvs[])
{
// creating an object of the class AbsoulteValue
AbsoulteValue obj = new AbsoulteValue();
int arr[] ={1, 3, -1};
int size = arr.length;

int ans = obj.maxVal(arr, size);

System.out.print("The maximum absolute value of the array: " + Arrays.toString(arr));
System.out.println(" is " + ans + "\n");

int arr1[] = {3, 4, 5, 9, 12};

size = arr1.length;

ans = obj.maxVal(arr1, size);

System.out.print("The maximum absolute value of the array: " + Arrays.toString(arr1));
System.out.println(" is " + ans + "\n");

int arr2[] = {13, -4, 5, -12};

size = arr2.length;

ans = obj.maxVal(arr2, size);

System.out.print("The maximum absolute value of the array: " + Arrays.toString(arr2));
System.out.println(" is " + ans + "\n");

int arr3[] = {-1, 2, 9, -7};

size = arr3.length;

ans = obj.maxVal(arr3, size);

System.out.print("The maximum absolute value of the array: " + Arrays.toString(arr3));
System.out.println(" is " + ans + "\n");

}
}

输出

The maximum absolute value of the array: [1, 3, -1] is 5

The maximum absolute value of the array: [3, 4, 5, 9, 12] is 13

The maximum absolute value of the array: [13, -4, 5, -12] is 28

The maximum absolute value of the array: [-1, 2, 9, -7] is 17

5) 找到由数组 arr 的元素组成的数字的下一个排列，大小为 s，而不改变元素的顺序。

示例：1

arr[] = {3, 1, 2}; s = 3;

答 321

解释: 使用数组元素组成的数字是 312。数字 312 的下一个排列是 321。

示例：2

arr[] = {1, 2, 3};

答 132

解释: 使用数组元素组成的数字是 123。数字 123 的下一个排列是 132。

文件名: NextPermutation.java

// import statement
import java.util.Arrays;

public class NextPermutation
{
// reversing the array from the position pos
public void reverse(int array[], int pos)
{
int size = array.length;

for(int i = pos, j = size - 1; i <= j; i++, j--)
{
// swap elements
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}


//  a method that finds next permutation using the array elements
public int[] nextPermutation(int arr[], int s)
{
if(s == 1) 
{
return arr;
}
int i;
for(i = s - 2; i >= 0; i--)
{
if(arr[i] < arr[i + 1])
break;
}
// if the whole array is sorted in the ascending order
// then the next permutation is reverse of the array arr
if(i < 0)
{
// reverse the complete array
reverse(arr, 0);

return arr;
}
int j;
for(j = s - 1; j > i; j--)
{
if(arr[j] > arr[i])
{
break;
}
}

// swap elements
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

// reverse from position i + 1
reverse(arr, i + 1);

return arr;

}

// generating number from the array elements
int findNo(int arr[], int size)
{
    int ans = 0;
    for(int i = 0; i < size; i++)
    {
        ans = arr[i] + (ans * 10);
    }
    
    return ans;
}

// main method
public static void main(String argvs[])
{
// creating an object of the class NextPermutation
NextPermutation obj = new NextPermutation();

// input array - 1
int arr[] ={1, 2, 3};
int size = arr.length;

int orginialNo = obj.findNo(arr, size);

int ans[] = obj.nextPermutation(arr, size);

int permutedNo = obj.findNo(ans, size);

System.out.println("The next permutation of " + orginialNo + " is " + permutedNo);

// input array - 2
int arr1[] ={1, 4, 3, 2};
size = arr1.length;

orginialNo = obj.findNo(arr1, size);

int ans1[] = obj.nextPermutation(arr1, size);

permutedNo = obj.findNo(ans1, size);

System.out.println("The next permutation of " + orginialNo + " is " + permutedNo);

// input array - 3
int arr2[] ={1, 3, 7, 9, 4};
size = arr2.length;

orginialNo = obj.findNo(arr2, size);

int ans2[] = obj.nextPermutation(arr2, size);

permutedNo = obj.findNo(ans2, size);

System.out.println("The next permutation of " + orginialNo + " is " + permutedNo);

}
}

输出

The next permutation of 123 is 132
The next permutation of 1432 is 2134
The next permutation of 13794 is 13947

6) 给定一个数组 arr，其中只包含非负数。使用给定数组 arr 中的所有非负数创建最大的数字。

示例：1

arr[] = {35, 1, 9};

答 9351

解释: 9 是最大的数字位，所以它将放在最前面。之后，数字 3 大于数字 1。因此，35 放在 1 之前。

示例：2

arr[] = {17, 22, 83, 7, 5};

答 83752217

解释: 8 是给定数组中最大的数字。因此，83 放在最前面。其他数字也进行相同的处理。

文件名: LargestNoExample.java

// import statement
import java.util.*;

public class LargestNoExample 
{

public String largestNumber(int a[], int size) 
{

String[] arr = new String[size];
for (int i = 0; i < size; i++) 
{
arr[i] = String.valueOf(a[i]);
}


Arrays.sort(arr, new Comparator<String>()
{
public int compare(String a, String b)
{
    // the biggest digit has to be put first
    return (b + a).compareTo(a + b);
}
});


StringBuilder sb = new StringBuilder();
for(String s: arr)
{
sb.append(s);
}

// if 0 is present is at the 
// first index, then it means all the
// number present at the other index are also zero
if(sb.charAt(0) == '0')
{    
//check if all zeroes are there
return String.valueOf(0);
}

return sb.toString();   
}
    
    
// main method
public static void main(String argvs[])
{
    
// creating an object of the class LargestNoExample
LargestNoExample obj = new LargestNoExample();

// input array - 1
int arr[] = {17, 22, 83, 7, 5};
int size = arr.length;

String str = obj.largestNumber(arr, size);

System.out.println("The largest number formed from the array: " + Arrays.toString(arr) + " is " + str);


// input array - 2
int arr1[] = {79, 21, 83, 7, 58};
size = arr1.length;

str = obj.largestNumber(arr1, size);

System.out.println("The largest number formed from the array: " + Arrays.toString(arr1) + " is " + str);


// input array - 2
int arr2[] = {0, 9, 99, 79, 87, 158};
size = arr2.length;

str = obj.largestNumber(arr2, size);

System.out.println("The largest number formed from the array: " + Arrays.toString(arr2) + " is " + str);

}

}

输出

The largest number formed from the array: [17, 22, 83, 7, 5] is 83752217
The largest number formed from the array: [79, 21, 83, 7, 58] is 837975821
The largest number formed from the array: [0, 9, 99, 79, 87, 158] is 99987791580

7) 给定一个包含 m 行和 m 列的二维矩阵。任务是以顺时针方向旋转矩阵 90 度。

示例：1

示例：2

文件名: RotateMatrix.java

// import statement
import java.util.Arrays;

public class RotateMatrix
{
public void rotate(int al[][]) 
{
transpose(al); 
int rowSize = al.length;
int colSize = al[0].length;
int i = 0;
while(i < colSize)
{
for(int j = 0; j < rowSize; j++)
{
    int temp =  al[j][i];
    al[j][i] = al[j][colSize - 1];
    al[j][colSize - 1] = temp;
}

i = i + 1;
colSize = colSize - 1;
}
}

void transpose(int a[][]) 
{ 
int rowSize = a.length;
int colSize = a[0].length;
for (int row = 0; row < rowSize; row++) 
{
for (int col = row; col < colSize; col++) 
{ 
    int temp = a[row][col];
    a[row][col] = a[col][row];
    a[col][row] = temp;
} 
}
}

public void display(int arr[][])
{
int rowSize = arr.length;
int colSize = arr[0].length;

for(int i = 0; i < rowSize; i++)
{
for(int j = 0; j < colSize; j++)
{
    System.out.print(arr[i][j] + " ");
}

System.out.println();
}
}

    
// main method
public static void main(String argvs[])
{
    
// creating an object of the class RotateMatrix
RotateMatrix obj = new RotateMatrix();

int[][] arr = new int[2][2];

arr[0][0] = 1; arr[0][1] = 3;
arr[1][0] = 2; arr[1][1] = 4;

System.out.println("The array is: ");
obj.display(arr);

obj.rotate(arr);
System.out.println();
System.out.println("After rotating to 90 degrees clockwise the array is: ");
obj.display(arr);

int[][] arr1 = new int[4][4];

arr1[0][0] = 4; arr1[0][1] = 8; arr1[0][2] = 7; arr1[0][3] = 2;
arr1[1][0] = 9; arr1[1][1] = 5; arr1[1][2] = 6; arr1[1][3] = 3;
arr1[2][0] = 0; arr1[2][1] = 8; arr1[2][2] = 1; arr1[2][3] = 6;
arr1[3][0] = 4; arr1[3][1] = 3; arr1[3][2] = 2; arr1[3][3] = 5; 

System.out.println();
System.out.println("The array is: ");
obj.display(arr1);

obj.rotate(arr1);
System.out.println();
System.out.println("After rotating to 90 degrees clockwise the array is: ");
obj.display(arr1);

}

}

输出

The array is: 
1 3 
2 4 

After rotating to 90 degrees clockwise the array is: 
2 1 
4 3 

The array is: 
4 8 7 2 
9 5 6 3 
0 8 1 6 
4 3 2 5 

After rotating to 90 degrees clockwise the array is: 
4 0 9 4 
3 8 5 8 
2 1 6 7 
5 6 3 2

8) 给定一个数组 arr，其中只包含非负数。找出给定数组 arr 中最小大小的子数组，该子数组排序后，整个数组就会排序。

示例：1

arr[] = {2, 4, 3, 8, 9};

答 {1, 2}

解释: 从索引 1 开始到索引 2 结束的子数组是最小的子数组，排序后整个数组就会排序。

示例：2

arr[] = {12, 34, 45, 67, 78, 88, 99, 102};

答 { }

解释: 给定数组已排序。因此，子数组为空。

文件名: SmallestSubArray.java

// import statement
import java.util.Arrays;

public class SmallestSubArray 
{
// method that finds the starting and ending 
// indices of the subarray that should be sorted to 
// sort the whole array
public int[] findSubarray(int a[], int size)
{
// for storing the first index of the subarray
int first = -1;

// for storing the second index of the subarray
int second = -1;
// for storing the result
int ans[] = {-1, -1};
for(int i = 0; i < size - 1; i++)
{
if(a[i] > a[i + 1])
{
first = i + 1;
break;
}
}

if(first == -1)
{
// if control reaches here, then the input array is already sorted.
return ans;
}

for(int j = size - 1; j >= 1; j--)
{
if(a[j] < a[j - 1])
{
second = j - 1; 
break;
}
}

int temp = first;
for(int i1 = temp; i1 < size; i1++)
{
if(a[i1] <= a[first])
first = i1;
}
temp = second;
for(int j = temp; j >= 0; j--)
{
if(a[j] >= a[second])
second = j;

}

temp = first;
for(int i = 0; i <= temp; i++)
{
if(a[i]  > a[first])
{
first = i; 
break;
}

}

temp = second;
for(int i = size-1; i >= temp; i--)
{
if(a[i] < a[second])
{
second = i; 
break;

}
}


ans[0] = first;
ans[1] = second;

return ans;
}

// main method
public static void main(String argvs[])
{
    
// creating an object of the class SmallestSubArray
SmallestSubArray obj = new SmallestSubArray();

int[] arr = {2, 4, 3, 8, 9};
int size = arr.length;
System.out.println("The array is: " + Arrays.toString(arr));
int ans[] = obj.findSubarray(arr, size);
if(ans[0] < 0)
{
System.out.println("Minimum subarray is not found as the array is already sorted \n");
}
else
{
System.out.println("Minimum subarray for sorting the array is:");
System.out.print("[");
for(int i = ans[0]; i < ans[1]; i++)
{
System.out.print(arr[i] + ", ");
}
System.out.println(arr[ans[1]] + "] \n");
}


int[] arr1 = {12, 34, 45, 67, 78, 88, 99, 102, 345, 555, 666, 777, 888, 999};
size = arr.length;
System.out.println("The array is: " + Arrays.toString(arr1));
int ans1[] = obj.findSubarray(arr1, size);
if(ans1[0] < 0)
{
System.out.println("Minimum subarray is not found as the array is already sorted \n");
}
else
{
System.out.println("Minimum subarray for sorting the array is:");
System.out.print("[");
for(int i = ans1[0]; i < ans1[1]; i++)
{
System.out.print(arr1[i] + ", ");
}
System.out.println(arr1[ans1[1]] + "] \n");
}


int[] arr2 = {1, 2, 3, 3, 4, 4, 5, 5, 7, 8, 9, 20, 14, 16, 19, 14, 19, 19, 20, 21, 22, 27, 30};
size = arr2.length;
System.out.println("The array is: " + Arrays.toString(arr2));
int ans2[] = obj.findSubarray(arr2, size);
if(ans2[0] < 0)
{
System.out.println("Minimum subarray is not found as the array is already sorted \n");
}
else
{
System.out.println("Minimum subarray for sorting the array is:");
System.out.print("[");
for(int i = ans2[0]; i < ans2[1]; i++)
{
System.out.print(arr2[i] + ", ");
}
System.out.println(arr2[ans2[1]] + "] \n");
}

}
}

输出

The array is: [2, 4, 3, 8, 9]
Minimum subarray for sorting the array is:
[4, 3] 

The array is: [12, 34, 45, 67, 78, 88, 99, 102, 345, 555, 666, 777, 888, 999]
Minimum subarray is not found as the array is already sorted 

The array is: [1, 2, 3, 3, 4, 4, 5, 5, 7, 8, 9, 20, 14, 16, 19, 14, 19, 19, 20, 21, 22, 27, 30]
Minimum subarray for sorting the array is:
[20, 14, 16, 19, 14, 19, 19]

9) 给定一个数组 arr，大小为 sz，一个键 k，以及一个段大小 s，使得 s 完全整除 sz。检查数组 arr 的每个大小为 s 的段是否包含键 k。

示例：1

arr[] = {5, 3, 2, 4, 3, 9, 11, 3, 12, 67, 45, 3}; sz = 12; k = 3; s = 3;

答案: 是的，数组 arr 的每个大小为 s 的段都包含键 k。

解释: sz / s = 12 / 3 = 4。这四个段是

{5, 3, 2} -----> 包含键 3

{4, 3, 9} -----> 包含键 3

{11, 3, 12} -----> 包含键 3

{67, 45, 3} -----> 包含键 3

因此，每个段都包含键 k，即 3。

示例：2

arr[] = {23, 56, 65, 21, 34, 67, 89, 9, 0, 23, 55, 44, 33, 22, 23}; sz = 15; k = 23; s = 5;

答案: 是的，数组 arr 的每个大小为 s 的段都包含键 k。

解释: sz / s = 15 / 5 = 3。这三个段是

{23, 56, 65, 21, 34} -----> 包含键 23

{67, 89, 9, 0, 23} -----> 包含键 23

{55, 44, 33, 22, 23} -----> 包含键 23

因此，每个段都包含键 k，即 23。

文件名: ArraySegmentKey.java

// A Java code that finds the every
// segment of size s of array arr have
// key K or not

import java.util.*;
public class ArraySegmentKey 
{
public boolean findingKinWindowSize(int size, int[] arr, int K, int s)
{
int i;
boolean b = false;

// Iterate from 0 to size - 1
for (i = 0; i < size; i = i + s) 
{
int j;
// Iterate from 0 to s - 1
for (j = 0; j < s; j++) 
{
if (i + j < size && arr[i + j] == K)
{
break;
}
}
if (j == s)
{
return false;
}
if (i + j >= size)
{
return false;
}
}
if (i >= size)
{
return true;
}
else
{
return b;
}
}

// main method
public static void main(String argvs[])
{
// creating an object of the class ArraySegmentKey
ArraySegmentKey obj = new ArraySegmentKey();

int arr[] = {5, 3, 2, 4, 3, 9, 11, 3, 12, 67, 45, 3};
int k = 3;
int s = 3;
int sz = arr.length;
if (obj.findingKinWindowSize(sz, arr, k, s))
{
System.out.println("For array " + Arrays.toString(arr));
System.out.println("Each segment of size " + s + " contains the key " + k + "\n");
}
else
{
System.out.println("For array " + Arrays.toString(arr));
System.out.println("Each segment of the array of size " + s + " does not contain the key " + k + "\n");
}

int arr1[] = {23, 56, 65, 21, 34, 67, 89, 9, 0, 23, 55, 44, 33, 22, 23};
int k1 = 23;
int s1 = 5;
int sz1 = arr1.length;
if (obj.findingKinWindowSize(sz1, arr1, k1, s1))
{
System.out.println("For array " + Arrays.toString(arr1));
System.out.println("Each segment of size " + s1 + " contains the key " + k1 + "\n");
}
else
{
System.out.println("For array " + Arrays.toString(arr1));
System.out.println("Each segment of the array of size " + s1 + " does not contain the key " + k1 + "\n");
}

int arr2[] = {1, 6, 7, 2, 3, 8, 9};
int k2 = 6;
int s2 = 1;
int sz2 = arr2.length;
if (obj.findingKinWindowSize(sz2, arr2, k2, s2))
{
System.out.println("For array " + Arrays.toString(arr2));
System.out.println("Each segment of size " + s2 + " contains the key " + k2 + "\n");
}
else
{
System.out.println("For array " + Arrays.toString(arr2));
System.out.println("Each segment of the array of size " + s2 + " does not contain the key " + k2 + "\n");
}

}
}

输出

For array [5, 3, 2, 4, 3, 9, 11, 3, 12, 67, 45, 3]
Each segment of size 3 contains the key 3

For array [23, 56, 65, 21, 34, 67, 89, 9, 0, 23, 55, 44, 33, 22, 23]
Each segment of size 5 contains the key 23

For array [1, 6, 7, 2, 3, 8, 9]
Each segment of the array of size 1 does not contain the key 6

10) 给定一个字符串，任务是找出该字符串在其字典序排序的排列中的排名。给定字符串的字符可能重复，也可能不重复。如果字符重复，则需要查看唯一的排列，然后确定排名。

示例：1

str = "caa"

答案: "caa" 在其字典序排序的排列中的排名是 3。

解释: 该字符串有三个字符，'a'、'a' 和 'c'，它们的字典序排序的排列是

"aac" ----------> 排名 - 1

"aca" ----------> 排名 - 2

"caa" ----------> 排名 - 3

因此，排名是 3。

示例：2

str = "dcab"

答案: "dcab" 在其字典序排序的排列中的排名是 23。

解释: 该字符串有四个字符，'a'、'b'、'c'、'd'，它们的字典序排序的排列是

"abcd" ----------> 排名 - 1

"abdc" ----------> 排名 - 2

"acbd" ----------> 排名 - 3

"acdb" ----------> 排名 - 4

"adbc" ----------> 排名 - 5

"adcb" ----------> 排名 - 6

"bacd" ----------> 排名 - 7

"badc" ----------> 排名 - 8

"bcad" ----------> 排名 - 9

"bcda" ----------> 排名 - 10

"bdac" ----------> 排名 - 11

"bdca" ----------> 排名 - 12

"cabd" ----------> 排名 - 13

"cadb" ----------> 排名 - 14

"cbad" ----------> 排名 - 15

"cbda" ----------> 排名 - 16

"cdab" ----------> 排名 - 17

"cdba" ----------> 排名 - 18

"dabc" ----------> 排名 - 19

"dacb" ----------> 排名 - 20

"dbac" ----------> 排名 - 21

"dbca" ----------> 排名 - 22

"dcab" ----------> 排名 - 23

因此，排名是 23。

文件名: PermutationRank.java

public class PermutationRank 
{
// a method that finds the rank
public int findRank(String str) 
{
int size = str.length();
// for storing factorials of numbers
long[] fact = new long[size + 1];
fact[0] = 1;

for (int i = 1; i <= size; i++) 
{
fact[i] = (fact[i - 1] * i);
}

// for storing the frequency of character 
int[] c = new int[52];

for (char ch : str.toCharArray()) 
{
c[o(ch)] = c[o(ch)] + 1;
}

long rank = 0;
int count = str.length();

for (char ch : str.toCharArray()) 
{
count = count - 1;
for (int t = 0; t < o(ch); t++) 
{
if (c[t] > 0) 
{
c[t] = c[t] - 1;
long trank = fact[count];

for (int i = 0; i < 52; i++) 
{
if (c[i] > 0) 
{
// a! / b!
// where a! represent the factorial when the charactes are unique and
// where b! is the factorial of repeated characters
trank = (trank / fact[c[i]]);
}
}
rank = (rank + trank);
c[t] = c[t] + 1;
}
}
c[o(ch)] = c[o(ch)] - 1;
}
return new Long((rank + 1)).intValue();
}

private int o(char ch) 
{
if (ch <= 'Z') return ch - 'A';
return ch - 'a' + 26;
}

// main method
public static void main(String argvs[])
{
PermutationRank obj = new PermutationRank();
String str = "caa";
int rank = obj.findRank(str);
str = "'caa'";
System.out.print("The rank of the string " + str + " is ");
System.out.println(rank + " among its lexicographically sorted permutations. \n");


str = "dcab";
rank = obj.findRank(str);
str = "'dcab'";
System.out.print("The rank of the string " + str + " is ");
System.out.println(rank + " among its lexicographically sorted permutations. \n");


str = "haaxxy";
rank = obj.findRank(str);
str = "'haaxxy'";
System.out.print("The rank of the string " + str + " is ");
System.out.println(rank + " among its lexicographically sorted permutations. \n");

str = "mttlks";
rank = obj.findRank(str);
str = "'mttlks'";
System.out.print("The rank of the string " + str + " is ");
System.out.println(rank + " among its lexicographically sorted permutations. \n");
}

}

输出

The rank of the string 'caa' is 3 among its lexicographically sorted permutations. 

The rank of the string 'dcab' is 23 among its lexicographically sorted permutations. 

The rank of the string 'haaxxy' is 61 among its lexicographically sorted permutations. 

The rank of the string 'mttlks' is 177 among its lexicographically sorted permutations.

11) 给定两个已排序的数组 arr 和 arr1。它们的长度可能相等，也可能不相等。找出这些给定数组的中位数。注意，不允许合并已排序的数组。

示例：1

arr = {-11, -10, -9, -2, 5, 17}

arr1 = {-4, 4, 7, 13, 16, 17, 19}

答案: 这些已排序数组的中位数位于索引处。

解释: 当合并这些已排序的数组时，我们得到以下结果。

mergedArray = {-11, -10, -9, -4, -2, 4, 5, 7, 13, 16, 17, 17, 19};

mergedArray 的大小为 13，是奇数。因此，只有一个中间元素位于索引 13 / 2 = 6 处。在第 6 个索引处，我们得到 5。因此，5 是这些已排序数组的中位数。

注意：我们在此处仅为解释目的而合并。在代码中，我们不会合并数组。

示例：2

arr = {5, 7, 9, 11, 13, 16, 19, 22}

arr1 = {-4, 4, 7, 8, 10, 11, 12, 14}

答案: 这些已排序数组的中位数是 10。

解释: 当合并这些已排序的数组时，我们得到以下结果。

mergedArray = {-4, 4, 5, 7, 7, 8, 9, 10, 11, 11, 12, 13, 14, 16, 19, 22};

mergedArray 的大小为 16，是偶数。因此，有两个中间元素分别位于 16 / 2 = 8^号和 16 / 2 - 1 = 7^号索引处。因此，中位数是 (10 + 11) / 2 = 10.5。

文件名: FindMedian.java

// import statement
import java.util.Arrays;

public class FindMedian 
{

// A utility method to get the median of two integers
private float MOI2(int x, int y) 
{
return (float) ((x + y) / 2.0);
}

// A utility method to get the median of three integers
private float MOI3(int x, int y, int z) 
{
return x + y + z - Math.max(x, Math.max(y, z)) - Math.min(x, Math.min(y, z));
}

// A utility method to get the median of four integers
private float MOI4(int w, int x, int y, int z) 
{
int max = Math.max(w, Math.max(x, Math.max(y, z)));
int min = Math.min(w, Math.min(x, Math.min(y, z)));
return (float) ((w + x + y + z - max - min) / 2.0);
}

// a utility method to get the median of a single array
private float medSingle(int arr1[], int s) 
{
if (s == 0)
{
return -1;
}
if (s % 2 == 0)
{
return (float) ((double) (arr1[s / 2] + arr1[s / 2 - 1]) / 2);

}

return arr1[s / 2];
}

// The method assumes that s2 is less than or equal to s1
// the method returns -1 if both the arrays are empty
private float findMedUtil(int arr1[], int s2, int arr2[], int s1) 
{

// the median only lies in the second array if the
// first array is empty
if (s2 == 0)
return medSingle(arr1, s1);

// only one element is present in the smaller array
if (s2 == 1) 
{

// Case 1: only one element is present in the larger array,
// simply call MO2()
if (s1 == 1)
return MOI2(arr1[0], arr2[0]);

// Case 2: consider the middle 3 elements of larger array and
// the only element of smaller array, if the larger array 
// has odd number of elements. 
if (s1 % 2 == 1)
{
return MOI2(arr2[s1 / 2], (int) MOI3(arr1[0], arr2[s1 / 2 - 1], arr2[s1 / 2 + 1]));
}

// Case 3: The following will be the three elements 
// if the larger array has even number of elements
// ... The middle two elements of the larger array
// ... The only one element of the smaller array
return MOI3(arr2[s1 / 2], arr2[s1 / 2 - 1], arr1[0]);
}

// two elements is present in the smaller array
else if (s2 == 2) 
{

// Case 4: Invoke MOI4() when the larger array also has two elements
if (s1 == 2)
{
return MOI4(arr1[0], arr1[1], arr2[0], arr2[1]);
}

// Case 5: when number of elements are present in the larger array are not multiple of 2
// then the median will be one of the following 3 elements
// 1. In the larger array, the element at the middle index
// 2. Maximum of the first element of the smaller array 
//    and element just before the middle of the larger array
// 3. Minimum of the second element of the smaller array and 
//    element just after the middle of the larger array
if (s1 % 2 == 1)
{
return MOI3(arr2[s1 / 2], Math.max(arr1[0], arr2[s1 / 2 - 1]), Math.min(arr1[1], arr2[s1 / 2 + 1]));
}

// Case 6: when number of elements are present in the larger array are multiples of 2
// Then, the median eleement will be one the following four elements
// 1 & 2) two middle elements of the larger array
// 3) In the smaller array, the maximum of the first element and 
//    the element that comes just before the first middle element present in the larger array
// 4. In the smaller array, the minimum of the second element and 
//    element just after the second middle in the larger array
return MOI4(arr2[s1 / 2], arr2[s1 / 2 - 1], Math.max(arr1[0], arr2[s1 / 2 - 2]), Math.min(arr1[1], arr2[s1 / 2 + 1]));
}

int indxa = (s2 - 1) / 2;
int indxb = (s1 - 1) / 2;

/*
* if a[indxa] <= b[indxb], then median
must be present in a[indxa....] and B[....indxb]
*/
if (arr1[indxa] <= arr2[indxb])
{
return findMedUtil(Arrays.copyOfRange(arr1, indxa, arr1.length), s2 / 2 + 1, arr2, s1 - indxa);
}

/*
* if arr1[indxa] > arr2[indxb], then median
must be present in arr1[...indxa] and arr2[indxb....]
*/
return findMedUtil(arr1, s2 / 2 + 1, Arrays.copyOfRange(arr2, indxb, arr2.length), s1 - indxa);
}

// A wrapper method written around the findMedianUtil(). The method
// ensures that the smaller array is passed as first argument
// to findMedUtil
public float findMedn(int arr1[], int s2, int arr2[], int s1)
{
if (s2 > s1)
{
return findMedUtil(arr2, s1, arr1, s2);
}

return findMedUtil(arr1, s2, arr2, s1);
}

// main method
public static void main(String argvs[])
{
// instantiating the class FindMedian
FindMedian obj = new FindMedian();

int arr1[] = {-11, -10, -9, -2, 5, 17};
int arr2[] = {-4, 4, 7, 13, 16, 17, 19};

int s2 = arr1.length;
int s1 = arr2.length;  

float f = obj.findMedn(arr1, s2, arr2, s1);

System.out.println("The median element is: " + f + "\n");


int arr3[] = {5, 7, 9, 11, 13, 16, 19, 22};
int arr4[] = {-4, 4, 7, 8, 10, 11, 12, 14};
s2 = arr3.length;
s1 = arr4.length;
f = obj.findMedn(arr3, s2, arr4, s1);

System.out.println("The median element is: " + f);
}
}

输出

The median element is: 5.0

The median element is: 10.5

12) 给定一个数组 arr，大小为 s。此外，还给了一个整数 tar。数组 arr 使用数组的某个元素作为枢轴进行旋转 {1, 2, 3, 4, 5} 可能会变成 {4, 5, 1, 2, 3}。找出整数 tar 是否存在于数组 arr 中。注意，数组 arr 在旋转之前是按非递减顺序排序的。

示例：1

arr = {7, 8, 9, 10, 0, 3, 4, 5, 6}; s = 9; tar = 3;

答 5.

解释: 数字 3 存在于索引 5 处。

示例：2

arr = {4, 5, 1, 2, 3}; s = 5; tar = 6;

答 -1

解释: 数字 6 不存在于数组中。

文件名: FindElement.java

public class FindElement
{

// when the array is rotated, we get two sorted arrays.
// for example {4, 5, 0, 1, 2, 3} has two sorted arrays
// {4, 5} and {0, 1, 2, 3}. In these two sorted arrays, one 
// can apply the binary search to find the index of the target element.
// Therefore, our first task is to find the boundary which divides 
// the given array into two subarrays which are sorted.
// Then, we will apply the binary search on these two subarrays to 
// look for the target element.

// a method that finds the element ele in the array a of length size
public int findIndex(int a[], int size, int ele)
{
int first = a[0];
int last = a[size - 1];
int mid;
int min = 0;
int max = size - 1;

// loop for finding the boundary
while(max - min != 1)
{
mid= (min + max) / 2;
if(a[mid] >= first)
{
min = mid;
}
else
{
max = mid;
}
}

// boundary found
// one subarray is 0 to min
// and another subarray is min + 1 to size - 1
int min1 = 0;
int min2 = min;

// searching in the first subarray, which is sorted, using the binary search.
while(min1 <= min2)
{
mid = (min1 + min2)/2;
if(a[mid] == ele)
{
return mid;
}
else if(a[mid] > ele)
{
min2 = mid - 1;
}
else
{
min1 = mid + 1;
}
}

min = min + 1;
max= size - 1;

// searching in the second subarray, which is also sorted, using the binary search.
while(min <= max)
{
mid = (min + max) / 2;
if(a[mid] == ele)
{
return mid;
}
else if(a[mid] > ele)
{
max = mid - 1;
}
else
{
min = mid + 1;
}
}

// target element not found!!
return -1;
}

// main method
public static void main(String argvs[])
{
// instantiating the class FindElement
FindElement obj = new FindElement();

// input array 
int arr[] = {7, 8, 9, 10, 0, 3, 4, 5, 6};
int s = arr.length;
int tar = 3; // number to be searched 

int index = obj.findIndex(arr, s, tar);

if(index >= 0)
{
System.out.println("The target element " + tar + " is found at the index " + index + "\n");
}
else
{
System.out.println("The target element is not found! \n");   
}


// input array 
int arr1[] = {34, 56, 67, 12, 13, 14, 15, 26, 28};
s = arr1.length;
tar = 19; // number to be searched 

index = obj.findIndex(arr1, s, tar);

if(index >= 0)
{
System.out.println("The target element " + tar + " is found at the index " + index + "\n");
}
else
{
System.out.println("The target element is not found!");   
}

}

}

输出

The target element 3 is found at the index 5

The target element is not found!

注意：线性搜索也可以在此处完成。但是，其时间复杂度将比二分查找高。

13) 给定一个数组 arr，大小为 s。数组 arr 按非递减顺序排序。此外，还给了一个整数 tar。找出整数 tar 是否存在于数组 arr 中。如果存在，找出整数 tar 的起始和结束索引。

示例：1

arr = {1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 10}; s = 13; tar = 5;

答案: 起始索引: 4, 结束索引: 7

解释: 在索引 4 到 7 之间，数字 5 存在。

示例：2

arr = {8, 10, 12, 56, 67, 70, 70, 70, 70, 75, 77, 78, 90, 93, 97}; s = 15; tar = 19;

答案: 目标数字 19 不存在于给定数组中

文件名: FindRange.java

// import statement
import java.util.Arrays;

public class FindRange
{
// a method that finds the range of the element target
// in the array a. if the element is not found an array {-1, -1}
// is returned. If the element is found, then the starting 
// and ending index of the element is returned.
public int[] findIndex(int a[], int size, int target)
{
int first = 0;
int last = size - 1;
int ans[] = {-1, -1}; // for storing the indices

// loop for finding the starting index
while(first < last)
{
int mid = (first + last) / 2;
if(a[mid] < target)
{
first = mid + 1;
}
else
{
last = mid;
}
}

// target element is  not found!
// hence {-1, -1} is returned
if(a[first] != target)
{
return ans;
}

// target element is found!
// update the ans array
ans[0] = first;
last = size - 1;

// loop for looking after the ending index
while(first < last)
{   
int mid = (first + ((last - first) / 2)) + 1;
if(a[mid] > target)
{
last = mid - 1;
}
else
{
first = mid;
}

}

ans[1] = last;
return ans;
}

// main method
public static void main(String argvs[])
{
// instantiating the class FindRange
FindRange obj = new FindRange();

// input array 
int arr[] = {1, 2, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 10};
int s = arr.length;
int tar = 5; // number to be searched 

int index[] = obj.findIndex(arr, s, tar);

if(index[0] >= 0)
{
System.out.println("Range of target element " + tar + " is: " + Arrays.toString(index) + "\n");
}
else
{
System.out.println("The target element is not found! \n");   
}


// input array 
int arr1[] = {8, 10, 12, 56, 67, 70, 70, 70, 70, 75, 77, 78, 90, 93, 97};
s = arr.length;
tar = 19; // number to be searched 

int index1[] = obj.findIndex(arr1, s, tar);

if(index1[0] >= 0)
{
System.out.println("Range of target element " + tar + " is: " + Arrays.toString(index1) + "\n");
}
else
{
System.out.println("The target element is not found! \n");   
}


}
}

输出

Range of target element 5 is: [4, 7]

The target element is not found!

14) 给定一个字符串 str。找出添加到字符串 str 以使其成为回文串所需添加的字符的最小值。字符必须添加到字符串的开头。

示例：1

str = "ABC";

答 2

解释: 在开头插入 "B"，得到 B + ABC ---> BABC。

在开头插入 "C"，得到 C + BABC ---> CBABC。因此，有 2 次插入操作。因此，答案是 2。

示例：2

str = "ABEBAAAA";

答 3

解释: 在开头插入 "A"，得到 A + ABEBAAAA ---> AABEBAAAA。

在开头插入 "A"，得到 A + AABEBAAAA ---> AAABEBAAAA。

在开头插入 "A"，得到 A + AAABEBAAAA ---> AAAABEBAAAA。

因此，有 3 次插入操作。因此，答案是 3。

文件名: MakePalindrome.java

public class MakePalindrome
{
public int minNoOfChars(String A) 
{
int n = A.length();
int ans = n;
while(n > 1 && !isPalindrome(A, n)) 
{
n = n - 1;
}
return ans - n;
}

public boolean isPalindrome(String A, int len) 
{
int i = 0, j = len - 1;
while(i <= j && (A.charAt(i) == A.charAt(j))) 
{
i = i + 1;
j = j - 1;
}
if(i > j) 
{
return true;
}
return false;
}

// main method
public static void main(String argvs[])
{
// instantiating the class MakePalindrome
MakePalindrome obj = new MakePalindrome();

String str= "ABC";

int noOfChars = obj.minNoOfChars(str);
str = "'ABC'";

System.out.println(noOfChars + " insert operations are required to make " + str + " a palindrome string." + "\n");

str= "ABEBAAAA";

noOfChars = obj.minNoOfChars(str);
str = "'ABEBAAAA'";

System.out.println(noOfChars + " insert operations are required to make " + str + " a palindrome string." + "\n");

}
}

输出

2 insert operations are required to make 'ABC' a palindrome string.

3 insert operations are required to make 'ABEBAAAA' a palindrome string.

15) 给定一个字符串数组和一个数字 n。以这样的方式格式化数组中的字符串，使得每行包含 n 个字符。使用贪婪方法插入字符串，即尽可能多地插入单词或字符。使用 ' ' 字符进行填充，以便每行有 n 个字符。额外的空格应均匀分布。如果空格的数量不能均匀分配到字符串中，则左侧的槽应比右侧的槽有更多的空格。对于最后一行，文本应左对齐，即额外的空格应放在右侧。

示例

Words = {"It", "is", "the", "example", "of", "sorting", "technique"}

N = 16

答案: 格式化后的行是

[
"It     is    the"
"example       of"
"sorting         "
"technique       "
]

文件名: TextJustified.java

// import statement
import java.util.*;

public class TextJustified 
{
public ArrayList<String> fullJustify(ArrayList<String> words, int maxWidth) 
{
ArrayList<String> result = new ArrayList<String>();

if(words == null || words.size() == 0)
{
return result;
}


int count = 0;
int last = 0;
ArrayList<String> list = new ArrayList<String>();
for(int i = 0; i < words.size(); i++)
{
count = count + words.get(i).length();

if(count + i - last > maxWidth)
{
int wordsLen = count-words.get(i).length();
int spaceLen = maxWidth - wordsLen;
int eachLen = 1;
int extraLen = 0;

if(i - last - 1 > 0)
{
eachLen = spaceLen / (i - last - 1);
extraLen = spaceLen % (i - last - 1);
}

StringBuilder sb = new StringBuilder();

for(int k = last; k < i - 1; k++)
{
sb.append(words.get(k));

int ce = 0;
while(ce < eachLen)
{
sb.append(" ");
ce = ce + 1;
}

if(extraLen > 0)
{
sb.append(" ");
extraLen = extraLen - 1;
}
}

sb.append(words.get(i - 1)); // the last words of the line

// only single word is possible in this line, required to fill the left with the spaces
while(sb.length() < maxWidth)
{
sb.append(" ");
}

result.add(sb.toString());

last = i;
count=words.get(i).length();
}
}

int lastLen = 0;
StringBuilder sb = new StringBuilder();

for(int i = last; i < words.size() - 1; i++)
{
count = count + words.get(i).length();
sb.append(words.get(i) + " ");
}

sb.append(words.get(words.size() - 1));
int d = 0;
while(sb.length() < maxWidth)
{
sb.append(" ");
}
result.add(sb.toString());

return result;
}
public static void main(String argvs[])
{

// instantiating the class TextJustified
TextJustified obj = new TextJustified();

ArrayList<String> al = new ArrayList<String>
(
Arrays.asList("It", "is", "the", "example", "of", "sorting", "technique")
);
int n = 16;
al = obj.fullJustify(al, n);

for(String str: al)
{
String s = "'";
System.out.println(s + str + s);
}

}
}

输出

'It     is    the'
'example       of'
'sorting         '
'technique       '

16) 给定一个整数数组 arr，其中每个数字都重复三次，只有一个数字除外，它只重复一次。返回只重复一次的数字。

示例

arr[] ={2, 2, 2, 4, 6, 6, 6, 5, 4, 9, 9, 9, 0, 0, 4, 0}

答 5

解释: 数字 5 只重复一次。

文件名: UniqueNumber.java

// import statement
import java.util.Arrays;

public class UniqueNumber
{

// a method that finds the number that 
// is repeated only once
public int findNo(int arr[], int size)
{

int singleRepeat = 0;
int doubleRepeat = 0;
int commonMask;
 
for( int j = 0; j < size; j++)
{

// bits that are coming twice
doubleRepeat  = doubleRepeat | (singleRepeat & arr[j]);

// bits that are coming once
singleRepeat  = singleRepeat ^ arr[j];

// bits that common in singleReapt and doubleRepeat
// only possible in those number which are getting
// repeat thrice
commonMask = (singleRepeat & doubleRepeat);

// eliminating the common bits
singleRepeat &= ~commonMask;

doubleRepeat &= ~commonMask;

}

return singleRepeat;


}

// main method
public static void main(String argvs[])
{
// instantiating the class UniqueNumber
UniqueNumber obj = new UniqueNumber();

// input array 
int arr[] = {2, 2, 2, 4, 6, 6, 6, 5, 4, 9, 9, 9, 0, 0, 4, 0};
int s = arr.length;
int uniqueNo = obj.findNo(arr, s);
System.out.println("Array is: " + Arrays.toString(arr));
System.out.println("The unique number is: " + uniqueNo + "\n");

int arr1[] = {6, 6, 6, 1, 1, 1, 4, 4, 4, 12, 0, 0, 0};
s = arr1.length;
uniqueNo = obj.findNo(arr1, s);
System.out.println("Array is: " + Arrays.toString(arr1));
System.out.println("The unique number is: " + uniqueNo + "\n");

}
}

输出

Array is: [2, 2, 2, 4, 6, 6, 6, 5, 4, 9, 9, 9, 0, 0, 4, 0]
The unique number is: 5

Array is: [6, 6, 6, 1, 1, 1, 4, 4, 4, 12, 0, 0, 0]
The unique number is: 12

17) 给定一个整数数组 arr。重新排列数组 arr，使得 arr[i] = arr[arr[i]]。空间复杂度必须是 O(1)。

示例

arr[] = {2, 1, 0}

答 {0, 1, 2};

解释: arr[0] = 2 => arr[arr[0]] 变成 arr[2] = 0;

arr[1] = 1 => arr[arr[1]] = arr[1] = 1

arr[2] = 0 => arr[arr[2]] = arr[0] = 2

因此，更新后的数组是 {0, 1, 2}

文件名: RearrangeArray.java

// import statement
import java.util.Arrays;

public class RearrangeArray
{

// method for rearranging the elements
public int[] rearrange(int a[], int size)
{
// Increase every Array element Arr[i] by (Arr[Arr[i]] % size) * size
for (int i = 0; i < size; i++)
{
a[i] = ((a[a[i]] % size) * size) + a[i];
}

// Divide every element by size.
for (int i = 0; i < size; i++)
{
a[i] = a[i] / size;
}
return a;
}

// main method
public static void main(String argvs[])
{
RearrangeArray obj = new RearrangeArray();

int a[] = {2, 1, 0};
int size = a.length;
System.out.println("Array before rearranging is: " + Arrays.toString(a));
int res[] = obj.rearrange(a, size);

System.out.println("Array after rearranging is: " + Arrays.toString(res) + "\n");

int arr[] = {2, 4, 3, 1, 0};
size = arr.length;
System.out.println("Array before rearranging is: " + Arrays.toString(arr));
int res1[] = obj.rearrange(arr, size);

System.out.println("Array after rearranging is: " + Arrays.toString(res1));

}
}

输出

Array before rearranging is: [2, 1, 0]
Array after rearranging is: [0, 1, 2]

Array before rearranging is: [2, 4, 3, 1, 0]
Array after rearranging is: [3, 0, 1, 4, 2]

注意：如果移除了 O(1) 空间复杂度条件，则问题将变得简单。可以创建一个与输入数组大小相同的数组，并将 a[a[i]] 的值复制到新创建的数组中。O(1) 空间复杂度使得问题变得棘手。

18) 给定一个正数 n。找出数字的二进制表示中存在的尾随零的数量。

示例：1

n = 20

答 2

解释: 20 的二进制表示是 10100。10100 中尾随零的总数为 2。因此，答案是 2。

示例：2

n = 9

答 0

解释: 9 的二进制表示是 1001。1001 中尾随零的总数为 0。因此，答案是 0。

文件名: TrailingZeros.java

public class TrailingZeros
{
public int countZeros(int n)
{
// array for storing the bits of the number
int arr[] = new int[n];
int index = 0;

// loop for converting the number into its binary representation
while(n != 0)
{
    int bit = n % 2;
    arr[index] = bit;
    index = index + 1;
    n = n / 2;
}

// for counting trailing zeros
int count = 0;

int size = arr.length;
for(int i = 0; i < size; i++)
{
    if(arr[i] == 0)
    {
        count = count + 1;
    }
    else
    {
        break;
    }
}

return count;

}

// main method
public static void main(String argvs[])
{
TrailingZeros obj = new TrailingZeros();

int n = 20;

int countZeros = obj.countZeros(n);

System.out.println("For number " + n + ", there are " + countZeros + " trailing zeros.");

n = 64;

countZeros = obj.countZeros(n);

System.out.println("For number " + n + ", there are " + countZeros + " trailing zeros.");


n = 3;

countZeros = obj.countZeros(n);

System.out.println("For number " + n + ", there are " + countZeros + " trailing zeros.");

}
}

输出

For number 20, there are 2 trailing zeros.
For number 64, there are 6 trailing zeros.
For number 3, there are 0 trailing zeros.

19) 给定一个数字 n。找出第 n 个二进制表示为回文数的数字。

示例：1

n = 1

答 1

解释: 1 的二进制表示是 1，1 是回文数。1 也是第 1 个数字。

示例：2

n = 3

答 5

解释: 第 3 个二进制表示为回文数的数字是 5。其二进制表示是 101。

例如：3

n = 9

答 27

解释: 第 9 个二进制表示为回文数的数字是 27。其二进制表示是 11011。

文件名: PalindromeNumbers.java

// import statement
import java.util.*;

public class PalindromeNumbers 
{
// converting the binary string into an integer
public static int changeStringToInt(String str)
{
int a = 0;

// loop for converting the binary string into integer
for (int j = 0; j < str.length(); j++) 
{
if (str.charAt(j) == '1')
{
a += 1 << j;
}
}
return a;
}

// a method for finding the nth number
// whose binary representation is a palindrome
public static int findNthNumber(int no)
{
// stores the binary palindrome string
Queue<String> que = new LinkedList<>();

// base case
if (no == 1)
return 1;
no = no - 1;

// adding the second palindrome string
que.add("11");

while (no-- > 0) 
{

// removing the current binary palindrome string 
// from the queue
String current = que.remove();

if (no == 0)
{
return changeStringToInt(current);
}

int l = current.length();

// if the length is even, then we have to choices
// for example 11 -> 101 or 111
if (l % 2 == 0) 
{
que.add(current.substring(0, l / 2) + "0" + current.substring(l / 2));
que.add(current.substring(0, l / 2) + "1" + current.substring(l / 2));
}

// if the length is odd, then we have only one choice
// for example 1 -> 111
else 
{
char midCh = current.charAt(l / 2);
que.add(current.substring(0, l / 2) + midCh
+ current.substring(l / 2));
}
}
return -1;
}

// main method
public static void main(String[] argvs)
{
int n = 7;
int no = findNthNumber(n);
System.out.println("The " + n + "th number whose binary representation is palindrome is: " + no);

n = 13;
no = findNthNumber(n);
System.out.println("The " + n + "th number whose binary representation is palindrome is: " + no);

}
}

输出

The 7th number whose binary representation is palindrome is: 17
The 13th number whose binary representation is palindrome is: 51

20) 给定一个整数数组 arr。大小为 w 的滑动窗口从数组的左侧向右侧移动。因此，一次只能观察 w 个数字。任务是找出每个窗口的最大值。观察以下示例。

示例

arr[] = {1, 4, -1, -4, 6, 4, 7, 8}; w = 3;

答 {4, 4, 6, 6, 7, 8}

说明

{[1, 4, -1,] -4, 6, 4, 7, 8} -> max(1, 4, -1) = 4

{1, [4, -1, -4,] 6, 4, 7, 8} -> max(4, -1, -4) = 4

{1, 4, [-1, -4, 6,] 4, 7, 8} -> max(-1, -4, 6) = 6

{1, 4, -1, [-4, 6, 4,] 7, 8} -> max(-4, 6, 4) = 6

{1, 4, -1, -4, [6, 4, 7,] 8} -> max(6, 4, 7) = 7

{1, 4, -1, -4, 6, [4, 7, 8]} -> max(4, 7, 8) = 8

文件名: SlidingWindowMax.java

// import statement
import java.util.*;

public class SlidingWindowMax 
{
// Uses a doubled-ended queue. When going through the array, we only care about the
// largest elements we receive. Any smaller element that came before the current 
// one is no longer required. Essentially our queue must always be in descending order.
public static ArrayList<Integer> slidingMaximum(List<Integer> A, int B) 
{
Deque<Integer> window = new LinkedList<Integer>();
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < A.size(); i++) 
{
int val = A.get(i);
// Remove all elements smaller than the current one from the queue
while (!window.isEmpty() && val >= A.get(window.getLast())) 
{
window.removeLast();
}
// Add the current element's index to the queue. It is important that we
// store the indices rather than the values.
window.add(i);
// The first element of the queue is always the largest. If the index of 
// this number is smaller than the window's stating index, then we remove it
if (window.getFirst() < (i + 1) - B) 
{
window.removeFirst();
}
// Ignores the first few interations
if (i >= B - 1)
{
result.add(A.get(window.getFirst()));
}
}
return result;
}
    
    
// main method
public static void main(String argvs[])
{

ArrayList<Integer> arr = new ArrayList<Integer>
(
Arrays.asList(1, 4, -1, -4, 6, 4, 7, 8)
);

int b = 3;

System.out.println("The array is: " + arr + "\n");

arr = slidingMaximum(arr, b);

System.out.println("The maximum values are: " + arr);


}

}

输出

The array is: [1, 4, -1, -4, 6, 4, 7, 8]

The maximum values are: [4, 4, 6, 6, 7, 8]

21) 给定一个逆波兰表示法中的算术表达式。计算给定表达式。

示例

A = ["4", "3", "+", "5", "*"]

答 35

说明

* -> () * ()

5: -> () * (5)

+: (() + ()) * (5)

3: (() + (3)) * (5)

4: ((4) + (3)) * (5)

= (7) * (5) = 35

文件名: EvaluateExpression.java

// import statement
import java.util.*;

public class EvaluateExpression 
{
public static int evaluateExp(ArrayList<String> al) 
{
Stack<Integer> stk = new Stack<>();

for(String st : al) 
{
if(st.equals("+") || st.equals("-") || st.equals("*") || st.equals("/")) 
{
// fetching first two numeric values from the right
// of the array list
int n1 = stk.pop();
int n2 = stk.pop();

// switch case for handling the operation
switch(st) 
{
case "+" : 
int s = n1 + n2;

// after performing the operation add the value to the stack
stk.push(s);
break;
case "-" : 
int d = n2 - n1;
stk.push(d);
break;
case "*" : 
int m = n1 * n2;
stk.push(m);
break;
case "/" : 
int div = n2 / n1;
stk.push(div);
}
}
else 
{
stk.push(Integer.parseInt(st));
}
}

return stk.pop();
}
// main method
public static void main(String argvs[])
{

ArrayList<String> exp = new ArrayList<String>
(
Arrays.asList("4", "3", "+", "5", "*")
);



System.out.println("The expression is: " + exp + "\n");

int ans = evaluateExp(exp);

System.out.println("The value of the expression is: " + ans + "\n");

exp = new ArrayList<String>
(
Arrays.asList("4", "13", "5", "/", "+")
);



System.out.println("The expression is: " + exp + "\n");

ans = evaluateExp(exp);

System.out.println("The value of the expression is: " + ans);


}

}

输出

The expression is: [4, 3, +, 5, *]

The value of the expression is: 35

The expression is: [4, 13, 5, /, +]

The value of the expression is: 6

22) 给定一个数字 n，表示代码中的总位数。格雷码总是从 0 开始。显示格雷码的序列。

示例

N = 3;

答 {0, 1, 3, 2, 6, 7, 5, 4}

0 0 0 ---> 0

0 0 1 ---> 1

0 1 1 ---> 3

0 1 0 ---> 2

1 1 0 ---> 6

1 1 1 ---> 7

1 0 1 ---> 5

1 0 0 ---> 4

文件名: GrayCode.java

// import statement
import java.util.*;

public class GrayCode 
{
    public ArrayList<Integer> findSeq(int a) 
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(a == 0)
        {
            return res;
        }
        
        // first two gray sequence are always 0 and 1
        res.add(0);
        res.add(1);
        
        if(a== 1)
        {
            return res;
        }
        while(a > 1)
        {
            int s = res.size();
            for(int i = s - 1; i >= 0; i--)
            {
                res.add(s + res.get(i));
            }
            a = a - 1;
        }
        
        return res;
    }
    
// main method
public static void main(String argvs[])
{

int n = 3;
GrayCode obj = new GrayCode();

ArrayList<Integer> al = obj.findSeq(n);

System.out.println("For n = " + n + ", the gray code sequence is: " + al + "\n");

n = 4;
al = obj.findSeq(n);

System.out.println("For n = " + n + ", the gray code sequence is: " + al + "\n");

n = 5;
al = obj.findSeq(n);

System.out.println("For n = " + n + ", the gray code sequence is: " + al + "\n");

}

}

输出

For n = 3, the gray code sequence is: [0, 1, 3, 2, 6, 7, 5, 4]

For n = 4, the gray code sequence is: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]

For n = 5, the gray code sequence is: [0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24, 25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16]

23) 给定一个包含 n 个整数的数组 arr。找出所有唯一的三个数（x、y 和 z），使得 x + y + z = 0。注意，三元组的顺序无关紧要，即 y + z + x 或 y + x + z 与 x + y + z 相同。

示例

arr = {-2, 0, 2, 4, -2, -4};

答案: 有三个唯一的三元组。{-2, 0, 2}, {-2, -2, 4}, {-4, 0, 4}

文件名: FindTriplets.java

// import statement
import java.util.*;

public class FindTriplet 
{
// a method that finds the unqiue triplets whose sum is zero
public ArrayList<ArrayList<Integer>> threeSumZero(ArrayList<Integer> A) 
{
int B = 0;

// for storing the unique triplets
ArrayList<ArrayList<Integer>> total = new ArrayList();


// sorting the list
Collections.sort(A);
int i = 0;

// loop that uses three pointer approach
while(i < A.size())
{
int j = i + 1, k = A.size() - 1;

while(j < k) 
{
long sum = (long)A.get(i) + (long)A.get(j) + (long)A.get(k);

if(sum == B)
{
ArrayList<Integer> ans = new ArrayList();
ans.add(A.get(i));
ans.add(A.get(j));
ans.add(A.get(k));

// checks whether the found triplet is unique or not
// if unique, then add it; otherwise, discard it.
if(!total.contains(ans))
{
total.add(ans);
}
}
if(sum > B) 
{
k = k - 1;
}

else 
{
j = j + 1;
}
}

i = i + 1;
}
return total;
}
    
// main method
public static void main(String argvs[])
{

// creating an object of the class FindTriplet 
FindTriplet obj = new FindTriplet();
ArrayList<Integer> al = new ArrayList<Integer>
(
Arrays.asList(-2, 0, 2, 4, -2, -4)
);


ArrayList<ArrayList<Integer>> triplets = obj.threeSumZero(al);

System.out.println("For the list: " + al);
System.out.println("Triplets are: " + triplets + "\n");


al = new ArrayList<Integer>
(
Arrays.asList(1, -4, 0, 0, 5, -5, 1, 0, -2, 4, -4, 1, -1, -4, 3, 4, -1, -1, -3)
);

triplets = obj.threeSumZero(al);

System.out.println("For the list: " + al);
System.out.println("Triplets are: " + triplets + "\n");

}

}

输出

For the list: [-4, -2, -2, 0, 2, 4]
Triplets are: [[-4, 0, 4], [-2, -2, 4], [-2, 0, 2]]

For the list: [-5, -4, -4, -4, -3, -2, -1, -1, -1, 0, 0, 0, 1, 1, 1, 3, 4, 4, 5]
Triplets are: [[-5, 0, 5], [-5, 1, 4], [-4, -1, 5], [-4, 0, 4], [-4, 1, 3], [-3, -2, 5], [-3, -1, 4], [-3, 0, 3], [-2, -1, 3], [-2, 1, 1], [-1, 0, 1], [0, 0, 0]]

24) 给定一个数组 arr，其中只包含非负整数（x1, x2, x3, ..., xn）。每个整数代表坐标（j, xj）。'n' 条垂直线被拉伸，使得线 j 的两个端点位于 (j, xj) 和 (j, 0)。找出两条线，它们与 x 轴共同创建一个容器，使得容器能够容纳最多的水量。假设水可以存储在 2D 容器中。注意，不允许倾斜容器。

示例：1

arr = {5, 1, 2, 3};

答 9

解释: 给定数组中有 4 条垂直线，它们的高度分别为 5、1、2 和 3。此外，5 和 3 相距 3 个单位。因此，容量是 min(5, 3) * 3 = 9。如果取其他任何一对垂直线，我们得到的容量都不会超过 9。

文件名: ContainerCapacity.java

// import statement
import java.util.*;

public class ContainerCapacity 
{
// a method that finds the maximum capacity
public int findMaxCapacity(ArrayList<Integer> height) 
{
int len = height.size();
int low = 0;
int high = len -1 ;  
int maxArea = 0;  
while (low < high) 
{  
maxArea = Math.max(maxArea, (high - low) * Math.min(height.get(low), height.get(high)));  
if (height.get(low) < height.get(high)) 
{  
low = low + 1;  
} 
else 
{  
high = high - 1;  
}  
}  
return maxArea;
}
    
// main method
public static void main(String argvs[])
{

// creating an object of the class ContainerCapacity 
ContainerCapacity obj = new ContainerCapacity();
ArrayList<Integer> al = new ArrayList<Integer>
(
Arrays.asList(5, 1, 2, 3)
);

int capacity = obj.findMaxCapacity(al);

System.out.println("For the list: " + al);
System.out.println("The maximum capacity is: " + capacity + "\n");

}
}

输出

For the list: [5, 1, 2, 3]
The maximum capacity is: 9

25) 给定一个包含 n 个整数的数组 arr。x1, x2 ,..., xn 和一个整数 J。返回大小为 J 的所有窗口中存在的唯一数字的数量。

示例：1

arr = {5, 1, 2, 3, 2, 5, 9, 8, 0, 0, 0}; J = 3

答 {3, 3, 2, 3, 3, 3, 3, 2, 1}

解释: 大小为 J（即 3）的所有窗口是

{5, 1, 2} ---> 3 个唯一数字

{1, 2, 3} ---> 3 个唯一数字

{2, 3, 2} ---> 2 个唯一数字

{3, 2, 5} ---> 3 个唯一数字

{2, 5, 9} ---> 3 个唯一数字

{5, 9, 8} ---> 3 个唯一数字

{9, 8, 0} ---> 3 个唯一数字

{8, 0, 0} ---> 2 个唯一数字

{0, 0, 0} ---> 1 个唯一数字

如果我们列出唯一元素，我们会得到 {3, 3, 2, 3, 3, 3, 3, 2, 1}。

文件名: UniqueNumbers.java

// import statement
import java.util.*;

public class UniqueNumbers 
{
// a method that finds count of unique numbers in the window of size B
public ArrayList<Integer> uniqueNums(ArrayList<Integer> A, int B) 
{
        
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

int i = 0;
int j = 0;
ArrayList<Integer> result = new ArrayList<Integer>();

while(j < A.size())
{
hm.put(A.get(j), hm.getOrDefault(A.get(j), 0) + 1);

if(B<(j - i + 1))
{

hm.put(A.get(i), hm.getOrDefault(A.get(i), 0)-1);

if(hm.get(A.get(i))==0)
hm.remove(A.get(i));

i = i + 1; 
}
if(B==(j-i+1))
{

result.add(hm.size());
}
j = j + 1;
}
return result;
}
    
// main method
public static void main(String argvs[])
{

// creating an object of the class UniqueNumbers 
UniqueNumbers obj = new UniqueNumbers();
ArrayList<Integer> al = new ArrayList<Integer>
(
Arrays.asList(5, 1, 2, 3, 2, 5, 9, 8, 0, 0, 0)
);
Integer J = 3;


System.out.println("For the list: " + al);
al = obj.uniqueNums(al, J);

System.out.println("The list of unique numbers are: " + al + "\n");


al = new ArrayList<Integer>
(
Arrays.asList(5, 6, 7, 3, 3, 3, 1)
);
J = 1;

System.out.println("For the list: " + al);
al = obj.uniqueNums(al, J);

System.out.println("The list of unique numbers are: " + al + "\n");

}
}

输出

For the list: [5, 1, 2, 3, 2, 5, 9, 8, 0, 0, 0]
The list of unique numbers are: [3, 3, 2, 3, 3, 3, 3, 2, 1]

For the list: [5, 6, 7, 3, 3, 3, 1]
The list of unique numbers are: [1, 1, 1, 1, 1, 1, 1]

26) 给定一个只包含整数的数组 arr。找出数组 arr 中的 4 个索引，使得 arr[i] + arr[j] = arr[k] + arr[l]，其中 i、j、k 和 l 是这 4 个索引。如果存在多个答案，则显示任何一组满足给定条件的 4 个索引。注意，所有索引必须是唯一的。

示例：1

arr = {-2, 0, 2, 4, -2, -4};

答 {0, 1, 2, 5}

解释: 索引 0、1、2 和 5 处的值分别是 -2、0、2 和 -4，并且

-2 + 0 = 2 + -4 => 2。其他答案可以是 {0, 2, 3, 5} 或 {1, 2, 3, 4}

文件名: EqualSum.java

// import statement
import java.util.*;

public class EqualSum 
{
public ArrayList<Integer> findInidices(ArrayList<Integer> A) 
{
// a map whose key is an integer and value is an array list
// the array list contains the indices such that sum of values 
// at those indices is equal to the key
// for example - A = [9, 4, 3, 2]
// map[13, [0, 1]];
// Now, 13 = A[0] + A[1] = 9 + 4 = 13
Map<Integer, ArrayList<Integer>> map = new HashMap<>();

// for storing those 4 indices such that A[i] + A[j] = A[k] + A[l]
ArrayList<Integer> result = new ArrayList<>();
for(int i = 0; i < A.size() - 1; i++)
{
for(int j = i + 1; j < A.size(); j++)
{
int sum = A.get(i) + A.get(j);
if(map.containsKey(sum))
{
// the k and l must be unique
// it is obivous that A[i] + A[j] = A[j] + A[i]
// 
int k = map.get(sum).get(0);
int l = map.get(sum).get(1);
if(k == i || k == j || l == i || l == j) 
{
continue;
}
map.get(sum).addAll(Arrays.asList(i,j));
}
else map.put(sum,new ArrayList<>(Arrays.asList(i,j)));
}
}
for(int i = 0;i < A.size() - 1; i++)
{
for(int j = i + 1; j < A.size(); j++)
{
int sum = A.get(i) + A.get(j);
// size greater than two means 
// we have found our four indices
if(map.get(sum).size() > 2)
{
result.addAll(Arrays.asList(i, j, map.get(sum).get(2), map.get(sum).get(3)));
return result;
}
}
}
return new ArrayList<>();
}

public static void main(String args[])
{ 
// creating an object of the class EqualSum
EqualSum obj = new EqualSum();


ArrayList<Integer> al = new ArrayList<Integer>
(
Arrays.asList(-2, 0, 2, 4, -2, -4)
);

System.out.println("For the list: " + al);
al = obj.findInidices(al);

System.out.println("The list of indices are: " + al + "\n");

al = new ArrayList<Integer>
(
Arrays.asList(2, 4, 5, 9, -1, 15, 7)
);

System.out.println("For the list: " + al);
al = obj.findInidices(al);

System.out.println("The list of indices are: " + al + "\n");


}
}

输出

For the list: [-2, 0, 2, 4, -2, -4]
The list of indices are: [0, 1, 2, 5]

For the list: [2, 4, 5, 9, -1, 15, 7]
The list of indices are: [0, 1, 4, 6]

27) 给定一个字符串 str 和一个字符串 X。查找 str 中的最小窗口，其中包含 X 中的所有字符。时间复杂度必须是线性的。注意，窗口的大小必须等于或大于字符串 X 的大小。

示例：1

S = "APPLBEXODEBLBNC"

X = "LNC"

答案: "LBNC"

解释: 任何其他窗口将需要更多的字符。最小尺寸的窗口在答案中提及。

文件名: SmallestWindow.java

// import statement
import java.util.*;

public class SmallestWindow 
{

    int[] a;
    int[] b;
public String minWindow(String A, String B) 
{
// for storing the frequency of characters
a = new int[256];
b = new int[256];
for(char c: B.toCharArray())
{
// storing the frequency of occurrance of 
// characters in the array b 
b[(int)c]++;
}
int n = A.length();
int l = 0;
int x = -1;
int y = n + 1;
for(int r = 0; r < n; r++)
{
char c = A.charAt(r);
a[(int)c]++;

while(l <= r && good(A.charAt(l)))
{
a[(int)A.charAt(l)]--;
l = l + 1;
}
if(good() && (r - l) < (y - x))
{
y = r;
x = l;
}

}

if(x == -1 && y == n + 1)
{
return "";
}

return A.substring(x, y + 1);

}
public boolean good(char c)
{
for(int i = 0; i < 256; i++)
{
if(a[i] < b[i])
{
return false;
}
}

return (a[(int)c] - b[(int)c] >= 1);
}
public boolean good()
{
// frequency of occurrance charcters in the String A 
// has to be greater than or equal to the frequency of characters 
// present in the string B
for(int i = 0; i < 256; i++)
{
if(a[i] < b[i])
{
return false;
}
}

return true;
}
    

// main method
public static void main(String args[])
{ 

// creating an object of the class SmallestWindow
SmallestWindow obj = new SmallestWindow();

String str = "APPLBEXODEBLBNC";
String t = "LNC";

String ans = obj.minWindow(str, t);

str = "'APPLBEXODEBLBNC'";
System.out.println("For the string: " + str);

System.out.println("The smallest window is: " + ans + "\n");

}
}

输出

For the string: 'APPLBEXODEBLBNC'
The smallest window is: LBNC

28) 给定一个长度为 l 的一维整数数组 arr。找出最长的子序列的长度，该子序列先递增然后递减。

示例

arr = {2, 11, 3, 10, 5, 4, 3, 2, 1}; l = 9

答 8

解释: 最长的递增然后递减的子序列是 {2, 3, 10, 5, 4, 3, 2, 1}。它有 8 个元素。因此，答案是 8。

文件名: LongestSubsequence.java

// import statement
import java.util.*;

public class LongestSubsequence 
{
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public int longestSubsequenceLength(final List<Integer> A) 
{
// list for containing the total number of elements in the increasing part
List<Integer> leftLIS = new ArrayList<>();

// list for containing the total number of elements in the decreasing part
List<Integer> rightLIS = new ArrayList<>();

if(A.isEmpty())
{
return 0;
}

int size = A.size();

// initializing the array
for(int i = 0 ; i < size ; i++) 
{
leftLIS.add(i, 1);
rightLIS.add(i, 1);
}

int max = 0;

// loop for considering the increasing part
for(int i = 0 ; i < size ; i++) 
{
for(int j = 0 ; j < i ; j++) 
{
if(A.get(i) > A.get(j)) 
{
leftLIS.set(i, Math.max(leftLIS.get(i), leftLIS.get(j) + 1));
}
}
}

// loop for considering the decreasing part
for(int i = size - 2 ; i >= 0; i -- )
{
for(int j = size - 1 ; j > i ; j--) 
{
if(A.get(i) > A.get(j)) 
{
rightLIS.set(i, Math.max(rightLIS.get(i), rightLIS.get(j) + 1));
}
}
}

// one part contains the increasing part
// other part contains the decreasing part
// Therefore, we have to combine the value from both the list
// The following loop does the same work and then finds the maximum
// In order to remove the redundant element -1 is used
for(int i = 0 ; i < size ; i++) 
{
// if max is less the sum of values from leftLIS, rightLIS, and - 1
// then update the max
if(max < (leftLIS.get(i) + rightLIS.get(i)) - 1) 
{
max = (leftLIS.get(i) + rightLIS.get(i)) - 1;
}
}
return max;
}


// main method
public static void main(String argvs[])
{
// creating an object of the class LongestSubsequence
LongestSubsequence obj = new LongestSubsequence();

ArrayList<Integer> al = new ArrayList<Integer>
(
Arrays.asList(2, 11, 3, 10, 5, 4, 3, 2, 1)
);

int val = obj.longestSubsequenceLength(al);

System.out.println("For the list: " + al);
System.out.println("The length of subsquence which is increasing and then decreasing is: " + val + "\n");

al = new ArrayList<Integer>
(
Arrays.asList(7, 6, 8, 10, 2, 5, 12, 30, 31, 20, 22, 18)
);

val = obj.longestSubsequenceLength(al);

System.out.println("For the list: " + al);
System.out.println("The length of subsequence which is increasing and then decreasing is: " + val);

}
}

输出

For the list: [2, 11, 3, 10, 5, 4, 3, 2, 1]
The length of subsequence which is increasing and then decreasing is: 8

For the list: [7, 6, 8, 10, 2, 5, 12, 30, 31, 20, 22, 18]
The length of subsequence which is increasing and then decreasing is: 8

29) 给定一组硬币 X。找出可以构成总和 S 的方法数。注意，集合 X 中提到的硬币有无限供应。确保空间复杂度为 O(S)。注意，硬币的顺序将被忽略，即 1 + 2 = 3 是一种方法；因此，2 + 1 = 3 不会被考虑，反之亦然。此外，硬币集合将始终按升序排列。

示例

X = {2, 3, 5, 7}; S = 15

答 10

解释: 有 10 种方法可以得到总和 S = 15。以下是这 10 种方法

2 + 2 + 2 + 2 + 2 + 2 + 3 = 15

2 + 2 + 2 + 3 + 3 + 3 = 15

2 + 2 + 2 + 2 + 2 + 5 = 15

2 + 3 + 5 + 5 = 15

2 + 2 + 3 + 3+ 5 = 15

2 + 2 + 2 + 2 + 7 = 15

2 + 3 + 3 + 7 = 15

3 + 3 + 3 + 3 + 3 = 15

3 + 5 + 7 = 15

5 + 5 + 5 = 15

文件名: CoinSum.java

// import statement
import java.util.*;

public class CoinSum 
{
public int countWays(ArrayList<Integer> A, int B) 
{
// the value of dp[j] represent the
// number of ways to get the sum j
int dp[] = new int[B + 1];
Arrays.fill(dp, 0);
        
dp[0] = 1;
        
for(int i = 0; i < A.size(); i++)
{
for(int j = A.get(i); j <= B; j++)
{
// finding the number of ways when 
// A[i] is included
dp[j] = dp[j] + dp[j - A.get(i)];
                
// finding number of ways when A[i]
// is excluded
dp[j] = dp[j];
}
}
        
return dp[B];
}

// main method
public static void main(String argvs[])
{
// creating an object of the class CoinSum
CoinSum obj = new CoinSum();

ArrayList<Integer> X = new ArrayList<Integer>
(
Arrays.asList(2, 3, 5, 7)
);

int sum = 15;


int ways = obj.countWays(X, sum);

System.out.println("For the set of coins: " + X);
System.out.println("There are " + ways + " ways to get the sum " + sum + "\n");

X = new ArrayList<Integer>
(
Arrays.asList(4, 6, 8, 9, 10)
);

sum = 90;


ways = obj.countWays(X, sum);

System.out.println("For the set of coins: " + X);
System.out.println("There are " + ways + " ways to get the sum " + sum);


}
}

输出

For the set of coins: [2, 3, 5, 7]
There are 10 ways to get the sum 15

For the set of coins: [4, 6, 8, 9, 10]
There are 385 ways to get the sum 90

30) 给定一个大小为 R * C 的棋盘，其中 R 代表总行数，C 代表总列数。创建矩阵 arr，使得 arr[x][y] 表示单元格(x, y) 上发生的皇后攻击次数，假设单元格中没有皇后。

注意

1) 皇后可以在棋盘上任意数量的方格上沿垂直方向、水平方向或对角线移动。皇后不是马，因此它不能跳过其他皇后。

2) 给定 R 个字符串的数组，每个字符串的大小为 C。字符串只包含 '0' 和 '1'。1 代表皇后，0 代表空单元格。因此，在任何单元格中，要么有一个皇后，要么该单元格是空的。

3) 最坏情况时间复杂度不能超过 O(R * C)。

示例

假设棋盘是

[1 0 0]

[0 0 1]

[0 1 0]

其中 1 是皇后位置，0 是空位。

没有皇后攻击单元格(1, 1)。请记住，我们必须假设我们正在评估攻击的单元格中没有皇后。

有 3 次攻击来自皇后到单元格(1, 2)。一次来自位于单元格(1, 1) 的皇后，一次来自位于单元格(2, 3) 的皇后，另一次来自单元格(3, 2)。

位于 (2, 3) 和 (1, 1) 的皇后攻击单元格(1, 3)。注意，这次我们考虑的是 1 索引。

同样，我们也可以计算其他单元格的皇后攻击次数。

最终矩阵是

[0, 3, 2]

[3, 3, 1]

[2, 1, 3]

文件名: QueenAttack.java

// import statement
import java.util.*;

public class QueenAttack 
{

public void fillQueens(int[][] grid,int i,int j,int n,int m,int[][] dp)
{
int[] dx = {-1, 0, 0, 1, -1, -1, 1, 1};
int[] dy = {0, -1, 1, 0, 1, -1, 1, -1};
for(int k = 0; k < 8; k++)
{
int x = i + dx[k];
int y = j + dy[k];
while(x >= 0 && x < n && y >= 0 && y < m)
{
dp[x][y]++;
if(grid[x][y] == 1)
break;
x += dx[k];
y += dy[k];
}
}
}

public ArrayList<ArrayList<Integer>> queenAttack(ArrayList<String> A) 
{
int n = A.size();
int m = A.get(0).length();
int[][] grid = new int[n][m];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
grid[i][j] = (A.get(i).charAt(j) == '0') ? 0 : 1;
}
}
int[][] dp =new int[n][m];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(grid[i][j] == 1)
{
fillQueens(grid,i,j,n,m,dp);
}
}
}

ArrayList<ArrayList<Integer>> arr=new ArrayList<>();
for(int i = 0;i < n; i++)
{
arr.add(new ArrayList<>());
for(int j = 0;j < m; j++)
{
arr.get(i).add(dp[i][j]);
}
}
return arr;
}


public int countWays(ArrayList<Integer> A, int B) 
{
// the value of dp[j] represent the
// number of ways to get the sum j
int dp[] = new int[B + 1];
Arrays.fill(dp, 0);

dp[0] = 1;

for(int i = 0; i < A.size(); i++)
{
for(int j = A.get(i); j <= B; j++)
{
// finding the number of ways when 
// A[i] is included
dp[j] = dp[j] + dp[j - A.get(i)];

// finding number of ways when A[i]
// is excluded
dp[j] = dp[j];
}
}

return dp[B];
}

// main method
public static void main(String argvs[])
{
// creating an object of the class QueenAttack
QueenAttack obj = new QueenAttack();

ArrayList<String> al = new ArrayList<String>
(
Arrays.asList("100", "001", "010")
);

ArrayList<ArrayList<Integer>> arr = obj.queenAttack(al);

System.out.println("For the chessboard: ");
for(String str : al)
{
System.out.println(str);
}
System.out.println();
System.out.println("The following matrix gives the number of queen attacks");

for(ArrayList<Integer> i : arr)
{
System.out.println(i);
}

}
}

输出

For the chessboard: 
1 0 0
0 0 1
0 1 0

The following matrix gives the number of queen attacks
[0, 3, 2]
[3, 3, 1]
[2, 1, 3]

编程面试题

1) 给定一个大小为 s 的整数数组 arr。现在，检查是否存在至少一个元素，该元素严格小于其右侧的所有元素，并且大于其左侧的所有元素。如果存在，则返回 true；否则，返回 false。忽略给定数组的边界元素。

2) 给定一个只读数组 arr，大小为 s，使得数组中的每个元素都不超过 s。此外，在数组中，除了 a1 以外，每个元素都只出现一次，a1 出现了两次，因此 a2 丢失了。找出 a1 和 a2 的值。注意，只读意味着不允许修改输入数组。

3) 给定一个只读数组 arr，大小为 s。找出可以将数组 arr 分成 3 个部分的方法，使得每个部分的总和相等。

4) 给定一个由 N 个整数 X1, X2, X3, ...., Xn 组成的数组 arr。你必须返回 f(a1, a2) 的最大值，其中 0 ≤ a1, a2, < N。给定 f(a1, a2) = |arr[a1] - a[a2]| + |a1 - a2|，其中 |y| 表示 y 的绝对值。

5) 找到由数组 arr 的元素组成的数字的下一个排列，大小为 s，而不改变元素的顺序。

6) 给定一个数组 arr，其中只包含非负数。使用给定数组 arr 中的所有非负数创建最大的数字。

7) 给定一个包含 m 行和 m 列的二维矩阵。任务是以顺时针方向旋转矩阵 90 度。

8) 给定一个数组 arr，其中只包含非负数。找出给定数组 arr 中最小大小的子数组，该子数组排序后，整个数组就会排序。

9) 给定一个数组 arr，大小为 sz，一个键 k，以及一个段大小 s，使得 s 完全整除 sz。检查数组 arr 的每个大小为 s 的段是否包含键 k。

10) 给定一个字符串，任务是找出该字符串在其字典序排序的排列中的排名。给定字符串的字符可能重复，也可能不重复。如果字符重复，则需要查看唯一的排列，然后确定排名。

11) 给定两个已排序的数组 arr 和 arr1。它们的长度可能相等，也可能不相等。找出这些给定数组的中位数。注意，不允许合并已排序的数组。

注意：我们在此处仅为解释目的而合并。在代码中，我们不会合并数组。

注意：线性搜索也可以在此处完成。但是，其时间复杂度将比二分查找高。

13) 给定一个数组 arr，大小为 s。数组 arr 按非递减顺序排序。此外，还给了一个整数 tar。找出整数 tar 是否存在于数组 arr 中。如果存在，找出整数 tar 的起始和结束索引。

14) 给定一个字符串 str。找出添加到字符串 str 以使其成为回文串所需添加的字符的最小值。字符必须添加到字符串的开头。

16) 给定一个整数数组 arr，其中每个数字都重复三次，只有一个数字除外，它只重复一次。返回只重复一次的数字。

17) 给定一个整数数组 arr。重新排列数组 arr，使得 arr[i] = arr[arr[i]]。空间复杂度必须是 O(1)。

注意：如果移除了 O(1) 空间复杂度条件，则问题将变得简单。可以创建一个与输入数组大小相同的数组，并将 a[a[i]] 的值复制到新创建的数组中。O(1) 空间复杂度使得问题变得棘手。

18) 给定一个正数 n。找出数字的二进制表示中存在的尾随零的数量。

19) 给定一个数字 n。找出第 n 个二进制表示为回文数的数字。

20) 给定一个整数数组 arr。大小为 w 的滑动窗口从数组的左侧向右侧移动。因此，一次只能观察 w 个数字。任务是找出每个窗口的最大值。观察以下示例。

21) 给定一个逆波兰表示法中的算术表达式。计算给定表达式。

22) 给定一个数字 n，表示代码中的总位数。格雷码总是从 0 开始。显示格雷码的序列。

23) 给定一个包含 n 个整数的数组 arr。找出所有唯一的三个数（x、y 和 z），使得 x + y + z = 0。注意，三元组的顺序无关紧要，即 y + z + x 或 y + x + z 与 x + y + z 相同。

25) 给定一个包含 n 个整数的数组 arr。x1, x2 ,..., xn 和一个整数 J。返回大小为 J 的所有窗口中存在的唯一数字的数量。

26) 给定一个只包含整数的数组 arr。找出数组 arr 中的 4 个索引，使得 arr[i] + arr[j] = arr[k] + arr[l]，其中 i、j、k 和 l 是这 4 个索引。如果存在多个答案，则显示任何一组满足给定条件的 4 个索引。注意，所有索引必须是唯一的。

27) 给定一个字符串 str 和一个字符串 X。查找 str 中的最小窗口，其中包含 X 中的所有字符。时间复杂度必须是线性的。注意，窗口的大小必须等于或大于字符串 X 的大小。

28) 给定一个长度为 l 的一维整数数组 arr。找出最长的子序列的长度，该子序列先递增然后递减。

30) 给定一个大小为 R * C 的棋盘，其中 R 代表总行数，C 代表总列数。创建矩阵 arr，使得 arr[x][y] 表示单元格(x, y) 上发生的皇后攻击次数，假设单元格中没有皇后。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

所有面试

公司面试

Technical Interview

Web Interview

PHP面试

.Net面试

Java Interview

Database Interview

编程面试题

1) 给定一个大小为 s 的整数数组 arr。现在，检查是否存在至少一个元素，该元素严格小于其右侧的所有元素，并且大于其左侧的所有元素。如果存在，则返回 true；否则，返回 false。忽略给定数组的边界元素。

2) 给定一个只读数组 arr，大小为 s，使得数组中的每个元素都不超过 s。此外，在数组中，除了 a1 以外，每个元素都只出现一次，a1 出现了两次，因此 a2 丢失了。找出 a1 和 a2 的值。注意，只读意味着不允许修改输入数组。

3) 给定一个只读数组 arr，大小为 s。找出可以将数组 arr 分成 3 个部分的方法，使得每个部分的总和相等。

4) 给定一个由 N 个整数 X1, X2, X3, ...., Xn 组成的数组 arr。你必须返回 f(a1, a2) 的最大值，其中 0 ≤ a1, a2, < N。给定 f(a1, a2) = |arr[a1] - a[a2]| + |a1 - a2|，其中 |y| 表示 y 的绝对值。

5) 找到由数组 arr 的元素组成的数字的下一个排列，大小为 s，而不改变元素的顺序。

6) 给定一个数组 arr，其中只包含非负数。使用给定数组 arr 中的所有非负数创建最大的数字。

7) 给定一个包含 m 行和 m 列的二维矩阵。任务是以顺时针方向旋转矩阵 90 度。

8) 给定一个数组 arr，其中只包含非负数。找出给定数组 arr 中最小大小的子数组，该子数组排序后，整个数组就会排序。

9) 给定一个数组 arr，大小为 sz，一个键 k，以及一个段大小 s，使得 s 完全整除 sz。检查数组 arr 的每个大小为 s 的段是否包含键 k。

10) 给定一个字符串，任务是找出该字符串在其字典序排序的排列中的排名。给定字符串的字符可能重复，也可能不重复。如果字符重复，则需要查看唯一的排列，然后确定排名。

11) 给定两个已排序的数组 arr 和 arr1。它们的长度可能相等，也可能不相等。找出这些给定数组的中位数。注意，不允许合并已排序的数组。

注意：我们在此处仅为解释目的而合并。在代码中，我们不会合并数组。

注意：线性搜索也可以在此处完成。但是，其时间复杂度将比二分查找高。

13) 给定一个数组 arr，大小为 s。数组 arr 按非递减顺序排序。此外，还给了一个整数 tar。找出整数 tar 是否存在于数组 arr 中。如果存在，找出整数 tar 的起始和结束索引。

14) 给定一个字符串 str。找出添加到字符串 str 以使其成为回文串所需添加的字符的最小值。字符必须添加到字符串的开头。

16) 给定一个整数数组 arr，其中每个数字都重复三次，只有一个数字除外，它只重复一次。返回只重复一次的数字。

17) 给定一个整数数组 arr。重新排列数组 arr，使得 arr[i] = arr[arr[i]]。空间复杂度必须是 O(1)。

注意：如果移除了 O(1) 空间复杂度条件，则问题将变得简单。可以创建一个与输入数组大小相同的数组，并将 a[a[i]] 的值复制到新创建的数组中。O(1) 空间复杂度使得问题变得棘手。

18) 给定一个正数 n。找出数字的二进制表示中存在的尾随零的数量。

19) 给定一个数字 n。找出第 n 个二进制表示为回文数的数字。

20) 给定一个整数数组 arr。大小为 w 的滑动窗口从数组的左侧向右侧移动。因此，一次只能观察 w 个数字。任务是找出每个窗口的最大值。观察以下示例。

21) 给定一个逆波兰表示法中的算术表达式。计算给定表达式。

22) 给定一个数字 n，表示代码中的总位数。格雷码总是从 0 开始。显示格雷码的序列。

23) 给定一个包含 n 个整数的数组 arr。找出所有唯一的三个数（x、y 和 z），使得 x + y + z = 0。注意，三元组的顺序无关紧要，即 y + z + x 或 y + x + z 与 x + y + z 相同。

25) 给定一个包含 n 个整数的数组 arr。x1, x2 ,..., xn 和一个整数 J。返回大小为 J 的所有窗口中存在的唯一数字的数量。

26) 给定一个只包含整数的数组 arr。找出数组 arr 中的 4 个索引，使得 arr[i] + arr[j] = arr[k] + arr[l]，其中 i、j、k 和 l 是这 4 个索引。如果存在多个答案，则显示任何一组满足给定条件的 4 个索引。注意，所有索引必须是唯一的。

27) 给定一个字符串 str 和一个字符串 X。查找 str 中的最小窗口，其中包含 X 中的所有字符。时间复杂度必须是线性的。注意，窗口的大小必须等于或大于字符串 X 的大小。

28) 给定一个长度为 l 的一维整数数组 arr。找出最长的子序列的长度，该子序列先递增然后递减。

30) 给定一个大小为 R * C 的棋盘，其中 R 代表总行数，C 代表总列数。创建矩阵 arr，使得 arr[x][y] 表示单元格(x, y) 上发生的皇后攻击次数，假设单元格中没有皇后。

相关帖子

2025年顶尖40项云计算面试题及答案

Python编码面试题

Java应届生面试题

Docker面试题

2025年顶尖40项网络安全面试题及答案

统计学面试题

2025年顶尖30项Microsoft Azure面试题

C++异常处理面试题

Java 8面试题

计算机网络口试题

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器