面试时碰到的Java 算法问题前 15 名（二）-阿里云开发者社区

动态规划：记忆和制表

动态规划是现代开发人员的核心算法技术，因为它专注于将问题分解为更简单的子问题以实现优化。子问题的解越优，整体解也越优。

[这是递归] 解决问题的基础，因此，任何优秀的面试官都会问这个问题。

动态规划问题可以通过自上而下的方法或自下而上的方法来解决，分别使用Memoization或Tabulation。面试官可能会要求提供一个，也可能由您决定。

下面我们将看到每个示例，以便您为任何替代方案做好准备。

8. 背包问题：

问题陈述：

想象一下，您是背着背包的冒险家，正在查看巨龙的宝库。

N给定两个表示项目的权重和利润的整数数组，实现一个函数knapSack()来找到这些项目的子集，这些项目将给我们最大的利润，而它们的累积权重不会超过给定的数字capacity。每个项目只能选择一次，这意味着当我们到达它时，我们可以跳过它或将它放入背包中。

将自上而下的方法与记忆结合使用。

class KnapsackProblem
{ 
    static int Knapsack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity) 
    {
        // write your code here
        return -1;
    }
};
复制代码

解决方案：

class KnapsackProblem
{ 
  public static int knapsackRecursive(int [][] lookupTable, int profits[], int profitsLength, int weights[], int weightsLength, int capacity, int currentIndex) {
    // base checks  
    if (capacity <= 0 || currentIndex >= profitsLength || currentIndex < 0 || weightsLength != profitsLength)
      return 0;
    // if we have already solved the problem, return the result from the table  
    if (lookupTable[currentIndex][capacity] != 0)
      return lookupTable[currentIndex][capacity];
    // recursive call after choosing the element at the currentIndex
    // if the weight of the element at currentIndex exceeds the capacity, we shouldn't process this
    int profit1 = 0;
    if (weights[currentIndex] <= capacity)
      profit1 = profits[currentIndex] + knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength,
        capacity - weights[currentIndex], currentIndex + 1);
    // recursive call after excluding the element at the currentIndex
    int profit2 = knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, currentIndex + 1);
    lookupTable[currentIndex][capacity] = Math.max(profit1, profit2);
    return lookupTable[currentIndex][capacity];
  }
  public static int knapSack(int profits[], int profitsLength, int weights[], int weightsLength, int capacity) 
  {
    int lookupTable[][] = new int [profitsLength][];
    for (int i = 0; i < profitsLength; i++) {
      lookupTable[i] = new int[capacity + 1];
      for (int j = 0; j < capacity + 1; j++)
        lookupTable[i][j] = 0;
    }
    return knapsackRecursive(lookupTable, profits, profitsLength, weights, weightsLength, capacity, 0);
  }
  public static void main(String args[]) 
  {
    int profits[] = {1, 6, 10, 16}; // The values of the jewelry
    int weights[] = {1, 2, 3, 5}; // The weight of each
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4,  7));
    System.out.println("Total knapsack profit ---> " + knapSack(profits, 4, weights, 4, 6));
  }
};
复制代码

解决方案分解：

时间复杂度： O(NC)*

该函数在函数内部knapSack创建了一个lookupTable存储最大容量可以获得的最大值的函数（第 29-35 行）。该函数调用辅助函数knapsackRecursive（第 36 行）。它返回仅使用第一个项目可以获得的最大值i，即在currentIndex保持总重量不超过重量的情况下的项目。

我们有两个不同的值（capacity和currentIndex），所以我们可以使用一个二维数组来存储递归函数中所有已解决子问题的结果knapsackRecursive。

我们需要存储每个子数组的结果，即每个可能的索引和每个可能的容量。如果lookupTable[currentIndex][capacity]之前已经计算过（第 10 行），则立即返回该值（第 11 行）。

否则，我们递归调用该函数：

使用项目，将结果保存在profit1（第 17 行）中。
没有该项，将结果保存在变量中profit2（第 21 行）。

在两者中，我们返回更大的结果（如第 23-24 行所做的那样）。

9.楼梯问题

问题陈述：

一个孩子跑上有n台阶的楼梯，一次可以跳 1 步、2 步或 3 步。实现一个函数来计算孩子可以跑上楼梯的可能方式的数量。

尝试使用带制表的自下而上方法来解决这个问题。

class StairCaseProblem
{
    public static int countWays(int n) 
    {
        // write your code here
        return -1;
    }
};
复制代码

解决方案：

class StairCaseProblem
{ 
  public static int countWays(int n) 
  { 
    int[] lookupTable = new int[n+1]; // Initialize lookup table
    lookupTable[0] = 1; // Setting the first three values
    lookupTable[1] = 1;
    lookupTable[2] = 2;
    for (int i = 3; i <= n; i++) 
        lookupTable[i] = lookupTable[i-1] + lookupTable[i-2] + lookupTable[i-3]; // Fill up the table by summing up previous two values
    return lookupTable[n]; 
  } 
  public static void main(String args[]) 
  {
    System.out.println(countWays(3));
  }
};
复制代码

解决方案分解：

时间复杂度： O(n)

我们知道：

到达零步的方法总数为 1（第 6 行）。
到达第一步的方式总数为 1（第 7 行）。
到达第二步的方法总数为 2（第 8 行）。

因此，我们用这三个值填充lookupTable（第 6-8 行）。

我们知道到达任何楼梯的总方式数n是走 1、2 或 3 步。因此，到达第 th 楼梯的方式总数n将等于到达 th 台阶的方式总数[n-1]、到达 th 台阶的方式数量[n-2]和到达 th 台阶的方式数量之和[n-3]。

lookupTable因此，通过对到达前三个步骤的方法求和来计算到达第 n 步的方法总数来填充的其余值（第 11 行）。

然后从（第 13 行）返回所需的值lookupTable。

贪心算法：局部最大化

贪婪是一种算法技术，一次构建一个解决方案，在每个选择中优先考虑直接、明显的好处。换句话说，它寻求最大化利润（正）并最小化成本（负）。

该技术基于局部最优选择将有助于全局最优解的想法。下面我们将看到一些面试问题，以帮助您在需要时使用此技术。

10：换机问题

问题陈述：

你必须制造这样一种零钱机，它只返回硬币形式的零钱。

你有无限数量的 25 美分、10 美分、5 美分和 1 美分硬币。用户将输入任何金额。对于每笔金额，您必须退还最少数量的硬币！

class ChangeMachine 
{
  // a public collection of available coins
  public static int [] coins = {25, 10, 5, 1}; 
  public static  ArrayList<Integer> getMinCoins(int amount)  // function to recieve change in the form of coins
  {
    ArrayList<Integer> change = new ArrayList<Integer>();
    // your awesome code goes here
    return change;
  }
}
复制代码

解决方案：

class ChangeMachine {
 public static int[] coins = {25, 10, 5, 1}; // a public collection of available coins
 // function to recieve change in the form of coins
 public static ArrayList < Integer > getMinCoins(int amount) {
  // an array list to store all the coins
  ArrayList < Integer > change = new ArrayList < Integer > ();
  for (int i = 0; i < coins.length; i++) // traverse through all available coins
  {
   while (amount >= coins[i]) // keep checking if the amount is greater than the max coin
   {
    amount -= coins[i]; // subtract the maximum coin selected from the total amount in every iteration
    change.add(coins[i]); // add the coin to the list of 'change'
   }
  }
  return change; // return the list containing all the change
 }
    public static void main(String args[]) 
    {
        // Play around with this amount to see how many coins you get!
        int amount = 1;
        System.out.println(amount + " --> " + getMinCoins(amount)); 
        amount = 17;
        System.out.println(amount + " --> " + getMinCoins(amount));   
        amount = 33;
        System.out.println(amount + " --> " + getMinCoins(amount)); 
        amount = 99;
        System.out.println(amount + " --> " + getMinCoins(amount));          
    }
}
复制代码

解决方案分解：

时间复杂度： O(n 2 )

第 3 行：给出一个包含可用硬币集的公共数组。
第6行：函数getMinCoins()定义；它的返回类型为 ArrayList，参数为 int amount。
第 9 行：分配 Integer 类型的 ArrayList 来存储变化。
第 10-17 行：for 循环int[]coins从头到尾遍历数组（按降序排列）。
第 12 行：由于第一个索引 coins 有 maximum 元素，所以在 while 条件中比较这个数量是否大于 max coin。
第 14 行：如果是，则从给定的数量中减去最大价值的硬币。
第 15 行：将此硬币添加到更改列表中。
第 17 行：当最大的硬币变得大于剩余数量时，while 循环中断并且递增的值i以移动到下一个（较小值）硬币。
不断迭代这个 for 循环，直到剩余数量不能再被可用硬币细分。

11：找到埃及分数

问题陈述：

每个正分数都可以表示为其唯一单位分数的总和。如果分子为 1 且分母为正整数，则分数为单位分数。例如，1/3是单位分数。这种表示称为埃及分数。

class Fraction {
 public static void printEgyptianFraction(int numerator, int denominator) {
  //write your code here
  int n = -1; //calculate the correct value 
  System.out.print("1/" + n + " , "); //printing out your solution
 }
}
复制代码

解决方案：

class Fraction
{
    public static void printEgyptianFraction(int numerator, int denominator) 
    {
      //if either numerator or denominator is zero
      if (denominator == 0 || numerator == 0){
        return;
      }
      //numerator divides denominator -> fraction in 1/n form
      if (denominator % numerator == 0) {
        System.out.print("1/" + denominator / numerator);
        return;
      }
      //denominator can divide numerator -> number not a fraction 
      if (numerator % denominator == 0) {
        System.out.println(numerator / denominator);
        return;
      }
      //if numerator greater than denominator 
      if (numerator > denominator) {
        System.out.println(numerator / denominator + " , ");
        printEgyptianFraction(numerator % denominator, denominator);
        return;
      }
      //denominator  greater than numerator here
      int n = denominator / numerator + 1;
      System.out.print("1/" + n + " , ");
      //call function recursively for remaining part  
      printEgyptianFraction(numerator * n - denominator, denominator * n);
}
}
class Main{
  public static void main(String[] args){
  //Example 1
  int numerator = 6, denominator = 14;
  System.out.print("Egyptian Fraction Representation of " + numerator + "/" + denominator + " is\n ");
  Fraction.printEgyptianFraction(numerator, denominator);
  System.out.println();
  //Example 2
  numerator = 2;
  denominator = 3;
  System.out.print("Egyptian Fraction Representation of " + numerator + "/" + denominator + " is\n ");
  Fraction.printEgyptianFraction(numerator, denominator);
  }
}
复制代码

解决方案分解：

时间复杂度： O(log_3)

对于形式为n/d的给定数字，其中 d > n，首先找到最大可能的单位分数，然后对剩余部分执行递归。

例如，考虑6/14。我们首先找到14/6的上限，即 3，因此第一个单位分数变为1/3。现在从6/14中减去1/3并重复计算6/14 – 1/3。******

我们使用贪心算法是因为我们要将分数化简为分母大于分子的形式，分子不整除分母。

方法是找到我们能找到的最大单位分数，然后从剩余分数中减去它。做减法总是减少这组单位分数，但它永远不会重复一个分数并最终会停止，这就是为什么我们称这种方法为贪心。

分而治之：

与动态规划类似，分而治之算法通过将问题分解为子问题来工作。它们的不同之处在于，分而治之算法解决每个子问题，然后组合结果形成最终解决方案，而动态规划中的子问题是完全独立的。

这是将在您的编码面试中测试的另一种主要算法类型。

12：欧氏算法问题

问题陈述：

给定两个整数a和b，计算将它们都整除而不留余数的最大数 (GCD)。

class EuclideanAlgorithm
{ 
    public static int GCD(int a, int b) 
    {
        // your awesome code goes here!
        return -1;
    }
} 
复制代码

解决方案：

class EuclideanAlgorithm
{ 
    public static int GCD(int a, int b) 
    {
        if (a == 0)
            return b;
        return GCD(b % a, a);
    }
    // Driver Program 
    public static void main(String[] args) 
    { 
        Random rand = new Random(); // built-in funtion provided by the library java.util.Random in Java for Random Number Generation
        int a = rand.nextInt(50);   // use random inputs 
        int b = a * rand.nextInt(10) + rand.nextInt(35);  
        System.out.println("GCD(" + a +  " , " + b+ ") = " + GCD(a, b)); 
        a = (rand.nextInt(150)%50); b = (rand.nextInt(200)%5);   // you can play around with the range of random numbers to see different outputs
        System.out.println("GCD(" + a +  " , " + b+ ") = " + GCD(a, b)); 
        a = rand.nextInt(10); b = rand.nextInt(10); 
        System.out.println("GCD(" + a +  " , " + b+ ") = " + GCD(a, b)); 
    }
} 
复制代码

解决方案分解：

时间复杂度： O(log min(a,b))

第 5 行：算法首先检查第一个数字（通过递归调用a获得）是否为 0。b %ab%a
第 6 行：如果是，则返回b。
第 7 行：否则，我们进行下一次递归调用GCD(b % a, a)。

13：排序数组中缺少数字

问题陈述：

给定一个从开始的连续整数数组x，中间缺少一个整数，以及数组的大小，找到缺少的数字！

class MissingNumber 
{
    public static int missingNumber(int arr[], int size) 
    {  
        // your awesome code here
        return Integer.MIN_VALUE;
    }
}
复制代码

解决方案：

class MissingNumber {
 // Performing a binary search like technique to find the missing number in the array 
 public static int missingNumber(int arr[], int size) {
  int leftLimit = 0, rightLimit = size - 1; // initialize limits
  // Keeping in check the Boundary Cases! 
  if (arr[leftLimit] != 1) // if '1' is not present at 0th index
   return 1;
  while (leftLimit <= rightLimit) // binary search
  {
   int middle = (leftLimit + rightLimit) / 2;
   // Element at index `i` should be `i+1` (e.g. 1 at index 0). If this is the first element  which is not `i`+ 1, then  missing element is middle+1 
   if (arr[middle] != middle + 1 && arr[middle - 1] == middle)
    return middle + 1;
   // If this is not the first missing element search in left subarray 
   if (arr[middle] != middle + 1)
    rightLimit = middle - 1; // update rightLimit to search only left
   // if it follows index+1 property then search in right side 
   else
    leftLimit = middle + 1; // update leftLimit to search only right
  }
  return -1; // if no element missing 
 }
 public static void main(String args[]) {
  int[] input1 = {1,2,4};
  int[] input2 = {1,2,3,4,6};
  int[] input3 = {2,3,4,5,6};
  int[] input4 = {1,2,3,4,5,6,7,8,9,10};
  System.out.println("Find the Missing Number!");
  System.out.println(Arrays.toString(input1) + " --> " + missingNumber(input1, input1.length));
  System.out.println(Arrays.toString(input2) + " --> " + missingNumber(input2, input2.length));
  System.out.println(Arrays.toString(input3) + " --> " + missingNumber(input3, input3.length) + "\t\t\t\t\t\t Corner Case I - Handeled");
  System.out.println(Arrays.toString(input4) + " --> " + missingNumber(input4, input4.length) + "\t\t\t Corner Case II - Handeled");
 }
}
复制代码

解决方案分解：

时间复杂度： O(log_n)

第 38 行：驱动程序missingNumber()以int [] arr和int size作为参数调用该函数。
第 6 行：初始化左右限制。
第 9-10 行：处理极端情况 1。1如果数组的第一个元素不等于 1，则返回。
第 12-18 行：首先找到数组的中间索引，如果 at 的元素middle不等于middle + 1，并且这是第一个缺失的元素，middle + 1则为缺失的元素。
第 21-26 行：如果这不是第一个缺失的元素并且arr[middle]不等于middle+1，则在右半部分搜索。否则，在数组的左半部分搜索。
第 28 行：处理极端情况 2。-1如果最终遍历了整个数组并且没有元素丢失，则返回。

图算法：

在我们的最后一节中，我们将研究问题以提高对常见图形相关问题的熟练程度。由于在社交媒体映射中的普遍存在，这些问题在采访中变得越来越流行，这意味着现在比以往任何时候都更需要准备好这种做法。

14：计算给定图级别中的节点数

问题陈述：

实现一个函数，该函数返回无向图给定级别的节点数。

图.java：

import java.io.*;
import java.util.*;
class Graph {
 private int vertices; //number of vertices 
 private LinkedList < Integer > adjacencyList[]; //Adjacency Lists 
 @SuppressWarnings("unchecked")
 // Constructor 
 Graph(int vert) {
  this.vertices = vert;
  this.adjacencyList = new LinkedList[vertices];
  for (int i = 0; i < this.vertices; ++i)
   this.adjacencyList[i] = new LinkedList();
 }
 // Function to add an edge into the graph 
 void addEdge(int source, int destination) {
  this.adjacencyList[source].add(destination);
 }
 public int getVertices() {
  return this.vertices;
 }
 public LinkedList < Integer > [] getAdj() {
  return this.adjacencyList;
 }
};
复制代码

主要的java：

class CountNodes {
 public static int numberOfNodesInGivenLevel(Graph g, int source, int level) {
  int count = 0; //count initialized to zero
  int num_of_vertices = g.getVertices(); //getVertices given in Graph.java file
  // Write - Your - Code
  return count;
 }
}
复制代码

解决方案：

class CountNodes {
   public static int numberOfNodesInGivenLevel(Graph g, int source, int level) {
    int count = 0;
    int num_of_vertices = g.getVertices();
    //Integer Array to hold the history of visited nodes (by default-false)
    //Make a node visited whenever you add it into queue
    int visited[] = new int[num_of_vertices];
    //Create a linkedlist array called Queue
    LinkedList < Integer > queue = new LinkedList < Integer > ();
    //mark the visited nodes as true by setting value to 1 and add them to the queue
    visited[source] = 1;
    queue.add(source);
    //Traverse while queue is not empty
    while (queue.size() != 0) {
     //add the vertex/node from queue to result
     source = queue.poll();
     //Get adjacent vertices to the current node from the list
     LinkedList < Integer > Llist[];
     Llist = g.getAdj();
     Iterator < Integer > i = Llist[source].listIterator();
     while (i.hasNext()) {
      int temp = i.next();
      //if not already visited then add to the Queue
      if (visited[temp] != 1) {
       visited[temp] = visited[source] + 1;
       if (visited[temp] < level)
       queue.add(temp);
      }
     }
    }
    //calculating the count for the level
    for (int i = 0; i < num_of_vertices; i++)
     if (visited[i] == level)
      count++;
    return count;
   }
  }
  class Main {
   public static void main(String args[]) {
    Graph g = new Graph(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 5);
    g.addEdge(2, 4);
    int answer;
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 1);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 2);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 3);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 4);
    System.out.println(answer);
   }
  }
复制代码

解决方案分解：

时间复杂度： O(V + E)

上面的解决方案修改了访问数组以存储每个节点的级别。稍后，它计算具有相同级别的节点（第 32-35 行）。

在这段代码中，在访问每个节点时，被访问节点的级别设置为其父节点级别的增量，即，

visited[child] = visited[parent] + 1 
复制代码

这就是确定每个节点级别的方式（第 26 行）。

15: 转置图

问题陈述：

实现一个将有向图作为输入并打印其转置的函数。

图.java：

import java.io.*;
import java.util.*;
class Graph {
 private int vertices; //number of vertices 
 private LinkedList < Integer > adjacencyList[]; //Adjacency Lists 
 @SuppressWarnings("unchecked")
 // Constructor 
 Graph(int vert) {
  this.vertices = vert;
  this.adjacencyList = new LinkedList[vertices];
  for (int i = 0; i < this.vertices; ++i)
   this.adjacencyList[i] = new LinkedList();
 }
 // Function to add an edge into the graph 
 void addEdge(int source, int destination) {
  this.adjacencyList[source].add(destination);
 }
 public int getVertices() {
  return this.vertices;
 }
 public LinkedList < Integer > [] getAdj() {
  return this.adjacencyList;
 }
 void printGraph() {
  for (int v = 0; v < this.vertices; v++) {
   System.out.print(v);
   for (Integer pCrawl: this.adjacencyList[v]) {
    System.out.print("->" + pCrawl);
   }
   System.out.print("\n");
  }
 }
};
复制代码

主要的java：

class Transpose {
 public static void getTranspose(Graph g) {
  int num_of_vertices = g.getVertices(); //getVertices defined in Graph.java file
  Graph transposedGraph = new Graph(num_of_vertices); //new graph to store the transpose
  //Write your code here
  transposedGraph.printGraph(); //calling print function on the final transposed graph
 }
}
复制代码

解决方案：

class CountNodes {
   public static int numberOfNodesInGivenLevel(Graph g, int source, int level) {
    int count = 0;
    int num_of_vertices = g.getVertices();
    //Integer Array to hold the history of visited nodes (by default-false)
    //Make a node visited whenever you add it into queue
    int visited[] = new int[num_of_vertices];
    //Create a linkedlist array called Queue
    LinkedList < Integer > queue = new LinkedList < Integer > ();
    //mark the visited nodes as true by setting value to 1 and add them to the queue
    visited[source] = 1;
    queue.add(source);
    //Traverse while queue is not empty
    while (queue.size() != 0) {
     //add the vertex/node from queue to result
     source = queue.poll();
     //Get adjacent vertices to the current node from the list
     LinkedList < Integer > Llist[];
     Llist = g.getAdj();
     Iterator < Integer > i = Llist[source].listIterator();
     while (i.hasNext()) {
      int temp = i.next();
      //if not already visited then add to the Queue
      if (visited[temp] != 1) {
       visited[temp] = visited[source] + 1;
       if (visited[temp] < level)
       queue.add(temp);
      }
     }
    }
    //calculating the count for the level
    for (int i = 0; i < num_of_vertices; i++)
     if (visited[i] == level)
      count++;
    return count;
   }
  }
  class Main {
   public static void main(String args[]) {
    Graph g = new Graph(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(3, 5);
    g.addEdge(2, 4);
    int answer;
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 1);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 2);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 3);
    System.out.println(answer);
    answer = CountNodes.numberOfNodesInGivenLevel(g, 0, 4);
    System.out.println(answer);
   }
  }
复制代码

解决方案分解：

时间复杂度： O(V + E)

首先，你制作另一个图表并开始反转它。遍历给定图的邻接表。当程序v在 vertex 的邻接表中找到一个顶点（即给定图中从to 的u一条边，在中添加一条从to 的边，添加到新图的vertex 的邻接表中）（第 9-13 行） ).u``v``v``u``transposedGraph``u``v

在第 19 行，该printGraph()函数将图形打印到控制台。您可以在文件中找到它的实现Graph.java（第 29-36 行）。

面试时碰到的Java 算法问题前 15 名（二）

动态规划：记忆和制表

8. 背包问题：

9.楼梯问题

贪心算法：局部最大化

10：换机问题

11：找到埃及分数

分而治之：

12：欧氏算法问题

13：排序数组中缺少数字

图算法：

14：计算给定图级别中的节点数

15: 转置图

热门文章

最新文章

相关课程

相关电子书

相关实验场景