分类： 算法

[力扣] 算法 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);
            }
        }

    }
}

[力扣] 算法 74 (C++)

74. 搜索二维矩阵

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int left = 0, right = row * col - 1;
        while (left < right) {
            auto mid = (left + right) / 2;
            auto num = matrix[mid / col][mid % col];
            if (num == target) 
                return true;
            if (num < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return matrix[left / col][left % col] == target;
    }
};

[力扣] 算法 190 (C++)

190. 颠倒二进制位

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        auto ret = (n >> 16) | (n << 16);// ((ret & 0xffff0000) >> 16) | ((ret & 0x0000ffff) << 16)
        ret = ((ret & 0xff00ff00) >> 8) | ((ret & 0x00ff00ff) << 8);
        ret = ((ret & 0xf0f0f0f0) >> 4) | ((ret & 0x0f0f0f0f) << 4);// 1111 0000
        ret = ((ret & 0xcccccccc) >> 2) | ((ret & 0x33333333) << 2);// 1100 0011
        ret = ((ret & 0xaaaaaaaa) >> 1) | ((ret & 0x55555555) << 1);// 1010 0101
        return ret;
    }
};

[力扣] 算法 150 (C#)

150. 逆波兰表达式求值

public class Solution
{
    public int EvalRPN(string[] tokens)
    {
        var stack = new Stack<int>();
        foreach (var token in tokens)
        {
            switch (token)
            {
                case var add when add == "+":
                    stack.Push(stack.Pop() + stack.Pop());
                    break;
                case var minus when minus == "-":
                    stack.Push(-stack.Pop() + stack.Pop());
                    break;
                case var mul when mul == "*":
                    stack.Push(stack.Pop() * stack.Pop());
                    break;
                case var div when div == "/":
                    var top = stack.Pop();
                    stack.Push(stack.Pop() / top);
                    break;
                default:
                    stack.Push(int.Parse(token));
                    break;
            }
        }
        return stack.Pop();
    }
}

[力扣] 算法 59 (C#)

59. 螺旋矩阵 II

public class Solution {
    public int[][] GenerateMatrix(int n) {
        var ret = new int[n][];
        for (var i = 0; i < ret.Length; i++)
            ret[i] = new int[n];
        var loc = (x:0, y:0);
        var dir = (x:0, y:1);
        for(var i = 0; i < n * n; i++)
        {
            ret[loc.x][loc.y] = i + 1;
            var next = (x:loc.x + dir.x, y:loc.y + dir.y);
            if(next.x < 0 || next.y<0||next.x == n || next.y == n || ret[next.x][next.y] != 0)
            {
                dir = (dir.y, -dir.x);
                next = (x: loc.x + dir.x, y: loc.y + dir.y);
            }
            loc = next;
        }
        return ret;
    }
}