Onwaier's Blog

大步后退亦或停止不前,不如匍匐前进

0%

参考资料

  1. Python OpenCV中的numpy与图像类型转换
  2. 解决ndarray的类型错误
  3. Python OpenCV格式和PIL.Image格式 互转
  4. python模块 opencv-python与PIL.Image图像常用方法与相互转换
  5. OpenCV读取图片与PIL读取图片的差别
  6. python中PIL.Image,OpenCV,Numpy图像格式相互转换
  7. PIL.Image和np.ndarray图片与Tensor之间的转换

Numpy与Opencv格式互转

参照资料1

Python OpenCV存储图像使用的是Numpy存储,所以可以将Numpy当做图像类型操作,操作之前还需进行类型转换,转换到int8类型

对Opencv存储的图像格式进行验证

  • 输入:
1
2
3
4
5
6
7
8
9
10
11
"""
numpy与Opencv图像类型的转换
> Python OpenCV存储图像使用的是Numpy存储,所以可以将Numpy当做图像类型操作,操作之前还需进行类型转换,转换到int8类型
"""
import cv2
import numpy as np
from PIL import Image

img = cv2.imread('./Messi.jpg')
print("shape:" + str(img.shape))
print(type(img)) #数据类型显示为numpy.ndarray
  • 输出:
1
2
shape:(500, 500, 3)
<class 'numpy.ndarray'>

存储类型为numpy.ndarray,这是否表明numpy与Opencv可以直接互操作呢?答案是否定的。因为图像存放时,每个像素值都是非负的,并且取值范围受限于存储位数的限制,所以将numpy.ndarray存储为图像格式,需要先将其进行类型转换。

  • 输入:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
array = np.ones([20, 30])
print("shape:" + str(array.shape))
print(type(array)) #数据类型显示numpy.ndarray 与Opencv图像类型格式相同

# 可以将ndarray作为Opencv图片进行处理,但在处理之前一般进行类型转换
"""
类型转换时需注意,我参照博客转成int8类型,可以写入,但是单通道转多通道会出错
Assertion failed) VScn::contains(scn) && VDcn::contains(dcn) && VDepth::contains(depth) in function 'CvtHelper'
参照github是类型错误导致的
"""
array = np.uint8(array)
print("shape:" + str(array.shape))
cv2.imwrite('test.jpg', array)

# 类型转换
array = cv2.cvtColor(array, cv2.COLOR_GRAY2BGR)
print("shape:" + str(array.shape))
cv2.imwrite('test2.jpg', array)
  • 输出:
1
2
3
4
shape:(20, 30)
<class 'numpy.ndarray'>
shape:(20, 30)
shape:(20, 30, 3)

正如注释所写,类型转换时,要注意,我参照资料1转为int8,在通道转换时出现了错误Assertion failed) VScn::contains(scn) && VDcn::contains(dcn) && VDepth::contains(depth) in function ‘CvtHelper’,参照资料2进行解决。

IPL.Image与Opencv相互转换

先复习一下Opencv与IPL.Image的读,写,显示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
"""
Opencv 图像的读,写,显示
PIL.Image的读,写,显示
"""

# Opencv读
img = cv2.imread('Messi.jpg')
# Opencv写
cv2.imwrite('Messi2.jpg', img)
# Opencv显示
cv2.imshow('Messi', img)


# PIL.Image读
img = Image.open('Messi.jpg')
# PIL.Image写
img.save('Messi3.jpg')
# PIL.Image显示
img.show()

Image.open()读取的通道顺序是RGB,cv2.imread()读取的通道顺序为BGR。 Image.open()函数只是保持了图像被读取的状态,但是图像的真实数据并未被读取,因此如果对需要操作图像每个元素,如输出某个像素的RGB值等,需要执行对象的load()方法读取数据 PIL.Image.save()直接保存RGB的图片 cv2.imwirte()保存图片的时候相当于做了BGR2RGB再去保存

OpenCV转换成PIL.Image格式

  • 代码:
1
2
3
4
5
6
import cv2  
from PIL import Image
import numpy
img = cv2.imread("Messi.jpg")
cv2.imshow("OpenCV",img)
Image.fromarray(cv2.cvtColor(img,cv2.COLOR_BGR2RGB))

PIL.Image转换成OpenCV格式:

  • 代码:
1
2
3
4
5
import cv2  
from PIL import Image
import numpy
image = Image.open("Messi.jpg")
img = cv2.cvtColor(numpy.asarray(image),cv2.COLOR_RGB2BGR)

PIL.Image与Numpy格式的相互转换

相当于 Opencv与PIL.Image的相互转换少了通道的变换。

  • Numpy转PIL.Image
1
2
3
4
5
import cv2
from PIL import Image
import numpy
array = np.ones(100, 200)
Image.fromarray(array)
  • PIL.Image转Numpy
1
2
3
4
5
import cv2
from PIL import Image
import numpy
image = Image.open("Messi.jpg")
array = numpy.asarray(image)

补充

参考资料6

list与tuple转换

1
2
3
a = [1, 2, 3]#a is a list
b = tuple(a) # b is a tuple
c = list(b) # c is a list

list,tuple,ndarray转换

1
2
3
a = [1, 2, 3] # a is a list
arr = np.array(a) # arr is a ndarray
b = tuple(arr) # b is a tuple
1
2
3
a = (1, 2, 3)# a is a tuple
arr = np.arr(a) # arr is a ndarray
b = list(arr) # b is a list

torch的tensor与numpy转换

1
2
3
4
5
# tensor 转numpy
array = a.numpy() # a is a tensor

# numpy 转tensor
torch.from_numpy(array) # array is a ndarray

tensor与PIL image转换

pytorch官方提供了torchvision.transforms包,可以用transforms来实现tensor 与PIL image的转换

ToTensor把一个取值范围是[0,255]的PIL.Image或者shape为(H,W,C)的numpy.ndarray,转换成形状为[C,H,W],取值范围是[0,1.0]的torch.FloadTensor

  • tensor与PIL image的转换
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
import torch
from torchvision import transforms
from PIL import Image
import cv2

# PIL Image转tensor

transform1 = transforms.Compose([
pass, # 这里可以写对PIL的相关操作(裁剪,旋转等)
transforms.ToTensor(),
]
)
img_PIL = Image.open('test.jpg').convert('RGB')
img_PIL_tensor = transform1(img_PIL)# 将PIL image转为tensor
print(type(img_PIL))
print(type(img_PIL_tensor))

# transforms也提供了tensor转PIL image的方法
new_img_PIL = transforms.ToPILImage()(img_PIL_Tensor).convert('RGB')

transform2 = transforms.Compose([
pass, # transform没有对Opencv的相关操作(裁剪,旋转等)
transforms.ToTensor(),
]
)

img_Opencv = cv2.imread('test'.jpg)
img_Opencv_tensor = transform2(img_Opencv)


参考资料

  1. 论文MJRTY A Fast Majority Vote Algorithm
  2. 算法演示网站
  3. 维基百科

算法解读

概述

摩尔投票法(Boyer–Moore majority vote algorithm)出自论文,算法解决的问题是如何在任意多的候选人(选票无序),选出获得票数最多的那个。常见的算法是扫描一遍选票,对每个候选人进行统计的选票进行统计。当候选人的数目固定时,这个常见算法的时间复杂度为:$O(n)$,当候选人的数目不定时,统计选票可能会执行较长时间,可能需运行$O(n^2)$的时间。当选票有序时,可以很容易编出$O(n)$的程序,首先找到中位数,然后检查中位数的个数是否超过选票的一半。这篇论文针对无序且侯选人不定的情形,提出了摩尔投票算法。算法的比较次数最多是选票(记为n)的两倍,可以在$O(n)$时间内选出获票最多的,空间开销为$O(1)$。

算法

  • 形象化描述

想象着这样一个画面:会议大厅站满了投票代表,每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的(所选的候选人不同)两个人,会打一架,并且会同时击倒对方。显而易见,如果一个人拥有的选票比其它所有人加起来的选票还要多的话,这个候选人将会赢得这场“战争”,当混乱结束,最后剩下的那个代表(可能会有多个)将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数(选票都未超过一半),那么最后站在那的代表(一个人)并不能代表所有的选票的大多数。因此,当某人站到最后时,需要统计他所选的候选人的选票是否超过一半(包括倒下的),来判断选票结果是否有效。

  • 算法步骤

算法分为两个阶段:pairing阶段和counting阶段。

  1. pairing阶段:两个不同选票的人进行对抗,并会同时击倒对方,当剩下的人都是同一阵营,相同选票时,结束。

  2. counting阶段:计数阶段,对最后剩下的下进行选票计算统计,判断选票是否超过总票数的一半,选票是否有效。

  • pairing阶段的简化

选票不同就要大干一架,太过粗鲁,这里提供一种更加现代化的文明方式。 在场的有个叫onwaier的,他很聪明,他想到一个方法。他用他那犀利人目光扫一遍所有代表们的选票,在脑子记住两件事,当前的候选人的名字cand和他对应的计数k(并不是他的选票数)。起始时,k的值为0,看每个人的选票时,先想想现在k是否为0,如果是0就将cand更新为他将看到的候选人的名字并且将k的值更新为1。观察每个人选票的过程,如果这个人的选票与cand相同,则将k的值加1;否则,将k的值减1。最后的cand可能胜选,还需统计他的总选票数是否超过一半。

算法证明

证明: 假设共有n个代表(一人一票,选票总数为n)。当onwaier看到第i个代表的选票时$(1 \leq i \leq n)$,前面他已经看到的所有选票可以分为两组,第一组是k个代表赞同cand;另一组是选票可以全部成对(选票不同)抵销。当处理完所有的选票时,如果存在大多数,则cand当选。 假设存在一个x其不同于cand,但拥有的选票超过$n/2$。但因为第二组的选票可以全部成对抵销,所以x最多的选票数为$(n - k) / 2$,因此x必须要收到第一组的选票才能超过一半,但是第一组的选票都是cand的,出现矛盾,假设不成立。 所以,如果存在大多数,cand就是那个。

算法演示

来自网站 选票情况为: A A A C C B B C C C B C C 结果应该是C

  • 算法执行过程

算法代码

  • 伪代码

伪代码来自维基百科

  • c++代码
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
35
/*
根据多数元素出现的次数大于n/2且超过其它元素出现次数之和这一特点,进行统计

时间复杂度为:O(n)
空间复杂度为:O(1)
*/
int majorityElement(vector<int>& nums) {
int k = 0, cand = 0;
//成对抵销阶阶段
for(auto num:nums){
if(k == 0){
cand = num;
k = 1;
}
else{
if(num == cand){
++k;
}
else{
--k;
}
}
}
//计数阶段 判断cand的个数是否超过一半
k = 0;
for(auto num:nums){
if(num == cand){
++k;
}
}
if(k <= nums.size() / 2){
cand = -1;//表示未超过一半
}
return cand;
}

算法应用

摩尔投票法的一大应用就是求众数。 相关题目有:

  1. 169. 多数元素

其中题1的代码和上面的c++代码相同,它就是摩尔选票法的直接应用。

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
/*
根据多数元素出现的次数大于n/2且超过其它元素出现次数之和这一特点,进行统计

时间复杂度为:O(n)
空间复杂度为:O(1)

摩尔选票法的直接应用,因为题目说明一定存在大多数,所以不用进行第二阶段
*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
int cnt = 0, res = 0;
for(auto num:nums){
if(cnt == 0){
res = num;
cnt = 1;
}
else{
if(num == res){
++cnt;
}
else{
--cnt;
}
}
}
return res;
}
};
  1. 229. 求众数 II

题2的代码则是摩尔选票法的变形。 题2可以看成这样一个情形:一个班里要选副班长,至多2位。每一个投一票,成为副班长得票必须超过总票数的三分之一。 因为可能会产生两名。所以候选人$cand$与计数$cnt$都转成相应的数组形式$cands$与$cnts$,长度都为2。 第一阶段成对抵销时,cands[0]cands[1]的选票不相互抵销,即如果代表将票投给了cands[0],则cands[1]对应的cnts[1]的值不变化。 投给cands[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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
时间复杂度为:O(n)
空间复杂度为:O(1)
*/
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int len = nums.size();
vector<int>res, cands, cnts;
if(len == 0){//没有元素,直接返回空数组
return res;
}
cands.assign(2, nums[0]);
cnts.assign(2, 0);
//第1阶段 成对抵销
for(auto num: nums){
bool flag = false;
for(int i = 0; i < cands.size(); ++i){
if(num == cands[i]){
++cnts[i];
flag = true;
break;
}
}
if(!flag){
bool flag2 = false;
for(int j = 0; j < cands.size(); ++j){
if(cnts[j] == 0){
flag2 = true;
cands[j] = num;
cnts[j]++;
}
}
if(!flag2){
for(int j = 0; j < cnts.size(); ++j){
--cnts[j];
}
}
}
}

//第2阶段 计数 数目要超过三分之一
cnts[0] = cnts[1] = 0;
if(cands[0] == cands[1])
cands.pop_back();
for(auto num:nums){
for(int i = 0; i < cands.size(); ++i){
if(cands[i] == num){
++cnts[i];
break;
}
}
}
for(int i = 0; i < cands.size(); ++i){
if(cnts[i] > len / 3){
res.push_back(cands[i]);
}
}
return res;
}
};
  1. 至多选出m个代表,每个选票数大于n / (m + 1)

只需要将题2的判断最后候选是否相同代码进行修改即可。

参考资料

  1. 【Dlib】人脸检测、特征点检测、人脸对齐、人脸识别
  2. 深度学习与人脸识别之-脸部分割与校正
  3. github项目FaceSegmentation
  4. http://dlib.net/face_alignment.py.html
  5. 知乎问答

关键点检测

首先获取模型,下载地址在,我使用的是获取脸部68个关键点的模型shape_predictor_68_face_landmarks.dat 68关键点位置示意图如下: 首先贴出python代码 ` ```python
“””
代码功能:

  1. 用dlib人脸检测器检测出人脸,返回的人脸矩形框
  2. 对检测出的人脸进行关键点检测并用圈进行标记
  3. 将检测出的人脸关键点信息写到txt文本中
    “””
    import cv2
    import dlib
    import numpy as np

predictor_model = ‘shape_predictor_68_face_landmarks.dat’
detector = dlib.get_frontal_face_detector()# dlib人脸检测器
predictor = dlib.shape_predictor(predictor_model)

cv2读取图像

test_img_path = “input/Messi.jpg”
output_pos_info = “output_pos_info/Messi.txt”
img = cv2.imread(test_img_path)
file_handle = open(output_pos_info, ‘a’)

取灰度

img_gray = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)

人脸数rects(rectangles)

rects = detector(img_gray, 0)

for i in range(len(rects)):
landmarks = np.matrix([[p.x, p.y] for p in predictor(img,rects[i]).parts()])
for idx, point in enumerate(landmarks):

    # 68点的坐标
    pos = (point[0, 0], point[0, 1])
    print(idx+1, pos)
    pos_info = str(point[0, 0]) + ' ' + str(point[0, 1]) + '\n'
    file_handle.write(pos_info)
    # 利用cv2.circle给每个特征点画一个圈,共68个
    cv2.circle(img, pos, 3, color=(0, 255, 0))
    # 利用cv2.putText输出1-68
    #font = cv2.FONT_HERSHEY_SIMPLEX
    #cv2.putText(img, str(idx+1), pos, font, 0.5, (0, 0, 255), 1, cv2.LINE_AA)

file_handle.close()
cv2.imwrite(“output/Messi_keypoints.png”, img)

大致过程如下:先用人脸检测器获取到人脸矩形框rectangles,再用68点shape模型获取`full_object_detection`对象。最后将关键点标记出来,并写入文本中。 `rects
1
2
3
4
5

```python
predictor = dlib.shape_predictor(predictor_model)
predictor(img,rects[i]).parts()
predictor(img, rects[i]).part(1)

predictor返回的是一个full_object_detection对象,通过parts()可以获得所有关键点的位置,通过part(idx)idx从0开始,可以获取某个关键点的信息。 测试图片的原图与标注关键点后图片如下图所示。

脸部分割

两种方式:矩形框分割人脸和 不规则形状分割人脸

矩形框分割人脸

可以采用dlib.get_face_chip()来分割人脸

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
"""
代码功能:
1. 用dlib人脸检测器检测出人脸,返回的人脸矩形框
2. 对检测出的人脸进行关键点检测并切割出人脸
"""
import cv2
import dlib
import numpy as np

predictor_model = 'shape_predictor_68_face_landmarks.dat'
detector = dlib.get_frontal_face_detector()# dlib人脸检测器
predictor = dlib.shape_predictor(predictor_model)

# cv2读取图像
test_img_path = "input/Messi.jpg"
img = cv2.imread(test_img_path)
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
# 人脸数rects
rects = detector(img, 0)
# faces存储full_object_detection对象
faces = dlib.full_object_detections()

for i in range(len(rects)):
faces.append(predictor(img,rects[i]))

face_images = dlib.get_face_chips(img, faces, size=320)
for image in face_images:
cv_bgr_img = cv2.cvtColor(image, cv2.COLOR_RGB2BGR)
cv2.imwrite('output/Messi_clip.png', cv_bgr_img)

Dlib检测出的脸部区域对于下巴和额头区域会做过多的裁剪,并且分割使用的是矩形框。 分割结果如图

不规则形状分割人脸

先用dlib等打点工具把人脸最外层的landmark点打出来,然后利用opencv的convexhull得到凸包然后就可以抠出人脸区域了.

python代码(获取人脸的掩模)

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def get_image_hull_mask(image_shape, image_landmarks, ie_polys=None):
# get the mask of the image
if image_landmarks.shape[0] != 68:
raise Exception(
'get_image_hull_mask works only with 68 landmarks')
int_lmrks = np.array(image_landmarks, dtype=np.int)

#hull_mask = np.zeros(image_shape[0:2]+(1,), dtype=np.float32)
hull_mask = np.full(image_shape[0:2] + (1,), 0, dtype=np.float32)

cv2.fillConvexPoly(hull_mask, cv2.convexHull(
np.concatenate((int_lmrks[0:9],
int_lmrks[17:18]))), (1,))

cv2.fillConvexPoly(hull_mask, cv2.convexHull(
np.concatenate((int_lmrks[8:17],
int_lmrks[26:27]))), (1,))

cv2.fillConvexPoly(hull_mask, cv2.convexHull(
np.concatenate((int_lmrks[17:20],
int_lmrks[8:9]))), (1,))

cv2.fillConvexPoly(hull_mask, cv2.convexHull(
np.concatenate((int_lmrks[24:27],
int_lmrks[8:9]))), (1,))

cv2.fillConvexPoly(hull_mask, cv2.convexHull(
np.concatenate((int_lmrks[19:25],
int_lmrks[8:9],
))), (1,))

cv2.fillConvexPoly(hull_mask, cv2.convexHull(
np.concatenate((int_lmrks[17:22],
int_lmrks[27:28],
int_lmrks[31:36],
int_lmrks[8:9]
))), (1,))

cv2.fillConvexPoly(hull_mask, cv2.convexHull(
np.concatenate((int_lmrks[22:27],
int_lmrks[27:28],
int_lmrks[31:36],
int_lmrks[8:9]
))), (1,))

# nose
cv2.fillConvexPoly(
hull_mask, cv2.convexHull(int_lmrks[27:36]), (1,))

if ie_polys is not None:
ie_polys.overlay_mask(hull_mask)
print()
return hull_mask

方法利用的就是opencv的convexhull得到凸包然后就可以抠出人脸区域。 得到掩模,这里使用两种方式来得到人脸区域 1. 将mask作为$\\alpha$通道,来控制图片区域的透明度,最后得到图片是4通道的

1
2
3
4
5
6
7
8
9
10
def merge_add_alpha(img_1, mask):
# merge rgb and mask into a rgba image
r_channel, g_channel, b_channel = cv2.split(img_1)
if mask is not None:
alpha_channel = np.ones(mask.shape, dtype=img_1.dtype)
alpha_channel *= mask*255
else:
alpha_channel = np.zeros(img_1.shape[:2], dtype=img_1.dtype)
img_BGRA = cv2.merge((b_channel, g_channel, r_channel, alpha_channel))
return img_BGRA

分割结果

  1. 掩模与原始图像进行与运算,返回图像是三通道。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge_add_mask(img_1, mask):
if mask is not None:
height = mask.shape[0]
width = mask.shape[1]
channel_num = mask.shape[2]
for row in range(height):
for col in range(width):
for c in range(channel_num):
if mask[row, col, c] == 0:
mask[row, col, c] = 0
else:
mask[row, col, c] = 255

r_channel, g_channel, b_channel = cv2.split(img_1)
r_channel = cv2.bitwise_and(r_channel, mask)
g_channel = cv2.bitwise_and(g_channel, mask)
b_channel = cv2.bitwise_and(b_channel, mask)
res_img = cv2.merge((b_channel, g_channel, r_channel))
else:
res_img = img_1
return res_img

分割结果为

人脸对齐

思路比较简单,计算两眼连线与水平线的夹角,然后通过角度得到对应的旋转矩阵。对图片进行相应的变换。

1
2
3
4
5
6
7
8
9
10
def single_face_alignment(face, landmarks):
eye_center = ((landmarks[36, 0] + landmarks[45, 0]) * 1. / 2, # 计算两眼的中心坐标
(landmarks[36, 1] + landmarks[45, 1]) * 1. / 2)
dx = (landmarks[45, 0] - landmarks[36, 0]) # note: right - right
dy = (landmarks[45, 1] - landmarks[36, 1])

angle = math.atan2(dy, dx) * 180. / math.pi # 计算角度
RotateMatrix = cv2.getRotationMatrix2D(eye_center, angle, scale=1) # 计算仿射矩阵
align_face = cv2.warpAffine(face, RotateMatrix, (face.shape[0], face.shape[1])) # 进行放射变换,即旋转
return align_face

人脸对齐后如图 这样就完成人脸检测—>人脸关键点检测—>人脸分割—>人脸对齐。 具体代码参照github 可以用以上方法对fer2013数据集进行预处理,如图所示。

问题描述

我的博客是两列布局,当文章内容过多时,向下滑动,左侧栏会出现空白,影响阅读体验。想要实现这种效果:当左侧栏滑到底时,不继续左边内容向下滑动。查阅网上的资料,实现的方法大致分为三种。

解决方法

解决方法大致分为两种类型:通过插件实现或者修改代码。

插件Q2W3 Fixed Widget

参考博客,我添加后没有达到理想效果,可能是哪里没设置好或者设置冲突。 - 安装插件 通过插件安装器搜索或者zip压缩包安装即可.

  • 设置Widget固定 先启动插件Q2W3 Fixed Widget,然后点击外观->小工具. 对于添加在左侧栏的小工具,多了一个设置选项。如图所示。 将需要固定的工具的Fixed widget勾上即可。

    修改代码

    参照博客

    1. 修改js和css代码
    • 修改single.php文件 在文件最后添加如下代码
    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
    <script type="text/javascript" src="http://code.jquery.com/jquery.min.js"></script>
    <script type="text/javascript">
    $(function(){
    var offset_left = $(".sidebar").offset().left; //body左边距 = 右边距
    var sidebar_w = $(".sidebar").width(); //侧边栏宽度
    var sidebar_h = $(".sidebar").outerHeight(); //侧边栏高
    var sidebar_top = $(".sidebar").offset().top; //侧边栏上边距
    console.log(sidebar_top + sidebar_h)
    console.log($(window).height())
    console.log($(document).height())
    console.log(window.innerHeight)
    $(document).scroll(function(){
    var scroll_h = $(document).scrollTop(); //滚动条高度
    if( scroll_h > (sidebar_top+sidebar_h - window.innerHeight)){ //当滚动条高度 > 侧边栏底部到顶部的高
    $(".sidebar").addClass("fixed"); //给侧边栏添加fixed类
    $(".fixed").css({
    'width':sidebar_w+'px', //设置宽度
    'top':sidebar_top + 'px' //设置上边距
    });
    }else{ //如果滚动条高度 < 侧边栏底部到顶部的高
    $(".sidebar").removeClass("fixed"); //去除侧边栏的fixed类
    }
    })
    });
    </script>
    • 修改style.cssstyle.css查找.sidebar在其下面添加类fixed的样式代码。
1
2
3
4
.fixed{
position:fixed;
z-index:999;
}

最后实现效果如图所求。 最后实现效果是左侧栏滑到底时,直接回到顶部。

  1. 利用第三方js代码 参照博客
  • 下载第三方js 在github下载theia-sticky-sidebar

放到js目录下,我的目录位置为:/www/wwwroot/onwaier.com/wp-content/themes/twentyfifteen/js

  • 修改single.php代码 在原代码最后加入以下代码
1
2
3
4
5
6
7
8
9
10
<script type="text/javascript" src="http://code.jquery.com/jquery.min.js"></script>
<script src="<?php echo esc_url( get_template_directory_uri() ); ?>/js/theia-sticky-sidebar.js"></script>
<script type="text/javascript">
$(document).ready(function() {
$('.sidebar').theiaStickySidebar({
// Settings
additionalMarginTop: 30
});
});
</script>

最后实现效果如图所求。 注意:上面代码修改都是single.php,只能修改每篇文章的侧栏滑动效果,如果想要修改首页的侧栏滑动效果,可以修改index.php的代码.

神经网络的训练过程

  1. 定义一个包含可训练参数的神经网络

  2. 迭代整个输入

  3. 通过神经网络处理输入

  4. 计算损失(loss)

  5. 反向传播梯度到神经网络的参数

  6. 更新网络的参数,典型的用一个简单的更新方法:weight = weight - learning_rate *gradient

定义神经网络

用下面代码可以构建一个典型的神经网络

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
35
36
37
38
39
import torch
import torch.nn as nn
import torch.nn.functional as F


class Net(nn.Module):

def __init__(self):
super(Net, self).__init__()
# 1 input image channel, 6 output channels, 5x5 square convolution
# kernel
self.conv1 = nn.Conv2d(1, 6, 5)
self.conv2 = nn.Conv2d(6, 16, 5)
# an affine operation: y = Wx + b
self.fc1 = nn.Linear(16 * 5 * 5, 120)
self.fc2 = nn.Linear(120, 84)
self.fc3 = nn.Linear(84, 10)

def forward(self, x):
# Max pooling over a (2, 2) window
x = F.max_pool2d(F.relu(self.conv1(x)), (2, 2))
# If the size is a square you can only specify a single number
x = F.max_pool2d(F.relu(self.conv2(x)), 2)
x = x.view(-1, self.num_flat_features(x))
x = F.relu(self.fc1(x))
x = F.relu(self.fc2(x))
x = self.fc3(x)
return x

def num_flat_features(self, x):
size = x.size()[1:] # all dimensions except the batch dimension
num_features = 1
for s in size:
num_features *= s
return num_features


net = Net()
print(net)

Conv2d

方法原型 torch.nn.Conv2d(in_channels, out_channels, kernel_size, stride=1, padding=0, dilation=1, groups=1, bias=True, padding_mode='zeros') 参数说明 - in_channels:输入图片的通道数 - out_channels:卷积操作后输出图片的通道数 - kernel_size:卷积核的尺寸 - stride:卷积的步长,默认为1 - padding:卷积的padding,默认为0 kernel_size, stride, padding取值可以为a single int或者a tuple of two intsa single int表示宽和高相同。a tuple of two ints表示第1个为宽的大小,第2个为高的大小。 计算输出图片的尺寸的方法:(dilation的值默认为1)

1
2
3
4
5
m = nn.Conv2d(16, 33, 3, stride=2)
input = torch.randn(20, 16, 50, 100)
print(m(input).size())
m = nn.Conv2d(16, 33, (3, 5), stride=(2, 1), padding=(4, 2))
print(m(input).size())

Linear

方法原型 torch.nn.Linear(in_features, out_features, bias=True) $y = xW^T + b$ 对传入的数据进行线性变换。 参数说明 in_features: 每个输入样例的尺寸 out_features:每个输出样例的尺寸 bias:如果设置为False,则不会学习额外的bias参数

1
2
3
4
m = nn.Linear(20, 30)
input = torch.randn(128, 20)
output = m(input)
print(output.size())

max_pool2d

最大池化 方法原型 torch.nn.functional.max_pool3d(*args, ** kwargs) 细节参考MaxPool2d torch.nn.MaxPool2d(kernel_size, stride=None, padding=0, dilation=1, return_indices=False, ceil_mode=False) 参数说明

1
2
3
4
m = nn.MaxPool2d(3, stride=2)
input = torch.randn(20, 16, 50, 32)
output = m(input)
print(output.size())

relu

方法原型 torch.nn.functional.relu(input, inplace=False) → Tensor relu激活函数 细节参照ReLU $ReLU(x)=max(0,x)$

net.parameters()

一个模型可训练的参数可以通过调用 net.parameters() 返回

1
2
3
params = list(net.parameters())
print(len(params))
print(params[0].size()) # conv1's .weight

计算损失值

一个损失函数需要一对输入:模型输出和目标,nn包中提供了一些常见的损失函数。其中nn.MSELoss(均方差)是最简单的损失函数。

1
2
3
4
5
6
7
8
# 计算损失值
output = net(input)
target = torch.randn(10) # a dummy target, for example
target = target.view(1, -1) # make it the same shape as output
criterion = nn.MSELoss()

loss = criterion(output, target)
print(loss)

反向传播

1
2
3
4
5
6
7
8
9
10
# 反向传播前后conv1的偏置项的变化
net.zero_grad() # zeroes the gradient buffers of all parameters

print('conv1.bias.grad before backward')
print(net.conv1.bias.grad)

loss.backward()

print('conv1.bias.grad after backward')
print(net.conv1.bias.grad)

更新神经网络参数

1
2
3
4
5
6
7
# 最简单的更新规则:随机梯度下降
# weight = weight - learning_rate * gradient

# 使用python来实现这个规则
learning_rate = 0.01
for f in net.parameters():
f.data.sub_(f.grad.data * learning_rate)
1
2
3
4
5
6
7
8
9
10
11
12
# 使用内置包
import torch.optim as optim

# create your optimizer
optimizer = optim.SGD(net.parameters(), lr=0.01)

# in your training loop:
optimizer.zero_grad() # zero the gradient buffers
output = net(input)
loss = criterion(output, target)
loss.backward()
optimizer.step() # Does the update 实现参数更新,一般放在反向传播后面

科比一路走好,愿曼巴精神永存!

具体用法参照官方文档

1
2
3
4
5
6
import torch
x = torch.ones(2, 2, requires_grad=True)
# .requires_grad 设置为 True,则会开始跟踪针对 tensor 的所有操作
# 调用 .backward() 来自动计算所有梯度
# 调用 .detach(),它将其与计算历史记录分离
print(x)

1
2
3
# 针对张量进行操作
y = x + 2
print(y)

1
2
3
4
5
# Tensor 和 Function 互相连接并构建一个非循环图,它保存整个完整的计算过程的历史信息
# 每个张量都有一个 .grad_fn 属性保存着创建了张量的 Function 的引用
# 用户自己创建张量,则g rad_fn 是 None
print(x.grad_fn)
print(y.grad_fn)

1
2
3
4
5
# 对 y 做更多的操作
z = y * y * 3
out = z.mean()

print(z, out)

1
2
3
4
5
6
7
8
# .requires_grad( ... ) 会改变张量的 requires_grad 标记。输入的标记默认为 False ,如果没有提供相应的参数。
a = torch.randn(2, 2)
a = ((a * 3) / (a - 1))
print(a.requires_grad)
a.requires_grad_(True)
print(a.requires_grad)
b = (a * a).sum()
print(b.grad_fn)

1
2
3
4
5
6
7
8
# out.backward(y) 后向传播
print(x.requires_grad, y.requires_grad, z.requires_grad)
print(out.requires_grad)
out.backward()
# 由梯度计算的链式法则算到所有的结果变量
# 所计算的梯度都是结果变量关于创建变量的梯度
# graph leaves(事先创建,而非运行得到的中间结果)
print(x.grad)

1
2
3
4
5
6
# 停止对跟踪历史中张量求导
print(x.requires_grad)
print((x ** 2).requires_grad)

with torch.no_grad():
print((x ** 2).requires_grad)

注意 1. 求导只对用户定义的变量进行,即对各个leaf Variable计算梯度 2. 运算结果变量的“requires_grad”是不可以更改的,且不会改变

参考PyTorch官方教程中文版

特点

支持GPU,灵活,支持动态神经网络,底层代码易于理解,命令式体验。

张量(tensor)学习

具体用法参照官方文档

1
2
3
4
import torch
# 构造一个5x3矩阵,不初始化。
x = torch.empty((5, 3)
print(x)

1
2
3
# 构造一个随机初始化的矩阵
x = torch.rand((5, 3))
print(x)

1
2
3
# 构造一个填充某个值的矩阵
x = torch.full((5, 3), 3.1415)
print(x)

1
2
3
# 构造全为0的矩阵,且数据类型为long
x = torch.zeros((5, 3), dtype = torch.long)
print(x)

1
2
3
4
# 构造单位矩阵
# torch.eye(n, m=None, out=None, dtype=None, layout=torch.strided, device=None, requires_grad=False) → Tensor
# Returns a 2-D tensor with ones on the diagonal and zeros elsewhere.
torch.eye(3)

1
2
3
# 使用数据构造一个张量
x = torch.tensor([5.5, 3])
print(x)

1
2
3
4
5
6
7
8
# 用已经存在的tensor构造一个tensor
x = x.new_ones((5, 3), dtype = torch.double)
# new_* methods take in sizes
print(x)

x = torch.randn_like(x, dtype = torch.float)
# size和原x的size相同,但数据类型不同
print(x)

1
2
# 获取维度信息 size()
print(x.size())

1
2
3
# 加法1 +
y = torch.rand(5, 3)
print(x + y)

1
2
3
4
# 加法2 torch.add
# torch.add(input, alpha=1, other, out=None)
# Each element of the tensor other is multiplied by the scalar alpha and added to each element of the tensor input. The resulting tensor is returned.
print(torch.add(x, y))

1
2
3
4
# 提供一个输出tensor作为参数
result = torch.empty((5, 3))
torch.add(x, y, out = result)
print(x + y)

1
2
3
4
5
# add x to y  (in-place)
# 即将x+y的值赋给y
# 任何使张量会发生变化的操作都有一个前缀
y.add_(x)
print(y)

1
2
3
4
5
6
# 改变大小:如果你想改变一个 tensor 的大小或者形状,你可以使用 torch.view:

x = torch.randn(4, 4)
y = x.view(16)
z = x.view(-1, 8) # the size -1 is inferred from other dimensions
print(x.size(), y.size(), z.size())

参照博客github项目

安装依赖(针对centos)

1
2
3
4
5
yum groupinstall 'Development Tools' -y
yum install libcurl-devel -y
yum install sqlite-devel -y
yum install libnotify-devel -y
curl -fsS https://dlang.org/install.sh bash -s dmd

安装后返回信息 执行source ~/dlang/dmd-2.090.0/activate激活环境。

安装客户端

1
2
3
4
5
git clone https://github.com/abraunegg/onedrive.git
cd onedrive
./configure
make clean; make;
sudo make install

认证

执行onedrive命令 复制链接,输入浏览器登录账号进行授权,再将授权后的链接地址复制到SSH客户端运行。

同步

显示参数

1
onedrive --display-config

测试参数

1
onedrive --synchronize --verbose --dry-run

展示执行同步命令即将发生的。 Note: —dry-run can only be used with —synchronize. It cannot be used with —monitor and will be ignored.

执行同步(默认)

默认会将onedrive的所有文件下到/root/onedrive中。

1
onedrive --synchronize

同步某个文件夹

只同步OndDrive某文件夹到本地

1
onedrive --synchronize --single-directory '<dir_name>'

单向—只执行下载同步

1
onedrive --synchronize --download-only 

单向—只执行上传同步

1
onedrive --synchronize --upload-only

部分参数说明

配置文件 在/root/.config/onedrive中 执行cd /root/.config/onedrive,新建配置文件touch config。然后将下面默认配置内容粘贴进去。

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
# Configuration for OneDrive Linux Client
# This file contains the list of supported configuration fields
# with their default values.
# All values need to be enclosed in quotes
# When changing a config option below, remove the '#' from the start of the line
# For explanations of all config options below see docs/USAGE.md or the man page.
#
# sync_dir = "~/OneDrive"
# skip_file = "~*.~**.tmp"
# monitor_interval = "45"
# skip_dir = ""
# log_dir = "/var/log/onedrive/"
# drive_id = ""
# upload_only = "false"
# check_nomount = "false"
# check_nosync = "false"
# download_only = "false"
# disable_notifications = "false"
# disable_upload_validation = "false"
# enable_logging = "false"
# force_http_11 = "false"
# force_http_2 = "false"
# local_first = "false"
# no_remote_delete = "false"
# skip_symlinks = "false"
# debug_https = "false"
# skip_dotfiles = "false"
# dry_run = "false"
# min_notify_changes = "5"
# monitor_log_frequency = "5"
# monitor_fullscan_frequency = "10"
# sync_root_files = "false"
# classify_as_big_delete = "1000"
# user_agent = ""

sync_dir

sync_dir 指定OneDrive中的文件同步到本地文件的位置 若修改sync_dir需在同步时,在原命令后加--resync,如onedrive --synchronize --resync

skip_dir

skip_dir同步时跳过本地的某些文件夹。

skip_file

skip_file同步时跳过本地的某些文件 注意:修改skip_dirskip_file都是相对sync_dir而言的,并且修改后同步,要在原命令后加--resync。 具体见这里

卸载客户端

在下载的onedrive目录下执行命令

1
2
sudo make uninstall
rm -rf ~/.config/onedrive

onedrive帮助

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
OneDrive - a client for OneDrive Cloud Services

Usage:
onedrive [options] --synchronize
Do a one time synchronization
onedrive [options] --monitor
Monitor filesystem and sync regularly
onedrive [options] --display-config
Display the currently used configuration
onedrive [options] --display-sync-status
Query OneDrive service and report on pending changes
onedrive -h --help
Show this help screen
onedrive --version
Show version

Options:

--auth-files ARG
Perform authorization via two files passed in as ARG in the format `authUrl:responseUrl`
The authorization URL is written to the `authUrl`, then onedrive waits for the file `responseUrl`
to be present, and reads the response from that file.
--check-for-nomount
Check for the presence of .nosync in the syncdir root. If found, do not perform sync.
--check-for-nosync
Check for the presence of .nosync in each directory. If found, skip directory from sync.
--confdir ARG
Set the directory used to store the configuration files
--create-directory ARG
Create a directory on OneDrive - no sync will be performed.
--debug-https
Debug OneDrive HTTPS communication.
--destination-directory ARG
Destination directory for renamed or move on OneDrive - no sync will be performed.
--disable-notifications
Do not use desktop notifications in monitor mode.
--disable-upload-validation
Disable upload validation when uploading to OneDrive
--display-config
Display what options the client will use as currently configured - no sync will be performed.
--display-sync-status
Display the sync status of the client - no sync will be performed.
--download-only
Only download remote changes
--dry-run
Perform a trial sync with no changes made
--enable-logging
Enable client activity to a separate log file
--force
Force the deletion of data when a 'big delete' is detected
--force-http-1.1
Force the use of HTTP/1.1 for all operations (DEPRECIATED)
--force-http-2
Force the use of HTTP/2 for all operations where applicable
--get-O365-drive-id ARG
Query and return the Office 365 Drive ID for a given Office 365 SharePoint Shared Library
--get-file-link ARG
Display the file link of a synced file
--help -h
This help information.
--local-first
Synchronize from the local directory source first, before downloading changes from OneDrive.
--log-dir ARG
Directory where logging output is saved to, needs to end with a slash.
--logout
Logout the current user
--min-notify-changes ARG
Minimum number of pending incoming changes necessary to trigger a desktop notification
--monitor -m
Keep monitoring for local and remote changes
--monitor-fullscan-frequency ARG
Number of sync runs before performing a full local scan of the synced directory
--monitor-interval ARG
Number of seconds by which each sync operation is undertaken when idle under monitor mode.
--monitor-log-frequency ARG
Frequency of logging in monitor mode
--no-remote-delete
Do not delete local file 'deletes' from OneDrive when using --upload-only
--print-token
Print the access token, useful for debugging
--remove-directory ARG
Remove a directory on OneDrive - no sync will be performed.
--resync
Forget the last saved state, perform a full sync
--single-directory ARG
Specify a single local directory within the OneDrive root to sync.
--skip-dir
Skip any directories that match this pattern from syncing
--skip-dot-files
Skip dot files and folders from syncing
--skip-file ARG
Skip any files that match this pattern from syncing
--skip-size
Skip new files larger than this size (in MB)
--skip-symlinks
Skip syncing of symlinks
--source-directory ARG
Source directory to rename or move on OneDrive - no sync will be performed.
--sync-root-files
Sync all files in sync_dir root when using sync_list.
--syncdir ARG
Specify the local directory used for synchronization to OneDrive
--synchronize
Perform a synchronization
--upload-only
Only upload to OneDrive, do not sync changes from OneDrive locally
--user-agent ARG
Specify a User Agent string to the http client
--verbose -v+
Print more details, useful for debugging (repeat for extra debugging)
--version
Print the version and exit

参见博客

作用

会话恢复、多会话、会话共享

用法

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
Options:
-4 Resolve hostnames only to IPv4 addresses.
-6 Resolve hostnames only to IPv6 addresses.
-a Force all capabilities into each window's termcap.
-A -[rR] Adapt all windows to the new display width & height.
-c file Read configuration file instead of '.screenrc'.
-d (-r) Detach the elsewhere running screen (and reattach here).
-dmS name Start as daemon: Screen session in detached mode.
-D (-r) Detach and logout remote (and reattach here).
-D -RR Do whatever is needed to get a screen session.
-e xy Change command characters.
-f Flow control on, -fn = off, -fa = auto.
-h lines Set the size of the scrollback history buffer.
-i Interrupt output sooner when flow control is on.
-l Login mode on (update /var/run/utmp), -ln = off.
-ls [match] or
-list Do nothing, just list our SockDir [on possible matches].
-L Turn on output logging.
-m ignore $STY variable, do create a new screen session.
-O Choose optimal output rather than exact vt100 emulation.
-p window Preselect the named window if it exists.
-q Quiet startup. Exits with non-zero return code if unsuccessful.
-Q Commands will send the response to the stdout of the querying process.
-r [session] Reattach to a detached screen process.
-R Reattach if possible, otherwise start a new session.
-s shell Shell to execute rather than $SHELL.
-S sockname Name this session <pid>.sockname instead of <pid>.<tty>.<host>.
-t title Set title. (window's name).
-T term Use term as $TERM for windows, rather than "screen".
-U Tell screen to use UTF-8 encoding.
-v Print "Screen version 4.01.00devel (GNU) 2-May-06".
-wipe [match] Do nothing, just clean up SockDir [on possible matches].
-x Attach to a not detached screen. (Multi display mode).
-X Execute <cmd> as a screen command in the specified session.

常用screen参数

screen -S yourname -> 新建一个叫yourname的session screen -ls -> 列出当前所有的session screen -r yourname -> 回到yourname这个session screen -d yourname -> 远程detach某个session screen -d -r yourname -> 结束当前session并回到yourname这个session

简单使用

安装screen

yum install screen

创建新会话

screen -S onwaier

显示会话列表

暂停与恢复会话

screen -d 27537 27537会话已变成detached状态 screen -r 27537 27537会话再次变成attached状态

杀死与清除dead会话

kill -9 27537 screen -wipe 27537

1304. 和为零的N个唯一整数

题目描述

给你一个整数 n,请你返回 任意 一个由 n 个 各不相同 的整数组成的数组,并且这 n 个数相加和为 0 。 示例 1: 输入:n = 5 输出:[-7,-1,1,3,4] 解释:这些数组也是正确的 [-5,-1,1,2,3],[-3,-1,2,-2,4]。 示例 2: 输入:n = 3 输出:[-1,0,1] 示例 3: 输入:n = 1 输出:[0] 提示: 1 <= n <= 1000

题解1

产生n个不同的数字和为0的方式有很多种,可以对称产生0左右两边的数。具体 如果$n = 2 m$,则结果为:$-m, -(m - 1), \dots, -1, 1, \dots, m - 1, m$。 如果$n = 2 m + 1$,则结果为:$-m, -(m - 1), \dots, -1, 0,1, \dots, m - 1, m$。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
vector<int> sumZero(int n) {
vector<int>res;
if(n & 1 == 1){
res.push_back(0);
}
for(int i = 1; i <= n >> 1; ++i){
res.push_back(i);
res.push_back(-i);
}
return res;
}
};

1305. 两棵二叉搜索树中的所有元素

题目描述

给你 root1 和 root2 这两棵二叉搜索树。 请你返回一个列表,其中包含 两棵树 中的所有整数并按 升序 排序。. 示例 1: 输入:root1 = [2,1,4], root2 = [1,0,3] 输出:[0,1,1,2,3,4] 示例 2: 输入:root1 = [0,-10,10], root2 = [5,1,7,0,2] 输出:[-10,0,0,1,2,5,7,10] 示例 3: 输入:root1 = [], root2 = [5,1,7,0,2] 输出:[0,1,2,5,7] 示例 4: 输入:root1 = [0,-10,10], root2 = [] 输出:[-10,0,10] 示例 5: 输入:root1 = [1,null,8], root2 = [8,1] 输出:[1,1,8,8] 提示: 每棵树最多有 5000 个节点。 每个节点的值在 [-10^5, 10^5] 之间。

题解1

对于二叉搜索树,中序遍历可以得到有序的序列。分别对两棵二叉搜索树中序遍历,然后再对结果进行归并排序。 但比赛为了求速度,直接将结果用sort排序。

代码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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/

void inorder(TreeNode* root, vector<int>& res){
if(root == NULL){
return;
}
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
class Solution {
public:
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
vector<int>res1;
inorder(root1, res1);//中序遍历
inorder(root2, res1);//中序遍历
sort(res1.begin(), res1.end());//这里可修改为归并排序
return res1;
}
};

1306. 跳跃游戏 III

题目描述

这里有一个非负整数数组 arr,你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时,你可以跳到 i + arr[i] 或者 i - arr[i]。 请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。 注意,不管是什么情况下,你都无法跳到数组之外。 示例 1: 输入:arr = [4,2,3,0,3,1,2], start = 5 输出:true 解释: 到达值为 0 的下标 3 有以下可能方案: 下标 5 -> 下标 4 -> 下标 1 -> 下标 3 下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 示例 2: 输入:arr = [4,2,3,0,3,1,2], start = 0 输出:true 解释: 到达值为 0 的下标 3 有以下可能方案: 下标 0 -> 下标 4 -> 下标 1 -> 下标 3 示例 3 输入:arr = [3,0,2,1,2], start = 2 输出:false 解释:无法到达值为 0 的下标 1 处。 提示: 1 <= arr.length <= 5 * 10^4 0 <= arr[i] < arr.length 0 <= start < arr.length

题解1

BFS,判断能否从起始下标到达值为0的下标位置

代码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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
vector<int>target;
int len = arr.size(), frt;
bool flag = false, res = false;
vector<int>mark(len, 0);
vector<int>mark1(len, 0);
for(int i = 0; i < arr.size(); ++i){//将值为0的数字的下标进行标记
if(arr[i] == 0){
mark[i] = 1;
flag = true;
}
}
if(!flag){//不存在值为0的数字
res = false;
}
else{
//BFS
queue<int>que;
que.push(start);
mark1[start] = 1;
while(!que.empty()){
frt = que.front();
que.pop();
if(mark[frt]){//移动值为0的位置,直接break
res = true;
break;
}
if(frt + arr[frt] < len && !mark1[frt + arr[frt]]){//向前移
que.push(frt + arr[frt]);
mark1[frt + arr[frt]] = 1;
}
if(frt - arr[frt] >= 0 && !mark1[frt - arr[frt]]){//向后移
que.push(frt - arr[frt]);
mark1[frt - arr[frt]] = 1;
}
}
}
return res;
}
};

1307. 口算难题

题目描述

给你一个方程,左边用 words 表示,右边用 result 表示。 你需要根据以下规则检查方程是否可解: 每个字符都会被解码成一位数字(0 - 9)。 每对不同的字符必须映射到不同的数字。 每个 words[i] 和 result 都会被解码成一个没有前导零的数字。 左侧数字之和(words)等于右侧数字(result)。 如果方程可解,返回 True,否则返回 False。 示例 1: 输入:words = [“SEND”,”MORE”], result = “MONEY” 输出:true 解释:映射 ‘S’-> 9, ‘E’->5, ‘N’->6, ‘D’->7, ‘M’->1, ‘O’->0, ‘R’->8, ‘Y’->’2’ 所以 “SEND” + “MORE” = “MONEY” , 9567 + 1085 = 10652 示例 2: 输入:words = [“SIX”,”SEVEN”,”SEVEN”], result = “TWENTY” 输出:true 解释:映射 ‘S’-> 6, ‘I’->5, ‘X’->0, ‘E’->8, ‘V’->7, ‘N’->2, ‘T’->1, ‘W’->’3’, ‘Y’->4 所以 “SIX” + “SEVEN” + “SEVEN” = “TWENTY” , 650 + 68782 + 68782 = 138214 示例 3: 输入:words = [“THIS”,”IS”,”TOO”], result = “FUNNY” 输出:true 示例 4: 输入:words = [“LEET”,”CODE”], result = “POINT” 输出:false 提示: 2 <= words.length <= 5 1 <= words[i].length, results.length <= 7 words[i], result 只含有大写英文字母 表达式中使用的不同字符数最大为 10

题解1

因为表达式中使用的不同字符数最大为10,字符的取值0-9(值不能相同)最多为$10!$种情况。思路如下: 首先将不重复的字符统计出来,然后用next_permutation产生不同的取值,判断是否符合情况。 这种暴力方式会超时,因为next_permutation产生取值的时间需要o(n)时间,并且包含重复的情况。

代码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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//超时
bool deal(vector<string>& words, string& result, unordered_map<char, int>& myMap){
for(int i = 0; i < words.size(); ++i){
if(words[i].size() > 1 && myMap[words[i][0]] == 0){//前导0
return false;
}
}
if(result.size() > 1 && myMap[result[0]] == 0){//前导0
return false;
}
int lSum = 0, rSum = 0, num = 0;
for(auto word:words){
num = 0;
for(auto ch:word){
num = num * 10 + myMap[ch];
}
lSum += num;
}
for(auto ch:result){
rSum = rSum * 10 + myMap[ch];
}
return lSum == rSum;
}
class Solution {
public:
bool isSolvable(vector<string>& words, string result) {
int len;
unordered_map<char, int>myMap;
string str;
int flag = false;
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for(auto word:words){
for(auto ch:word){
if(myMap.find(ch) == myMap.end()){
str.push_back(ch);
myMap[ch] = 0;
}
}
}
len = str.size();
do{
for(int i = 0; i < len; ++i){
myMap[str[i]] = arr[i];
}
if(deal(words, result, myMap)){
flag = true;
break;
}
}while(next_permutation(arr, arr + 10));
return flag;
}
};

题解2

用dfs来代替next_permutation,不会产生重复的情况。加入前导0的标记并将map换成数组。

代码2

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
vector<int>myMap(26, 0);
vector<bool>mark(26, 0);
string str;
bool res = false;

bool deal(vector<string>& words, string& result){//判断相加后是否相等
int lSum = 0, rSum = 0, num = 0;
for(auto word:words){
num = 0;
for(auto ch:word){
num = num * 10 + myMap[ch - 'A'];
}
lSum += num;
}
for(auto ch:result){
rSum = rSum * 10 + myMap[ch - 'A'];
}
return lSum == rSum;
}

void dfs(vector<string>& words, string& result, int pos, int used){//递归暴力
if(res){
return;
}
if(pos == str.size()){
if(deal(words, result)){
res = true;
}
return;
}
for(int i = 0; i < 10; ++i){
if((mark[str[pos] - 'A'] && i == 0) used >> i & 1) continue;//前导0或者数字重复
myMap[str[pos] - 'A'] = i;
dfs(words, result, pos + 1, used 1 << i);
}

}


class Solution {
public:
bool isSolvable(vector<string>& words, string result) {
int len;
myMap.clear();
str.clear();
res = false;
mark.assign(26, 0);
myMap.assign(26, 0);
for(auto word:words){//统计字符的个数
mark[word[0] - 'A'] = 1;
for(auto ch:word){
if(!myMap[ch - 'A']){
str.push_back(ch);
myMap[ch - 'A'] = 1;
}
}
}
mark[result[0] - 'A'] = 1;
for(auto ch:result){
if(!myMap[ch - 'A']){
str.push_back(ch);
myMap[ch - 'A'] = 1;
}
}
len = str.size();
dfs(words, result, 0, 0);
return res;
}
};

题解3

参照圈子

代码3

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
35
36
37
38
39
40
41
42
vector<char> h;
vector<int> base;
vector<int> coe(26,0);
vector<bool> not_zero(26,false);

bool dfs (int pos,int used, int sum) {
if(pos == h.size()) return sum == 0;
for(int i = 0 ; i < 10 ; i++) {
if(used>>i & 1) continue;
if(i==0 && not_zero[h[pos]-'A']) continue;
if(dfs(pos+1,used 1<<i, sum+i*coe[h[pos]-'A'])) return true;
}
return false;
};


class Solution {
public:
bool isSolvable(vector<string>& words, string result) {

h.clear();
base.clear();
coe.assign(26, 0);
not_zero.assign(26, false);
words.push_back(result);
base.push_back(1);
for(int i = 1 ; i <= 8 ; i++) base.push_back(base.back()*10);

for(int j = 0 ; j < words.size() ; j++) {
string x = words[j];
for(int i = 0 ; i < x.size() ; i++) {
if(i==0) not_zero[x[i]-'A'] = true;
h.push_back(x[i]);
int flag = j==words.size()-1?-1:1;
coe[x[i]-'A'] += flag * base[x.size()-1-i];
}
}
sort(h.begin(),h.end());
h.erase(unique(h.begin(),h.end()),h.end());
return dfs(0,0,0);
}
};