初级编程通关练习题 #18 – 离坐标中心最近的N个点
给定一组平面坐标集合S，找出这些坐标中距离中心点（0，0）距离最近的N个点列表，N大于1小于坐标集合的长度。 输入样例： S = [[4, 1], [6, 3], [5, -2], [-1, 4], [3, -3], [-2, -4], [1, 1]] N = 3 输出样例： [[1, 1], [4, 1], [-1, 4]] 上面的输入样例中，距离坐标中心点最近的三个点是 [1,…
【算法案例】分而治之算法（Divide and Conquer）搜索距离最近的两点
距离最近的两点（Closest Pairs of Points）是计算几何中的一个著名问题：给定一组平面坐标，找出该组坐标里面距离最近的两个点。如下图中所示，红色两点是所有坐标点中距离最近的一对。 该图片来自维基百科 - Closest pairs of points problem. 最简单直接的解决方法是暴力破解（Brutal Force），也就是计算所有两点之间的距离，然后找到最小值。但是这种方法需要的计算时间随着坐标位置的增加会呈指数级别增长，所以暴力破解方法的时间复杂度是 O(n2)。 一个更好的解决办法是采用分而治之算法（Divide and Conquer）。也就是先用二分法递归计算出各点之间的距离，然后逐一合并找出最小的那一个距离。这个算法的时间复杂度是 O(nlog2n) 。但是这里面有一个地方需要做特殊处理，我们一起来看看具体算法： 注：该图片来自网页 - Closest Pair: A Divide-and-Conquer Approach 算法思路： 把所有的点集合 S 分为大致数量相等的两部分 S1和…
中级编程通关练习题 #10 – 递增数列
给定一个全部是数字的字符串，检查里面的数字是否包含一个递增数列。一个递增数列就是从第三个数字开始，每个数字都是前面两个数字之和。譬如，字符串 “123581321”里面就包含一个递增数列：1、2、3、5、8、13、21，因为 1+2 = 3， 2+3 = 5，5+8 = 13， 8+13 = 21。 输入样例： "230326294156250" 输出样例： True 上面的输入样例的数字可以分割成下面的数列：2，30，32，62，94，156，250。从第三个数字开始，每个数字都是前面两个数字相加之和。所以输出结果是 True。 算法思路： 可以采用递归回溯（backtrack）算法，从第三个数字开始检查，前面两个数字相加是否等于后面数字的开始数字。如果相等，则递归继续检查。如果不相等，则增加前面两个数字的长度，然后再次做检查。
中级编程通关练习题 #9 – 旋转矩阵
给定一个 m x n 的矩阵（m > 3, n > 3），和一个旋转角度（90°，180°，270°），按照度数来逆时针旋转矩阵。譬如下图中的样例，给定的矩阵分别逆时针旋转90°、180°、270°后的结果： 输入样例： matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]angle = 90 输出样例： [[4, 8,…
初级编程通关练习题 #17 – 数组合并区间
给定一个数组，里面的每个元素都是一个区间，即两个数值组成的子数组，第一个数值代表区间低值，第二个数值代表区间高值。实现一个函数检查数组里面的每一个区间，如果两个区间有重合的部分则合并为一个区间，返回合并后的区间列表。 输入样例： array = [[-2, 3], [10, 13], [2, 5], [7, 10], [15, 17]] 输出样例： [[-2, 5], [7, 13], [15, 17]] 算法思路： 首先将数组按照区间的低值由小到大排序从第二个区间开始，检查每一个区间的低值和它前面的区间的高值是否有重合如果有重合则合并两个区间，如果没有重合则把该区间添加到返回列表中。
高级编程通关练习题 #3 – 矩阵围城
给定一个 m x n 字符串矩阵，m 和 n 都大于 3。矩阵里的每一个元素都是一个字母，检查是否有相同字母在矩阵里面形成一个围城。如下图所示，字母 a 在这个 7 x 5 的矩阵里面形成了一个围城。 输入样例： grid = [["a", "a", "a", "a", "a", "b", "b"],["a", "c", "c", "c", "a", "a",…
初级编程通关练习题 #16 – 面积最大值
给定一组整数数组，数组里的每一个数值都代表长方形的边长，另外一边的边长为数值之间的距离（每个数值和相邻数值之间的距离都为 1）请找出该长方形的最大面积。 输入样例： [6, 16, 9, 12, 16, 7, 13, 10, 15, 17] 输出样例： 128 在上面的输入样例中，面积最大值为第二个数值16到最后数值17之间的区域，如下图所示。两个数值之间的距离为8，16 x 8 = 128。 算法思路： 需要准备两个指针，一个从头往后移动，另外一个从尾往前移动。每次移动指针时检查当前指针指向的两个数值所组成的面积，如果比已经找到的最大值要大，则替换最大值。每次只能移动两个指针其中的一个，当前数值最大的那个指针保持不动，移动另外一个指针。每次移动指针后，需要再次比较两个数值来决定下次移动哪一个指针。
中级编程通关练习题 #8 – 矩阵区域最大值
给定一个 MxN 的矩阵，里面的数值都是 1 和 0，一个有效区域是数值为 1 的位置上下左右连接而成。矩阵内部可能有多个有效区域，请找出区域最大的那一个。譬如下面的图案代表一个 12 x 7 的矩阵，黑色格子代表 0，黄色格子代表 1，矩阵里面总共有五个有效区域，最大的一个是8（八个黄色格子连接在一起）。 输入样例： matrix = [[0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0,…
中级编程通关练习题 #7 – 有效IP地址组合
给定一个字符串里面都是数字，按照IP地址的格式来进行分隔，找出所有合法的点分十进制IP地址组合。 IP地址由32位二进制数组成，为便于使用，常以XXX.XXX.XXX.XXX形式表现，每组XXX代表小于或等于255的10进制数，该表示方法称为点分十进制。 例如 CodeGuru.Academy的IP地址是： 162.241.244.103。更多关于IP地址的信息，可以查看维基百科https://zh.wikipedia.org/wiki/IP%E5%9C%B0%E5%9D%80。 输入样例： "1010235" 输出样例： ['1.0.10.235', '1.0.102.35', '10.1.0.235', '10.10.2.35', '10.10.23.5', '10.102.3.5', '101.0.2.35', '101.0.23.5'] 上面的输入样例字符串"1010235"，总共可以分隔为八个不同的有效IP地址。 算法思路： 首先需要定义一个函数来检查一个点分十进制是否是合法的IP地址。然后可以采用下面两种方法来进行字符串分隔：方法一：使用递归函数进行深度优先搜索方法二：多重内嵌for循环来穷举所有的可能，并逐一检查
初级编程通关练习题 #15 – 电话号码字母组合
给定一个正整数 N（N 的长度大于 1 小于 5），按照下面图案中电话按键每个数字所对应的字母字符串，找出该整数可以表示的全部字母组合。注意：数字 1 没有对应的字母。 (该图片来自维基百科 - https://en.wikipedia.org/wiki/Telephone_exchange_names ) 输入样例： N= 3415 输出样例： ['dgj', 'dgk', 'dgl', 'dhj', 'dhk', 'dhl', 'dij', 'dik', 'dil', 'egj', 'egk', 'egl', 'ehj', 'ehk',…