【求答案】最近面过最恶心的两道题

麻倉枼

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

条件： 6~8小时，超时可以继续做题，直到做出答案。。
第一道题：input是 string digits (example: "124345353"), int target (example: 7)，添加“+”或者“*”进去使得答案为target。Return string type, 如果没有答案，return "No solution"

第二道题，google上找到题目，没找到思路，答案做出一半不到，已经没超时了。。真的是**。。

题目： http://www-personal.engin.umd.um ... 488/sample-test.txt

补充内容 (2018-1-19 10:57):
已经有答案了，可以用来参考一下

magicsets

最后答案就是题目样例给的那样，可以快速用这个online C++工具执行一下：
http://cpp.sh/3qhuej

6 tiles
link 1
11
23
link 2
44
11
11
23
link 3
44
11
1116
2336
link 4
44
5111
711116
2336
link 5
44
5111
71111662
233664
link 6
4448
511116
71111662
233664
--------
7 tiles
link 1
12
34
link 2
5112
6334
link 3
755112
866334
link 4
97755112
08866334
link 5
97755112
08866334
66
42
link 6
97755112
08866334
08 66
18 42
link 7
97755112
08866334
08 66 34
18 42 95
--------
10 tiles
link 1
11
12
link 2
11
12
12
93
link 3
11
12
12
93
93
99
link 4
11
12
12
93
9339
9998
link 5
11
12
12
93
933995
999886
link 6
11
12
12
93
93399557
99988666
link 7
11
12
12 77
93 57
93399557
99988666
link 8
1113
1224
12 77
93 57
93399557
99988666
link 9
1113
122445
12 4777
93 57
93399557
99988666
link 10
1113
122445
12244777
9339 57
93399557
99988666

复制代码

magicsets

本帖最后由 magicsets 于 2018-1-19 23:33 编辑

第二个题目确实比较复杂，这种工程上的复杂性可以通过抽象、分解模块并封装来处理

我试着写了一下，主要定义了5个类：
Point, Rectangle, Tile, Canvas, TileManager

其中Point和Rectangle用于服务坐标计算以及对拼图边界的处理

Tile表示一个2X2的砖片，支持旋转操作

Canvas用于抽象一个“无边界”，支持负数坐标的拼图

在实现了以上基础设施的情况下，再实现拼图算法，结构和代码就比较清晰了

#include <array>
#include <cstddef>
#include <cstring>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <unordered_set>
#include <vector>
#define DISALLOW_COPY_AND_ASSIGN(classname) \
classname(const classname &other) = delete; \
classname& operator=(const classname &other) = delete
struct Point {
int x, y;
Point shift(const Point &delta) const {
return { x + delta.x, y + delta.y };
}
Point operator-() const {
return { -x, -y };
}
bool operator==(const Point &other) const {
return x == other.x && y == other.y;
}
};
struct PointHasher {
std::size_t operator()(const Point &loc) const {
return (static_cast<std::size_t>(loc.x) << 32) | static_cast<std::size_t>(loc.y);
}
};
struct Rectangle {
int left, right, top, bottom;
int width() const {
return right - left + 1;
}
int area() const {
return (right - left + 1) * (bottom - top + 1);
}
bool contains(const Point &loc) const {
return loc.x >= left && loc.x <= right && loc.y >= top && loc.y <= bottom;
}
int address(const int x, const int y) const {
return x - left + (y - top) * width();
}
Rectangle intersect(const Rectangle &other) const {
return { std::max(left, other.left),
std::min(right, other.right),
std::max(top, other.top),
std::min(bottom, other.bottom) };
}
Rectangle extend(const Rectangle &other) const {
return { std::min(left, other.left),
std::max(right, other.right),
std::min(top, other.top),
std::max(bottom, other.bottom) };
}
};
class Canvas {
public:
Canvas(const Rectangle &frame, const char blank)
: frame_(frame), blank_(blank),
cells_(static_cast<char*>(std::malloc(frame_.area()))) {
std::memset(cells_, blank_, frame_.area());
}
~Canvas() {
std::free(cells_);
}
char& operator[](const Point &loc) {
if (!frame_.contains(loc)) {
const Rectangle nframe = {
Extend(loc.x, frame_.left), Extend(loc.x, frame_.right),
Extend(loc.y, frame_.top), Extend(loc.y, frame_.bottom)
};
resize(nframe);
}
return cells_[frame_.address(loc.x, loc.y)];
}
std::string toString(const Rectangle &box) const {
const Rectangle region = frame_.intersect(box);
std::string out;
for (int y = region.top; y <= region.bottom; ++y) {
out.append(cells_ + frame_.address(region.left, y), region.width());
out.push_back('\n');
}
return out;
}
private:
static int Extend(const int value, int bound) {
if (bound < 0) {
while (bound > value) {
bound *= 2;
}
} else {
while (bound < value) {
bound *= 2;
}
}
return bound;
}
void resize(const Rectangle &nframe) {
char *ncells = static_cast<char*>(std::malloc(nframe.area()));
std::memset(ncells, blank_, nframe.area());
for (int y = frame_.top; y <= frame_.bottom; ++y) {
std::memcpy(ncells + nframe.address(frame_.left, y),
cells_ + frame_.address(frame_.left, y),
frame_.width());
}
std::free(cells_);
cells_ = ncells;
frame_ = nframe;
}
Rectangle frame_;
const char blank_;
char *cells_;
DISALLOW_COPY_AND_ASSIGN(Canvas);
};
class Tile {
public:
Tile(const char lu, const char ru, const char rb, const char lb)
: cells_({{lu, ru, rb, lb}}) {
}
Tile(const Tile &other) {
std::memcpy(cells_.data(), other.cells_.data(), sizeof(cells_));
}
Tile rotate90() const {
return Tile(cells_[3], cells_[0], cells_[1], cells_[2]);
}
char operator[](const int corner) const {
return cells_[corner];
}
private:
// 0 1
// XX
// XX
// 3 2
std::array<char, 4> cells_;
};
class TileManager {
public:
TileManager()
: canvas_({-8, 8, -8, 8}, ' '),
shadow_({-8, 8, -8, 8}, kEmptyCell),
bounds_({0, 0, 0, 0}) {
}
void link(const char **tiles) {
std::vector<Tile> input;
while (true) {
input.emplace_back(tiles[0][0], tiles[0][1], tiles[1][1], tiles[1][0]);
if (tiles[2] == 0) {
break;
}
tiles += 3;
}
std::cout << input.size() << " " << "tiles\n";
for (int i = 0; i < input.size(); ++i) {
link(input[i]);
std::cout << "link " << (i + 1) << "\n";
std::cout << canvas_.toString(bounds_) << "\n";
}
}
private:
void link(Tile tile) {
const Point loc = locate(tile);
for (int dir = 0; dir < 4; ++dir) {
const Point cell = loc.shift(kTileOffsets[dir]);
slots_.erase(cell);
const char ch = tile[dir];
canvas_[cell] = ch;
shadow_[cell] = kInvalidCell;
for (int i = 0; i < 2; ++i) {
const Point slot = cell.shift(kSlotOffsets[dir * 2 + i]);
char &orig = shadow_[slot];
if (orig == kEmptyCell) {
orig = ch;
slots_.emplace(slot);
} else if (orig != kInvalidCell && orig != ch) {
orig = kInvalidCell;
slots_.erase(slot);
}
}
}
bounds_ = bounds_.extend({loc.x, loc.x + 1, loc.y, loc.y + 1});
}
Point locate(Tile &target) {
if (slots_.empty()) {
return {0, 0};
}
for (const Point &slot : slots_) {
for (const Point &offset : kTileOffsets) {
const Point loc = slot.shift(-offset);
for (int rotate = 0; rotate < 4; ++rotate) {
target = target.rotate90();
if (matches(target, loc)) {
return loc;
}
}
}
}
throw std::runtime_error("Invalid input!");
}
bool matches(const Tile &tile, const Point &loc) {
int count = 0;
for (int dir = 0; dir < 4; ++dir) {
const char expected = shadow_[loc.shift(kTileOffsets[dir])];
if (expected == kEmptyCell) {
continue;
}
if (expected != tile[dir]) {
return false;
}
++count;
}
return count >= 2;
}
Canvas canvas_;
Canvas shadow_;
Rectangle bounds_;
std::unordered_set<Point, PointHasher> slots_;
constexpr static char kEmptyCell = '.';
constexpr static char kInvalidCell = 'X';
const static std::array<Point, 4> kTileOffsets;
const static std::array<Point, 8> kSlotOffsets;
DISALLOW_COPY_AND_ASSIGN(TileManager);
};
const std::array<Point, 4> TileManager::kTileOffsets = {{
{ 0, 0 }, { 1, 0 }, { 1, 1 }, { 0, 1 }
}};
const std::array<Point, 8> TileManager::kSlotOffsets = {{
{ -1, 0 }, { 0, -1 },
{ 0, -1 }, { 1, 0 },
{ 1, 0 }, { 0, 1},
{ 0, 1 }, { -1, 0 }
}};
int main(int argc, char *argv[]) {
std::unique_ptr<TileManager> tm;
tm = std::make_unique<TileManager>();
const char *tiles1[] = {
"11", // 1
"23",
"",
"44", // 2
"11",
"",
"16", // 3
"36",
"",
"51", // 4
"71",
"",
"46", // 5
"26",
"",
"14", // 5
"68",
0
};
tm->link(tiles1);
std::cout << "--------\n\n";
tm = std::make_unique<TileManager>();
const char *tiles2[] = {
"12", // 1
"34",
"",
"36", // 2
"15",
"",
"56", // 3
"78",
"",
"78", // 4
"90",
"",
"46", // 5
"26",
"",
"88", // 6
"01",
"",
"93", // 7
"54",
0
};
tm->link(tiles2);
std::cout << "--------\n\n";
tm = std::make_unique<TileManager>();
const char *tiles3[] = {
"11", // 1
"12",
"",
"12", // 2
"93",
"",
"93", // 3
"99",
"",
"39", // 4
"98",
"",
"95", // 5
"86",
"",
"57", // 6
"66",
"",
"77", // 7
"57",
"",
"13", // 8
"24",
"",
"45", // 9
"47",
"",
"24", // 10
"39",
0
};
tm->link(tiles3);
return 0;
}

复制代码

真淘蛮

fb 的题，见到有人写过，对的话加点米吧

public List<String> equation(String e) {
      List<String> res = new LinkedList<>();
      if (e.length() == 0) return res;
      String[] temp = e.split("=");
      String left = temp[0], right = temp[1];
      Map<Integer, List<String>> l = new HashMap<>();
      findResult(l, left, 0, 0, "");
      Map<Integer, List<String>> r = new HashMap<>();
      findResult(r, right, 0, 0, "");
      for (Integer num1 : l.keySet()) {
         if (r.containsKey(num1)) {
            for (String ll : l.get(num1)) {
                  for (String rr : r.get(num1)) {
                     res.add(ll + "=" + rr);
                  }
            }
         }
      }
      return res;
}

public void findResult(Map<Integer, List<String>> map, String str, int start, int sum, String cur) {
      if (start == str.length()) {
         if (!map.containsKey(sum)) map.put(sum, new LinkedList<>());
         map.get(sum).add(cur);
         return;
      }
      for (int i = start; i < str.length(); i++) {
         String s = str.substring(start, i + 1);
         if (s.length() > 1 && s.charAt(0) == '0') break;
         int num = Integer.parseInt(s);
         findResult(map, str, i + 1, sum + num, cur + "+" + s);
         findResult(map, str, i + 1, sum - num, cur + "-" + s);
      }
}

littlegirl

第一題是leetcode 282
PS可以帮忙加米吗？

ouyangivan

哟西，校友啊，要不要一起抱团刷题

麻倉枼

ouyangivan 发表于 2018-1-18 08:21
哟西，校友啊，要不要一起抱团刷题

我好久没刷题了。怎么刷都会忘记答案，现在巩固C++基础和其他东西中。

伊罗伊罗

ouyangivan 发表于 2018-1-18 21:21
哟西，校友啊，要不要一起抱团刷题

求一起刷题！！！

伊罗伊罗

第二题是不是深度优先搜索。需要找到一条长度为N的路径。每个tile经过旋转可以产生4个点，这四个需要指向同一个用来表示visited的object。不过这样做复杂度有点高要n平方。不知道有没有更好的方法。

麻倉枼

伊罗伊罗发表于 2018-1-19 00:19
第二题是不是深度优先搜索。需要找到一条长度为N的路径。每个tile经过旋转可以产生4个点，这四个需要指向同 ...

我的答案比较bruteforce，可能你做出来后看看可不可以？
另外这道题是C的，被我强制改成C++（用了vector）

麻倉枼

本帖最后由麻倉枼于 2018-1-19 11:13 编辑

magicsets 发表于 2018-1-19 10:36
最后答案就是题目样例给的那样，可以快速用这个online C++工具执行一下：
http://cpp.sh/3qhuej

大神我感觉你C++功底很强，请教一下平时除了看书多练习外怎样提高C++功力呢？

一些很基础的debug，我现在都不知道怎样做好：
1.如何debug template?
2.如何debug smart pointer?
3.如何debug lvalue和rvalue的程序？(Ex:如何debug 一个argument是copy了还是move了）
4.如何debug initializer list constructor?

其次我想请教下，哪里可以学习，怎样练习这些内容：
1. template
2. variadic template
3. Serialization
4. Reflection
5. Proxy class
6. move (rvalue)
暂时这么多，顺便发一贴当做自己学习checklist

【求答案】最近面过最恶心的两道题

注册一亩三分地论坛，查看更多干货！

相关帖子

评分

评分

评分

评分

浏览过的版块