// #include <ctime>
inline auto click()
{
static auto begin = clock();
auto end = clock();
auto ret = (float)(end - begin) / CLOCKS_PER_SEC;
begin = end;
return ret;
}
月度归档: 2021年4月
[力扣] 算法 633 (C++)
633. 平方数之和
class Solution {
public:
bool judgeSquareSum(int c) {
auto i = 0L;
auto j = long(sqrt(c));
while(i <= j) {
auto rsl = i * i + j * j;
if (rsl == c)
return true;
if (rsl < c)
i++;
else
j--;
}
return false;
}
};
[C++] 推箱子
[力扣] 算法 208 (C#)
208. 实现 Trie (前缀树)
public class Trie
{
class Node
{
public readonly Node[] child = new Node[26];
public bool isEnd;
public void Insert(CharEnumerator chars)
{
ref var node = ref child[chars.Current - 'a'];
if (node == null)
node = new Node();
if (chars.MoveNext())
node.Insert(chars);
else
node.isEnd = true;
}
}
Node root = new Node();
public Trie() { root.isEnd = true; }
public void Insert(string word)
{
if (word == string.Empty)
return;
var itor = word.GetEnumerator();
itor.MoveNext();
root.Insert(itor);
}
public bool Search(string word)
{
var node = root;
foreach (var ch in word)
{
ref var next = ref node.child[ch - 'a'];
if (next == null)
return false;
node = next;
}
return node.isEnd;
}
public bool StartsWith(string prefix)
{
var node = root;
foreach (var ch in prefix)
{
ref var next = ref node.child[ch - 'a'];
if (next == null)
return false;
node = next;
}
return true;
}
}
[Java] 迷宫寻路
题目请参考:PTA7-1 迷宫寻路 (20分)
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static final Scanner input = new Scanner(System.in);
public static void main(String[] args) {
for (;;) {
int row = input.nextInt();
if (row < 0) {
break;
}
Maze maze = new Maze(row, input.nextInt());
if (maze.process()) {
Maze.Node now = maze.goal;
StringBuilder sb = new StringBuilder();
while (now != null) {
sb.insert(0, now.forPrint());
now = now.from;
}
System.out.println(sb);
} else {
System.out.println("NO FOUND");
}
}
}
static class Maze {
int row;
int col;
Node[][] maze;
PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing(Node::f));
Node goal;
class Node {
final int x;
final int y;
int g;
final int h;
Node from;
boolean closed;
Node(int x, int y) {
this.x = x;
this.y = y;
h = Math.abs(x - row) + Math.abs(y - col);
}
int f() {
return g + h;
}
void setParent(Node parent) {
g = parent.g + 1;
from = parent;
}
String forPrint() {
return (x + 1) + "," + (y + 1) + System.lineSeparator();
}
void addToClose() {
closed = true;
}
}
Maze(int row, int col) {
this.row = row;
this.col = col;
maze = new Node[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (input.nextInt() == 0) {
maze[i][j] = new Node(i, j);
}
}
}
goal = maze[row - 1][col - 1];
}
boolean process() {
if (maze[0][0] != null) {
open.add(maze[0][0]);
}
while (!open.isEmpty()) {
Node parent = open.poll();
if (parent == goal) {
return true;
}
parent.addToClose();
spread(parent);
}
return false;
}
void spread(Node parent) {
int x = parent.x;
int y = parent.y;
trySpread(parent, x - 1, y);
trySpread(parent, x + 1, y);
trySpread(parent, x, y - 1);
trySpread(parent, x, y + 1);
}
void trySpread(Node parent, int childX, int childY) {
if (childX < 0 || childX == row || childY < 0 || childY == col) {
return;
}
Node child = maze[childX][childY];
if (child == null || child.closed) {
return;
}
if (open.contains(child)) {
if (parent.g + 1 < child.g) {
child.setParent(parent);
}
} else {
child.setParent(parent);
open.add(child);
}
}
}
}