Joyce' Blog
0%

发表于

题目描述

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

题解

不能简单地认为，从s3里面过滤掉s1，把结果与s2比较久可以。 ×

动态规划！二维数组。s3要么和s1匹配一位，要么和s2匹配一位，在二维数组里体现为：上面或左边的布尔值，结合两个串中特定位置的字符，决定了当前矩阵元素的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isInterleave(string s1, string s2, string s3) {
	int len1 = s1.length();
	int len2 = s2.length();
	int len3 = s3.length();
	if (len1 + len2 != len3)return false;
	bool **dp = new bool*[len1+1];
	for (int i = 0; i <= len1; i++)
		dp[i] = new bool[len2+1];
	for (int i = 0; i <= len1; i++)
		for (int j = 0; j <= len2; j++)
			dp[i][j] = false;
	dp[0][0] = true;
	for (int i = 1; i <= len1; i++)
		if (dp[i - 1][0] && s1[i - 1] == s3[i - 1])dp[i][0] = true;
	for (int j = 1; j <= len2; j++)
		if (dp[0][j - 1] && s2[j - 1] == s3[j - 1])dp[0][j] = true;
	for (int i = 1; i <= len1; i++)
		for (int j = 1; j <= len2; j++)
			if (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1])
				dp[i][j] = true;
			else if(dp[i][j - 1] && s2[j - 1] == s3[i + j - 1])
				dp[i][j] = true;
	return dp[len1][len2];
}

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.3 MB, 在所有 C++ 提交中击败了94.76%的用户

666……现在我信了，遇到字符串题，先想DP。

发表于 更新于

参考：https://gist.github.com/kevinkindom/108ffd675cb9253f8f71

python提供了两个socket模块：

  • Socket：提供标准的BSD Socket API
  • SocketServer：提供服务器中心，可简化网络服务器开发

这里主要学习Socket模块。

创建Socket

格式：socket(family, type[,protocal])

使用给定套接族，套接字类型，协议编号（默认为0）创建套接字

socket 类型 描述
socket.AF_UNIX 用于同一台机器上的进程通信（既本机通信）
socket.AF_INET 用于服务器与服务器之间的网络通信
socket.AF_INET6 基于IPV6方式的服务器与服务器之间的网络通信
socket.SOCK_STREAM 基于TCP的流式socket通信
socket.SOCK_DGRAM 基于UDP的数据报式socket通信

例：

1
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)

Socket函数

TCP发送数据时，已建立好TCP链接，所以不需要指定地址，而UDP是面向无连接的，每次发送都需要指定发送给谁。服务器与客户端发送的数据是字符串。

服务器端 Socket 函数

Socket 函数 描述
s.bind(address) 将套接字绑定到地址，在AF_INET下，以tuple(host, port)的方式传入，如s.bind((host, port))
s.listen(backlog) 开始监听TCP传入连接，backlog指定在拒绝链接前，操作系统可以挂起的最大连接数，该值最少为1，大部分应用程序设为5
s.accept() 接受TCP链接并返回（conn, address），其中conn是新的套接字对象，可以用来接收和发送数据，address是链接客户端的地址。

客户端 Socket 函数

Socket 函数 描述
s.connect(address) 链接到address处的套接字，一般address的格式为tuple(host, port)，如果链接出错，则返回socket.error错误

公共 Socket 函数

Socket 函数 描述
s.recv(bufsize[, flag]) 接受TCP套接字的数据，数据以字符串形式返回，buffsize指定要接受的最大数据量，flag提供有关消息的其他信息，通常可以忽略
s.send(string[, flag]) 发送TCP数据，将字符串中的数据发送到链接的套接字，返回值是要发送的字节数量，该数量可能小于string的字节大小
s.settimeout(timeout) 设置套接字操作的超时时间，timeout是一个浮点数，单位是秒，值为None则表示永远不会超时。一般超时期应在刚创建套接字时设置，因为他们可能用于连接的操作，如s.connect()
s.recvfrom(bufsize[, flag]) 接受UDP套接字的数据u，与recv()类似，但返回值是tuple(data, address)。其中data是包含接受数据的字符串，address是发送数据的套接字地址
s.sendto(string[, flag], address) 发送UDP数据，将数据发送到套接字，address形式为tuple(ipaddr, port)，指定远程地址发送，返回值是发送的字节数
s.close() 关闭套接字

步骤

TCP 服务器

1、创建套接字，绑定套接字到本地IP与端口

1
2
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind()

2、开始监听链接

1
s.listen()

3、进入循环，不断接受客户端的链接请求

1
2
While True:
    s.accept()

4、接收客户端传来的数据，并且发送给对方发送数据

1
2
s.recv()
s.sendall()

5、传输完毕后，关闭套接字

1
s.close()

TCP 客户端

1、创建套接字并链接至远端地址

1
2
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect()

2、链接后发送数据和接收数据

1
2
s.sendall()
s.recv()

3、传输完毕后，关闭套接字

实例

Socket 编程实践之服务器端代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import socket

HOST = '192.168.1.100'
PORT = 8001

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.bind((HOST, PORT))
s.listen(5)

print 'Server start at: %s:%s' %(HOST, PORT)
print 'wait for connection...'

while True:
    conn, addr = s.accept()
    print 'Connected by ', addr

    while True:
        data = conn.recv(1024)
        print data

        conn.send("server received you message.")

# conn.close()

Socket 编程实践之客户端代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import socket
HOST = '192.168.1.100'
PORT = 8001

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((HOST, PORT))

while True:
    cmd = raw_input("Please input msg:")
    s.send(cmd)
    data = s.recv(1024)
    print data

    #s.close()

附

编程时一定要注意编码方式啊……比如下面：

1
print(u'q' == b'q')

结果为False。

本来想当输入“q”时就断开TCP连接，结果因为编码不同，一直没跳出循环，导致了报错。

u/U:表示unicode字符串

r/R:非转义的原始字符串

在python中交换两个列表：

如大小相等的2个列表a, b，交换这两个列表的内容：

1
a, b = b, a

也等同于：

1
2
3
mid = a
a = b
b = mid

发表于

C文件路径用双斜杠

因为 \ 在 C/C++/C# 中是转义前导字符，例如 \n 代表换行。

如果路径中刚好有类似转义字符开头的，那么就会引起问题，所以路径中的 \ 必须用 \ 的形式。

Windows文件层级用反斜杠「\」

Windows 用反斜杠（“\”）的历史来自 DOS。

DOS 的另一个传统是用斜杠（“/”）表示命令行参数。

如今的 Windows 内核在处理路径时可以同时支持斜杠和反斜杠。很多时候我们看到用斜杠时出错，是因为应用程序层面的原因。比如 cmd.exe 就不支持用斜杠表示路径，而PowerShell.exe 支持，也正因为这个原因，PowerShell 开始转而使用减号作为命令行参数的起始符。

UNIX文件层级用斜杠「/」

UNIX 环境中，用减号（“-”）和双减号（“–”）表示命令行参数。

用斜杠表示命令行参数是兼容性原因。IBM 在最初加入 DOS 开发时贡献了大批工具，它们都是用斜杠处理命令行参数的。而这个传统源自于 DEC/IBM，比如当年的 VMS 就是用斜杠处理命令行参数，它的目录分隔符是美元符（“$”）。

发表于 更新于

DES中用到的python库函数

1
isinstance(object, classinfo)

isinstance() 函数来判断一个对象是否是一个已知的类型，类似 type()。如果对象的类型与参数二的类型（classinfo）相同则返回 True，否则返回 False。

1
ord(c)

ord() 函数是 chr() 函数（对于8位的ASCII字符串）或 unichr() 函数（对于Unicode对象）的配对函数，它以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值（返回值是对应的十进制整数），或者 Unicode 数值，如果所给的 Unicode 字符超出了你的 Python 定义范围，则会引发一个 TypeError 的异常。

1
bin(x)

bin() 返回一个整数 int 或者长整数 long int 的二进制表示（0b开头）。

1
str.count(sub, start= 0,end=len(string))

count() 方法用于统计字符串里某个字符出现的次数。可选参数为在字符串搜索的开始与结束位置。

字符串的奇偶验证码
1
2
3
4
5
6
7
8
9
10
11
12
13
def bytetobit(text):
    bintext = ""
    for letter in text:
        bits = bin(ord(letter))
        newbits = str(bits[2:])

        if bits.count('1') % 2 == 1:
            # 使所有1出现的个数为奇数
            newbits = newbits + "0 "
        else:
            newbits = newbits + "1 "
        bintext = bintext + newbits
    return bintext
1
zip([iterable, ...])

iterable是一个或多个迭代器，返回元组列表。

zip() 函数用于将可迭代的对象作为参数，将对象中对应的元素打包成一个个元组，然后返回由这些元组组成的列表。如果各个迭代器的元素个数不一致，则返回列表长度与最短的对象相同，利用 * 号操作符，可以将元组解压为列表。

发表于
我傻了，居然以为冒号后面的1是赋值为1的意思。如果不是为了写EFLAGS的话，可能一直都还不知道位域这东西。菜是原罪。

C位域

带有预定义宽度的变量被称为位域。

声明

在结构内声明位域的形式如下：

1
2
3
4
struct
{
  type [member_name] : width ;
};

type只能为 int(整型)，unsigned int(无符号整型)，signed int(有符号整型) 三种类型，决定了如何解释位域的值。

width表示位域中位的数量。宽度必须小于或等于指定类型的位宽度。

解释

直接用菜鸟上的例子来说了：如果结构中包含多个 TRUE/FALSE 变量，如下：

1
2
3
4
5
struct
{
  unsigned int widthValidated;
  unsigned int heightValidated;
} status;

status结构需要 8 字节的内存空间，但实际上每个变量只存储 0 或 1。在这种情况下，C 语言提供了一种更好的利用内存空间的方式：定义变量的宽度来告诉编译器，上面的结构可以重写成：

1
2
3
4
5
struct
{
  unsigned int widthValidated : 1;
  unsigned int heightValidated : 1;
} status;

上面的结构中，status 变量将占用 4 个字节的内存空间，但是只有 2 位被用来存储值。如果您用了 32 个变量，每一个变量宽度为 1 位，那么 status 结构将使用 4 个字节，但只要您再多用一个变量，如果使用了 33 个变量，那么它将分配内存的下一段来存储第 33 个变量，这个时候就开始使用 8 个字节。

例

位域可以存储多于 1 位的数，例如，需要一个变量来存储从 0 到 7 的值，可以定义一个宽度为 3 位的位域，如下：

1
2
3
4
struct
{
  unsigned int age : 3;
} Age;

发表于

VMware中的ubuntu虚拟机开机一直停留在启动画面

解决方案：

管理员方式启动CMD，命令行窗口输入netsh winsock reset，重启计算机。

“虚拟机”–“设置”–“显示器”–取消“加速3D图形的选项”。

发表于 更新于

题目描述

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

题解

居然连二叉搜索树是啥都不记得了 嘤

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

So, 递归吧。

理解了思路，代码还是很好写的。不过，有点懵比的是，让我觉得效率很低的递归，居然：

执行用时 :12 ms, 在所有 C++ 提交中击败了93.46%的用户

内存消耗 :15.9 MB, 在所有 C++ 提交中击败了87.26%的用户

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
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<TreeNode*> makeTree(int left, int right)
{
	vector<TreeNode*> res;
	TreeNode *r;
	if (left >= right)
	{
		if (left > right)return { NULL };
		r= new TreeNode(left);
		return { r };
	}
	for (int i = left; i <= right; i++)
	{
		vector<TreeNode*> lefts = makeTree(left, i - 1);
		vector<TreeNode*> rights = makeTree(i + 1, right);
		for (int j = 0; j < lefts.size(); j++)
		{
			for (int k = 0; k < rights.size(); k++)
			{
				r = new TreeNode(i);
				r->left = lefts[j];
				r->right = rights[k];
				res.push_back(r);
			}
		}
	}
	return res;
}
vector<TreeNode*> generateTrees(int n) {
	if (n < 1)return{};
	return makeTree(1, n);
}

那，如果改成引用传参呢？

不改了，没意思。下一个。

题目描述

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

题解

像上面一样递归也可以，但是动态规划是不是更合适。嗯主要原因是n=19时，运行超出时间限制了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int numTrees(int n) {
	if (n < 2)return n;
	int *countTree = new int[n+1];
	//count[i]表示有i个节点的二叉搜索树的总数
	countTree[0] = 1;
	countTree[1] = 1;
	for (int i = 2; i <= n; i++)
		countTree[i] = 0;
	for (int i = 2; i <= n; i++)
	{
		for (int j = 0; j < i; j++)
		{//j表示左子树的结点个数
			countTree[i] += countTree[j] * countTree[i - j - 1];
		}
	}
	return countTree[n];
}

执行用时 :4 ms, 在所有 C++ 提交中击败了61.10%的用户

内存消耗 :7.4 MB, 在所有 C++ 提交中击败了100.00%的用户

发表于

题目描述

给定一个二叉树，返回它的中序 遍历。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<int> res2;
void mid_travel(TreeNode* root)
{
	if (root)
	{
		mid_travel(root->left);
		res2.push_back(root->val);
		mid_travel(root->right);
	}
}
vector<int> inorderTraversal(TreeNode* root) {
	mid_travel(root);
	return res2;
}

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

你是想说莫里斯遍历？巧了，我不会。写个基于栈的循环吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> inorderTraversal2(TreeNode* root) {
	if (!root)return{};
	stack<TreeNode*> s;
	vector<int> ret;
	s.push(root);
	TreeNode* tmp = root->left;
	while (tmp)
	{
		s.push(tmp);
		tmp = tmp->left;
	}
	while (!s.empty())
	{
		ret.push_back(s.top()->val);
		tmp = s.top()->right;
		s.pop();
		while (tmp)
		{
			s.push(tmp);
			tmp = tmp->left;
		}
	}
	return ret;
}

两个时空比居然没太大差别？

多亏了官方题解的动图，才能这么快地一遍过。

发表于 更新于

memcpy(), 如果源区间和目的区间有重叠时, 它的行为会怎么样?

首先 man memcpy，看一下相关描述：

description

note

从网上又找到memcpy的定义：

1
2
void *memcpy(void *dst, const void *src, size_t n);
//If copying takes place between objects that overlap, the behavior is undefined.

对于地址重叠的情况，该函数的行为是未定义的。

代码测试

test

尴尬了……理论上不该是这样的正确结果啊……

知乎上说结果会是“hhhhhhhhhhhhhh”，还分析了一大波。

fugai

其实关键就在于，对于上面两种情况，从高地址还是低地址开始拷贝。

如果要自己实现这个函数的话，判断源地址和目的地址的大小，才决定到底是从高地址开始拷贝还是低地址开始拷贝。

看看memcpy()的源码，其实就是这样实现滴。（Linux v5.5.9 https://elixir.bootlin.com/linux/latest/source/arch/alpha/lib/memcpy.c）

1
2
3
4
5
6
7
8
9
10
11
void *memcpy(void *dst, const void *src, size_t len)
void * memcpy(void * dest, const void *src, size_t n)
{
	if (!(((unsigned long) dest ^ (unsigned long) src) & 7)) {
		__memcpy_aligned_up ((unsigned long) dest, (unsigned long) src,
				     n);
		return dest;
	}
	__memcpy_unaligned_up ((unsigned long) dest, (unsigned long) src, n);
	return dest;
}

光是下面这样的话，会有问题啊。(git://gcc.gnu.org/git/gcc.git)

1
2
3
4
5
6
7
8
9
10
11
12

/* Public domain. */
#include <stddef.h>
void *
memcpy (void *dest, const void *src, size_t len)
{
char *d = dest;
const char *s = src;
while (len--)
*d++ = *s++;
return dest;
}

android / kernel / lk / master / . / lib / libc / string / memcpy.c这里面倒没看见有判断。

发表于 更新于

题目描述

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

题解

DFS + 剪枝：每次取一个字符，要么直接拼上去，要么加个小数点再拼上去，然后剔除掉不符合条件的分支。

看评论区似乎要重点考虑“0”的情况。

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
vector<string> res;
void dfs(string &s, int start, int end,int count,string des)
{
	//位数错误
	if (count>end - start || 3 * count < end- start)return;
	if (count == 0) {
		string k = des.substr(1,des.length()-1);
		int i = start;
		while (i < end)
		{
			k = k + s[i];
			i++;
		}
		res.push_back(k); 
		return; 
	}
	int k = 0;
	dfs(s, start + 1, end, count - 1,des+ '.' + s[start]);
	if (s[start] != '0')
		dfs(s, start + 2, end, count - 1,  des + '.' + s[start] + s[start + 1] );
	if(s[start] != '0'&&end-start>=3&&(s[start]-'0')*100+(s[start+1]-'0')*10+(s[start+2]-'0')<256)//三位数的值不大于255
		dfs(s, start + 3, end, count - 1, des + '.' + s[start]+ s[start + 1] + s[start + 2] );
}
vector<string> restoreIpAddresses(string s) {
	dfs(s, 0, s.length(), 4,"");
	return res;
}

666，我自己都没想到这么快。

执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗 :8.4 MB, 在所有 C++ 提交中击败了89.69%的用户

字符串与数值的转化，已经有现成的函数，sscanf和sprintf要学会用了。

函数形参声明为引用，能提高效率。

回溯算法事实上就是在一个树形问题上做深度优先遍历。