Dark Mode Toggle

几道算法题

2016 Feb 21 See all posts

几道算法作业题，之前对算法题颇有怨念，总觉得有点浪费时间，有那么多更好玩的事情可以发掘。一分钟默写出KMP算法又怎么样？自己琢磨出Boyer-Moore算法才是真的厉害。既然是不得不做的作业，真花时间做出来了其实还挺有意思，基本的算法素养(常见的算法，复杂度，势分析)还是应该有的，记录一下免得忘

1. 无限循环小数循环节计算

输入：正整数 a 和 b （只需要处理32位或64位整数即可，不需要高精度计算）

输出：a/b的除法结果。循环节用大括号包围起来。

举例：

输入 10/5 输出 2

输入 1/4 输出 0.25

输入 1/3 输出 0.{3}

public class Fraction2DecimalAlgo {

    /**
     * 保存每一次除法的余数，当出现余数重复时，就发现了循环节
     * @param N 分子
     * @param D 分母
     * @return 小数形式, 循环节用括号包围
     */
    public static String fraction2decimal(int N, int D) {
        HashMap<Integer, Integer> remainder = new HashMap<Integer, Integer>();
        StringBuilder sb = new StringBuilder();
        sb.append(N / D);
        sb.append('.');
        N = N % D;
        int i = 0;                              //计数器
        while (remainder.get(N) == null) {      // a.发现循环节终止循环   b.余数为0就是非循环的小数，也终止循环
            remainder.put(N, i++);
            N = N * 10;
            sb.append(N / D);
            N = N % D;
            if (N == 0)
                break;
        }
        if (N != 0) {                          //对于循环小数，当前计数器位置 - 循环节开始的地方，插入括号
            int len = i - remainder.get(N);
            sb.insert(sb.length() - len, '(');
            sb.append(')');
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(fraction2decimal(1, 7));
        System.out.println(fraction2decimal(1, 2));
    }
}

2.蛋疼的联合国电梯

3名反恐士兵(counter-terrorists)将3名恐怖分子(terrorists)从电梯底层押送至电梯顶层，

押送过程中电梯最多只能容纳2人，最少1人；
试问有多少种走法，并给出过程

/**
 * 蛋疼的联合国电梯
 * M = 3 时候
 * 初始态 (3, 3) <==> (0, 0)
 * 结果态 (0, 0) <==> (3, 3)
 * 每次可以 {{0, 2}, {1, 1}, {2, 0}, {0, 1}, {1, 0}}, 且往返交替
 * 求所有可能的走法
 *
 */
public class BackTrackAlgo {

    private final int M;
    private boolean[][] m;
    private boolean turn;         // go true  back false
    private int[][] record;       // 000000 - 111111   size = 2 << (M * 2)
    private String[] action;
    private boolean[] check;
    private int pos = 1;
    private static int c = 1;     // 解法计数

    public BackTrackAlgo(int M) {
        this.M = M;
        int px = M, py = M;
        m = new boolean[M+1][M + 1];
        int totalState = 2 << (M * 2);
        record = new int[totalState][2];
        check = new boolean[totalState];
        action = new String[totalState];
        for (int i = 0; i < M + 1; i++)
            for (int j = 0; j < M + 1; j++) {
                if (i == j || i == 0 || i == M) ;
                else m[i][j] = true;
            }
        record[0][0] = record[0][1] = M;
        check[0] = true;
        search(px, py);
    }

    /*判断这一状态是否在前面已经出现过*/
    boolean isRepeat(int x, int y, boolean turn) {
        for (int i = 0; i < pos; i++)
            if (x == record[i][0] && y == record[i][1] && turn == check[i])
                return true;
        return false;
    }

    void search(int px, int py) {
        int[][] goStep = {{0, 2}, {1, 1}, {2, 0}, {0, 1}, {1, 0}};  //每次可能有5种走法
        String [] desc = {"T>T>", "T>C>", "C>C>", "T>", "C>"};
        int i;
        if (px == 0 && py == 0) {
            System.out.println(String.format("method %d:", c++));
            for (i = 0; i < pos; i++) {
                String str = String.format("(%d, %d) <==> (%d, %d) action:%s", record[i][0], record[i][1],
                        M - record[i][0], M - record[i][1], action[i]);
                System.out.println(str);
            }
        } else if (!turn) {
            for (i = 0; i < 5; i++) {
                px -= goStep[i][0];
                py -= goStep[i][1];
                if (px < 0 || px > 3 || py < 0 || py > 3 || m[px][py] || isRepeat(px, py, turn)) {
                    px += goStep[i][0];
                    py += goStep[i][1];
                    continue;
                }
                record[pos][0] = px;
                record[pos][1] = py;
                action[pos] = desc[i];
                check[pos] = turn;
                pos++;
                turn = !turn;
                search(px, py);
                pos--;                     //回溯
                turn = !turn;
                px += goStep[i][0];
                py += goStep[i][1];
            }
        } else {
            for (i = 0; i < 5; i++) {
                px += goStep[i][0];
                py += goStep[i][1];
                if (px < 0 || px > 3 || py < 0 || py > 3 || m[px][py] || isRepeat(px, py, turn)) {
                    px -= goStep[i][0];
                    py -= goStep[i][1];
                    continue;
                }
                record[pos][0] = px;
                record[pos][1] = py;
                action[pos] = desc[i].replaceAll(">", "<");
                check[pos] = turn;
                pos++;
                turn = !turn;
                search(px, py);
                pos--;                    //回溯
                turn = !turn;
                px -= goStep[i][0];
                py -= goStep[i][1];
            }
        }
    }


    public static void main(String[] args) {
        new BackTrackAlgo(3);
    }
}

同事的解法更简洁好懂：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class UnionElevator {

    static class State implements Cloneable {
        int BT, BC; //bottom terrorists, bottom counter-terrorists
        int TT, TC; //top ...
        boolean EB; //is elevator at bottom?

        public String toString() {
            return "T" + BT + "C" + BC + ":" + "T" + TT + "C" + TC + ":" + (EB ? "B" : "T");
        }

        public State clone() {
            State s = new State();
            s.BT = BT;
            s.BC = BC;
            s.TT = TT;
            s.TC = TC;
            s.EB = EB;
            return s;
        }

    }

    Set<String> states = new HashSet<>();
    List<String> steps = new ArrayList<>();
    
    void doStep(State s, String step, int dBT, int dBC) {
        State next;
        next = s.clone();
        next.BT += dBT;
        next.BC += dBC;
        next.TT -= dBT;
        next.TC -= dBC;
        if(next.BT >= 0 && next.BC >= 0 && next.TT >= 0 && next.TC >= 0) {
            if((next.BT <= next.BC || next.BC == 0) && (next.TT <= next.TC || next.TC == 0)) {
                String nextStateStr = next.toString();
                //如果满足约束条件，而且这个状态之前没出现过，那么纪录下来并从这个状态继续穷举所有可能性
                if(!states.contains(nextStateStr)) {
                    states.add(nextStateStr);
                    steps.add(step);
                    act(next);
                    steps.remove(steps.size() - 1);
                    states.remove(nextStateStr);
                }
            }
        }
    }

    void act(State s) {
        if(s.TT == 3 && s.TC == 3) {
            System.out.println("----");
            for (String step : steps) {
                System.out.println(step);
            }
        }
        else {
            if(s.EB) {
                //move up
                s.EB = false;
                doStep(s, "T> T>", -2, 0);
                doStep(s, "C> C>", 0, -2);
                doStep(s, "T> C>", -1, -1);
                doStep(s, "T>   ", -1, 0);
                doStep(s, "   C>", 0, -1);
            }
            else {
                //move down
                s.EB = true;
                doStep(s, "T< T<", +2, 0);
                doStep(s, "C< C<", 0, +2);
                doStep(s, "T< C<", +1, +1);
                doStep(s, "T<   ", +1, 0);
                doStep(s, "   C<", 0, +1);
            }
        }
    }

    void solve() {
        State s = new State();
        s.BT = 3;
        s.BC = 3;
        s.EB = true;
        states.add(s.toString());
        act(s);
    }

    public static void main(String[] args) {
        new UnionElevator().solve();
    }
}

3.关键字检索

比如我们有很多句子： "hello world", "nice to meet you", "how are you", "help yourself"
老师只需要输入其中某个单词的前缀，我们要快速找到含有这个单词的句子。
举例：
输入 "h" 找到 "hello world", "how are you", "help yourself"
输入 "how" 找到 "how are you"
输入 "you" 找到 "how are you", "help yourself"
输入 "yourself" 找到 "help yourself"
为了简化这个问题，我们假设所有句子都是由小写字母和空格组成，不含其它字符。
要求：请实现一个trie树和倒排文档，实现以上搜索功能。

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * 关键字检索, Trie树来支持前缀查找, 倒排索引来支持全词匹配
 */
public class InvertedIndexAlgo {

    public class Trie {
        private boolean isLeaf;
        private HashMap<Character, Trie> map;

        public Trie() {
            map = new HashMap<Character, Trie>();
            isLeaf = false;
        }

        public void put(String s) {
            if (s.length() == 0) {
                isLeaf = true;
                return;
            }
            if (!map.containsKey(s.charAt(0))) {
                map.put(s.charAt(0), new Trie());
            }
            map.get(s.charAt(0)).put(s.substring(1));
        }

        public void travelTree(String perm) {
            if (isLeaf) {
                System.out.println(perm);
            }
            if (map.size() == 0) return;
            for (Character c : map.keySet()) {
                map.get(c).travelTree(perm + c);
            }
        }

        public void travelTree(String perm, List<String> sl) {
            if (isLeaf) {
                sl.add(perm);
            }
            if (map.size() == 0) return;
            for (Character c : map.keySet()) {
                map.get(c).travelTree(perm + c, sl);
            }
        }

        public List<String> getSuggestions(String q) {
            List<String> suggestions = new ArrayList<>();
            getSuggestions(q, "", suggestions);
            return suggestions;
        }

        public void getSuggestions(String q, String perm, List<String> sl) {
            if (q.length() == 0) {
                travelTree(perm, sl);
            }
            if (map.size() == 0) return;
            if (q.length() > 0 && map.containsKey(q.charAt(0))) {
                map.get(q.charAt(0)).getSuggestions(q.substring(1), perm + q.charAt(0), sl);
            }
        }

//        public static void main(String[] args) {
//            Trie pt=new Trie();
//            pt.put("hello");
//            pt.put("hell");
//            pt.put("how");
//            //pt.travelTree("");
//            System.out.println(pt.getSuggestions("h"));
//            System.out.println(pt.getSuggestions("he"));
//        }
    }

    private final List<String> inputList;
    private Map<String, Set<Integer>> map;
    private Trie trie;

    public InvertedIndexAlgo(List<String> inputList) {
        this.inputList = inputList;
        map = new HashMap<>();
    }

    public void build() {
        for (int i = 0; i < inputList.size(); i++) {
            String str = inputList.get(i);
            String[] words = str.split("\\s");
            for (String word : words) {
                Set<Integer> value = map.getOrDefault(word, new HashSet<>());
                value.add(i);
                map.put(word, value);
            }
        }
        trie = new Trie();
        map.keySet().forEach(trie::put);
    }

    public List<String> search(String str) {
        Set<Integer> indexSet = map.getOrDefault(str, new HashSet<>());
        trie.getSuggestions(str).forEach(s -> {
            Set<Integer> prefixIndexSet = map.getOrDefault(s, Collections.emptySet());
            indexSet.addAll(prefixIndexSet);
        });
        return indexSet.stream().map(inputList::get).collect(Collectors.toList());
    }

    public static void main(String[] args) {
        List<String> inputList = Stream.of("hello world",
                "nice to meet you",
                "how are you",
                "help yourself"
                ).collect(Collectors.toList());
        InvertedIndexAlgo invertedIndexAlgo = new InvertedIndexAlgo(inputList);
        invertedIndexAlgo.build();

        Stream.of("h", "hello", "you", "yourself").forEach(s -> {
            System.out.println(String.format("search:[%s] results:", s));
            invertedIndexAlgo.search(s).forEach(System.out::println);
            System.out.println("------");
        });
    }
}

4.路径规划

最优路径的定义：从起点开始到所有可能的终点，节点权重之和最高的路径。
输入：n个节点，m个路径，起点
输出：最优路径的权重值之和
举例：
3个节点：
A 1
B 2
C 2
3条路径：
A->B
B->C
A->C
起点：
A
输出：5 （最优路径是 A->B->C ，权重之和是 1+2+2=5）
提示：如果输入的学习路径有环，请输出 -1。数据量较多请注意算法复杂度。

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 规划学习路径
 * topsort + dp
 */
public class DAGLongestPathAlgo {

    public static void main(String[] args) {
        int[][] m = new int[6][6];
        m[0][1] = 3;
        m[1][2] = 3;
//        m[2][0] = 3;               //加一个环
        m[2][4] = 3;
        m[4][5] = 3;
        m[3][4] = 3;
        m[0][3] = 3;
        m[3][5] = 3;
        int[] dp_max = new int[6];
        Arrays.fill(dp_max, 0);
        int[] dp_min = new int[6];
        Arrays.fill(dp_min, Integer.MAX_VALUE);

        int[] commingEdges = new int[6];
        int edgesCount = 0;
        Arrays.fill(commingEdges, 0);
        for(int i = 0; i < m.length; i++){
            for(int j = 0; j< m.length; j++){
                if (m[i][j] != 0){
                    commingEdges[j]++;
                    edgesCount++;
                }
            }
        }
        boolean[] v = new boolean[m.length];
        Queue<Integer> q = new LinkedList<Integer>();
        for (int i = 0; i < commingEdges.length; i++)
            if (commingEdges[i] == 0) {
                q.add(i);
                dp_max[i] = 0;
                dp_min[i] = 0;
            }

        while (!q.isEmpty()) {
            int i = q.poll();
            if (v[i])
                continue;
            v[i] = true;
            for (int j = 0; j < m.length; j++)
                if (m[i][j] != 0) {
                    edgesCount--;
                    commingEdges[j]--;
                    if (commingEdges[j] == 0)
                        q.add(j);
                    dp_max[j] = Math.max(dp_max[j], dp_max[i] + m[i][j]);
                    dp_min[j] = Math.min(dp_min[j], dp_min[i] + m[i][j]);
                }
        }
        if (edgesCount > 0) {
            System.out.println("found circle! -1");
        } else
            System.out.println(dp_max[5] + " " + dp_min[5]);
    }

}