GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — LeetCode_algorithm/NumDecodings.java at master · rpj911/LeetCode_algorithm Expand file tree/ Copy pathNumDecodings.javaMore file actions 56 lines (44 loc) · 1.44 KB / Copy pathNumDecodings.javaFile metadata and controls56 lines (44 loc) · 1.44 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 package Algorithms; public class NumDecodings { public static void main(String[] strs) { int num = numDecodings("10"); } public static int numDecodings(String s) { // state: f[i]: from 0 to i , the number of ways to decode. // func: f[i] = f[i - 1] + 1 + f[i - 2] * if (s.charAt(i - 1) and s.charAt(i) is a char) // that is : s.charAt(i - 1) < = 2 // init: f[0] = 1 // solution: f[len - 1] if (s == null || s.length() == 0) { return 0; } int len = s.length(); // in here, 0 means int[] num = new int[len]; if ((int)s.charAt(0) - (int)'0' <= 0) { return 0; } else { num[0] = 1; } for (int i = 1; i < len; i++) { num[i] = 0; int curr = (int)s.charAt(i) - (int)'0'; int pre = (int)s.charAt(i - 1) - (int)'0'; if (curr >= 1) { num[i] += num[i - 1]; } int sum = pre * 10 + curr; if (sum >= 10 && sum <= 26) { if (i >= 2) { num[i] += num[i - 2]; } else { num[i] += 1; } } if (num[i] == 0) { return 0; } } return num[len - 1]; } } |
| You are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |