遍历算法(1)

遍历算法主要用在在处理迷宫问题,图,最短路径,以及枚举所有可能等问题上。下面我们通过一个简单的例子,来入门深度优先和广度优先算法:

  1 package com.rampage.algorithm.base;
  2 
  3 import java.util.ArrayList;
  4 import java.util.LinkedHashSet;
  5 import java.util.List;
  6 import java.util.Set;
  7 
  8 /**
  9  * 相关的搜索算法实例 假设有1-9,9个数字,现在任意取三个,要求得到一共能得到多少个不同值的数字。如果可能的化输出所有可能的值。
 10  * 
 11  * @author zyq
 12  *
 13  */
 14 public class SearchAlgorithm {
 15     private static int totalCount = 0; // 存储总计数
 16     private static Set<String> results = new LinkedHashSet<String>(); // 存储所有的结果
 17 
 18     public static void main(String[] args) {
 19         deepFirstSearch();
 20         breadthFirstSearch();
 21     }
 22 
 23     /**
 24      * 广度优先搜索:广度优先搜索算法的核心是列表。首先就得到第一步可以放的所有数,然后依次将其放入列表。接下来逐个处理列表中的每个数,给出接下来可能出现的第二个数,
 25      * 处理完列表中的一个数就将该数从列表中移除。依次类推,直到待处理的列表中的元素为空。
 26      */
 27     private static void breadthFirstSearch() {
 28         totalCount = 0;
 29         results.clear();
 30         List<String> possibleList = new ArrayList<String>();
 31 
 32         // 初始化列表,开始时第一号盒子可以放入1-9
 33         for (int i = 1; i < 10; i++) {
 34             possibleList.add(i + "");
 35         }
 36 
 37         // 列表不为空的时候循环处理,因为又要增加又要删除,此时逆序遍历(此时即使用iterator,但是iterator没法删除元素,所以仍然会报错。)
 38         while (!possibleList.isEmpty()) {
 39             for (int i=possibleList.size() - 1; i>=0; i--) {
 40                 String element = possibleList.get(i);
 41                 // 长度为3说明3个数都放过了
 42                 if (element.length() == 3) {
 43                     totalCount++;
 44                     results.add(element);
 45                     possibleList.remove(i);
 46                     continue;
 47                 }
 48 
 49                 for (int j = 1; j < 10; j++) {
 50                     // 如果已经包含,则该数字不能再使用
 51                     if (element.contains(j + "")) {
 52                         continue;
 53                     } else {
 54                         // 如果没有包含对应的数字,则此时将数字加到元素后面,作为新的可能结果列表放入列表中
 55                         possibleList.add(element + j);
 56                     }
 57                 }
 58 
 59                 // 移除已经处理过的元素
 60                 possibleList.remove(i);
 61             }
 62             
 63         }
 64 
 65         System.out.println("Total count:" + totalCount);
 66         System.out.println(results);
 67     }
 68 
 69     /**
 70      * 采用深度优先算法实现:深度优先算法的核心思想是迭代。既然要迭代就应该先抽象出每一步需要重复处理的数据。 可以这样思考深度优先算法:
 71      * 假设有三个盒子,先往1号盒子放入1, 然后往2号盒子放入2,最后往3号盒子放入3.这样其实就组成了一个组合:123
 72      * 要想得到其他的组合,则必须先收回3号盒子中的3,然后放入剩下的任意一个。依次类推,当3号盒子可能的情况都放完了之后,就需要同时取回3号和2号盒子中的东西,
 73      * 然后在开始试。依次类推:
 74      * 
 75      */
 76     private static void deepFirstSearch() {
 77         totalCount = 0;
 78         results.clear();
 79         int[] book = new int[10]; // 定义已经使用过的数字,如果使用过某数字i,那么book[i] = 1
 80         int[] result = new int[3]; // 存储当前的三个数字组成的数组
 81         go(book, result, 0);
 82         System.out.println("Total count:" + totalCount);
 83         System.out.println(results);
 84     }
 85 
 86     /**
 87      * @param book
 88      *            存储已经放过的数字
 89      * @param step
 90      *            第几步,就相当于前面所说的放第几个盒子(第一个盒子对应第0步)
 91      */
 92     private static void go(int[] book, int[] result, int step) {
 93         if (step == 3) {
 94             totalCount++;
 95             results.add(new String(result[0] + "" + result[1] + "" + result[2]));
 96             return;
 97         }
 98         for (int i = 1; i < 10; i++) {
 99             if (book[i] == 1) {
100                 continue;
101             }
102             book[i] = 1; // 标记i已经被使用
103             result[step] = i;
104             // 因为是深度优先,所以需要继续往更深处遍历
105             go(book, result, step + 1);
106 
107             // 因为还要尝试其他组合所以这里沿路返回
108             book[i] = 0;
109             result[step] = 0;
110         }
111     }
112 }

 输出结果为:

1 Total count:504
2 [123, 124, 125, 126, 127, 128, 129, 132, 134, 135, 136, 137, 138, 139, 142, 143, 145, 146, 147, 148, 149, 152, 153, 154, 156, 157, 158, 159, 162, 163, 164, 165, 167, 168, 169, 172, 173, 174, 175, 176, 178, 179, 182, 183, 184, 185, 186, 187, 189, 192, 193, 194, 195, 196, 197, 198, 213, 214, 215, 216, 217, 218, 219, 231, 234, 235, 236, 237, 238, 239, 241, 243, 245, 246, 247, 248, 249, 251, 253, 254, 256, 257, 258, 259, 261, 263, 264, 265, 267, 268, 269, 271, 273, 274, 275, 276, 278, 279, 281, 283, 284, 285, 286, 287, 289, 291, 293, 294, 295, 296, 297, 298, 312, 314, 315, 316, 317, 318, 319, 321, 324, 325, 326, 327, 328, 329, 341, 342, 345, 346, 347, 348, 349, 351, 352, 354, 356, 357, 358, 359, 361, 362, 364, 365, 367, 368, 369, 371, 372, 374, 375, 376, 378, 379, 381, 382, 384, 385, 386, 387, 389, 391, 392, 394, 395, 396, 397, 398, 412, 413, 415, 416, 417, 418, 419, 421, 423, 425, 426, 427, 428, 429, 431, 432, 435, 436, 437, 438, 439, 451, 452, 453, 456, 457, 458, 459, 461, 462, 463, 465, 467, 468, 469, 471, 472, 473, 475, 476, 478, 479, 481, 482, 483, 485, 486, 487, 489, 491, 492, 493, 495, 496, 497, 498, 512, 513, 514, 516, 517, 518, 519, 521, 523, 524, 526, 527, 528, 529, 531, 532, 534, 536, 537, 538, 539, 541, 542, 543, 546, 547, 548, 549, 561, 562, 563, 564, 567, 568, 569, 571, 572, 573, 574, 576, 578, 579, 581, 582, 583, 584, 586, 587, 589, 591, 592, 593, 594, 596, 597, 598, 612, 613, 614, 615, 617, 618, 619, 621, 623, 624, 625, 627, 628, 629, 631, 632, 634, 635, 637, 638, 639, 641, 642, 643, 645, 647, 648, 649, 651, 652, 653, 654, 657, 658, 659, 671, 672, 673, 674, 675, 678, 679, 681, 682, 683, 684, 685, 687, 689, 691, 692, 693, 694, 695, 697, 698, 712, 713, 714, 715, 716, 718, 719, 721, 723, 724, 725, 726, 728, 729, 731, 732, 734, 735, 736, 738, 739, 741, 742, 743, 745, 746, 748, 749, 751, 752, 753, 754, 756, 758, 759, 761, 762, 763, 764, 765, 768, 769, 781, 782, 783, 784, 785, 786, 789, 791, 792, 793, 794, 795, 796, 798, 812, 813, 814, 815, 816, 817, 819, 821, 823, 824, 825, 826, 827, 829, 831, 832, 834, 835, 836, 837, 839, 841, 842, 843, 845, 846, 847, 849, 851, 852, 853, 854, 856, 857, 859, 861, 862, 863, 864, 865, 867, 869, 871, 872, 873, 874, 875, 876, 879, 891, 892, 893, 894, 895, 896, 897, 912, 913, 914, 915, 916, 917, 918, 921, 923, 924, 925, 926, 927, 928, 931, 932, 934, 935, 936, 937, 938, 941, 942, 943, 945, 946, 947, 948, 951, 952, 953, 954, 956, 957, 958, 961, 962, 963, 964, 965, 967, 968, 971, 972, 973, 974, 975, 976, 978, 981, 982, 983, 984, 985, 986, 987]
3 Total count:504
4 [918, 917, 916, 915, 914, 913, 912, 928, 927, 926, 925, 924, 923, 921, 938, 937, 936, 935, 934, 932, 931, 948, 947, 946, 945, 943, 942, 941, 958, 957, 956, 954, 953, 952, 951, 968, 967, 965, 964, 963, 962, 961, 978, 976, 975, 974, 973, 972, 971, 987, 986, 985, 984, 983, 982, 981, 819, 817, 816, 815, 814, 813, 812, 829, 827, 826, 825, 824, 823, 821, 839, 837, 836, 835, 834, 832, 831, 849, 847, 846, 845, 843, 842, 841, 859, 857, 856, 854, 853, 852, 851, 869, 867, 865, 864, 863, 862, 861, 879, 876, 875, 874, 873, 872, 871, 897, 896, 895, 894, 893, 892, 891, 719, 718, 716, 715, 714, 713, 712, 729, 728, 726, 725, 724, 723, 721, 739, 738, 736, 735, 734, 732, 731, 749, 748, 746, 745, 743, 742, 741, 759, 758, 756, 754, 753, 752, 751, 769, 768, 765, 764, 763, 762, 761, 789, 786, 785, 784, 783, 782, 781, 798, 796, 795, 794, 793, 792, 791, 619, 618, 617, 615, 614, 613, 612, 629, 628, 627, 625, 624, 623, 621, 639, 638, 637, 635, 634, 632, 631, 649, 648, 647, 645, 643, 642, 641, 659, 658, 657, 654, 653, 652, 651, 679, 678, 675, 674, 673, 672, 671, 689, 687, 685, 684, 683, 682, 681, 698, 697, 695, 694, 693, 692, 691, 519, 518, 517, 516, 514, 513, 512, 529, 528, 527, 526, 524, 523, 521, 539, 538, 537, 536, 534, 532, 531, 549, 548, 547, 546, 543, 542, 541, 569, 568, 567, 564, 563, 562, 561, 579, 578, 576, 574, 573, 572, 571, 589, 587, 586, 584, 583, 582, 581, 598, 597, 596, 594, 593, 592, 591, 419, 418, 417, 416, 415, 413, 412, 429, 428, 427, 426, 425, 423, 421, 439, 438, 437, 436, 435, 432, 431, 459, 458, 457, 456, 453, 452, 451, 469, 468, 467, 465, 463, 462, 461, 479, 478, 476, 475, 473, 472, 471, 489, 487, 486, 485, 483, 482, 481, 498, 497, 496, 495, 493, 492, 491, 319, 318, 317, 316, 315, 314, 312, 329, 328, 327, 326, 325, 324, 321, 349, 348, 347, 346, 345, 342, 341, 359, 358, 357, 356, 354, 352, 351, 369, 368, 367, 365, 364, 362, 361, 379, 378, 376, 375, 374, 372, 371, 389, 387, 386, 385, 384, 382, 381, 398, 397, 396, 395, 394, 392, 391, 219, 218, 217, 216, 215, 214, 213, 239, 238, 237, 236, 235, 234, 231, 249, 248, 247, 246, 245, 243, 241, 259, 258, 257, 256, 254, 253, 251, 269, 268, 267, 265, 264, 263, 261, 279, 278, 276, 275, 274, 273, 271, 289, 287, 286, 285, 284, 283, 281, 298, 297, 296, 295, 294, 293, 291, 129, 128, 127, 126, 125, 124, 123, 139, 138, 137, 136, 135, 134, 132, 149, 148, 147, 146, 145, 143, 142, 159, 158, 157, 156, 154, 153, 152, 169, 168, 167, 165, 164, 163, 162, 179, 178, 176, 175, 174, 173, 172, 189, 187, 186, 185, 184, 183, 182, 198, 197, 196, 195, 194, 193, 192]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏owent

线段树相关问题 (引用 PKU POJ题目) 整理

如果(a < b – 1){分别计算a、b的次数和线段树[a + 1, b – 1)的次数,取大(小)的一项};

19420
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继续Lee...

12310
来自专栏ACM算法日常

独角兽与数列(置换群循环)- HDU 4985

群论是法国数学家伽罗瓦(Galois)的发明。伽罗瓦是一个极具传奇性的人物,年仅21岁就英年早逝于一场近乎自杀的决斗中。他用该理论,具体来说是伽罗瓦群,解决了五...

9130
来自专栏aCloudDeveloper

公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 ...

99990
来自专栏趣谈编程

快速排序(基础版)

16930
来自专栏Jacklin攻城狮

简谈常用算法

9820
来自专栏数据结构与算法

P3808 【模版】AC自动机(简单版)

题目背景 这是一道简单的AC自动机模版题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 题目描述 给定n个模...

29160
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

21220
来自专栏好好学java的技术栈

“365算法每日学计划”:java语言基础题目及解答(06-10打卡)

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

12320
来自专栏欧阳大哥的轮子

常用的数学函数以及浮点数处理函数

在编程中我们总要进行一些数学运算以及数字处理,尤其是浮点数的运算和处理,这篇文章主要介绍C语言下的数学库。而其他语言中的数学库函数的定义以及最终实现也是通过对C...

21220

扫码关注云+社区

领取腾讯云代金券