- 浏览: 130542 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
For example:
Given s = "aabb", return ["abba", "baab"].
Given s = "abc", return [].
[分析]
先按照Palindrome Permutation 的方法判断输入字符串 s 能否排列成为一个回文串。通过检查开始构造过程,有两个思路:
思路1:按照leetcode的提示,我们仅需构造回文的前半部分。先利用前面判断过程中的map获得回文前半部分所有的字符,相同字符排列在一起,然后按照Permutation II一题的思路获得前半部分所有的排列情况,最后组合回文的前后部分加入结果集。
思路2:从中间往两端递归构造回文串。
[ref]
https://leetcode.com/discuss/53638/0ms-easy-c-solution
https://leetcode.com/discuss/53613/my-accepted-java-solution
For example:
Given s = "aabb", return ["abba", "baab"].
Given s = "abc", return [].
[分析]
先按照Palindrome Permutation 的方法判断输入字符串 s 能否排列成为一个回文串。通过检查开始构造过程,有两个思路:
思路1:按照leetcode的提示,我们仅需构造回文的前半部分。先利用前面判断过程中的map获得回文前半部分所有的字符,相同字符排列在一起,然后按照Permutation II一题的思路获得前半部分所有的排列情况,最后组合回文的前后部分加入结果集。
思路2:从中间往两端递归构造回文串。
[ref]
https://leetcode.com/discuss/53638/0ms-easy-c-solution
https://leetcode.com/discuss/53613/my-accepted-java-solution
public class Solution { // Method 1 public List<String> generatePalindromes(String s) { List<String> ret = new ArrayList<String>(); if (s == null || s.length() == 0) return ret; if (s.length() == 1) {ret.add(s); return ret;} int[] map = new int[256]; for (int i = 0; i < s.length(); i++) map[s.charAt(i)]++; int oddCount = 0; int oddIdx = -1; StringBuilder half = new StringBuilder(); for (int i = 0; i < 256; i++) { if ((map[i] & 1) == 1) { oddIdx = i; oddCount++; if (oddCount == 2) return ret; } int halfCount = map[i] / 2; for (int j = 0; j < halfCount; j++) half.append((char)i); } List<String> halfPermutation = new ArrayList<String>(); getPermutation(half.toString().toCharArray(), new boolean[half.length()], new StringBuilder(), halfPermutation); for (String curr : halfPermutation) { StringBuilder curr2 = new StringBuilder(curr); if (oddIdx != -1) curr += (char)oddIdx; ret.add(curr + curr2.reverse().toString()); } return ret; } public void getPermutation(char[] chars, boolean[] used, StringBuilder item, List<String> result) { if (item.length() == chars.length) { result.add(item.toString()); } else { for (int i = 0; i < chars.length; i++) { if (used[i] || (i > 0 && chars[i] == chars[i - 1] && !used[i - 1])) continue; item.append(chars[i]); used[i] = true; getPermutation(chars, used, item, result); used[i] = false; item.deleteCharAt(item.length() - 1); } } } // Method 2 public List<String> generatePalindromes2(String s) { List<String> ret = new ArrayList<String>(); int[] map = new int[256]; for (int i = 0; i < s.length(); i++) map[s.charAt(i)]++; int oddCount = 0; int oddIdx = -1; for (int i = 0; i < 256; i++) { if ((map[i] & 1) == 1) { oddIdx = i; oddCount++; if (oddCount == 2) return ret; } } String curr = ""; if (oddIdx != -1) { curr += (char)oddIdx; map[oddIdx]--; } dfs(curr, map, s.length(), ret); return ret; } public void dfs(String curr, int[] map, int n, List<String> ret) { if (curr.length() < n) { for (int i = 0; i < map.length; i++) { if (map[i] > 0) { curr = (char)i + curr + (char)i; map[i] -= 2; dfs(curr, map, n, ret); curr = curr.substring(1, curr.length() - 1); map[i] += 2; } } } else { ret.add(curr); } } }
发表评论
-
Leetcode - Factor Combination
2015-08-28 09:53 821Numbers can be regarded as prod ... -
Leetcode - Generate Parentheses
2015-08-08 17:01 485[分析] 第一个思路(错误的~):假设递归函数返回 n - ... -
Leetcode - Word Search II
2015-08-03 21:25 935iven a 2D board and a list of w ... -
Leetcode - Word Search
2015-08-03 21:03 479Given a 2D board and a word, fi ... -
Leetcode - Subset
2015-08-02 12:06 915[分析] 三种思路 思路1:每层递归新加一个元素,第一层递归, ... -
Leetcode - Subset II
2015-08-02 12:13 922[分析] 延续Subset三种思路,关键是添加去重处理 思路 ... -
Leetcode - Gray Code
2015-08-01 17:26 545原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation Sequence
2015-08-01 17:19 481原题链接:https://leetcode.com/probl ... -
Leetcode - Permutation II
2015-08-01 10:49 568原题链接:https://leetcode.com/probl ... -
Leetcode - Combination
2015-08-01 08:36 457[分析] 从 n 个数中取 k 个数,第一个数有 n 种取法… ... -
Leetcode - Combination Sum III
2015-07-31 22:04 499[分析] 思路就是枚举k个数所有可能的组合并判断是否符合条件。 ... -
Leetcode - Combination Sum II
2015-07-31 21:06 576[分析] 输入数组中的每个元素至多使用一次,相较于Combin ... -
Leetcode - Combination Sum
2015-07-31 20:21 554Given a set of candidate number ... -
Leetcode - Sudoku Solver
2015-07-31 09:14 434[分析] 做Valid Sudoku时表示3*3区块的下标想得 ... -
Leetcode - N Queues II
2015-07-30 20:52 377[分析] 做完N皇后第一题,这个就so easy~ pu ... -
Leetcode - N-Queens
2015-07-30 20:38 406[分析] N皇后摆放规则:两个皇后不能共存于同一行、同一列以及 ... -
Leetcode - Word Ladder II
2015-06-26 09:19 500Given two words (start and end) ... -
Leetcode - Combination Sum III
2015-06-10 10:09 512Find all possible combinati ... -
Leetcode - Palindrome Partition
2015-05-21 09:56 747Given a string s, partition s s ... -
Leetcode - WordBreak III
2015-04-16 08:30 424Given a string s and a dictio ...
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode 答案解析 golang解答
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-helper-1.7.1
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-tag-dynamic programming
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。