动态规划：记忆和制表
动态规划是现代开发人员的核心算法技术，因为它专注于将问题分解为更简单的子问题以实现优化。子问题的解越优，整体解也越优。
[这是递归] 解决问题的基础，因此，任何优秀的面试官都会问这个问题。
动态规划问题可以通过自上而下的方法或自下而上的方法来解决，分别使用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 行）。
