部分算法题记录
注：这篇主要是一些算法题的解题记录，题目无难度，解答无参考价值。主要目的是让自己多敲一敲键盘，写一些多少需要大脑参与的代码。
2019-08-15
遇到三道算法题，没一道正确解出来的……悲惨。这里先记录一下题目内容和概述，做完了之后再补上解答，争取做到高效 + 少 Bug。
1. 有序循环链表插值
定义循环链表，其中值有序存储，例如 1 -> 3 -> 5 -> 7 (-> 1)，现在需要插入一个值在合适的位置，例如插入 6 得到 1 -> 3 -> 5 -> 6 -> 7 (-> 1)。
分享一下错误思路：这个题初看不难，于是慌忙写上基本步骤，然后……出错。有几个点没有考虑到：如果插入的值比最后一项大的话？如果插入的值比最后一项小的话？如果插入的值和链表中的值，或者链表中的值相等的话？这些第一次写都没考虑到。
大概是比较正确的解答，如下的 template<typename T> void List<T>::insert(T x) 是主要解答内容。为了练手……这边同时给了基本的数据结构实现。
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
template<typename T = int>
class ListNode {
public:
ListNode(T);
ListNode(const ListNode &) = delete;
ListNode &operator=(const ListNode &) = delete;
ListNode(ListNode &&) = delete;
ListNode &operator=(ListNode &&) = delete;
static ListNode *make_cycle(std::vector <T>);
~ListNode();
T val;
ListNode *next;
};
template<typename T = int>
class List {
template<typename U>
friend std::ostream &operator<<(std::ostream &os, const List<U> &list);
public:
List(ListNode<T> *);
List(const List &) = delete;
List &operator=(const List &) = delete;
List(List &&) = delete;
List &operator=(List &&) = delete;
void insert(T);
~List();
ListNode<T> *head;
};
template<typename T>
ListNode<T>::ListNode(T x) : val(x), next(nullptr) {}
template<typename T>
ListNode<T> *ListNode<T>::make_cycle(std::vector <T> v) {
std::sort(v.begin(), v.end());
ListNode *temp = new ListNode(0);
ListNode *now = temp;
for (auto i : v) {
now->next = new ListNode(i);
now = now->next;
}
ListNode *head = temp->next;
now->next = head;
delete temp;
return head;
}
template<typename T>
ListNode<T>::~ListNode() {}
template<typename T>
List<T>::List(ListNode<T> *head) : head(head) {}
template<typename T>
void List<T>::insert(T x) {
ListNode<T> *now = this->head;
if (now == nullptr) return;
while (now->next != nullptr && now->next != this->head) {
if (x >= now->val && x <= now->next->val) {
ListNode<T> *temp = now->next;
now->next = new ListNode<T>(x);
now->next->next = temp;
return;
}
now = now->next;
}
if (x >= now->val) {
ListNode<T> *temp = now->next;
now->next = new ListNode<T>(x);
now->next->next = temp;
} else if (x <= now->next->val) {
ListNode<T> *temp = now->next;
now->next = new ListNode<T>(x);
now->next->next = temp;
this->head = now->next;
}
}
template<typename T>
List<T>::~List() {
std::set < ListNode<T> * > s;
ListNode<T> *now = this->head;
while (now != nullptr && s.find(now) == s.end()) {
s.insert(now);
now = now->next;
}
for (auto i : s) delete i;
}
template<typename T>
std::ostream &operator<<(std::ostream &os, const List<T> &list) {
std::set < ListNode<T> * > s;
ListNode<T> *now = list.head;
while (now->next != nullptr && s.find(now->next) == s.end()) {
s.insert(now);
os << now->val << " -> ";
now = now->next;
}
os << now->val;
return os;
}
int main() {
List<int> cycle(ListNode<int>::make_cycle(std::vector < int > {4, 7, 3, 6}));
cycle.insert(1);
cycle.insert(6);
cycle.insert(5);
cycle.insert(8);
cycle.insert(9);
cycle.insert(9);
cycle.insert(0);
cycle.insert(0);
cycle.insert(3);
cycle.insert(3);
cycle.insert(7);
std::cout << cycle << std::endl;
return 0;
}
编译，运行 $ valgrind ./a.out ，结果如下。
==29806== Memcheck, a memory error detector
==29806== Copyright (C) 2002-2017, and GNU GPL’d, by Julian Seward et al.
==29806== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==29806== Command: ./a.out
==29806==
0 -> 0 -> 1 -> 3 -> 3 -> 3 -> 4 -> 5 -> 6 -> 6 -> 7 -> 7 -> 8 -> 9 -> 9
==29806==
==29806== HEAP SUMMARY:
==29806== in use at exit: 0 bytes in 0 blocks
==29806== total heap usage: 48 allocs, 48 frees, 75,160 bytes allocated
==29806==
==29806== All heap blocks were freed – no leaks are possible
==29806==
==29806== For counts of detected and suppressed errors, rerun with: -v
==29806== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
正常运行，正常析构，没有内存泄漏。题目不难，做好困难（当然，不犯蠢的话，简单的写出插值函数并不出错不是一件很难的事……）。
2. 线段数组去除被完全覆盖项
定义线段的数据结构，给出数组，去除被完全覆盖的项。例如，{[1, 5], [2, 3], [4, 6]} 去除覆盖项后得到 {[1, 5], [4, 6]}。
// TODO：
// 等我想出比 O(n^2) 更好的算法再回来填这里……
3. 固定格式字符串转树
给出字符串，例如 (1 (3 0 8) (5 (9 2 3) 6))，生成一棵树如下。
1 -> 3
-> 8
-> 5 -> 9 -> 2
-> 3
-> 6
题目没有太大难度，无非是确定边界条件之后递归求解。但是……字符串处理有点复杂，还有确定下一个递归条件的点比较麻烦。大概写了一个简单版本的，不带泛型，并且默认就都有节点（上面题意里有空节点占位符，这里就不写了）。同时参考了来自这里简单的打印函数，视觉效果丰富一些，大致如下。
#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <set>
#include <string>
#include <vector>
class TreeNode {
public:
TreeNode(int);
TreeNode(const TreeNode &) = delete;
TreeNode &operator=(const TreeNode &) = delete;
TreeNode(TreeNode &&) = delete;
TreeNode &operator=(TreeNode &&) = delete;
static TreeNode *make_complete(std::vector<int>, int, int);
static TreeNode *from_string(const std::string &);
static void collect(std::set<TreeNode *> &, TreeNode *);
~TreeNode();
int val;
TreeNode *left;
TreeNode *right;
private:
static TreeNode *from_vector_string(const std::vector <std::string> &, int,
int);
static int find_front(const std::vector <std::string> &, int);
static int find_back(const std::vector <std::string> &, int);
};
class Tree {
friend std::ostream &operator<<(std::ostream &os, const Tree &root);
public:
Tree(TreeNode *root);
Tree(const Tree &) = delete;
Tree &operator=(const Tree &) = delete;
Tree(Tree &&) = delete;
Tree &operator=(Tree &&) = delete;
~Tree();
TreeNode *root;
private:
static void print(std::ostream &os, std::string prefix, const TreeNode *node,
bool left);
};
TreeNode::TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode *TreeNode::make_complete(std::vector<int> v, int m, int n) {
if (m < n) {
TreeNode *p = new TreeNode(v[m]);
p->left = TreeNode::make_complete(v, 2 * m + 1, n);
p->right = TreeNode::make_complete(v, 2 * m + 2, n);
return p;
}
return nullptr;
}
TreeNode *TreeNode::from_string(const std::string &str) {
std::vector <std::string> v;
std::string temp;
for (auto c : str) {
if ((c == '(' || c == ')' || c == ' ') && !temp.empty()) {
v.push_back(temp);
temp = std::string();
}
if (c >= '0' && c <= '9') {
temp.append(std::string(1, c));
} else if (c == '(' || c == ')') {
v.push_back(std::string(1, c));
}
}
TreeNode *head = TreeNode::from_vector_string(v, 0, v.size() - 1);
for (auto i : v) {
std::cout << i << " ";
}
std::cout << std::endl;
return head;
}
TreeNode *TreeNode::from_vector_string(const std::vector <std::string> &v, int m,
int n) {
TreeNode *root = new TreeNode(std::atoi(v[m + 1].c_str()));
if (((n - m) == 4) && v[m] == "(" && v[n] == ")") {
root->left = new TreeNode(std::atoi(v[m + 2].c_str()));
root->right = new TreeNode(std::atoi(v[m + 3].c_str()));
} else if (m < n) {
if (v[m + 2] != "(") {
root->left = new TreeNode(std::atoi(v[m + 2].c_str()));
} else {
int i = TreeNode::find_front(v, m + 2);
root->left = TreeNode::from_vector_string(v, m + 2, i);
}
if (v[n - 1] != ")") {
root->right = new TreeNode(std::atoi(v[m + 3].c_str()));
} else {
int i = TreeNode::find_back(v, n - 1);
root->right = TreeNode::from_vector_string(v, i, n - 1);
}
}
return root;
}
int TreeNode::find_front(const std::vector <std::string> &v, int front) {
assert(v[front] == "(");
int count = 0;
for (int i = front; i < v.size(); i++) {
if (v[i] == "(")
count++;
else if (v[i] == ")")
count--;
else
continue;
if (!count) return i;
}
return -1;
}
int TreeNode::find_back(const std::vector <std::string> &v, int back) {
assert(v[back] == ")");
int count = 0;
for (int i = back; i >= 0; i--) {
if (v[i] == ")")
count++;
else if (v[i] == "(")
count--;
else
continue;
if (!count) return i;
}
return -1;
}
void TreeNode::collect(std::set<TreeNode *> &s, TreeNode *node) {
if (node == nullptr || s.find(node) != s.end()) return;
s.insert(node);
TreeNode::collect(s, node->left);
TreeNode::collect(s, node->right);
}
TreeNode::~TreeNode() {}
Tree::Tree(TreeNode *root) : root(root) {}
void Tree::print(std::ostream &os, std::string prefix, const TreeNode *node,
bool left) {
if (node != nullptr) {
os << prefix;
os << (left ? "├──" : "└──");
os << node->val << std::endl;
Tree::print(os, prefix + (left ? "│ " : " "), node->left, true);
Tree::print(os, prefix + (left ? "│ " : " "), node->right, false);
}
}
Tree::~Tree() {
std::set < TreeNode * > s;
TreeNode::collect(s, this->root);
for (auto i : s) delete i;
}
std::ostream &operator<<(std::ostream &os, const Tree &root) {
Tree::print(os, "", root.root, false);
return os;
}
int main() {
// std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 2, 4, 6};
// Tree tree(TreeNode::make_complete(v, 0, v.size()));
Tree tree(TreeNode::from_string(
"(1 (1 (4 8 9) (2 5 5)) (0 (1 4 (3 6 2)) (2 5 5)))"));
std::cout << tree << std::endl;
return 0;
}
写这个的主要时间，浪费在用在迭代器寻找匹配括号的位置了……find(), begin(), rbegin(), end(), rend()……用法本身不复杂，但是配上奇怪的想法和与 index 值结合的需要，索性直接手写了。
主函数中被注释的项是用来测试数据结构书写正确性的，下面就是内容了。还是编译、运行 $ valgrind ./a.out。
==19132== Memcheck, a memory error detector
==19132== Copyright (C) 2002-2017, and GNU GPL’d, by Julian Seward et al.
==19132== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==19132== Command: ./a.out
==19132==
( 1 ( 1 ( 4 8 9 ) ( 2 5 5 ) ) ( 0 ( 1 4 ( 3 6 2 ) ) ( 2 5 5 ) ) )
└──1
├──1
│ ├──4
│ │ ├──8
│ │ └──9
│ └──2
│ ├──5
│ └──5
└──0
├──1
│ ├──4
│ └──3
│ ├──6
│ └──2
└──2
├──5
└──5==19132==
==19132== HEAP SUMMARY:
==19132== in use at exit: 0 bytes in 0 blocks
==19132== total heap usage: 74 allocs, 74 frees, 79,788 bytes allocated
==19132==
==19132== All heap blocks were freed – no leaks are possible
==19132==
==19132== For counts of detected and suppressed errors, rerun with: -v
==19132== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
打印完美，没有泄漏，不保证容错了，就先这样吧。
2019-08-20
谁能想到，我已经不会写 01 背包了呢……呵。直接原因是行列处理反了，其他原因就不再多找了，都是借口。
铭记一下这一刻，还是记录一下代码吧。
输入：
n 物品个数， m 背包总重量
第一排数字记录每个物品的重量
第二排数字记录每个物品的价值5
10
2 2 6 5 4
6 3 5 4 6
输出：
15
#include <algorithm>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
int main() {
int m = 0, n = 0;
while (std::cin >> n >> m) {
std::vector<int> weights;
std::vector<int> values;
std::vector<std::pair<int, int>> items;
for (int i = 0; i < n; i++) {
int tmp = 0;
std::cin >> tmp;
weights.push_back(tmp);
}
for (int i = 0; i < n; i++) {
int tmp = 0;
std::cin >> tmp;
values.push_back(tmp);
}
for (int i = 0; i < n; i++) {
items.emplace_back(std::make_pair(weights[i], values[i]));
}
std::sort(items.begin(), items.end(),
[](std::pair<int, int> a, std::pair<int, int> b) {
return a.first < b.first;
});
int dp[n + 1][m + 1];
std::memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j < items[i - 1].first) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - items[i - 1].first] +
items[i - 1].second);
}
}
}
std::cout << dp[n][m] << std::endl;
}
return 0;
}
2019-08-27
做算法题哪里有擅长不擅长的，都是刷题刷出来的，谁能不刷题就擅长这些早 TM 上清华北大了。
LeetCode 5 - Longest Palindromic Substring
很久以前写过，现在碰到一下想不出来了，所以上手直接暴力拆解，O(n^3)……找了一下以前的解答，似乎要好一些，放在这里记录一下。
class Solution {
public:
string longestPalindrome(string s) {
int table[1001][1001];
memset(table, sizeof(table), 0);
int max = 0, left = 0, right = 0;
for (int j = 0; j < s.size(); j++) {
for (int i = 0; i < s.size(); i++) {
bool flag;
if (i == j)
flag = true;
else if (j - i == 1 && s[i] == s[j])
flag = true;
else if (j - i > 1 && s[i] == s[j] && table[i + 1][j - 1])
flag = true;
else
flag = false;
if (flag) {
table[i][j] = j + 1 - i;
if (table[i][j] > max) {
max = table[i][j];
left = i;
right = j;
}
}
else
table[i][j] = 0;
}
}
return s.substr(left, right - left + 1);
}
};
慢……需要学习动态规划的解法。
2019-09-25
具体的只记得一道了……
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr)
return true;
else if (p == nullptr || q == nullptr)
return false;
else if (p->val != q->val)
return false;
else
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};