LeetCode 246&247&248题解：Strobogrammatic Number II&III（JAVA版本）-白红宇

LeetCode 246&247&248题解：Strobogrammatic Number II&III（JAVA版本）

阅读量：4040 次

发布时间：2019-05-24

本文共 4817 字，大约阅读时间需要 16 分钟。

LeetCode246&247&248题解：Strobogrammatic Number I&II&III （JAVA版本）

LeetCode 246

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 represented as a string.

Example 1:

Input: "69"

Output: true

Example 2:

Input: "88"

Output: true

Example 3:

Input: "962"

Output: false

算法设计

package com.bean.algorithm.basic;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;public class StrobogrammaticNumber {	public boolean isStrobogrammatic(String s) {		// 69, 88, 00, 11, 6969, 698869, 69869, 6908069, 886988		Map
   
     map = new HashMap<>();		map.put('6', '9');		map.put('9', '6');		map.put('0', '0');		map.put('1', '1');		map.put('8', '8');		int i = 0, j = s.length() - 1;		while (i <= j) {			if (!map.containsKey(s.charAt(i)))				return false;			if (map.get(s.charAt(i++)) != s.charAt(j--))				return false;		}		return true;	}	public static void main(String[] args) {		// TODO Auto-generated method stub		StrobogrammaticNumber strobogrammatic = new StrobogrammaticNumber();		boolean flag = strobogrammatic.isStrobogrammatic("88");		System.out.println("FLAG is: " + flag);	}}

程序运行结果：

FLAG is: true

LeetCode 247

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 = 2

Output: ["11","69","88","96"]

算法设计

package com.bean.algorithm.basic;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;public class StrobogrammaticNumberII {	public List
   
     findStrobogrammatic(int n) {		List
    
      res = new ArrayList<>();		if (n == 0)			return res;		if (n == 1)			return Arrays.asList("0", "1", "8");		Map
     
       map = new HashMap
      
       ();		map.put('0', '0');		map.put('1', '1');		map.put('6', '9');		map.put('8', '8');		map.put('9', '6');		dfs(map, new char[n], 0, n, res);		return res;	}	private void dfs(Map
       
         map, char[] buffer, int index, int n, List
        
          res) { // when index just passed the mid point, (n+1)/2 works for both odd and even if (index == (n + 1) / 2) { res.add(String.valueOf(buffer)); return; } for (char ch : map.keySet()) { if (index == 0 && n > 1 && ch == '0') continue; if (index == n / 2 && (ch == '6' || ch == '9')) continue; buffer[index] = ch; buffer[n - 1 - index] = map.get(ch); dfs(map, buffer, index + 1, n, res); } } public static void main(String[] args) { // TODO Auto-generated method stub StrobogrammaticNumberII strobogrammatic=new StrobogrammaticNumberII(); List
         
           list=strobogrammatic.findStrobogrammatic(2); System.out.println(list); }}

程序输出结果

[11, 69, 88, 96]

LeetCode 248

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

Input: low = "50", high = "100"

Output: 3

Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note:

Because the range might be a large number, the low and high numbers are represented as string.

算法设计

package com.bean.algorithm.basic;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;public class StrobogrammaticNumberIII {	int count = 0;	public int strobogrammaticInRange(String low, String high) {		Map
   
     map = new HashMap<>();		map.put('0', '0');		map.put('1', '1');		map.put('6', '9');		map.put('8', '8');		map.put('9', '6');		List
    
      res = new ArrayList<>();		for (int len = low.length(); len <= high.length(); len++) {			dfs(map, low, high, new char[len], 0, len - 1, res);		}		System.out.println(res);		return count;	}	private void dfs(Map
     
       map, String low, String high, char[] buffer, int left, int right,			List
      
        res) {		if (left > right) {			String num = new String(buffer);			if ((num.length() == low.length() && num.compareTo(low) < 0)					|| (num.length() == high.length() && num.compareTo(high) > 0)) {				return;			}			count++;			res.add(num);			return;		}		for (char ch : map.keySet()) {			if (buffer.length != 1 && left == 0 && ch == '0')				continue;			if (left == right && ch != map.get(ch))				continue;			buffer[left] = ch;			buffer[right] = map.get(ch);			dfs(map, low, high, buffer, left + 1, right - 1, res);		}	}	public static void main(String[] args) {		// TODO Auto-generated method stub		StrobogrammaticNumberIII strobogrammatic = new StrobogrammaticNumberIII();		int ANSWER = strobogrammatic.strobogrammaticInRange("50", "100");		System.out.println(ANSWER);	}}

程序运行结果：

[69, 88, 96]

转载地址：http://ditdi.baihongyu.com/

你可能感兴趣的文章