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

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<Character, Character> 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<String> findStrobogrammatic(int n) {
		List<String> res = new ArrayList<>();
		if (n == 0)
			return res;
		if (n == 1)
			return Arrays.asList("0", "1", "8");
		Map<Character, Character> map = new HashMap<Character, Character>();
		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<Character, Character> map, char[] buffer, int index, int n, List<String> 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<String> 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<Character, Character> map = new HashMap<>();
		map.put('0', '0');
		map.put('1', '1');
		map.put('6', '9');
		map.put('8', '8');
		map.put('9', '6');
		List<String> 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<Character, Character> map, String low, String high, char[] buffer, int left, int right,
			List<String> 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]
3