leetcode.字典序问题汇总

leetcode386

题目 具体实现

class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> lexicalOrder(int n) { for(int i = 1;i < 10;i++){ dfs(n,i); } return res; } public void dfs(int max, int cur){ if(cur > max){ return; } res.add(cur); for(int i = 0;i < 10;i++){ dfs(max, cur*10+i); } } }

leetcode440

题目 具体实现

class Solution { public int findKthNumber(int n, int k) { int prefix = 1; int count = 1; while(count < k){ int tmp = getNum(n,prefix); if(count + tmp > k){ prefix *= 10; count++; }else{ prefix += 1; count += tmp; } } return prefix; } public int getNum(int max, long prefix){ long next = prefix + 1; int count = 0; while(prefix <= max){ count += Math.min(max+1,next) - prefix; prefix *= 10; next *= 10; } return count; } }

leetcode1061

题目 思想：并查集

具体实现

class Solution { public String smallestEquivalentString(String A, String B, String S) { UF uf = new UF(); int lenA = A.length(); for (int i = 0; i < lenA; i++) { uf.union(A.charAt(i)- 'a', B.charAt(i)- 'a'); } StringBuilder res = new StringBuilder(); for (int i = 0; i < S.length(); i++) { res.append((char)(uf.find(S.charAt(i) - 'a')+'a')); } return res.toString(); } } class UF { int[] parents; public UF() { parents = new int[26]; for (int i = 0; i < 26; i++) { parents[i] = i; } } public void union(int a, int b) { // System.out.println(a); int aP = find(a); int bP = find(b); System.out.println(aP); if (aP < bP) { parents[bP] = aP; } else { parents[aP] = bP; } } public int find(int x) { // System.out.println(x); while (parents[x] != x) { x = parents[x]; } // System.out.println(parents[x]); return parents[x]; } }

leetcode1415

题目 具体实现

class Solution { List<String> res = new ArrayList<>(); char arrArray[] = {'a','b','c'}; public String getHappyString(int n, int k) { if(k > 3 * (1 << (n-1))){ return ""; } dfs(n,""); return res.get(k-1); } public void dfs(int n, String path){ if(n == 0){ res.add(path); return; } for(int i = 0;i < arrArray.length;i++){ if(path.length() >= 1 && arrArray[i] == path.charAt(path.length()-1)){ continue; } dfs(n-1, path+arrArray[i]); } } }

代码来源：leetcode题解