参考消息官方网站阅读,学生免费服务器,科技有限公司简介,品牌vi形象设计公司文章目录1. 题目2. 解题1. 题目
我们都知道安卓有个手势解锁的界面#xff0c;是一个 3 x 3 的点所绘制出来的网格。
给你两个整数#xff0c;分别为 m 和 n#xff0c;其中 1 ≤ m ≤ n ≤ 9#xff0c; 那么请你统计一下有多少种解锁手势#xff0c;是至少需要经过…
文章目录1. 题目2. 解题1. 题目
我们都知道安卓有个手势解锁的界面是一个 3 x 3 的点所绘制出来的网格。
给你两个整数分别为 m 和 n其中 1 ≤ m ≤ n ≤ 9 那么请你统计一下有多少种解锁手势是至少需要经过 m 个点但是最多经过不超过 n 个点的。
先来了解下什么是一个有效的安卓解锁手势:
每一个解锁手势必须至少经过 m 个点、最多经过 n 个点。解锁手势里不能设置经过重复的点。假如手势中有两个点是顺序经过的那么这两个点的手势轨迹之间是绝对不能跨过任何未被经过的点。经过点的顺序不同则表示为不同的解锁手势。 解释:
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |无效手势4 - 1 - 3 - 6 连接点 1 和点 3 时经过了未被连接过的 2 号点。
无效手势4 - 1 - 9 - 2 连接点 1 和点 9 时经过了未被连接过的 5 号点。
有效手势2 - 4 - 1 - 3 - 6 连接点 1 和点 3 是有效的因为虽然它经过了点 2 但是点 2 在该手势中之前已经被连过了。
有效手势6 - 5 - 4 - 1 - 9 - 2 连接点 1 和点 9 是有效的因为虽然它经过了按键 5 但是点 5 在该手势中之前已经被连过了。
示例:
输入: m 1n 1
输出: 9来源力扣LeetCode 链接https://leetcode-cn.com/problems/android-unlock-patterns 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考官方题解判断是否有效比较难写
class Solution {vectorbool visited;
public:int numberOfPatterns(int m, int n) {int ans 0;for(int len m; len n; len){visited vectorbool (9, false);ans cal(-1,len);}return ans;}bool isok(int idx, int last){if(visited[idx]) return false;if(last -1) return true;//第一个数if((idxlast)%2 1) return true;//相邻的两个数int mid (idxlast)/2;if(mid 4)//对角线的两个端点要连起来return visited[mid];//看中点是否占用if(idx%3 ! last%3 idx/3 ! last/3)return true;//不是 同行或者 同列 的两个端点return visited[mid];//检查0,6中间是3有没有被占用}int cal(int last, int len){if(len 0) return 1;int sum 0;for(int i 0; i 9; i){if(isok(i, last)){visited[i] true;sum cal(i, len-1);visited[i] false;}}return sum;}
};296 ms 6.1 MB
1,9, 389497 5,9, 387488, 有38万多种手势。 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
