1. 递增数组的规律

题目来源

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

1.1 解题思路

双指针法：

数列满足递增，设两个头尾两个指针i和j，

若ai + aj == sum，就是答案（相差越远乘积越小，原因见1.2）； 若ai + aj > sum，aj肯定不是答案之一（前面已得出 i 前面的数已是不可能），j -= 1； 若ai + aj < sum，ai肯定不是答案之一（前面已得出 j 后面的数已是不可能），i += 1；

1.2 Trick

一开始的思路是利用哈希表（字典）存储 之和为 tsum 的 array[i] 和 array[j]，key为（ array[i], array[j]）, value 是 乘积；最后在存在解时，按照values值排序哈希表，将第一位的key转换为list返回即可。

1
2
3
if hashmap:
    return list(sorted(hashmap.items(), key=lambda item:item[1])[0][0])  
else: return []

但是，其实有个规律助于我们理解“输出两个数的乘积最小的”这句话。

假设：若b>a,且存在，a + b = s; (a - m ) + (b + m) = s, 则：(a - m )(b + m) = ab - (b-a)m - m*m < ab；说明外层的乘积更小。

即第一次遇到的解为最终解。从而有1.1 的解题思路。

1.3 时间复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

1.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding:utf-8 -*-
class Solution:
    # 既然是排序好的，就好办了：左右加逼
    def FindNumbersWithSum(self, array, tsum):
        # write code here
#         hashmap = {}
        i,j = 0, len(array) - 1
        while i <= j :
            if array[i] + array[j] < tsum:
                i+=1
            elif array[i] + array[j] > tsum:
                j-=1
            elif array[i] + array[j] == tsum: 
                return [array[i],array[j]]   
#                 hashmap[(array[i],array[j])] = array[i] * array[j]
#                 i+=1
#                 j-=1
                
        return []
#         if hashmap:
#             return list(sorted(hashmap.items(), key=lambda item:item[1])[0][0])  
#         else: return []

2. 顺时针输出矩阵 == 边转置边输出矩阵第一行

题目来源

  • 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
  • 难度：中等

2.1 Trick

这道题可以使用一种超简单且易理解的方法：

  1. 储存第一行，并将第一行从矩阵中去掉，

  2. 将矩阵“变相转置”（这里的转置理解为将矩阵从地上立起来，比如矩阵是【【1,2,3】， 【4,5,6】】 将它“变相转置”（立起来）为 【【3,6】，【2,5】，【1,4】】 ）

  3. 重复以上两步，直到将第一行去掉之后矩阵为空。

2.2 时间复杂度

  • 时间复杂度：O(mn), 矩阵中每个元素遍历一次
  • 空间复杂度：O(mn), 每个元素需要存下来

2.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        out_list = []
        while matrix:
            # 取出矩阵第一行，这必须是第一步，否则改动矩阵后，再取第一行不符合题意要求
            out_list.extend(matrix[0])
            
            # 如果还有其他行,去掉第一行；否则跳出循环
            # 取了第一行后，就应该改动矩阵，否则立起矩阵也失去意义
            if len(matrix)>1:
                matrix = matrix[1::]
            else:
                break
            # “转置”：把矩阵“立”起来
            matrix = [[row[i] for row in matrix] for i in range(len(matrix[0])-1,-1,-1)]
        return out_list