Java 编程挑战

17 Mar 2025 | 阅读 17 分钟

Java 编程挑战 是我们需要通过逻辑来解决的复杂问题，并将该逻辑实现到任何编程语言中。解决编程挑战可以培养逻辑思维和分析能力。如果您正在准备面试，则必须至少解决一次这些编程挑战。建议在直接查看解决方案之前，先理解问题并推导出您的解决方案或方法。

在本节中，我们将讨论一些在面试的第二轮（即编码轮）中经常被问到的最重要的编程挑战。

货架安装问题
老鼠进洞问题
硬币找零问题
直线上的最大点数
金条问题

注意：一个问题可以有多种解决方法，因此逻辑和方法可能与其他解决方案或方法不同。在本节中，我们使用 Java 编程语言来解决问题。

让我们一个一个地解决这些挑战。

货架安装问题

问题陈述

已知墙壁的长度为 'w'，两个货架的长度分别为 'm' 和 'n'。要求找出需要使用的每种类型的货架数量，以使墙壁被覆盖，且留下的空白空间最少。两个货架中较大的那个价格更便宜，因此更受青睐。然而，首要任务是最小化空白空间。

让我们通过一个例子来理解问题陈述。

示例

假设墙壁的长度为 7 米 (w = 7)，第一个货架的长度为 3 米 (m = 3)，第二个货架的长度为 5 米 (n = 5)。我们需要找到第一种和第二种货架的数量。设数量分别为 x 和 y。

通过数学方法求解，可以得出以下方程：

7 = 3x + 2y

要解决此类方程，我们进行试错法。

最佳最优解是第三种，即 x = 1 且 y = 2，原因有两个：

空白空间为零。
第二个货架（长度较大且价格便宜）的数量更多。因此，也考虑了成本因素。

3 * 1 + 2 * 2 = 7

空白空间 = 7 - 7 = 0 (墙壁长度 - (第一种和第二种货架的总长度))

让我们取另一组值：

w = 29, m = 3, n = 9

29 = 3x + 9y

0 * 3 + 3 * 9 = 27

X = 0, Y = 3

空白尺寸 = 29 - 27 = 2

让我们取另一组值：

w = 24, m = 4, n = 7

24 = 4x + 7y

6 * 4 + 0 * 7 = 24

X = 6, Y = 0

空白尺寸 = 24 - 24 = 0

这里需要注意的是，较大的货架比较小的货架便宜的约束条件。从 0 开始，我们增加大尺寸货架的数量，直到它们能被安装。在每种情况下，计算空白空间，最后存储最小化空白空间的值。如果两种情况下的空白空间相同，则优先选择大尺寸货架数量更多的方案。

FittingShelves.java

public class FittingShelves{
    // w is the length of the wall
    // m is the length of the first shelf
    // n is the length of the second shelf
    static void shelves( int w, int m, int n )
    {
        // Assuming m is always smaller than n
        // x is the number of shelves of m length
        // y is the number of shelves of n length
        // emp is the number of remaining spaces
        // Keeping y = 0 and solving the equation so formed (as in the above example) for x, the values shall be initialized as follows
        // empty spaces can be calculated as the remainder of the division of length of wall and length of 1st shelf for which we calculated the value of x
        int x = w / m, y = 0, emp = w % m, min_emp = w ;
        // storing the values of x, y and emp
        int num1 = x, num2 = y ;
        min_emp = emp ;        
        // maximum value of n can-not be more than the length of the wall 'w', therefore iterating the loop uptil the value of w
        while ( w >= n ) 
        {
            // incrementing the value of y to calculate x against different values of y (1, 2, 3, ...)
            y += 1 ;
            w = w - n ;
            // calculating the value of x. In the remaining part, any number of shelves of length can be placed
            x = w / m ;
            emp = w % m ;
            if( emp <= min_emp)
            {
                num1 = x ;
                num2 = y ; 
                min_emp = emp ;
            }
        }
        // printing the values on console
        System.out.println( " X : " + num1 + " Y : " + num2 + " Empty Space : " + min_emp ) ;
    }
    public static void main( String[ ] args )
    {
        // initializing the values 
        int w = 24, m = 3, n = 5 ;
        // calling the function ' shelves ' with the above values
        shelves( w, m, n ) ; 
        // initializing different set of values
        w = 7 ;
        m = 3 ;
        n = 5 ;
        // calling the function 'shelves' with the above values
        shelves( w, m, n ) ;
    }
}

输出

X : 3 Y : 3 Empty Space : 0
X : 2 Y : 0 Empty Space : 1

老鼠进洞问题

问题陈述

有 x 只老鼠和 x 个洞排成一条直线。每个洞只能容纳 1 只老鼠。老鼠的位置使其可以停留在当前位置，或从 x 向右移动一步到 x + 1，或从 x 向左移动一步到 x - 1。进行任何这些移动只需要 1 分钟。将老鼠分配到洞中，以便最后一只老鼠进入洞的时间最小化。

示例

假设老鼠的位置是：4, -4, 2，洞的位置是：4, 0, 5。我们需要以最小化整个过程所需时间的方式将老鼠分配到洞中。

为方便理解，我们创建两个数组，一个存储老鼠的位置，另一个存储洞的位置。

要计算老鼠从其各自位置移动到洞位置所需的时间，我们只需遍历中间的位置。简而言之，我们减去老鼠和洞的位置。

情况 1：老鼠从位置 4 移动到洞的位置 4

时间：4 - 4 = 0

情况 2：老鼠从位置 -4 移动到洞的位置 0

时间：0 - (-4) = 0

情况 3：老鼠从位置 2 移动到洞的位置 5

时间：5 - 2 = 3

显然，计算出的时间中的最大值为 4。因此，可以说分配所有老鼠到洞中至少需要 4 分钟。

该问题可以使用贪心算法解决。我们可以通过将每只老鼠放到最近的洞来最小化时间。这可以通过对老鼠和洞的位置进行排序来实现。通过这种方式，我们可以将老鼠放在洞列表中合适的位置。然后，我们可以找到老鼠和相应洞口位置之间的最大差值。

算法

最好将老鼠的位置按升序排序。
对洞的位置进行排序
循环 i = 1 到 N：根据 |老鼠(i) - 洞(i)| 的值更新答案。它应该是所有差值中的最大值。
设 i1 < i2 为两个老鼠的位置，设 j1 < j2 为两个洞的位置。

max(|i1- j1|, |i2 - j2|) <= max(|i1 - j2|, |i2 - j1|)，

其中 '|a - b|' 表示 (a - b) 的绝对值。

MiceHoles.java

import java.util.* ;   
public class MiceHoles
{ 
    /* this function computes minimum time required to place the mice to a hole and returns the same */
    public int Holes( ArrayList< Integer > mice, ArrayList< Integer > holes ) 
    { 
        /* check if the size of mice and holes is same or not as this is a constraint of the question */
        if ( mice.size( ) != holes.size( ) ) 
           return -1 ; 
        // sorting the list of mice and holes in an ascending order
        Collections.sort( mice ) ; 
        Collections.sort( holes ) ;    
        int size = mice.size( ) ; 
        /* computing the difference between the mice and holes at each position as per our solution explained in the example */
        int max = 0 ;         
        for ( int i = 0; i < size; i++ ) 
        /* using the abs function of the math class to print the positive or absolute value */
            if ( max < Math.abs( mice.get( i ) - holes.get( i ) ) ) 
                max = Math.abs( mice.get( i ) - holes.get( i ) ) ; 
  
        // returning the computed ' max ' value
        return Math.abs( max ) ; 
    } 
    public static void main( String[ ] args ) 
    { 
        miceHoles mH = new miceHoles( ) ;         
        // creating any array list of type integer
        ArrayList< Integer > mice = new ArrayList< Integer >( ) ; 
        // adding the values in the arraylist using the add( ) method
        mice.add( 5 ) ; 
        mice.add( 2 ) ; 
        mice.add( 3 ) ; 
        // creating another array list of type integer
        ArrayList< Integer > holes = new ArrayList< Integer >( ) ; 
        holes.add( 4 ) ; 
        holes.add( 0 ) ; 
        holes.add( 5 ) ; 
        System.out.println( " The last mouse gets into" + 
         " the hole in time : " + mH.Holes( mice, holes ) ) ; 
    } 
}

输出

The last mouse gets into the hole in time: 2

硬币找零问题

给定一个值 N，如果我们想为 N 美分找零，并且我们有无限供应的每种硬币 C = {C1, C2, …., Cm}面值的硬币。有多少种方法可以找零？硬币的顺序无关紧要。

示例 1

设总和为 N = 5，硬币类型为 C = {1, 2}

对于给定的值，必须排列可能的找零组合，同时牢记找零的总和必须为 5。

{1, 1, 1, 1, 1}

{1, 1, 1, 2}

{1, 2, 2}

我们可以生成 3 种组合，其中硬币可以重新排列以给出总和 5。因此，输出必须是 3。

示例 2

设 N = 4 且 C = {1, 2, 3}

对于给定的值，必须排列可能的找零组合，同时牢记找零的总和必须为 5。

{1, 1, 1, 1}

{1, 1, 2}

{2, 2}

{1, 3}

我们可以生成 4 种组合，其中硬币可以重新排列以给出总和 5。因此，输出必须是 4。

现在，为了找到总计数，我们可以将解决方案划分为两个子集的子解决方案：

包含至少一个 (i - 1)^th 类型硬币（最后一个硬币）的解决方案
不包含 (i - 1)^th 类型硬币（或最后一个硬币）的解决方案

因此，我们需要创建一个函数，例如 totalWays(C[ ], i , n)，它将通过计算解决方案的数量来计算总数的多少种方法，然后我们可以返回 totalWays(C[ ], i - 1, n) 和 totalWays(C[ ], i, n - C[ i - 1 ]) 的总和。

该问题具有最优子结构性质，因为我们可以通过将其分解为子问题并首先解决它们来解决问题。

现在，我们将使用上述递归结构来实现此硬币找零问题的解决方案。

算法： -

在这里，我们给出了每种给定价值的硬币，它可以出现任意次数。这意味着此处允许重复，这称为无界背包。

现在，我们对于特定类型的硬币有两种选择：

包含它
排除它

但我们必须记住，第一种选择，即包含过程，不是只进行一次，而是我们可以包含任何类型的硬币和任何数量的硬币，直到
N < 0。

所以，基本上，如果我们处于 C[i-1]（即最后一个硬币），我们可以包含该硬币的任意数量的实例（这是无界包含），即调用 totalWays(C, i , n - C[i-1]) 直到我们得到

n <= 0;

然后我们移到下一个类型的硬币，即 C[i-2]。

但是请记住，在移到 C[i-2] 硬币（倒数第二个硬币）之后，我们不能再回头，也不能对 C[ i - 1 ] 做任何选择，即 totalWays(C, i - 1, n)。

最后，我们将两个子问题的解决方案相加，
即 totalWays(C, i - 1, n) + totalWays(C , i , n - C[i-1])；这是我们需要找到的答案。

CoinChange.java

class CoinChange
{
    //  creating a recursive function which returns the total count of all the possible 
    // ways we can get the sum n from the given coins

    //  C[ ] contains all the types of coins
    //  i is the count of types of coins
    //  n is the total sum given to us
    static int totalWays( int C[ ], int i, int n )
    {
        // If n is equals to 0 then we have 1 solution found
        // ( do not include any coin )
        if ( n == 0 )
            return 1 ;
        // If the n is less than 0 then solution doesn't exist as in this case the sum of 
        // coins have become greater than n itself and hence, not the solution 
       // so, return 0
        if ( n < 0 )
            return 0 ;
        // If we don't have coins ( C[ ] is empty ) but still have n greater than 0 
        // then also we don't have the solution, so return 0
        if ( i <= 0 && n >= 1 )
            return 0 ;
        // we return the count of total ways by adding: -
        // 1. the solution computed by including c[ i - 1 ] element ( i.e, last element )
        // 2. the solution computed by excluding C[ i - 1 ] element
        return totalWays( C, i - 1, n ) +
               totalWays( C, i, n - C[ i - 1 ] ) ;
    }
    public static void main( String args[ ] )
    {
        // arr[ ] contains all the types of coins that we need to use
        int arr[ ] = { 2, 3 } ;
        // m is the count of coins we need to use
        int i = arr.length ;
        // printing the result returned by calling the
        System.out.println( totalWays( arr, i, 6 ) ) ;
    }
}

输出

以下是给定输入的递归树。

N = 6, C = {2, 3}

计算直线上的最大点数

问题陈述

给定二维平面上的 N 个点，坐标为 (x, y) 对，我们需要找到可以位于同一条直线上的最大点数。

示例

输入：points[ ] = { -3, 5 }, { 0, 0 }, { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 8 }

位于同一条直线上的最大点数是 {0, 0}, {1, 1}, {2, 2}, {3, 3}。因此，计数为 4。

首先取一个点，例如 'a'，然后计算它与我们给出的其他点的斜率。之后，我们将使用 HashMap 来记录所有斜率，然后检查有多少个点具有相同的斜率，这将帮助我们找出有多少个点与 'a' 位于同一条直线上，并最终更新 'count' 的值，即同一直线上的最大点数。

我们将对每个点重复此操作，并继续更新 'count' 的值，如果我们发现任何其他直线上的点数比之前记录的要多。

注意：当我们通过公式 (y2 - y1) / (x2 - x1) 计算斜率时，可能会遇到一个问题，即当结果小于 '1' 时，因为在这种情况下斜率将趋近于 0（零），这不是正确的答案。因此，为了克服这个问题，我们将使用一个内置的数学函数，即 "Math.atan"，它将帮助我们避免这个问题。

此算法的时间复杂度为 O(n²)。

MaxPoint.java

import java.util.*;
class MaxPoint {
  // creating a function that takes in x-coordinates array
  // and y-coordinates array as int a[ ] and int b[ ] respectively
  // and returns the count of maximum points on a straight line
    public static int MaximumPoints( int s[ ], int t[ ] ) {  
    // initializing all the required values
    HashMap< Double, Integer > map = null ;
    int count = 0, ov = 0, same = 0, maximum_current = 0 ;
    double slope = 0, x, y ;
    // starting an outer loop which will iterate over 
    // x-coordinates, i.e., a[ i ]
    for ( int i = 0 ; I < s.length ; i++ ) {    
    // instantiating the HashMap which will be required
    // for recording every slope with respect to a 
    // pair of coordinates
      map = new HashMap< >( ) ;
      same = 0 ;
      count = 0 ;
      // starting the inner loop which will iterate over
      // y-coordinates, i.e. b[ j ]
      // setting j = i since we need not to find the slopes
      // for values that we've already found
      for( int j = i ; j < t.length ; j++ ) {        
        // if i == j  then they are a pair of coordinates ( x, y )
        // so, increment same as they will always be a part
        // of the coordinates on a same line
        if( i == j )
          same++ ;
        // else check if ( x2 - x1 is 0 )
        // and if 0 then we represent the infinity with
        // maximum integer value
        else{
          if( s[ j ] - s[ i ] == 0 ) {
          slope = Integer.MAX_VALUE ;
          continue ;
          }
          // here, we are calculating x = x2 - x1 
          // and y = y2 - y1 and then finally the slope
          // as ( y / x )          
          else {
            x = s[ j ] - s[ i ] ;
            y = t[ j ]- t[ i ] ;
            slope = Math.atan( y / x ) ; } 
            // if the map contains the slope as key already
            // then get the value of it and increment it and
            // again, store it back
            if( map.containsKey( slope ) ) {
              ov = map.get( slope ) ;
              map.put( slope, ov + 1 ) ;
            }   
            // else if the map doesn't contain the slope
            // then put this new key, value pair in the map 
            else map.put( slope, 1 ) ;
        }
      }
      // now, retrieving all the key, values from the map
      // and updating the new count value
      Set< Map.Entry< Double, Integer > > entries = map.entrySet( ) ;
        for( Map.Entry< Double, Integer > entry: entries ) {
          count = Math.max( count,entry.getValue( ) ) ;
        }
       // finally, updating the value of max_curr
       maximum_current = Math.max( maximum_current, count+same ) ;
    }
    return maximum_current ;
  }
  public static void main( String[ ] args ) {
  int count = 0 ;  
  // a[ ] is for x-coordinates
  // b[ ] is for y-coordinates
  int a[ ] = { -1, 0, 1, 2, 3, 3 } ;
  int b[ ] = { 1, 0, 1, 2, 3, 4 } ;
  count = MaximumPoints( a, b ) ;
  System.out.print( " Maximum points are " +count ) ;
  }
}

输出

Maximum points are 4

金条谜题

问题陈述

一个人为雇主工作了七天，作为报酬，他会得到一根金条。金条被分成七块，并像链条一样连接在一起。每天工作结束时会给他一块金子。为了能够每天支付他一块金子，需要对金条链进行最少次数的切割，以及在哪里切割？

解决方案

为了解决这个问题，我们将使用一个数学公式，即2ⁿ - 1。

这里，'n' 是一个从 '1' 到 'x' 的数字。

并且，2^x - 1 应该小于我们可以拥有的金块总数。

因此，在我们的例子中，2^x - 1 < 7，因为我们可以拥有的金块总数为 7。

我们将使用上述方法对金条链进行切割，以获得最少次数的切割来支付该人。

所以，第一次切割 'n' 是 1： -

2¹ - 1 => 2 - 1 = 1

因此，我们将第一次切割在第一段之后进行，即在第一段和第二段之间。

第二次切割 'n' 是 2： -

2² - 1 => 4 - 1 = 3

因此，我们将第二次切割在第三段之后进行，即在金条的第三段和第四段之间。这样就剩下四段没有切割（第四段到第七段）。

现在，第三次切割 'n' 是 3： -

2³ - 1 => 8 - 1 = 7

现在，我们知道 2ⁿ - 1 < 7，所以这次切割不适用。

因此，我们需要对金条进行的最小切割次数为 2，并且这些切割将分别在金条的第一段（第一段和第二段之间）和第三段（第三段和第四段之间）之后进行。

解释

设 A = 第一段（仅 1 段）

设 B = 第二段和第三段（2 段）

设 C = 第四段到第七段（4 段）

第一天，我们将 A（即第一段）交给这个人。

第二天，我们将 B（即 2 段）给他，同时将 A（1 段）从他那里拿回来。这样，在第二天结束时，他手中只剩下 2 段（B）。

第三天，我们将 A 再次给他。现在，他拥有 A + B（即总共 3 段）。

第四天，我们将 C（4 段）给他，但会拿回 A 和 B。所以，他在第四天结束时拥有 4 段。

第五天，我们将 A 给他。

第六天，我们将 B 给他，但会拿回 A。现在，他拥有 C + B（即 6 段）。

第七天，我们将 A 给他，完成谜题。

GoldBarPuzzle.java

class GoldBarPuzzle {
    public static int cutsOnBar( int segments ) {
        int n = 0 ;
        int count = 1 ;
        while ( (Math.pow( 2, count ) - 1 ) < segments ) {
            n = n + 1 ;
            ++count ;
        }
        return n ;
    }
    public static void main( String[ ] args ) {
        int seg = 7 ;
        System.out.print( cutsOnBar( seg ) ) ;
    }
}

输出

下一主题Java URL Encoder

Java 编程挑战

注意：一个问题可以有多种解决方法，因此逻辑和方法可能与其他解决方案或方法不同。在本节中，我们使用 Java 编程语言来解决问题。

货架安装问题

老鼠进洞问题

硬币找零问题

计算直线上的最大点数

金条谜题

联系信息

关注我们

教程

面试题

在线编译器

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

Java Conversion

Java Misc

Java 编程挑战

注意：一个问题可以有多种解决方法，因此逻辑和方法可能与其他解决方案或方法不同。在本节中，我们使用 Java 编程语言来解决问题。

货架安装问题

老鼠进洞问题

硬币找零问题

计算直线上的最大点数

金条谜题

相关帖子

Java 中用于中序遍历的 Morris 遍历

DoubleBuffer rewind() Method in Java with Examples

如何在 Java 中检查字符串是否只包含 ASCII 字符

Emirp Number in Java

Java Atomic

Java 中的 3N+1 问题

Merge Two Arrays in Java

如何在 Java 中添加两个日期

Java 中素数整数子数组的最大总和

ClassCast Exception in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器