Joyce' Blog

insertion-sort-list

发表于 2020-05-31

题目描述

对链表进行插入排序。

题解

ListNode* insertionSortList(ListNode* head) {
    ListNode*prehead=new ListNode(INT_MIN);
    if(!head||!head->next)return head;
    prehead->next=head;
    ListNode*current=head->next;
    ListNode*precur=head;
    while(current)
    {
        if(current->val>=precur->val)
        {
            precur=current;
            current=current->next;
        }
        else
        {
            int target=current->val;
            precur->next=current->next;
            ListNode*p=prehead;
            ListNode*q=prehead->next;
            while(q->val<target)
            {
                p=q;
                q=q->next;
            }
            p->next=current;
            current->next=q;
            current=precur->next;
        }
    }
    return prehead->next;
}

SpringBoot入门遇到的问题（二）

发表于 2020-05-30

登录页面可以再设置一个“忘记密码”的功能

登录和注册直接应该有链接，不然太生硬。

假设没有异常情况发生，比如用户名重复

SpringBoot入门遇到的问题（一）

发表于 2020-05-26 更新于 2020-05-30

JDK版本替换

https://blog.csdn.net/qq_34584049/article/details/80619338

Unable to import maven project: See logs for details

http://maven.apache.org/docs/history.html

idea是2017的，用的maven3.6.2不行，要下载maven3.5.0才行

IntelliJ IDEA 中右键新建时，选项没有Java class

https://blog.csdn.net/qq_27093465/article/details/52912444

IDEA卡在Downloading maven plugins

更换阿里源

程序包org.springframework.stereotype不存在

https://blog.csdn.net/weixin_44104367/article/details/100732699

java.sql.SQLException: Access denied for user ‘root‘@’localhost’ (using password: YES)

yml是区分数据类型的，所以如果用户名或者密码是数字的话，就要小心了。所以如果password为000000的话，最终获取到的值是0，显然不对，那么6个0怎么表示呢？只能用字符串”000000”

在连接数据库时，有Mysql报错：MySQL ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)
于是在cmd下登录mysql也出现了同样的错误，所以得出结论：不是代码的问题，可能是配置环境的问题

https://segmentfault.com/a/1190000015678751

唉还要复习sql语句。

lru-cache

发表于 2020-05-21

题目描述

设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作？

题解

哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。

删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)O(1)。

当缓存容量已满，我们不仅仅要删除最后一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 得到。如果 Node 结构中只存储 val，那么我们就无法得知 key 是什么，就无法删除 map 中的键，造成错误。

class LRUCache {
private:
	int cap;
	list<pair<int, int>> cache;
	unordered_map<int, list<pair<int, int>>::iterator> map;
public:
	LRUCache(int capacity){
		this->cap = capacity;
	}
	int get(int key){
		auto it = map.find(key);
		if (it == map.end())return -1;
		pair<int, int> kv = *(map[key]);
		cache.erase(map[key]);
		cache.push_front(kv);
		map[key] = cache.begin();
		return kv.second;
	}
	void put(int key, int value) {
		auto it = map.find(key);
		if (it != map.end()){
			pair<int, int> kv = *(map[key]);
			kv.second = value;
			cache.erase(map[key]);
			cache.push_front(kv);
			map[key] = cache.begin();
		}
		else{
			if (map.size() == cap){
				auto lastPair = cache.back();
				map.erase(lastPair.first);
				cache.pop_back();
			}
			cache.push_front(make_pair(key, value));
			map[key] = cache.begin();
		}
	}
};

链接：https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

之后要准备复现论文了，刷题的事情就暂且停一停吧。

binary-tree-preorder-traversal

发表于 2020-05-19

题目描述

给定一个二叉树，返回它的前序遍历。进阶: 递归算法很简单，你可以通过迭代算法完成吗？

题解

void preorder(TreeNode* root, vector<int>& vec)
{
	if (!root)return;
	vec.push_back(root->val);
	preorder(root->left,vec);
	preorder(root->right,vec);
}
vector<int> preorderTraversal(TreeNode* root) {
	vector<int> res = {};
	preorder(root, res);
	return res;
}

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

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

既如此，何必用迭代？

vector<int> preorderTraversal2(TreeNode* root) {
	vector<int> res = {};
	stack<TreeNode*> st;
	if (!root)return{};
	st.push(root);
	TreeNode* tmp;
	while (!st.empty())
	{
		tmp = st.top();
		st.pop();
		res.push_back(tmp->val);
		if (tmp->right)
			st.push(tmp->right);
		if (tmp->left)
			st.push(tmp->left);
	}
	return res;
}

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

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

reorder-list

发表于 2020-05-18

题目描述

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

题解

利用双向队列，问题就很简单了。

void reorderList(ListNode* head) {
	if (!head || !head->next)return;
	deque<ListNode*> de;
	ListNode*tmp = head->next;
	while (tmp)
	{
		de.push_back(tmp);
		tmp = tmp->next;
	}
	tmp = head;
	while (!de.empty())
	{
		tmp->next = de.back();
		de.pop_back();
		tmp = tmp->next;
		if (de.empty())
			tmp->next = NULL;
		else
		{
			tmp->next = de.front();
			de.pop_front();
			tmp = tmp->next;
		}
	}
	tmp->next = NULL;
}

linked-list-cycle-ii

发表于 2020-05-17

题目描述

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

说明：不允许修改给定的链表。进阶：你是否可以不用额外空间解决此题

题解

仍然使用双指针的方法，关键点是：

走a+nb步一定是在环入口
第一次相遇时慢指针已经走了nb步

第一次相遇，快慢指针必然都走过a步进入环中，在环中相遇。 f = 2s 且 f=s+nb，因此 s=nb , f=2nb，即第一次相遇时，fast和slow 指针分别走了 2n，n 个 环的周长。慢指针在环中已经走了nb，再让它走a步就到了入口节点了。

ListNode *detectCycle(ListNode *head) {
	if (!head || !head->next)return nullptr;
	ListNode *t1 = head, *t2 = head;
	do
	{
		t1 = t1->next;
		t2 = t2->next;
		if (t2)
			t2 = t2->next;
		else
			return nullptr;
	} while (t1 && t2&&t1 != t2);
	if (!t2)return nullptr;
	ListNode* tmp = head;
	while (tmp != t1)
	{
		tmp = tmp->next;
		t1 = t1->next;
	}
	return tmp;
}

真是失败啊。所以要学着改变了呢。

word-break-ii

发表于 2020-05-16

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

题解

本想在上一题基础上改一改，结果超出时间限制。需要先验证能否拆分，如果直接求字符串，一些用例会内存超限。

vector<string> wordBreak(string s, vector<string>& wordDict) {
	if (!wordBreak2(s, wordDict))return{};
	vector<vector<string>> dp(s.size() + 1, vector<string>());
	for (int i = 0; i < s.length(); i++)
	{
		if (i&&dp[i].empty())continue;
		for (string word : wordDict)
		{
			int wlen = word.length();
			int newEnd = i + wlen;
			if (newEnd > s.length())continue;
			if (s.compare(i, wlen, word, 0, wlen))continue;
			if (i == 0)
			{
				dp[newEnd].push_back(word);
				continue;
			}
			for (string d : dp[i])
				dp[newEnd].push_back(d + " " + word);
		}
	}
	return dp.back();
}

word-break

发表于 2020-05-15

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

题解

字符串的大多数问题都是动态规划。

dp[i] =    (  dp[i-1] && contains(subStr(i-1,i))  )
        || (  dp[i-2] && contains(subStr(i-2,i))  )
        || (  dp[i-3] && contains(subStr(i-3,i))  ) 
        || ...

bool wordBreak(string s, vector<string>& wordDict) {
	int slen = s.length();
	bool* dp = new bool[slen+1];
	dp[0] = true;
	for (int i = 1; i <= slen; i++)
		dp[i] = false;
	unordered_set<string> ss;
	ss.insert(std::begin(wordDict), std::end(wordDict));
	for (int i = 1; i <= slen; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (dp[j] && ss.count(s.substr(j, i - j)))
			{
				dp[i] = true;
				break;
			}
		}
	}
	return dp[slen];
}

copy-list-with-random-pointer

发表于 2020-05-14

题目描述

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的 深拷贝。

题解

和之前的clone graph很相似，使用一个queue用来遍历所有节点，是用一个unordered_map来记录被访问过的节点(key)以及clone得到的新节点(value)。

Node* copyRandomList(Node* head) {
	if (!head)return NULL;
	queue<Node*>q;
	unordered_map<Node*, Node*> m;
	m[head] = new Node(head->val);
	q.push(head);

	Node *t1, *t2, *t3;
	while (!q.empty())
	{
		t1 = q.front();
		q.pop();
		if (!m.count(t1))
			m[t1] = new Node(t1->val);
		t2 = t1->next;
		if (t2)
		{
			if (!m.count(t2))
				m[t2] = new Node(t2->val);
			m[t1]->next = m[t2];
			q.push(t2);
		}
		t3 = t1->random;
		if (t3)
		{
			if (!m.count(t3))
				m[t3] = new Node(t3->val);
			m[t1]->random = m[t3];
		}
	}
	return m[head];
}