​LeetCode刷题实战351:安卓系统手势解锁

共 3396字,需浏览 7分钟

 ·

2021-08-20 00:05

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 安卓系统手势解锁,我们先来看题面:
https://leetcode-cn.com/problems/android-unlock-patterns/

Given an Android 3x3 key lock screen and two integers m and n, where 1 ≤ m ≤ n ≤ 9, count the total number of unlock patterns of the Android lock screen, which consist of minimum of m keys and maximum n keys.


我们都知道安卓有个手势解锁的界面,是一个 3 x 3 的点所绘制出来的网格。
给你两个整数,分别为 m 和 n,其中 1 ≤ m ≤ n ≤ 9,那么请你统计一下有多少种解锁手势,是至少需要经过 m 个点,但是最多经过不超过 n 个点的。

先来了解下什么是一个有效的安卓解锁手势:
每一个解锁手势必须至少经过 m 个点、最多经过 n 个点。
解锁手势里不能设置经过重复的点。
假如手势中有两个点是顺序经过的,那么这两个点的手势轨迹之间是绝对不能跨过任何未被经过的点。
经过点的顺序不同则表示为不同的解锁手势。

示例

解题

https://blog.csdn.net/qq_21201267/article/details/107738912

参考官方题解,判断是否有效,比较难写

class Solution {
  vector<bool> visited;
public:
    int numberOfPatterns(int m, int n) {
      int ans = 0;
      for(int len = m; len <= n; ++len)
      {
        visited = vector<bool> (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((idx+last)%2 == 1) return true;//相邻的两个数
      int mid = (idx+last)/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;
    }
};

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-340题汇总,希望对你有点帮助!
LeetCode刷题实战341:扁平化嵌套列表迭代器
LeetCode刷题实战342:4的幂
LeetCode刷题实战343:整数拆分
LeetCode刷题实战344:反转字符串
LeetCode刷题实战345:反转字符串中的元音字母
LeetCode刷题实战346:数据流中的移动平均值
LeetCode刷题实战347:前 K 个高频元素
LeetCode刷题实战348:设计井字棋
LeetCode刷题实战349:两个数组的交集
LeetCode刷题实战350:两个数组的交集 II

浏览 29
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报