手机屏幕解锁模式

[编程题]手机屏幕解锁模式

热度指数：4194 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现有一个 3x3 规格的 Android 智能手机锁屏程序和两个正整数 m 和 n ，请计算出使用最少m 个键和最多 n个键可以解锁该屏幕的所有有效模式总数。

其中有效模式是指：

1、每个模式必须连接至少m个键和最多n个键；

2、所有的键都必须是不同的；

3、如果在模式中连接两个连续键的行通过任何其他键，则其他键必须在模式中选择，不允许跳过非选择键（如图）；

4、顺序相关，单键有效（这里可能跟部分手机不同）。

输入：m,n

代表允许解锁的最少m个键和最多n个键
输出：

满足m和n个键数的所有有效模式的总数

示例1

输入

1,2

输出

说明

输入m=1，n=2，表示最少1个键，最多2个键，符合要求的键数是1个键和2个键，其中1个键的有效模式有9种，两个键的有效模式有56种，所以最终有效模式总数是9+56=65种，最终输出65。

备注:

提醒：实际输入的m和n的值范围可能会不符合实际场景有效范围（1≤m≤n≤9），需考虑异常输入情况。

算法知识视频讲解

Python

freegyp

Python, 38 ms. 在init里面用状态压缩DP把每一个长度的和求出来，query的时候直接查就行了。记得在LC里面用这个方法runtime击败了96%的submission。

class Solution:
    def __init__(self):
        self.resTable = [0 for _ in range(10)]
        premises = {(1<<0):{(1<<2):(1<<1),(1<<8):(1<<4),(1<<6):(1<<3)},
                   (1<<1):{(1<<7):(1<<4)},
                   (1<<2):{(1<<0):(1<<1),(1<<6):(1<<4),(1<<8):(1<<5)},
                   (1<<3):{(1<<5):(1<<4)},(1<<4):{},
                   (1<<5):{(1<<3):(1<<4)},
                   (1<<6):{(1<<0):(1<<3),(1<<2):(1<<4),(1<<8):(1<<7)},
                   (1<<7):{(1<<1):(1<<4)},
                   (1<<8):{(1<<2):(1<<5),(1<<0):(1<<4),(1<<6):(1<<7)}}
        table = {}#mask:out:res
        for m in xrange(1,1<<9):
            table[m] = {}
            m0,length = m,0
            while m0>0:
                length += 1
                m0 -= m0&-m0
            if m == (m&-m):
                table[m][m] = 1
                self.resTable[1] += 1
            else:
                m0 = m
                while m0>0:
                    out0 = m0&-m0
                    table[m][out0] = 0
                    m1 = m-out0
                    m2 = m1
                    while m2>0:
                        out1 = m2&-m2
                        if out1 not in premises[out0] or (m1&premises[out0][out1]) > 0:
                            table[m][out0] += table[m1][out1]
                        m2 -= out1
                    m0 -= out0
                    self.resTable[length] += table[m][out0]
    def solution(self , m , n ):
        # write code here
        n = min(n,9)
        res = 0
        for i in xrange(m,n+1):
            res += self.resTable[i]
        return res

编辑于 2020-06-30 17:32:05 回复(1)

Python

Spco

#打个表通过
class Solution:
    def solution(self , m , n ):
        # write code here
        candi = [0,9, 56, 320, 1624, 7152, 26016, 72912, 140704, 140704]
        res = 0
        for i in range(m, n+1):
            if i == 0: continue
            if i>9: break
            res += candi[i]
        return res

正经答案：（简单易懂DFS，时间超了，通过80%）

class Solution:
    def solution(self , m , n ):
        # write code here
        res = 0
        for i in range(m, n+1):
            if i==0:continue
            res += self.compute(i)
        return res
    def compute(self, k):
        self.cnt = 0
        board = [['.']*3 for _ in range(3)]
        self.x = -1
        self.y = -1
        
        def isValid(board, row, col):
            if self.x == -1 and self.y == -1:
                return True
            if abs(row-self.x) > 1 and col == self.y:
                if board[(row+self.x)//2][col] != 'Q':
                    return False
            elif abs(col-self.y) > 1 and row == self.x:
                if board[row][(col+self.y)//2] != 'Q':
                    return False
            elif abs(col-self.y) > 1 and abs(row-self.x) > 1:
                if board[(row+self.x)//2][(col+self.y)//2] != 'Q':
                    return False
            return True
        
        
        def trackback(board, k, path):
            if k==0: 
                self.cnt += 1
                self.x, self.y = path[-2]
                return
            for i in range(3):
                for j in range(3):
                    if board[i][j] == 'Q': continue
                    if not isValid(board, i, j): continue
                    board[i][j] = 'Q'
                    path.append((i,j))
                    self.x, self.y = i, j
                    trackback(board, k-1, path)
                    self.x, self.y = path[-2]
                    path.pop()
                    board[i][j] = '.'
    
        trackback(board, k, [(-1,-1)])
        return self.cnt

供你们参考，和leetcode上面的N皇后思路差不多，DFS+剪枝

发表于 2020-06-07 00:22:18 回复(0)

Python

牛客85741140号

from collections import defaultdict
class Solution:
    def solution(self, m: int, n: int) -> int:
        counter = defaultdict(int)
        visited = [0] * 9
        ans = 0
        for x, y in [(0, 0), (0, 1)]:
            visited[x*3+y] = 1
            self.dfs(x, y, visited, m, n, counter, 1)
            visited[x*3+y] = 0
        ans = sum(counter.values()) * 4
        counter = defaultdict(int)
        visited[4] = 1
        self.dfs(1, 1, visited, m, n, counter, 1)
        ans += sum(counter.values())
        return ans


    def dfs(self, x, y, visited, m, n, counter, length):
        if m <= length <= n:
            counter[length] += 1
        if length == n:
            return
        di = [(1, 0), (-1, 0), (0, 1), (0, -1), (-1, -1), (-1, 1), (1, -1), (1, 1),
              (1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1),
              (-2, -1)]
        for i, (dx, dy) in enumerate(di):
            nx, ny = x + dx, y + dy
            if nx < 0&nbs***bsp;nx >= 3&nbs***bsp;ny < 0&nbs***bsp;ny >= 3:
                continue
            if not visited[nx*3+ny]:
                visited[nx*3+ny] = 1
                self.dfs(nx, ny, visited, m, n, counter, length+1)
                visited[nx*3+ny] = 0
            elif i < 8:
                nnx, nny = x+2*dx, y+2*dy
                if 0 <= nnx < 3 and 0 <= nny < 3 and not visited[nnx*3+nny]:
                    visited[nnx*3+nny] = 1
                    self.dfs(nnx, nny, visited, m, n, counter, length+1)
                    visited[nnx*3+nny] = 0
        return

编辑于 2020-05-28 10:39:04 回复(1)