锁屏图案的种类数目

锁屏模式

题目描述

现有一个 3x3 规格的 Android 智能手机锁屏程序和两个正整数 m 和 n ，请计算出使用最少m 个键和最多 n个键可以解锁该屏幕的所有有效模式总数。 其中有效模式是指： 1、每个模式必须连接至少m个键和最多n个键； 2、所有的键都必须是不同的； 3、如果在模式中连接两个连续键的行通过任何其他键，则其他键必须在模式中选择，不允许跳过非选择键（如图）； 4、顺序相关，单键有效（这里可能跟部分手机不同）。

输入：m,n 代表允许解锁的最少m个键和最多n个键 输出： 满足m和n个键数的所有有效模式的总数

解题思路

仍然是采用回溯的思路，不过这一题的选择列表比较多，除了东南西北、东北东南西南西北八个方向距离为1的点外，还有距离为2的点，还有距离为根号3的点。要以矩阵中的每一个点为起点开始dfs，因为即使组成模式的点相同但起点不同也视为不同的模式。值得注意的是，在访问距离为2的点时要先检查他们的中点是否已经访问过。

public class LockMode {
    private boolean[][] visited = new boolean[3][3];
    private int[][] dirs1 = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1}};
    private int[][] dirs2 = new int[][]{{0, 2}, {0, -2}, {2, 0}, {-2, 0}, {2, -2}, {2, 2}, {-2, 2}, {-2, -2}};
    private int[][] dirs3 = new int[][]{{2, 1}, {2, -1}, {-2, 1}, {-2, -1}, {1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
    private int count = 0;
    int m, n;

    public int solution (int m, int n) {
        this.m = m;
        this.n = n;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                dfs(i, j, 1);
            }
        }
        return count;
    }

    private void dfs(int i, int j, int step) {
        if (m <= step && step <= n) count++;
        if (step == n) return;

        visited[i][j] = true;
        for (int[] dir : dirs1) {
            int x = i + dir[0], y = j + dir[1];
            if (0 <= x && x < 3 && 0 <= y && y < 3 && !visited[x][y]) {
                dfs(x, y, step + 1);
            }
        }

        for (int[] dir : dirs2) {
            int x = i + dir[0], y = j + dir[1];
            if (0 <= x && x < 3 && 0 <= y && y < 3 && !visited[x][y]) {
                int midX = i + dir[0] / 2, midY = j + dir[1] / 2;
                if (visited[midX][midY])
                    dfs(x, y, step + 1);
            }
        }

        for (int[] dir : dirs3) {
            int x = i + dir[0], y = j + dir[1];
            if (0 <= x && x < 3 && 0 <= y && y < 3 && !visited[x][y]) {
                dfs(x, y, step + 1);
            }
        }
        visited[i][j] = false;
    }
}

数位之积

题目描述

现给定任意正整数 n，请寻找并输出最小的正整数 m（m>9），使得 m 的各位（个位、十位、百位 ... ...）之乘积等于n，若不存在则输出 -1。

示例

输入：100
输出：455

解题思路

贪心地对输入的n进行分解因数，每次都尝试分解为[2,9]区间内最大的因数，把因数压入栈中，再对剩余的部分递归进行该操作，递归终止的条件是n小于10。最后将栈中的数依高位到低位放到结果中。如果在处理过程中发现n是大于10的质数则通过标记表示不存在对应的数。

public class MultiplyDigits {
    private Deque<Integer> stack = new LinkedList<>();
    private boolean canDo = true;

    public int solution (int n) {
        cal(n);
        if (canDo) {
            int result = 0;
            while (!stack.isEmpty())
                result = result * 10 + stack.pop();
            return result;
        } else {
            return -1;
        }
    }

    private void cal(int n) {
        if (n < 10) {
            stack.push(n);
            return;
        }
        for (int i = 9; i >= 2; i--) {
            if (n % i == 0) {
                stack.push(i);
                cal(n / i);
                return;
            }
        }
        canDo = false;
    }
}

手机产量

题目描述

在vivo产线上，每位职工随着对手机加工流程认识的熟悉和经验的增加，日产量也会不断攀升。 假设第一天量产1台，接下来2天(即第二、三天)每天量产2件，接下来3天(即第四、五、六天)每天量产3件 ... ... 以此类推，请编程计算出第n天总共可以量产的手机数量。

解题思路

这题没有什么特殊的地方，使用等差数列求和公式找到n天时当天能生产几部手机，再依次把前面生产的手机相加就可以了。

public class Solution {
    public int solution (int n) {
        int days = 1, sum = days * (days + 1);
        while (sum < 2 * n) {
            days++;
            sum = days * (days + 1);
        }
        int product = 0, i = 1;
        while (i < days) {
            product += i * i;
            i++;
        }
        i--;
        int remain = n - ((1 + i) * i / 2);
        product += days * remain;
        return product;
    }
}