247. Strobogrammatic Number II

cnTomato 发布于2019-08-14 17:29 / 3007人阅读

摘要：题目链接这题和都可以做，一种思路就是从中间开始往两边延伸，每次有种可能性和，其中开头处不能是。可以加或者用优化。

247. Strobogrammatic Number II

题目链接：https://leetcode.com/problems...

这题recursion和iteration都可以做，一种思路就是从中间开始往两边延伸，每次c[i-k], c[i+k]有5种可能性: (6, 9), (9, 6), (1, 1), (8, 8)和(0, 0)，其中开头处不能是0。可以加memo或者用dp table优化。

public class Solution {
    public List findStrobogrammatic(int n) {
        List dp = new ArrayList();
        if(n % 2 == 1) {
            dp.add("0"); dp.add("1"); dp.add("8");
        }
        else dp.add("");
        
        if(n <= 1) return dp;
        
        // get permutation of (0, n/2)
        String[] numbers = new String[] {"0", "1", "6", "8", "9"};
        String[] reverse = new String[] {"0", "1", "9", "8", "6"};
        for(int i = n / 2 - 1; i >= 0; i--) {
            List temp = new ArrayList();
            for(String s : dp) {
                if(i != 0) temp.add(numbers[0] + s + reverse[0]);
                for(int j = 1; j < numbers.length; j++) {
                    temp.add(numbers[j] + s + reverse[j]);
                }
            }
            dp = temp;
        }
        
        return dp;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66665.html

246. 247. 248. Strobogrammatic Number I II II

摘要：题目解答题目解答先考虑最底层的两种情况，当和当的时候，就是最中间的数为空还是存在唯一的一个数。然后我们在这个基础上，用循环两个数两个数地一起向外扩张。扩张后的结果存在里，作为再服务于上一层的扩张，得到最终结果。 246.Strobogrammatic NumberI题目：A strobogrammatic number is a number that looks the same w...

Fundebug 2019-08-14 16:31 评论0 收藏0
[LeetCode] 247. Strobogrammatic Number II

Problem A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. Example: Input: n = 2Output...

GHOST_349178 2019-08-16 13:50 评论0 收藏0
Strobogrammatic Number 系列 LC解题记录（未完成）

摘要：所以这题先建立一个对应的，然后扫一遍字符串就可以了。复杂度分析第二题题目内容解决思路一看关键词，通常都是，深搜一遍，挖地三尺，雁过拔毛。复杂度分析第三题题目内容解决思路复杂度分析该系列共三道题，Company Tag只有一个Google，那就必须要做了。第一题题目内容 A strobogrammatic number is a number that looks the same ...

王晗 2019-08-14 14:23 评论0 收藏0
[Leetcode] Strobogrammatic Number 对称数

摘要：比如，先判断和是有映射的，然后和自己又是映射，所以是对称数。这样每次从中间插入两个对称的字符，之前插入的就被挤到两边去了。只插入一个字符时不能插入和插入字符和它的对应字符 Strobogrammatic Number I A strobogrammatic number is a number that looks the same when rotated 180 degrees ...

wendux 2019-08-14 12:34 评论0 收藏0
[LeetCode] 246. Strobogrammatic Number

Problem A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Write a function to determine if a number is strobogrammatic. The number is represent...

whatsns 2019-08-19 11:14 评论0 收藏0