【数据结构与算法之面试题】穷举法和回溯法系列面试题

柔光的暖阳◎ 2024-03-26 21:04 140阅读 0赞

【数据结构与算法之面试题】穷举法和回溯法系列面试题

文章目录

      • 【数据结构与算法之面试题】穷举法和回溯法系列面试题
          • 1 数组元素之差的最小值
          • 2 数的分组问题
          • 3 最佳的碰面地点
          • 4 多点共线问题
          • 5 复原IP地址
          • 6 矩阵中的相邻数
          • 7 被包围的区域

穷举法和回溯法：

  • 相似点

    • 首先建立问题的解空间树
    • 再在解空间树中进行搜索，直到找到问题答案

  • 不同点

    不同之处在于它们对于解空间树的搜索方式

    • 穷举法简单粗暴
    • 回溯则深搜 + 剪枝
1 数组元素之差的最小值

【题目描述】有一个整数数组，请求出该数组中不同元素两两之差绝对值的最小值，注意主要计算出最小值即可，不需要给出具体的元素。

本题可以用穷举法求解，步骤如下：

  1. 首先设定一个最小值初值minVal，这个值最好等于一个较大的数，要确保出它比计算出的最小值大。
  2. 计算出数组中每两个元素之差的绝对值difference，并将difference 与 minVal 进行比较，如果difference 更小，则将difference 赋值给 minVal，使得minVal 成为新的最小值。
  3. 重复2，直到比较完数组中两两元素之差的绝对值。
  4. 返回结果minVal

其实这道题最大的难点在于如何穷举出数组中元素的两两组合，并计算这两个元素之差的绝对值。在实际应用中，数组可能会包含很多元素，因此我们必须按照一定的规则来遍历解空间，穷举出所有数组元素的两两组合。

假设数组a 中包含n 个元素，分别为 a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n a_1,a_2,…,a_i,a_{i+1},…,a_n a1,a2,…,ai,ai+1,…,an，那么这个数组中的元素的两两组合可以与下面矩阵中元素一一对应。

在这里插入图片描述

排除掉矩阵对角线上的元素组合一共是 n 2 − n n^2 - n n2−n 种组合，而且又因为 数组元素对 ( a i , a j ) 和 ( a j , a i ) (a_i,a_j) 和 (a_j,a_i) (ai,aj)和(aj,ai)沿对角线对称，因为取绝对值后 |ai - aj| = |aj - ai|，所以我们我们只要穷举出矩阵的上三角或者下三角区域，一共是 $(n^2 - n)/ 2 $ 种组合。

当然我们并不需要真的搞一个这样的矩阵出来，可以通过一个二重循环模拟访问矩阵上三角区域中元素的过程。

Java 实现：

  1. /**
  2.  * @Projectname: JavaData_StructureAndAlgorithm
  3.  * @Classname: TheMinimumDifferenceBetweenTheElementsOfAnArray
  4.  * @Author: Ding Jiaxiong
  5.  * @Data:2023/3/18 15:10
  6.  */
  8. public class TheMinimumDifferenceBetweenTheElementsOfAnArray {
  11.     public static int getMinDifference(int[] array) {
  14.         int minVal = 32767;
  15.         int row = 0;
  16.         int column = 0;
  18.         for (row = 0; row < array.length; row++) {
  20.             for (column = row + 1; column < array.length; column++) {
  22.                 if (Math.abs(array[column] - array[row]) < minVal) {
  24.                     minVal = Math.abs(array[column] - array[row]);
  25.                 }
  26.             }
  27.         }
  29.         return minVal;
  30.     }
  32.     public static void main(String[] args) {
  35.         int[] array = {
  36.     1, 12, 23, 4, 25, 20, 122};
  37.         System.out.println(getMinDifference(array));
  39.     }
  41. }

运行结果

在这里插入图片描述

2 数的分组问题

【题目描述】有10个任意的正整数，将其分为组A和组B，要求组A 中的每个数据的和 与组B中每个数据的和 之差 的绝对值最小。设计算法实现这样的分组。

举个栗子：数组array[10] = {2,3,6,8,9,10,0,23,16,65}，输出的结果应该是 A：{65,6}、B：{16,23,0,10,9,8,3,2} 。因为组A 中每个数据的和等于 65 + 6 = 71，组B中每个数据的和等于 16 + 23 + 0 + 10 + 9 + 8 + 3 + 2 = 71，差为0.

其实解决这道题最直观的方法就是穷举法了。我们可以将这10个数任意分为组A 和 组B，然后计算组A 中每个数字的和S1，组B的和S2，|S1 - S2| 最小的方案就是答案。

首先确定解空间的 大小，【二进制位码】将10个任意的整数分为两组有 2 10 − 2 2^{10} - 2 210−2 = 1022种方案。

同样借助位码来遍历解空间中的每一种分组方案。

Java 实现：

  1. /**
  2.  * @Projectname: JavaData_StructureAndAlgorithm
  3.  * @Classname: TheProblemOfGroupingNumbers
  4.  * @Author: Ding Jiaxiong
  5.  * @Data:2023/3/18 15:35
  6.  */
  8. public class TheProblemOfGroupingNumbers {
  11.     public static int getBestGrouping(int[] array) {
  14.         int scheme, bitmask, index;
  15.         int difference = 0;
  17.         int sumA = 0, sumB = 0;
  18.         int res = 0;
  20.         for (int i = 0; i < 10; i++) {
  22.             difference = difference + array[i]; // 初始化差值
  23.         }
  25.         for (scheme = 0x0001; scheme <= 0x03fe; scheme++) {
  26.      // 在2^10 - 2 的范围内搜索, 0x03fe十进制是1022
  27.             for (bitmask = 0x0001, index = 9; bitmask <= 0x0200; bitmask = bitmask * 2, index--) {
  29.                 if ((bitmask & scheme) != 0) {
  31.                     sumA = sumA + array[index];  // 组A 中的元素和
  32.                 } else {
  34.                     sumB = sumB + array[index];  // 组B 中的元素和
  35.                 }
  36.             }
  38.             if (Math.abs(sumA - sumB) < difference) {
  40.                 res = scheme;
  41.                 difference = Math.abs(sumA - sumB);
  42.             }
  44.             sumA = 0;
  45.             sumB = 0;
  46.         }
  48.         return res;
  49.     }
  51.     public static void main(String[] args) {
  54.         int[] array = {
  55.     2, 3, 6, 8, 9, 10, 0, 23, 16, 65};
  56.         int bitmask, index;
  57.         int res = getBestGrouping(array);
  58.         System.out.println(Integer.toBinaryString(res));
  60.         System.out.println("Group A: ");
  61.         for (bitmask = 0x0001, index = 9; bitmask <= 0x0200; bitmask = bitmask * 2, index--) {
  63.             if ((bitmask & res) != 0) {
  65.                 System.out.println(array[index]);
  66.             }
  67.         }
  69.         System.out.println("Group B: ");
  70.         for (bitmask = 0x0001, index = 9; bitmask <= 0x0200; bitmask = bitmask * 2, index--) {
  72.             if ((bitmask & res) == 0) {
  74.                 System.out.println(array[index]);
  75.             }
  76.         }
  78.     }
  80. }

运行结果

在这里插入图片描述

二进制位上 = 1表示分到组A，=0 表示分到组B

没问题。

3 最佳的碰面地点

【题目描述】有一队人(两人或以上) 要在一个地方碰面，他们希望最小化总行走距离。

给定一个二维的网格，格子里面的值要么是0，要么是1，其中1表示某人所处的位置，规定这些人每次只能横向走一格或者纵向走一格。

编写一个程序，计算这一队人在网格中的最佳碰面地点。

举个栗子：

在这里插入图片描述

最终得到的结果应该是(0,2)，3人的总行走距离为 2+ 2+ 2 =6.

在这里插入图片描述

【穷举法】方法就是计算网格中的每个 “1点”( 可能有多个，记作 p p p)到达网格中的某个点(记作 q i q_i qi)的距离之和(记作 d i d_i di)， q i q_i qi 要穷举到 m x n 的每一个格子，这样就可以得到一组距离之和 d 1 , d 2 , . . . , d m n d_1,d_2,…,d_{mn} d1,d2,…,dmn，其中最小的距离和就是答案。对应的 q i q_i qi 即碰面地点。

其实只要不刻意“绕路”，网格中两个点的距离可以直接用曼哈顿距离公式进行计算。

Java 解法：

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  4. /**
  5.  * @Projectname: JavaData_StructureAndAlgorithm
  6.  * @Classname: ThePerfectMeetingPlace
  7.  * @Author: Ding Jiaxiong
  8.  * @Data:2023/3/18 16:25
  9.  */
  11. class position {
  13.     int row;
  14.     int col;
  16.     public position(int row, int col) {
  18.         this.row = row;
  19.         this.col = col;
  20.     }
  21. }
  23. public class ThePerfectMeetingPlace {
  26.     // 二维穷举法
  27.     public static position getBestMeetingPlace(ArrayList<position> p, int gridRows, int gridColumns) {
  30.         int distance = 0;
  31.         int minDistance = 10000;
  33.         position pr = new position(0, 0);
  35.         for (int row = 0; row < gridRows; row++) {
  37.             for (int col = 0; col < gridColumns; col++) {
  40.                 for (int i = 0; i < p.size(); i++) {
  42.                     distance = distance + Math.abs(p.get(i).row - row) + Math.abs(p.get(i).col - col);
  43.                 }
  45.                 if (minDistance > distance) {
  47.                     minDistance = distance;
  48.                     pr.row = row;
  49.                     pr.col = col;
  50.                 }
  52.                 distance = 0;
  53.             }
  54.         }
  56.         return pr;
  57.     }
  59.     public static position getBestMeetingPlace(int[][] grid) {
  62.         ArrayList<position> p = new ArrayList<position>();
  64.         for (int i = 0; i < grid.length; i++) {
  66.             for (int j = 0; j < grid[0].length; j++) {
  68.                 if (grid[i][j] == 1) {
  70.                     p.add(new position(i, j));
  71.                 }
  72.             }
  73.         }
  75.         return getBestMeetingPlace(p, grid.length, grid[0].length);
  76.     }
  78.     public static void main(String[] args) {
  81.         int[][] grid = {
  83.                 {
  84.     1, 0, 0, 0, 1},
  85.                 {
  86.     0, 0, 0, 0, 0},
  87.                 {
  88.     0, 0, 1, 0, 0}
  89.         };
  91.         position bestMeetingPlace = getBestMeetingPlace(grid);
  92.         System.out.println(bestMeetingPlace.row + " " + bestMeetingPlace.col);
  94.     }
  96. }

运行结果

在这里插入图片描述

还有一种改进后的一维穷举法的实现：

  1. import java.util.ArrayList;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: BestMeetingPlace
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/18 16:37
  8.  */
  10. class position {
  12.     int row;
  13.     int col;
  15.     public position(int row, int col) {
  17.         this.row = row;
  18.         this.col = col;
  19.     }
  20. }
  22. public class BestMeetingPlace {
  25.     // 一维穷举法
  26.     public static int getBestMeetingPlace(ArrayList<Integer> p, int length) {
  29.         int distance = 0;
  30.         int minDistance = 10000;
  32.         int res = 0;
  34.         for (int i = 0; i < length; i++) {
  36.             for (int j = 0; j < p.size(); j++) {
  38.                 distance = distance + Math.abs(p.get(j) - i);
  39.             }
  41.             if (minDistance > distance) {
  43.                 minDistance = distance;
  44.                 res = i;
  45.             }
  46.             distance = 0;
  47.         }
  49.         return res;
  50.     }
  52.     public static position getBestMeetingPlace(int[][] grid) {
  54.         ArrayList<Integer> prow = new ArrayList<Integer>();
  55.         ArrayList<Integer> pcolumn = new ArrayList<Integer>();
  57.         for (int i = 0; i < grid.length; i++) {
  59.             for (int j = 0; j < grid[0].length; j++) {
  61.                 if (grid[i][j] == 1) {
  63.                     prow.add(i);
  64.                     pcolumn.add(j);
  65.                 }
  66.             }
  67.         }
  69.         // 计算纵向最佳碰面地点的行号
  70.         int row = getBestMeetingPlace(prow, grid.length);
  71.         // 计算横向最佳碰面地点的列号
  72.         int col = getBestMeetingPlace(pcolumn, grid[0].length);
  74.         return new position(row, col);
  75.     }
  77.     public static void main(String[] args) {
  80.         int[][] grid = {
  82.                 {
  83.     1, 0, 0, 0, 1},
  84.                 {
  85.     0, 0, 0, 0, 0},
  86.                 {
  87.     0, 0, 1, 0, 0}
  88.         };
  90.         position bestMeetingPlace = getBestMeetingPlace(grid);
  91.         System.out.println(bestMeetingPlace.row + " " + bestMeetingPlace.col);
  93.     }
  95. }

运行结果

在这里插入图片描述

对于一个m x n 的网格，采用二维数组穷举的时间复杂度为 O ( m n ) O(mn) O(mn) ，而使用一维数组穷举的时间复杂度为 O ( m ) + O ( n ) O(m) + O(n) O(m)+O(n)

4 多点共线问题

【题目描述】给定n (n > 2) 个位于多一平面的点，求最多有多少个点位于同一条直线上。

举个栗子，给定点{1,1}、{2,2}、{3,3}，输出结果为3

因为给定的n 个点相互独立，所以只能通过穷举法求解。

“两点确定一直线”，因为平面内存在无数条直线，不可能全部一一列举出来判断，我们只需要穷举那些经过了平面中两个点的直线，然后判断其他点是否位于该直线上。

计算多点共线问题的步骤：

  1. 通过平面中的两点确定一条直线
  2. 如果该直线被访问过，则直接返回步骤1 枚举下一条直线；否则判断平面上的其他点是否也位于该直线上，并记录下该直线上点的数量，然后返回步骤1 继续枚举下一条直线。

当平面上由两点确定的直线全部被访问后，记录中每条直线对应的点的数量最大的即为所求。

Java 实现：

  1. import java.util.HashMap;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: Multi_pointCollinearProblem
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/18 19:25
  8.  */
  10. class point {
  12.     int x;
  13.     int y;
  15.     public point(int x, int y) {
  17.         this.x = x;
  18.         this.y = y;
  19.     }
  20. }
  22. class line {
  24.     int a;
  25.     int b;
  26.     int cb;
  28.     public line(int a, int b, int cb) {
  30.         this.a = a;
  31.         this.b = b;
  32.         this.cb = cb;
  33.     }
  35.     public int hashCode() {
  37.         return 0;
  38.     }
  40.     public boolean equals(Object anObject) {
  42.         if (anObject instanceof line) {
  44.             line anLine = (line) anObject;
  45.             // 判断两条直线是否重合的条件1
  46.             if (anLine.a == this.a && anLine.b == this.b && anLine.cb == this.cb) {
  48.                 return true;
  49.             }
  50.             // 判断两条直线是否重合的条件2
  51.             if (anLine.a == -this.a && anLine.b == -this.b && anLine.cb == -this.cb) {
  53.                 return true;
  54.             }
  55.             // 判断两条直线是否重合的条件3
  56.             if ((double) anLine.a * (double) this.b == (double) this.a * (double) anLine.b && (double) anLine.b * (double) this.cb == (double) this.b * (double) anLine.cb && (double) anLine.a * (double) this.cb == (double) this.a * (double) anLine.cb) {
  58.                 return true;
  59.             }
  61.             return false;
  62.         }
  64.         return false;
  65.     }
  67. }
  69. public class Multi_pointCollinearProblem {
  72.     public static HashMap<line, Integer> map = new HashMap<line, Integer>();
  74.     public static boolean hasThisLine(line l) {
  76.         if (map.containsKey(l)) {
  78.             return true;
  79.         }
  80.         map.put(l, 2);
  81.         return false;
  82.     }
  84.     public static int getMaxSameLinePoints(point[] points) {
  86.         for (int i = 0; i < points.length; i++) {
  88.             for (int j = i + 1; j < points.length; j++) {
  91.                 // 根据点point[i] 和 point[j] 确定一条直线
  92.                 int a = points[i].y - points[j].y;
  93.                 int b = points[i].x - points[j].x;
  94.                 int cb = b * points[i].y - a * points[i].x;
  96.                 line l = new line(a, b, cb);
  98.                 // 如果没有访问过这条直线, 则开始计算这条直线上点的数量,并用pointsNum 记录
  99.                 if (!hasThisLine(l)) {
  101.                     for (int k = 0; k < points.length; k++) {
  103.                         if (k != i && k != j) {
  105.                             if (b * points[k].y == a * points[k].x + cb) {
  107.                                 // k点在直线上
  108.                                 int pointsNum = map.get(l);
  109.                                 map.put(l, ++pointsNum);
  110.                             }
  111.                         }
  112.                     }
  113.                 }
  114.             }
  115.         }
  117.         // 遍历找出最大值
  118.         int maxPoints = 0;
  119.         for (Integer numbers : map.values()) {
  121.             if (numbers > maxPoints) {
  123.                 maxPoints = numbers;
  124.             }
  125.         }
  127.         return maxPoints;
  128.     }
  130.     public static void main(String[] args) {
  133.         point[] points = new point[4];
  134.         // 第1个点坐标为(1,0)
  135.         points[0] = new point(1, 0);
  136.         // 第2个点坐标为(1,2)
  137.         points[1] = new point(1, 2);
  138.         // 第3个点坐标为(3,0)
  139.         points[2] = new point(3, 0);
  140.         // 第4个点坐标为(0,3)
  141.         points[3] = new point(0, 3);
  143.         System.out.println(getMaxSameLinePoints(points));
  145.     }
  147. }

运行结果

在这里插入图片描述

答案是：{3,0}、{1,2}、{0,3}这三个点最多共线。

5 复原IP地址

【题目描述】给定一个只包含数字的字符串，打印出由该字符串构成的所有可能的IP地址。

举个例子：

  • 如果给定”25525511135”，则应该打印出 255.255.11.135 和 255.255.111.35
  • 如果给定”1111”，则应该打印出 1.1.1.1
  • 当然也有可能无法构成IP地址

这道题最容易想到的还是穷举，在一串由数字构成的字符串中间添加3 个点. ，使其构成一个合法的IP地址。

每两个数字之间的间隙都可以尝试放置一个点。

假设有n 个这样的间隙，将这3 个点随意放置到这n 个间隙中，则共有 C(n , 3)种方法。

这样虽然直观，但是其实效率不高，因为存在冗余计算。比如333.33.3.3 一定不是IP地址，因为333 > 255，同理333.3.33.3 也不会是IP地址，还有333.3.3.33这种，所以这样就浪费时间。

所以为了避免冗余，提升算法效率，这里推荐使用回溯法 + 剪枝。

Java 实现：

  1. /**
  2.  * @Projectname: JavaData_StructureAndAlgorithm
  3.  * @Classname: RecoveryIPAddress
  4.  * @Author: Ding Jiaxiong
  5.  * @Data:2023/3/18 19:56
  6.  */
  8. public class RecoveryIPAddress {
  11.     /**
  12.      * @param s           指定的字符串
  13.      * @param index       本次递归调用中所要判定的子串在s 中的起始位置下标
  14.      * @param pointNumber 本次递归调用要放置第几个分割点
  15.      */
  16.     public static void printValidIPAddress(StringBuffer s, int index, int pointNumber) {
  19.         if (pointNumber == 3) {
  21.             if (isValid(s.substring(index, s.length()))) {
  23.                 // 得到一个结果, 打印
  24.                 System.out.println(s);
  25.             }
  26.             return;
  27.         }
  29.         for (int i = index + 1; i < s.length(); i++) {
  31.             if (isValid(s.substring(index, i))) {
  33.                 // 如果从index到 i - 1的子串满足IP地址格式要求，则在第i - 1个数字后面加分割点，然后pointNumber ++
  34.                 s.insert(i, '.');
  35.                 pointNumber++;
  36.                 printValidIPAddress(s, i + 1, pointNumber);
  37.                 // 回溯到上一层,继续探索下一个分支
  38.                 pointNumber--;
  39.                 s.deleteCharAt(i);
  40.             }
  41.         }
  42.     }
  44.     // 判断s 是否符合IP地址的格式要求
  45.     public static boolean isValid(String s) {
  47.         if (s.length() == 0) {
  49.             return false;
  50.         }
  51.         int ans = 0;
  52.         for (int i = 0; i < s.length(); i++) {
  54.             // 包含非数字字符
  55.             if (s.charAt(i) - '0' > 9 || s.charAt(i) - '0' < 0) {
  57.                 return false;
  58.             }
  60.             ans = ans * 10 + (s.charAt(i) - '0');
  61.             // 大于255
  62.             if (ans > 255) {
  64.                 return false;
  65.             }
  66.         }
  68.         // 由0开头
  69.         if (s.charAt(0) == '0' && s.length() > 1) {
  71.             return false;
  72.         }
  74.         return true;
  75.     }
  77.     public static void main(String[] args) {
  80.         StringBuffer ip = new StringBuffer("25525511135");
  81.         printValidIPAddress(ip,0,0);
  82.         StringBuffer ip2 = new StringBuffer("3333333");
  83.         printValidIPAddress(ip2,0,0);
  85.     }
  87. }

运行结果

在这里插入图片描述

6 矩阵中的相邻数

【题目描述】给定一个包含正整数1 和 5 的矩阵，同时给定其中一个数字5 在矩阵中的坐标(row, column)，要求计算出该矩阵中与(row, column)位置上的元素5 相邻的5 的数量，并打印出这些相邻元素5 在矩阵中的坐标(行号和列号)。【注意】所谓相邻是指该元素的上下左右4 个方向上的元素，而且相邻具有可传递性，即相邻的相邻也算相邻。

举个栗子：

在这里插入图片描述

这道题比较简单的方法就是回溯法。

假定规给定元素5 的下标为(1,0)，那么可以采用深搜策略，逐步查找出于矩阵中第1行第0列的元素5相邻的元素5.

具体步骤：

  1. 定义变量count 计算矩阵中相邻元素5 的数量，初始0

  2. 从第1行第0列的元素5出发，依次访问与其相邻的 4个元素。

    • 如果当前访问到的相邻元素是5，则count++，然后将这个5 作为新起点继续深搜
    • 如果当前访问到的相邻元素不是5，则【剪枝】回退到上一次访问的元素5，访问下一个相邻元素。

这个过程中一定要着重考虑到两个问题：

  • 重复搜索：利用HashSet 辅助查重
  • 矩阵越界：矩阵中的元素可能并没有上下左右四个相邻元素。

Java 实现描述：

  1. import java.util.HashSet;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: AdjacentNumber
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/18 20:33
  8.  */
  10. public class AdjacentNumber {
  13.     public static int count = 0;
  14.     public static HashSet<String> set = new HashSet<String>();
  16.     public static int getAdjacentNumber(int row, int column, int[][] matrix) {
  18.         // 上下左右4个元素的行号
  19.         int[] rowIndex = {
  20.     row + 1, row, row - 1, row};
  21.         // 上下左右4个元素的列号
  22.         int[] columnIndex = {
  23.     column, column + 1, column, column - 1};
  25.         String index = row + "," + column;
  26.         set.add(index); // 将当前访问过的5的坐标加入HashSet, 以便查重
  28.         for (int i = 0; i < 4; i++) {
  30.             // 依次从上下左右四个方向深搜
  31.             if (isValidPosition(rowIndex[i], columnIndex[i], matrix)) {
  33.                 /**
  34.                  * 满足条件
  35.                  * 1. 没有越界
  36.                  * 2. 元素为5
  37.                  * 3. 未被访问过
  38.                  */
  39.                 System.out.println("row = " + rowIndex[i] + " column = " + columnIndex[i]);
  40.                 count++;
  41.                 getAdjacentNumber(rowIndex[i], columnIndex[i], matrix); // 递归深搜
  42.             }
  43.         }
  44.         return count;
  45.     }
  47.     public static boolean isValidPosition(int row, int column, int[][] matrix) {
  50.         // 判断是否越界
  51.         if (row < 0 || row >= matrix.length || column < 0 || column >= matrix[0].length) {
  53.             return false;
  54.         }
  56.         // 判断是否为5
  57.         if (matrix[row][column] != 5) {
  59.             return false;
  60.         }
  62.         // 判断是否被访问过
  63.         String index = row + "," + column;
  64.         if (set.contains(index)) {
  66.             return false;
  67.         }
  69.         return true;
  70.     }
  72.     public static void main(String[] args) {
  75.         int[][] matrix = {
  77.                 {
  78.     1, 1, 5, 5, 1},
  79.                 {
  80.     5, 5, 5, 1, 1},
  81.                 {
  82.     1, 1, 5, 5, 1},
  83.                 {
  84.     1, 1, 5, 1, 1},
  85.                 {
  86.     5, 1, 1, 1, 5}
  87.         };
  89.         System.out.println(getAdjacentNumber(1, 0, matrix));
  91.     }
  93. }

运行结果

在这里插入图片描述

没毛病。

7 被包围的区域

【题目描述】给定一个二维矩阵，包含字母X 和 O。请找到所谓被X 围绕的区域，并将这些区域里所有的 O 用X 替换。

举个栗子：

在这里插入图片描述

其实不难发现，这个问题可以转换成在矩阵中所有边界上的O 以及与它们相连的O 都没有被替换，而其他的O 就被替换了。

深搜深搜。

Java 实现：

  1. import com.sun.javafx.image.PixelUtils;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: TheAreaUnderSiege
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/18 20:48
  8.  */
  10. public class TheAreaUnderSiege {
  13.     public static void surroundAreas(char[][] matrix) {
  16.         int maxX = matrix.length - 1; // 矩阵行数 -1
  17.         int maxY = matrix[0].length - 1; // 矩阵列数 -1
  19.         for (int j = 0; j <= maxY; j++) {
  21.             if (matrix[0][j] == 'o') {
  23.                 expand(0, j, matrix, maxX, maxY);
  24.             }
  25.         }
  27.         for (int j = 0; j <= maxY; j++) {
  29.             if (matrix[maxX][j] == 'o') {
  31.                 expand(maxX, j, matrix, maxX, maxY);
  32.             }
  33.         }
  35.         for (int i = 1; i < maxX; i++) {
  37.             if (matrix[i][0] == 'o') {
  39.                 expand(i, 0, matrix, maxX, maxY);
  40.             }
  41.         }
  43.         for (int i = 1; i < maxX; i++) {
  45.             if (matrix[i][maxY] == 'o') {
  47.                 expand(i, maxY, matrix, maxX, maxY);
  48.             }
  49.         }
  51.         for (int i = 0; i <= maxX; i++) {
  53.             for (int j = 0; j <= maxY; j++) {
  55.                 if (matrix[i][j] == 'o') {
  57.                     matrix[i][j] = 'x';
  58.                 } else if (matrix[i][j] == '#') {
  60.                     matrix[i][j] = 'o';
  61.                 }
  62.             }
  63.         }
  64.     }
  66.     public static void expand(int x, int y, char[][] matrix, int maxX, int maxY) {
  69.         if (x > maxX || x < 0 || y > maxY || y < 0) {
  71.             return;
  72.         }
  74.         if (matrix[x][y] == 'x') {
  76.             return;
  77.         }
  79.         if (matrix[x][y] == '#') {
  81.             return;
  82.         }
  84.         if (matrix[x][y] == 'o') {
  86.             matrix[x][y] = '#';
  87.         }
  89.         expand(x + 1, y, matrix, maxX, maxY);
  90.         expand(x, y + 1, matrix, maxX, maxY);
  91.         expand(x - 1, y, matrix, maxX, maxY);
  92.         expand(x, y - 1, matrix, maxX, maxY);
  94.     }
  96.     public static void main(String[] args) {
  99.         char[][] matrix = {
  101.                 {
  102.     'x', 'x', 'o', 'o', 'x', 'x', 'x', 'o'},
  103.                 {
  104.     'x', 'o', 'o', 'x', 'x', 'x', 'x', 'x'},
  105.                 {
  106.     'x', 'o', 'o', 'o', 'o', 'x', 'x', 'x'},
  107.                 {
  108.     'x', 'o', 'x', 'x', 'x', 'o', 'x', 'x'},
  109.                 {
  110.     'x', 'x', 'x', 'o', 'x', 'o', 'o', 'x'},
  111.                 {
  112.     'x', 'o', 'o', 'x', 'x', 'o', 'o', 'x'},
  113.                 {
  114.     'x', 'o', 'o', 'x', 'x', 'x', 'o', 'x'},
  115.                 {
  116.     'x', 'x', 'x', 'x', 'x', 'x', 'o', 'x'},
  117.         };
  119.         for (int i = 0; i <= 7; i++) {
  121.             for (int j = 0; j <= 7; j++) {
  123.                 System.out.print(matrix[i][j] + " ");
  124.             }
  125.             System.out.println();
  126.         }
  127.         System.out.println("===================================================");
  128.         surroundAreas(matrix);
  129.         for (int i = 0; i <= 7; i++) {
  131.             for (int j = 0; j <= 7; j++) {
  133.                 System.out.print(matrix[i][j] + " ");
  134.             }
  135.             System.out.println();
  136.         }
  139.     }
  141. }

运行结果

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读