ACM实用笔记，小白入.doc

### ACM实用笔记精炼知识点 #### 一、十大算法概览 1. **递归算法**：通过调用自身来解决问题的方式。适用于可以分解为相同子问题的情形。 2. **排序算法**：如快速排序、冒泡排序等，用于将一系列元素按照某种规则进行排序。 3. **二分查找算法**：在有序数组中查找指定元素，通过不断缩小搜索范围提高效率。 4. **搜索算法**：包括广度优先搜索(BFS)和深度优先搜索(DFS)，用于遍历或搜索树或图中的节点。 5. **哈希算法**：通过哈希函数将任意长度的数据映射到固定长度的值，用于快速查找和存储。 6. **贪心算法**：在每个步骤选择当前最优解，期望最终能得到全局最优解。 7. **分治算法**：将问题分解为两个或更多的相同或相似的子问题，直至最后子问题可以简单地直接求解。 8. **回溯算法**：一种搜索算法，当探索到某一步时，发现原先的选择不满足条件，则退回上一步重新选择。 9. **动态规划算法**：通过将原问题分解为相互重叠的子问题进行求解，避免重复计算。 10. **字符串匹配算法**：如KMP算法，用于在一个字符串中查找另一个字符串的位置。 #### 二、十大数据结构介绍 1. **数组**：线性数据结构，元素按顺序存储，访问速度快但插入删除操作较慢。 2. **链表**：每个元素包含指向下一个元素的链接，适合频繁插入删除操作。 3. **栈**：后进先出(LIFO)的数据结构，常用于解决括号匹配等问题。 4. **队列**：先进先出(FIFO)的数据结构，适合处理需要按顺序执行的任务。 5. **散列表**：通过哈希函数将键映射到数组中的位置，实现快速查找。 6. **二叉树**：每个节点最多有两个子节点的树结构，广泛应用于排序和查找算法中。 7. **堆**：通常实现为完全二叉树，分为最大堆和最小堆，用于实现优先队列。 8. **跳表**：一种概率数据结构，通过增加多级索引来优化搜索性能。 9. **图**：由顶点和边组成的数据结构，用于模拟各种关系网络。 10. **Trie 树**：又称前缀树，用于高效存储和检索字符串。 #### 三、Java编程技巧 1. **字符串操作** - **字符串转ASCII码**：使用`str.codePointAt(index)`方法。 - **字符串分割**：使用`String.split()`方法。例如： ```java String string = "004-034556"; String[] parts = string.split("-"); String part1 = parts[0]; // "004" String part2 = parts[1]; // "034556" ``` - **字符串转数字**：使用`Integer.parseInt()`或`Double.parseDouble()`等方法。 2. **数组操作** - **求数组最大值和最小值**：使用循环遍历数组。 ```java int a[] = {1, 32, 14, 15, 61, 7, 9, 12, 11, 18}; int max = a[0]; int min = a[0]; for (int i = 0; i < a.length; i++) { if (max < a[i]) { max = a[i]; } if (min > a[i]) { min = a[i]; } } System.out.println("最大值：" + max); System.out.println("最小值：" + min); ``` - **数组排序**：使用`Arrays.sort()`方法。例如，升序排列： ```java int scores[] = {1, 2, 3, 89, 4}; Arrays.sort(scores); for (int i : scores) { System.out.println(i); } ``` 若要降序排列，可使用`Collections.reverseOrder()`方法。 3. **字符操作** - **从字符串获取字符**：使用`charAt(index)`方法。 ```java String str = "adadsauo"; char firstChar = str.charAt(0); // 获取第一个字符 char ithChar = str.charAt(i); // 获取第 i 个字符 ``` 以上内容覆盖了ACM竞赛中常见的算法与数据结构知识点，并结合了实际编程语言Java的具体应用实例。这些知识点对于初学者来说至关重要，不仅能够帮助他们更好地理解计算机科学的基本概念，还能提升他们在实际编程中的应用能力。希望这份笔记能对大家有所帮助。