LeetCode_35 Search a 2D Matrix

题目描述:

1
2
3
4
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

输入样例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false

解法一

由于二维矩阵是有序的,所以可以拉成一维矩阵做二分查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or target is None:
return False
rows, cols = len(matrix), len(matrix[0])
low, high = 0, rows * cols - 1
while low <= high:
mid = (low + high) / 2
num = matrix[mid / cols][mid % cols]
if num == target:
return True
elif num < target:
low = mid + 1
else:
high = mid - 1
return False

解法二

1
2
3
4
5
6
7
for line in matrix:
try:
line.index(target)
return True
except:
pass
return False

解法三

1
2
import numpy as np
return np.isin(target, matrix)

LeetCode_35 Search Insert Position

题目描述:

1
2
3
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.

输入样例:
Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0

1.解法一:暴力遍历

由于给的数组是有序的,所以可以从左往右顺序遍历,把target与数组元素对比,直到找到比target大的元素,该元素的下标即所求。
Time: O(n)
Space: O(n)
code

1
2
def searchInsert(self, nums, target):
return len([num for num in nums if target > num])

2. 解法二:二分查找

依然还是利用数组是有序,这个非常重要的特点。用二分查找可以降低算法时间复杂度。
Time: O(lgN)
Space: O(1)
需要注意的几个点:

  1. mid = (low + high) / 2,这样求中值的方法很容易造成溢出, 当(low + high)大于Integer.MAX_VALUE的时候会溢出,所以推荐使用位运算:mid = (low + high) >> 1,或mid = low + (high - low) / 2
  2. low = mid + 1, 这里的加1绝对不能漏掉,都则程序会陷入死循环。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    def searchInsert(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if target <= nums[0]:
    return 0
    elif target > nums[-1]:
    return len(nums)
    else:
    return self.findUpBorder(nums, target)
    def findUpBorder(self, nums, target):
    low, high = 0, len(nums) - 1
    #mid = low + (high - low) / 2
    mid = (low + high) >> 1
    while(high > low):
    if target < nums[mid]:
    high = mid
    else:
    low = mid + 1
    mid = (low + high) >> 1
    if target == nums[mid - 1]:
    return mid - 1
    return mid

Eigen API 使用

1. 矩阵定义和初始化

1
2
3
MatrixXd D; //声明一个double型的矩阵
MatrixXd D(N, N); //声明一个N * N的double矩阵
MatrixXd D = MatrixXD::zero(N, N); //声明并定义一个N * N的double型的矩阵

最推荐的初始化方法是第三种方法

Eigen matrix 和 Opencv mat的相互转换

在Opencv中core/include/opencv2/core/eigen.hpp文件中已经实现了Eigen matrix和Oencv mat之间的相互转换。下面随便列举两个API。详细的代码内容可以从eigen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void eigen2cv( const Eigen::Matrix<_Tp, _rows, _cols, _options, _maxRows, _maxCols>& src, Mat& dst )
{
if( !(src.Flags & Eigen::RowMajorBit) )
{
Mat _src(src.cols(), src.rows(), DataType<_Tp>::type,
(void*)src.data(), src.stride()*sizeof(_Tp));
transpose(_src, dst);
}
else
{
Mat _src(src.rows(), src.cols(), DataType<_Tp>::type,
(void*)src.data(), src.stride()*sizeof(_Tp));
_src.copyTo(dst);
}
}
void cv2eigen( const Matx<_Tp, _rows, 1>& src,
Eigen::Matrix<_Tp, Eigen::Dynamic, 1>& dst )
{
dst.resize(_rows);
if( !(dst.Flags & Eigen::RowMajorBit) )
{
const Mat _dst(1, _rows, DataType<_Tp>::type,
dst.data(), (size_t)(dst.stride()*sizeof(_Tp)));
transpose(src, _dst);
}
else
{
const Mat _dst(_rows, 1, DataType<_Tp>::type,
dst.data(), (size_t)(dst.stride()*sizeof(_Tp)));
src.copyTo(_dst);
}
}

这里列举一个使用例子。

1
2
Mat im = imread(path);
cv2eigen(res, b);

Search string

描述:

1
对于一个给定的 source 字符串和一个 target 字符串,你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1。

样例:

1
2
如果 source = "source" 和 target = "target",返回 -1。
如果 source = "abcdabcdefg" 和 target = "bcd",返回 1。

我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int strStr(String source, String target) {
if(source == null || target == null){
return -1;
}
if(target.length() == 0){
return 0;
}
for(int i = 0; i < source.length(); i++){
if(source.charAt(i) == target.charAt(0)){
int j;
for(j = 0; j < target.length(); j++){
if(i + j < source.length()){
if(source.charAt(i + j) != target.charAt(j)){
break;
}
}else{
return -1;
}
}
if(j == target.length()){
return i;
}
}
}
return -1;
}

修改后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int strStr(String source, String target) {
if(source == null || target == null){
return -1;
}
for(int i = 0; i < source.length() - target.length() + 1; i++){
int j = 0;
for(j = 0; j < target.length(); j++){
if(source.charAt(i + j) != target.charAt(j)){
break;
}
}
if(j == target.length()){
return i;
}
}
return -1;
}

听见

2018年12月25日,这个日子应该会是我这辈子最后悔的一天。现在我坐在回武汉的火车上,就在昨天晚上,我的爷爷去世了。

人在去世之前,可能自己的内心确实是知道的,所以向来不主动给我打电话的爷爷要求奶奶给我打电话,他听觉退化了,从电话里了解到我在学校过得很好之后,问我时候能回家,有些想我了。我说,我还有一个多月就放寒假了。他笑着挂了电话。大概半个小时候,妈妈打电话过来说爷爷去世了,心肌梗塞导致的,走得很快。

看着火车窗外的风景快速流逝,我感觉到我最爱的亲人也从这个世界消失了,眼泪也不知不觉的留下。

《Python核心编程》第一章习题-正则表达式

1-1

识别后续的字符串: “bat” 、 “bit” 、 “but” 、 “hat” 、 “hit”或者“hut”

1
2
3
strList = ['bat','bit','but','hat','hit','hut']
for c in strList:
print re.match(r'[bh][aiu]t', c).group()

1-2

匹配由单个空格分隔的任意单词对,也就是姓和名。

1
print re.match(r'[A-Za-z]+\s[A-Za-z]+', 'Lin Ye').group()

1-3

匹配由单个逗号和单个空白符分隔的任何单词和单个字母,如姓氏的首字母。

1
result = re.match(r'([A-Za-z]\.)+?\s[A-Za-z]+', 'J. q')

1-4

匹配所有有效 Python 标识符的集合。

1
result = re.match(r'[A-Za-z_][\w_]+', '_abc')

1-5

例如,美国街道地址使用如下格式:1180 Bordeaux Drive。使你的正则表达式足够灵活,以支持多单词的街道名称,如 3120 De la Cruz Boulevard。

1
result = re.match(r'\d+\s([a-zA-Z]+\s*)+', '3120 De la Cruz Boulevard')

1-6

匹配以 “www” 起始且以 “.com” 结尾的简单Web 域名; 例如, www://www. yahoo.com/。选做题:你的正则表达式也可以支持其他高级域名,如.edu、.net 等(例如, http://www.foothill.edu)

1
result = re.match(r'^www\..*\.(com|net|edu)$', 'www.foothill.edu')

1-7

匹配所有能够表示 Python 整数的字符串集。

1
result = re.match(r'[-+]?\d+', '753965')

1-8

匹配所有能够表示 Python 长整数的字符串集

1
result = re.match(r'[-+]?\d+[lL]', '753965L')

1-9

匹配所有能够表示 Python 浮点数的字符串集。

1
result = re.search(r'\d+(\.\d*)?', '1.')

1-10

匹配所有能够表示 Python 复数的字符串集。

1
result = re.search(r'[-]?\d+(\.\d*)?[+-][-]?\d+(\.\d*)?[Jj]', '-1-1j')

1-11

匹配所有能够表示有效电子邮件地址的集合(从一个宽松的正则表达式开始,然后尝试使它尽可能严谨,不过要保持正确的功能).

1
result = re.search(r'(\w+\.)?\[email protected]\w+\.\w+', '[email protected]')

1-12

匹配所有能够表示有效的网站地址的集合 (URL)( )(从一个宽松的正则表达式开始, 然后尝试使它尽可能严谨,不过要保持正确的功能

1
result = re.search(r'(http://)?(w{3}\.)?\w+.com','http://www.baidu.com')

1-13

type()是python的内置函数,写一个正则表达式返回类型

1
2
3
4
>>> type(0)
<type 'int'>
>>> type(.34)
<type 'float'>

1
2
data = "<type 'float'>"
patt = r"'(\w+)'"

1-14

处理日期。 1.2 节提供了来匹配单个或者两个数字字符串的正则表达式模式, 来表示1~ 9 的月份(0?[1-9])。创建一个正则表达式来表示标准日历中剩余三个月的数字。

1
2
patt = r'1[012]'
data = '10'

1-15

处理信用卡号码。1.2 节还提供了一个能够匹配信用卡(CC)号码([0-9]{15,16}) 的正则表达式模式。然而,该模式不允许使用连字符来分割数字块。创建一个允许使用连字符的正则表达式,但是仅能用于正确的位置。例如,15 位的信用卡号码使用 4-6-5 的模式,表明 4 个数字-连字符-6 个数字-连字符-5 个数字;16 位的信用卡号码使用 4-4-4-4 的模式。 记住, 要对整个字符串进行合适的分组。 选做题: 有一个判断信用卡号码是否有效的标准算法。编写一些代码,这些代码不但能够识别具有正确格式的号码,而且能够识别有效的信用卡号码。

1
patt = r'\d{4}-\d{6}-\d{5}|\d{4}-\d{4}-\d{4}-\d{4}'

数据库原理

数据库基本原理

谈到存储与实例,实例是程序,用于将物理上的关系转为逻辑上的关系,将复杂的问题简单化。
(1)块与页
数据库通常不以行(hang)为单位加载数据,因为行的粒度太小(几百字节甚至更低),如果每次IO只读取这点数据,那么IO会很频繁。我们希望程序读取一行数据时再读取连续的许多行数据到内存中,提高击中率。
数据库通常对数据做物理大小的划分,例如以4KB,8KB,16KB等大小为基本单位,称之为块。每个块会存储多行数据,数据库给每个块一个标识符,块内部的每行数据都有自己的行号。数据库使用数据字典来记录数据库中各数据块的偏移量,便于访问。
(2)多个连续块
一个表要存储许多数据,随着数据量的增加肯定不止一个块来存放。然而,磁盘IO是串行化,很多时候我们一次寻道能够读取更多的数据,此时将多个块的数据连续放在一起组成一组数据,可以提高设备性能。
由于内存空间的限制,数据库会以LRU算法管理块,让某些击中率较高的块留在内存,某些击中率较低的块从内存释放掉。如果一个连续的数据块加载后,中间有部分块没有被访问,那么就会被写回磁盘,这些连续加载的顺序快中间就会存在间隙,当再次加载这样的块时,数据库通常不会再一次加载这些块,而是加载空隙中没有的块,这样会造成了多次IO。
(3)修改表
如果一个表中的每一个数据块都存储了数据,此时要向一个表中添加一个字段,并马上向这个字段写值,会发生什么呢?
某些数据库会事先在写入每个块时给它们预留少量的空间,也就是每个块都不会写满,以便于添加字段时来用。如果添加的是超长字段,那么预留的空间也不够,数据的某个部分会存在另一个块中,一次IO变成了多次IO。所以线上数据库加字段不是一件很随意的事情。
当表结构发生改变时,通常会创建一个新表,并将原表中的数据全部拷贝到新表中,在拷贝过程中会“锁表”。这种操作对于小表的操作还行,对于大表就会很耗时。因此对于大数据的存储,通常采用所谓的“分库分表”策略。
(4)删除表