Joyce' Blog
0%

发表于

题目描述

对于给定的链表，删除倒数第n个节点，返回头节点。

解题思路

一个指针遍历两次，或者两个指针遍历一次。对于两个指针p,q，需要固定间隔长度n (p-q=n)，然后同时移动两个指针，直至q移到链表尾。此时q指向需要被移除的节点。注意返回空指针的处理。

易错情况：

([1,2],1) ([1,2],2) ([1],1)

编译时报错：error: expected unqualified-id before 'while'

原因是在类的定义中误写了循环体。

代码

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
struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };	

ListNode * removeNthFromEnd(ListNode* head, int n) {
	ListNode *p =head, *q = head;
	int i = n;
    bool flag=false;
	while (i--)
	{
        if(q->next)
		    q = q->next;
        else
            flag=true;
	}
	if (!q->next&&flag)//要删除的是头节点
		if (p->next)
			return p->next;
		else
			return NULL;
	while (q->next)
	{
		q = q->next;
		p = p->next;
	}
	p->next = p->next->next;
	return head;
}

发表于 更新于

题目描述

给定一个整数数组nums和一个整数值target，找出nums中所有的4个数之和等于target的组合。

解题思路

降低时间复杂度的关键在于避免重复地找出这四个数。将4个数之和转化为两组数之和，即外层之和、内层之和。排序肯定是要有的。之后就是外层的两个指针缩小范围，然后内层两个指针向中间走的过程了。

代码

嘤……我放弃了，还是好好学习别人的代码吧……

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector<vector<int>> res;
        if (size < 4) return res;
        sort(nums.begin(), nums.end());
        int s1 = 0;
        int e1 = size - 1;
        while (s1 < e1 - 2) {
        	if (nums[s1] + nums[e1-2] + nums[e1-1] + nums[e1] < target) s1++;
        	else if (nums[s1] + nums[s1+1] + nums[s1+2] + nums[e1] > target) e1--;
        	else {
        		int tmp1 = s1;
        		int tmp2 = e1;
        		twoSum(s1, s1+1, e1-1, e1, res, nums, target);
        		tmp2--;
        		while (s1 < tmp2 - 2) {
        			while (nums[tmp2] == nums[tmp2+1]) tmp2--;
        			twoSum(s1, s1+1, tmp2-1, tmp2, res, nums, target);
                    tmp2--;
        		}
        		tmp1++;
        		while (tmp1 < e1 - 2) {
        			while (nums[tmp1] == nums[tmp1-1]) tmp1++;
        			twoSum(tmp1, tmp1+1, e1-1, e1, res, nums, target);
                    tmp1++;
        		}
                e1--;
        		while (s1 < e1 - 2 && nums[e1] == nums[e1+1]) e1--;
        		s1++;
                while (s1 < e1 - 2 && nums[s1] == nums[s1-1]) s1++;
        	}
        }
        sort(res.begin(),res.end());
        return res;
    }

    void twoSum(int s1, int s2, int e2, int e1, vector<vector<int>>& res, vector<int>& nums, int target) {
    	while (s2 < e2) {
			if (nums[s1] + nums[s2] + nums[e2] + nums[e1] < target) s2++;
			else if (nums[s1] + nums[s2] + nums[e2] + nums[e1] > target) e2--;
			else {
				vector<int> tmp{nums[s1], nums[s2], nums[e2], nums[e1]};
				res.push_back(tmp);
				while (s2 < e2 - 1 && nums[s2] == nums[s2+1]) s2++;
				s2++;
			}
		}
        return;
    }
};

发表于 更新于

鸟哥的Linux私房菜

Linux常用命令：

计算器：bc

翻页：[shift] + { [pgup]|[pgdn] }

求助：date –help 或 man date 或 info date

关机：shutdown

vim指令

在一般指令模式中：

/word：向光标之下寻找一个名称为word的字符串

?word：向光标之上寻找一个名称为word的字符串

n：重复前一个搜寻动作

N：反向进行前一个搜寻动作

发表于 
1
2
3
4
5
6
7
8
import 模块名
模块名.xxx = 引用


from 模块名 import *
xxx = 拷贝  # 能修改属性值　　

函数,类... : "import 模块名" 和 "from 模块名 import *" 都是引用

发表于 更新于
还是要养成记笔记的习惯才好

既然大家都那么推崇LaTeX，那还是学着用好了。

LaTeX配置环境：TeXLive；编辑器：Texstudio。

数学公式

很多markdown编辑器都支持LaTeX数学公式。

分两种模式：行内模式（行文中插入），行间模式（单独成行）。

使用equation环境对公式编号。

中文支持

引入CJK宏包并应用CJK环境。

1
2
3
4
5
6
7
8
9
\documentclass[UTF8]{article}

\usepackage{ctex}

\begin{document}

我和我的祖国，一刻也不能分割。

\end{document}

或者，ctexart那几个环境相当于是在“\begin{document}”和“\end{document}”之间自动加入CJK环境

1
2
3
4
5
6
7
\documentclass[UTF8]{ctexart}

\begin{document}

无论我走到哪里，都留下一首赞歌。

\end{document}

清华的论文模版

发表于 更新于

题目描述

2-9中的数字组成的字符串，按照电话按键的模式，给出所有能映射到的字符串。

解决方案

初步的想法是递归，类似于树的结构。

字符转字符串：

1
2
string s="";
s+='a';

最开始关于paths的想法有点错误，递归函数，每次传入的路径应该只有一条，而不是一个数组。要把问题细化。

关于字符串tmp的设置就不要用switch-case了，用map吧。

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
string c2 = "abc";
string c3 = "def";
string c4 = "ghi";
string c5 = "jkl";
string c6 = "mno";
string c7 = "pqrs";
string c8 = "tuv";
string c9 = "wxyz";

void findPath(string digits, int begin, string path, vector<string>& res)
{
	string tmp = "";
	switch (digits[begin])
	{
	case '2':
	{
		tmp = c2;
		break;
	}
	case '3':
	{
		tmp = c3;
		break;
	}
	case '4':
	{
		tmp = c4;
		break;
	}
	case '5':
	{
		tmp = c5;
		break;
	}
	case '6':
	{
		tmp = c6;
		break;
	}
	case '7':
	{
		tmp = c7;
		break;
	}
	case '8':
	{
		tmp = c8;
		break;
	}
	case '9':
	{
		tmp = c9;
		break;
	}
	}
	int len = digits.length();
	if (begin == len - 1)
	{
		for (int i = 0; i < tmp.length(); ++i)
		{
			res.push_back(path + tmp[i]);
		}
		return;
	}
	for (int i = 0; i < tmp.length(); ++i)
	{
		findPath(digits, begin + 1, path + tmp[i], res);
	}
}
vector<string> letterCombinations(string digits) {
	vector<string> res;
	int len = digits.length();
	if (len > 0)
		findPath(digits, 0, "", res);
	return res;
}

发表于

题目描述

给一组数，和一个数字target，找出三个数字，使这三个数字的和最接近target。这个问题，其实和3Sum相同，也难怪这个题的通过率会是上一题的二倍了。

解决方案

要注意赋给res的初值。并且我认为不用去除重重复搜索的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int threeSumClosest(vector<int>& nums, int target) {
	sort(nums.begin(),nums.end());
	int size = nums.size();
	int res = nums[0] + nums[1] + nums[2];
	for (int i = 0; i < size - 2; i++)
	{
		int j = i + 1; int k = size - 1;
		while (j < k)
		{
			int sum = nums[i] + nums[j] + nums[k];
			if (abs(sum-target) < abs(res-target))
				res = sum;
			if (sum < target)
				++j;
			else if (sum > target)
				--k;
			else
				return target;
		}
	}
	return res;
}

发表于 更新于

智能眼镜的网页端需要生成测试数据，先尝试一下生成随机数据，再试着尽量把数据做得合理一些。

phpMyAdmin 是一种 MySQL数据库前台的基于PHP的工具。

pymysql是用来连接python和mysql之间的通道，在使用python编程时，通过它来和mysql数据库进行交互。

安装pymysql模块：在终端输入pip install pymysql

此次只向data_series表中生成数据。data_series中的字段有user_id，date，distance，lux和angle。use_login表中，目前只有id为3,6,25三位用户，user_id要满足这一限制。

np.random.randn(n)该函数返回一个样本，有n个数，具有标准正态分布。

打算先以15min为间隔，生成一整天的数据，因此每次随机产生的应该有96个数据。从distance入手，想要的是在[5,200]之间正态分布的96个整数。

为了生成正态分布，需要载入包为scipy统计包中的norm

1
from scipy.stats import norm

没有的话还是要先安装：pip install scipy

调出来生成的数据还算正常的distance:

1
2
3
distance = r.uniform((5-40)/10, (200-40)/10)
distance = norm.rvs(distance, size=120)
distance = distance*10+40

利用pandas生成等间隔时间：96个时间，间隔为900s

1
dateTime = pd.date_range('2019-9-10 00:00:00', periods=96, freq='900s')

连接数据库时，pycharm报错：”Lost connection to MySQL server during query“，是因为我把端口号写错了，MySQL使用的端口号为3306

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
import random as r
from scipy.stats import norm
import pandas as pd
import pymysql

userId = (3, 6, 25)
dateTime = pd.date_range('2019-9-10 00:00:00', periods=96, freq='900s')

distance = r.uniform((5 - 40) / 10, (200 - 40) / 10)
distance = norm.rvs(distance, size=120)
distance = distance * 10 + 40

lux = r.uniform((30 - 720) / 770, (25000 - 720) / 770)
lux = norm.rvs(lux, size=120)
lux = lux * 770 + 700

angle = r.uniform(-45 / 10, 45 / 10)
angle = norm.rvs(angle, size=120)
angle = angle * 10

conn = pymysql.connect(host='127.0.0.1', port=3306, db='ahri', user='root', password='', charset='utf8')
cur = conn.cursor()

for i in range(96):  # 插入数据
    tmpId = r.choice(userId)  # 在列表中随机取一个
    print(tmpId, str(dateTime[i]), distance[i], lux[i], angle[i])
    cur.execute("insert into data_series(user_id,date,distance,lux,angle) values(%s,%s,%s,%s,%s)",
                (tmpId, str(dateTime[i]), int(distance[i]), int(lux[i]), int(angle[i])))
cur.execute('select * from data_series')  # 查询数据
for s in cur.fetchall():
    print(s)
conn.commit()

cur.close()
conn.close()

发表于

题目描述

给一组整数，求出所有和为零的三元组。

解决方案

暂时只想到了遍历，还没有想到复杂度更低的方法

  • vector<vector> res; 注意赋值时，要使用push_back()，而不是=

  • 注意去重！

  • 最开始使用了三层循环，结果时间超限，所以将最内层循环换成了二分查找

代码

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
vector<vector<int>> threeSum(vector<int>& nums) {
	//为了去重，将数字排序，与前面重复的数字就不要再向后搜索
	sort(nums.begin(), nums.end());

	int size = nums.size();
	vector<vector<int>> res;
	int usedi = 0; int usedj = 0; 
	bool flag = true;//有三个以上的0时，只加入一次
	for (int i = 0; i < size - 2; ++i)
	{		
		for (int j = i + 1; j < size - 1; ++j)
		{			
			int t = 0 - nums[i] - nums[j];
			if (t >= 0)
			{//既然已经经过排序，那么要找的第三个数一定是个非负数
			 //复杂度过高，将内层的遍历改成二分查找
				int left = j + 1; int right = size - 1;
				while (left <= right)
				{
					int mid = (left + right) / 2;
					if (nums[mid] < t)
					{
						left = mid+1;
					}
					else if (nums[mid] > t)
					{
						right = mid-1;
					}
					else
					{
						vector<int> y;
						y.push_back(nums[i]);
						y.push_back(nums[j]);
						y.push_back(t);
						res.push_back(y);
						break;
					}
				}
			}
			usedj = nums[j];
			while ( j < size - 2 && usedj == nums[j+1])
				++j;
		}	
		usedi = nums[i];
		while ( i < size - 3 && usedi == nums[i+1])
			++i;//与前面重复的数字就不要再向后搜索
	}
	return res;
}

找到另外一种思路：不需要三层，两层就够了，外层思路不变，在内层，从两端向中间移动。

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
vector<vector<int>> threeSum2(vector<int>& nums) {
	//为了去重，将数字排序，与前面重复的数字就不要再向后搜索
	sort(nums.begin(), nums.end());

	int size = nums.size();
	vector<vector<int>> res;
	int usedi = 0; int usedj = 0;
	bool flag = true;//有三个以上的0时，只加入一次
	for (int i = 0; i < size - 2; ++i)
	{
		int j = i + 1; int k = size - 1;

		while (j < k)
		{
			int t = nums[i] + nums[j] + nums[k];
			if (t == 0)
			{
				vector<int> y;
				y.push_back(nums[i]);
				y.push_back(nums[j]);
				y.push_back(nums[k]);
				res.push_back(y);
				while (j < size - 2 && nums[j] == nums[j + 1]) ++j;
				while (k > 0 && nums[k] == nums[k - 1]) --k;
				++j;
				--k;
				continue;
			}
			else if (t > 0)
				--k;
			else
				++j;
		}
		usedi = nums[i];
		while (i < size - 3 && usedi == nums[i + 1])
			++i;//与前面重复的数字就不要再向后搜索
	}
	return res;
}

发表于
注意数组为空的情况！！！

题目描述

输入一组字符串，输出这些字符串共有的最长前缀

题目分析

二重循环，外层是字符串长度向后移动，内层是每个字符串依次比较。得到了最容易想到的解决方法：

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
string longestCommonPrefix(vector<string>& strs) {
	string s = "";
	int size = strs.size();
	if (size == 0)
		return s;
	int* lens = new int[size];
	int min= strs[0].length();
	for (int i = 1; i < size; ++i)
	{
		lens[i] = strs[i].length();
		if (lens[i] < min)
			min = lens[i];
	}
	char ch;
	bool flag = true;
	for (int i = 0; i < min && flag; ++i)//字符串长度
	{
		ch = strs[0][i];
		for (int j = 0; j < size; ++j)//遍历每个字符串
		{
			if (strs[j][i] != ch)
			{
				flag = false;
				break;
			}
		}
		if (flag)
			s = s + ch;
	}
	return s;
}

但是提交之后发现内存使用量太大，难道是因为我开了一个记录长度的数组？突然想到递归也是可以解决的。

查了一下其他人的做法，发现了自己的不足：需要返回的字符串prefix，不需要一个个字母地附加。当字符串数组strs不为空时，令prefix=strs[0]，然后外层遍历res的字符，内层遍历strs数组，利用strs[i].indexOf(prefix) != 0和prefix.substring(0, prefix.length() - 1)已有的函数。这样空间复杂度为O(1)。