[左神面试指南] 其他题目[上]篇

CDxxx 从 5 随机到 7 随机及其扩展

/* rand1To5实现等概率随机产生1~7的随机函数rand1To7 */
public int rand1To5() 
{
	return (int) (Math.random() * 5) + 1;
}
public int rand1To7() 
{
    int num = 0;
    do 
    {
    	num = (rand1To5() - 1) * 5 + rand1To5() - 1;
    } 
    while (num > 20);
    return num % 7 + 1;
}

/* 用rand01p实现等概率随机产生1~6的随机函数rand1To6。*/
public int rand01p() 
{
	// 可随意改变 p
    double p = 0.83;
	return Math.random() < p ? 0 : 1;
}
public int rand01() 
{
    int num;
    do 
    {
    	num = rand01p();
    } 
    while (num == rand01p());
    return num;
}
public int rand0To3() 
{
	return rand01() * 2 + rand01();
}
public int rand1To6() 
{
    int num = 0;
    do 
    {
    	num = rand0To3() * 4 + rand0To3();
    } 
    while (num > 11);
    return num % 6 + 1;
}

/* 用rand1ToM(m)实现等概率随机产生1~n的随机函数rand1ToN。*/
public int rand1ToM(int m)
{
    return (int) (Math.random() * m) + 1;
}
public int rand1ToN(int n, int m)
{
    int[] nMSys = getMSysNum(n - 1, m);
    int[] randNum = getRanMSysNumLessN(nMSys, m);
    return getNumFromMSysNum(randNum, m) + 1;
}
// 把 value 转成 m 进制数
public int[] getMSysNum(int value, int m)
{
    int[] res = new int[32];
    int index = res.length - 1;
    while (value != 0)
    {
        res[index--] = value % m;
        value = value / m;
    }
    return res;
}
// 等概率随机产生一个 0~nMsys 范围的数，只不过是用 m 进制数表达的
public int[] getRanMSysNumLessN(int[] nMSys, int m)
{
    int[] res = new int[nMSys.length];
    int start = 0;
    while (nMSys[start] == 0) start++;
    int index = start;
    boolean lastEqual = true;
    while (index != nMSys.length)
    {
        res[index] = rand1ToM(m) - 1;
        if (lastEqual)
        {
            if (res[index] > nMSys[index])
            {
                index = start;
                lastEqual = true;
                continue;
            }
            else
                lastEqual = res[index] == nMSys[index];
        }
        index++;
    }
    return res;
}
// 把 m 进制数转换成十进制数
public int getNumFromMSysNum(int[] mSysNum, int m)
{
    int res = 0;
    for (int i = 0; i != mSysNum.length; i++)
        res = res * m + mSysNum[i];
    return res;
}

CD55 一行代码求两个数的最大公约数

public class CD55_1
{
    public static  int solution(int m, int n)
    {
        return n == 0 ? m : solution(n, m % n);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n, m;
        n = in.nextInt();
        m = in.nextInt();
        System.out.println(solution(n, m));
    }
}

CD56 有关阶乘的两个问题1

/* 因子5的个数 */
public class CD56_1
{
    public static long solution(long num)
    {
        if (num < 0) return 0;
        long res = 0;
        while (num != 0)
        {
            res += num / 5;
            num /= 5;
        }
        return res;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        long n;
        n = in.nextLong();
        System.out.println(solution(n));
    }
}

CD57 有关阶乘的两个问题

public class CD57_1
{
    /* 2的因子 */
    public static long solution1(long num)
    {
        if (num < 1) return -1;
        long res = 0;
        while (num != 0)
        {
            num >>= 1;
            res += num;
        }
        return res;
    }

    /*
     * 如果把N!的结果中因子2的总个数记为Z,
     * 把N的二进制数表达式中1的个数记为m,
     * 还存在如下一个关系 Z = N - m，
     */
    public static long solution2(long num)
    {
        if (num < 1) return -1;
        long ones = 0;
        long tmp = num;
        while (tmp != 0)
        {
            ones += (tmp & 1) != 0 ? 1 : 0;
            tmp >>= 1;
        }
        return num - ones;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        System.out.println(solution1(n));
    }
}

CD58 判断一个点是否在矩形内部

public class CD58_1
{
    public static boolean solution(double x1, double y1, double x2, double y2,
                                   double x3, double y3, double x4, double y4,
                                   double x, double y)
    {
        if (y1 == y2) return isInside(x1, y1, x4, y4, x, y);
        double l = Math.abs(y4 - y3);
        double k = Math.abs(x4 - x3);
        double s = Math.sqrt(k * k + l * l);
        double sin = l / s;
        double cos = k / s;
        double x1R = cos * x1 + sin * y1;
        double y1R = -x1 * sin + y1 * cos;
        double x4R = cos * x4 + sin * y4;
        double y4R = -x4 * sin + y4 * cos;
        double xR = cos * x + sin * y;
        double yR = -x * sin + y * cos;
        return isInside(x1R, y1R, x4R, y4R, xR, yR);
    }

    public static boolean isInside(double x1, double y1, double x4, double y4, double x, double y)
    {
        if (x <= x1 || x >= x4 || y >= y1 || y <= y4)
            return false;
        else return true;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        double[][] points = new double[5][2];
        for (int i = 0; i < points.length; i++)
        {
            points[i][0] = in.nextDouble();
            points[i][1] = in.nextDouble();
        }
        System.out.println(solution(points[0][0], points[0][1], points[1][0], points[1][1],
                points[2][0], points[2][1], points[3][0], points[3][1],
                points[4][0], points[4][1]) ? "Yes" : "No");
    }
}

CD59 判断一个点是否在三角形内部

/* 如果点O在三角形ABC中,
 * 那么从三角形的一点出发,
 * 逆时针走过所有边的过程中,
 * 点O始终都在走过边的左侧。
 */
public class CD59_1
{
    public static boolean solution(double x1, double y1, double x2, double y2,
                                   double x3, double y3, double x, double y)
    {
        if (crossProduct(x3 - x1, y3 - y1, x2 - x1, y2 - y1) >= 0)
        {
            double tmpx = x2;
            double tmpy = y2;
            x2 = x3;
            y2 = y3;
            x3 = tmpx;
            y3 = tmpy;
        }
        if (crossProduct(x2 - x1, y2 - y1, x - x1, y - y1) < 0)
            return false;
        if (crossProduct(x3 - x2, y3 - y2, x - x2, y - y2) < 0)
            return false;
        if (crossProduct(x1 - x3, y1 - y3, x - x3, y - y3) < 0)
            return false;
        return true;
    }

    public static double crossProduct(double x1, double y1, double x2, double y2)
    {
        return x1 * y2 - x2 * y1;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        double[][] points = new double[4][2];
        for (int i = 0; i < points.length; i++)
        {
            points[i][0] = in.nextDouble();
            points[i][1] = in.nextDouble();
        }
        System.out.println(solution(points[0][0], points[0][1], points[1][0], points[1][1],
                points[2][0], points[2][1], points[3][0], points[3][1]) ? "Yes" : "No");
    }
}

CD60 折纸问题

public class CD60_1
{
    public static PrintWriter out = new PrintWriter(System.out);

    public static void solution(int n)
    {
        process(1, n, true);
    }

    public static void process(int i, int N, boolean down)
    {
        if (i > N) return;
        process(i + 1, N, true);
        out.println(down ? "down " : "up ");
        process(i + 1, N, false);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        solution(n);
        out.flush();
    }
}

CD61 能否完美地拼成矩形

/*
 * 1. 大矩形面积 = 小矩形面积之和
 * 2. 除大矩形的四个顶点只出现 1 次之外，其他任何小矩形的顶点都必须出现偶数次
 */
public class CD61_1
{

    public static boolean solution(int[][] arr)
    {
        int ldx = Integer.MAX_VALUE, ldy = Integer.MAX_VALUE, rux = Integer.MIN_VALUE, ruy = Integer.MIN_VALUE;
        int area = 0;
        HashSet<String> set = new HashSet<>();
        for (int[] rec : arr)
        {
            if (ldx > rec[0] || (ldx == rec[0] && ldy > rec[1]))
            {
                ldx = rec[0];
                ldy = rec[1];
            }
            if (rux < rec[2] || (rux == rec[2] && ruy < rec[3]))
            {
                rux = rec[2];
                ruy = rec[3];
            }
            area += (rec[2] - rec[0]) * (rec[3] - rec[1]);
            String leftDown = rec[0] + "_" + rec[1];
            String leftUp = rec[0] + "_" + rec[3];
            String rightDown = rec[2] + "_" + rec[1];
            String rightUp = rec[2] + "_" + rec[3];
            if (!set.add(leftDown)) set.remove(leftDown);
            if (!set.add(leftUp)) set.remove(leftUp);
            if (!set.add(rightDown)) set.remove(rightDown);
            if (!set.add(rightUp)) set.remove(rightUp);
        }
        if (!set.contains(ldx + "_" + ldy) || !set.contains(ldx + "_" + ruy) || !set.contains(rux + "_" + ruy) || !set.contains(rux + "_" + ldy) || set.size() != 4)
            return false;
        else
            return area == (rux - ldx) * (ruy - ldy);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] arr = new int[n][4];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < arr[0].length; j++)
                arr[i][j] = in.nextInt();
        System.out.println(solution(arr) ? "Yes" : "No");
    }
}

CDxxx 蓄水池算法

public int rand(int max) 
{
	return (int) (Math.random() * max) + 1;
}
public int[] getKNumsRand(int k, int max) 
{
    if (max < 1 || k < 1) 
        return null;
    int[] res = new int[Math.min(k, max)];
    for (int i = 0; i != res.length; i++) 
    	res[i] = i + 1; // 前 k 个数直接进袋子
    for (int i = k + 1; i < max + 1; i++) 
    {
        if (rand(i) <= k)  // 决定 i 进不进袋子
        res[rand(k) - 1] = i; // i 随机替掉袋子中的一个
    }
    return res;
}

CD62 设计有 setAll 功能的哈希表

public class CD62_1
{
    public static class MyValue
    {
        private Integer value;
        private long time;

        public MyValue(Integer value, long time)
        {
            this.value = value;
            this.time = time;
        }

        public Integer getValue()
        {
            return this.value;
        }

        public long getTime()
        {
            return this.time;
        }
    }

    public static class MyHashMap
    {
        private HashMap<Integer, MyValue> baseMap;
        private long time;
        private MyValue setAll;

        public MyHashMap()
        {
            this.baseMap = new HashMap<Integer, MyValue>();
            this.time = 0;
            this.setAll = new MyValue(null, -1);
        }

        public boolean containsKey(Integer key)
        {
            return this.baseMap.containsKey(key);
        }

        public void put(Integer key, Integer value)
        {
            this.baseMap.put(key, new MyValue(value, this.time++));
        }

        public void setAll(Integer value)
        {
            this.setAll = new MyValue(value, this.time++);
        }

        public int get(Integer key)
        {
            if (this.containsKey(key))
            {
                if (this.baseMap.get(key).getTime() > this.setAll.getTime())
                    return this.baseMap.get(key).getValue();
                else
                    return this.setAll.getValue();
            }
            else
                return -1;
        }
    }

    public static void main(String[] args)
    {
        MyHashMap myMap = new MyHashMap();
        Scanner in = new Scanner(System.in);
        int op, num1, num2, n;
        n = in.nextInt();
        while (n-- > 0)
        {
            op = in.nextInt();
            switch (op)
            {
                case 1:
                    num1 = in.nextInt();
                    num2 = in.nextInt();
                    myMap.put(num1, num2);
                    break;
                case 2:
                    num1 = in.nextInt();
                    System.out.println(myMap.get(num1));
                    break;
                case 3:
                    num1 = in.nextInt();
                    myMap.setAll(num1);
                    break;
            }
        }
    }
}

CD63 最大的 leftMax 与 rightMax 之差的绝对值

public class CD63_1
{
    public static int solution(int[] arr)
    {
        int[] lArr = new int[arr.length];
        int[] rArr = new int[arr.length];
        lArr[0] = arr[0];
        rArr[arr.length - 1] = arr[arr.length - 1];
        for (int i = 1; i < arr.length; i++)
            lArr[i] = Math.max(lArr[i - 1], arr[i]);
        for (int i = arr.length - 2; i > -1; i--)
            rArr[i] = Math.max(rArr[i + 1], arr[i]);
        int ans = 0;
        for (int i = 0; i < arr.length - 1; i++)
            ans = Math.max(ans, Math.abs(lArr[i] - rArr[i + 1]));
        return ans;
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

public class CD63_2
{
    public static int solution(int[] arr)
    {
        int ans = Integer.MIN_VALUE;
        for (int num : arr) ans = Math.max(num, ans);
        return ans - Math.min(arr[0], arr[arr.length - 1]);
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = in.nextInt();
        System.out.println(solution(arr));
    }
}

CD64 设计 LRU 缓存结构

public class CD64_1
{
    public static class Node
    {
        public Integer value;
        public Node last;
        public Node next;

        public Node(Integer value)
        {
            this.value = value;
        }
    }

    public static class NodeDoubleLinkedList
    {
        private Node head;
        private Node tail;

        public NodeDoubleLinkedList()
        {
            this.head = null;
            this.tail = null;
        }

        public void addNode(Node newNode)
        {
            if (newNode == null)
                return;
            if (this.head == null)
            {
                this.head = newNode;
                this.tail = newNode;
            }
            else
            {
                this.tail.next = newNode;
                newNode.last = this.tail;
                this.tail = newNode;
            }
        }

        public void moveNodeToTail(Node node)
        {
            if (this.tail == node) return;
            if (this.head == node)
            {
                this.head = node.next;
                this.head.last = null;
            }
            else
            {
                node.last.next = node.next;
                node.next.last = node.last;
            }
            node.last = this.tail;
            node.next = null;
            this.tail.next = node;
            this.tail = node;
        }

        public Node removeHead()
        {
            if (this.head == null) return null;
            Node res = this.head;
            if (this.head == this.tail)
            {
                this.head = null;
                this.tail = null;
            }
            else
            {
                this.head = res.next;
                res.next = null;
                this.head.last = null;
            }
            return res;
        }
    }

    public static class MyCache
    {
        private HashMap<Integer, Node> keyNodeMap;
        private HashMap<Node, Integer> nodeKeyMap;
        private NodeDoubleLinkedList nodeList;
        private int capacity;

        public MyCache(int capacity)
        {
            if (capacity < 1)
                throw new RuntimeException("should be more than 0.");
            this.keyNodeMap = new HashMap<>();
            this.nodeKeyMap = new HashMap<>();
            this.nodeList = new NodeDoubleLinkedList();
            this.capacity = capacity;
        }

        public Integer get(Integer key)
        {
            if (this.keyNodeMap.containsKey(key))
            {
                Node res = this.keyNodeMap.get(key);
                this.nodeList.moveNodeToTail(res);
                return res.value;
            }
            return -1;
        }

        public void set(Integer key, Integer value)
        {
            if (this.keyNodeMap.containsKey(key))
            {
                Node node = this.keyNodeMap.get(key);
                node.value = value;
                this.nodeList.moveNodeToTail(node);
            }
            else
            {
                Node newNode = new Node(value);
                this.keyNodeMap.put(key, newNode);
                this.nodeKeyMap.put(newNode, key);
                this.nodeList.addNode(newNode);
                if (this.keyNodeMap.size() == this.capacity + 1)
                    this.removeMostUnusedCache();
            }
        }

        private void removeMostUnusedCache()
        {
            Node removeNode = this.nodeList.removeHead();
            Integer removeKey = this.nodeKeyMap.get(removeNode);
            this.nodeKeyMap.remove(removeNode);
            this.keyNodeMap.remove(removeKey);
        }
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int op, num1, num2, n, k;
        n = in.nextInt();
        k = in.nextInt();
        MyCache myCache = new MyCache(k);
        while (n-- > 0)
        {
            op = in.nextInt();
            switch (op)
            {
                case 1:
                    num1 = in.nextInt();
                    num2 = in.nextInt();
                    myCache.set(num1, num2);
                    break;
                case 2:
                    num1 = in.nextInt();
                    System.out.println(myCache.get(num1));
                    break;
            }
        }
    }
}

CD65 LFU 缓存结构设计

public class CD65_1
{
    public static class Node
    {
        public Integer key;
        public Integer value;
        public Integer times; // 发生get或set的次数总和
        public Node up;
        public Node down;

        public Node(int key, int value, int times)
        {
            this.key = key;
            this.value = value;
            this.times = times;
        }
    }

    public static class NodeList
    {
        public Node head;
        public Node tail;
        public NodeList last;
        public NodeList next;

        public NodeList(Node node)
        {
            head = node;
            tail = node;
        }

        public void addNodeFromHead(Node newHead)
        {
            newHead.down = head;
            head.up = newHead;
            head = newHead;
        }

        public boolean isEmpty()
        {
            return head == null;
        }

        public void deleteNode(Node node)
        {
            if (head == tail)
            {
                head = null;
                tail = null;
            }
            else
            {
                if (node == head)
                {
                    head = node.down;
                    head.up = null;
                }
                else if (node == tail)
                {
                    tail = node.up;
                    tail.down = null;
                }
                else
                {
                    node.up.down = node.down;
                    node.down.up = node.up;
                }
            }
            node.up = null;
            node.down = null;
        }
    }

    public static class LFUCache
    {
        private int capacity; // 缓存的大小限制
        private int size; // 缓存目前有多少个节点
        private HashMap<Integer, Node> records;// 表示节点(Node)在哪个桶(NodeList)里
        private HashMap<Node, NodeList> heads;
        private NodeList headList; // 整个结构中位于最左的桶

        public LFUCache(int K)
        {
            this.capacity = K;
            this.size = 0;
            this.records = new HashMap<>();
            this.heads = new HashMap<>();
            headList = null;
        }

        // removeNodeList：刚刚减少了一个节点的桶
        private boolean modifyHeadList(NodeList removeNodeList)
        {
            if (removeNodeList.isEmpty())
            {
                if (headList == removeNodeList)
                {
                    headList = removeNodeList.next;
                    if (headList != null)
                        headList.last = null;
                }
                else
                {
                    removeNodeList.last.next = removeNodeList.next;
                    if (removeNodeList.next != null)
                        removeNodeList.next.last = removeNodeList.last;
                }
                return true;
            }
            return false;
        }


        // node 这个节点的次数+1 了，这个节点原来在 oldNodeList 里。
        // 把 node 从 oldNodeList 删掉，然后放到次数+1 的桶中
        private void move(Node node, NodeList oldNodeList)
        {
            oldNodeList.deleteNode(node);
            NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;
            NodeList nextList = oldNodeList.next;
            if (nextList == null)
            {
                NodeList newList = new NodeList(node);
                if (preList != null)
                    preList.next = newList;
                newList.last = preList;
                if (headList == null)
                    headList = newList;
                heads.put(node, newList);
            }
            else
            {
                if (nextList.head.times.equals(node.times))
                {
                    nextList.addNodeFromHead(node);
                    heads.put(node, nextList);
                }
                else
                {
                    NodeList newList = new NodeList(node);
                    if (preList != null) preList.next = newList;
                    newList.last = preList;
                    newList.next = nextList;
                    nextList.last = newList;
                    if (headList == nextList)
                        headList = newList;
                    heads.put(node, newList);
                }
            }
        }

        public void set(int key, int value)
        {
            if (records.containsKey(key))
            {
                Node node = records.get(key);
                node.value = value;
                node.times++;
                NodeList curNodeList = heads.get(node);
                move(node, curNodeList);
            }
            else
            {
                if (size == capacity)
                {
                    Node node = headList.tail;
                    headList.deleteNode(node);
                    modifyHeadList(headList);
                    records.remove(node.key);
                    heads.remove(node);
                    size--;
                }
                Node node = new Node(key, value, 1);
                if (headList == null)
                    headList = new NodeList(node);
                else
                {
                    if (headList.head.times.equals(node.times))
                        headList.addNodeFromHead(node);
                    else
                    {
                        NodeList newList = new NodeList(node);
                        newList.next = headList;
                        headList.last = newList;
                        headList = newList;
                    }
                }
                records.put(key, node);
                heads.put(node, headList);
                size++;
            }
        }

        public Integer get(int key)
        {
            if (!records.containsKey(key)) return -1;
            Node node = records.get(key);
            node.times++;
            NodeList curNodeList = heads.get(node);
            move(node, curNodeList);
            return node.value;
        }
    }


    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int op, num1, num2, n, k;
        n = in.nextInt();
        k = in.nextInt();
        LFUCache lfuCache = new LFUCache(k);
        while (n-- > 0)
        {
            op = in.nextInt();
            switch (op)
            {
                case 1:
                    num1 = in.nextInt();
                    num2 = in.nextInt();
                    lfuCache.set(num1, num2);
                    break;
                case 2:
                    num1 = in.nextInt();
                    System.out.println(lfuCache.get(num1));
                    break;
            }
        }
    }
}

CDxxx 设计 RandomPool 结构

    public class Pool<K>
    {
        private HashMap<K, Integer> keyIndexMap;
        private HashMap<Integer, K> indexKeyMap;
        private int size;

        public Pool()
        {
            this.keyIndexMap = new HashMap<K, Integer>();
            this.indexKeyMap = new HashMap<Integer, K>();
            this.size = 0;
        }

        public void insert(K key)
        {
            if (!this.keyIndexMap.containsKey(key))
            {
                this.keyIndexMap.put(key, this.size);
                this.indexKeyMap.put(this.size++, key);
            }
        }

        public void delete(K key)
        {
            if (this.keyIndexMap.containsKey(key))
            {
                int deleteIndex = this.keyIndexMap.get(key);
                int lastIndex = --this.size;
                K lastKey = this.indexKeyMap.get(lastIndex);
                this.keyIndexMap.put(lastKey, deleteIndex);
                this.indexKeyMap.put(deleteIndex, lastKey);
                this.keyIndexMap.remove(key);
                this.indexKeyMap.remove(lastIndex);
            }
        }

        public K getRandom()
        {
            if (this.size == 0) return null;
            int randomIndex = (int) (Math.random() * this.size);
            return this.indexKeyMap.get(randomIndex);
        }
    }