409 Longest Palindrome[Easy]
思路: 不能直接用一个 hash 数组来做记录奇偶数, 因为会出现多个总数为奇数的字符和一个总数为奇数的长字符.
还要进行判断建一个 HashSet 需要挑出最长的奇数字符串 没有将奇数字符串中的成对出现的偶数部分加入到最后的结果中.
- class Solution {
- public int longestPalindrome(String s) {
- if (s == null || s.length() == 0) {
- return 0;
- }
- HashSet<Character> set = new HashSet<>();
- int count = 0;
- for (int i = 0; i <s.length(); i++) {
- if (set.contains(s.charAt(i))) {
- set.remove(s.charAt(i));
- count++;
- } else {
- set.add(s.charAt(i));
- }
- }
- if (set.isEmpty()) {
- return count * 2;
- }
- return count * 2 + 1;
- }
- }
49. Group Anagrams[Medium]
思路: 用一个 hashtable 来存 数组来存一个集合? 如何能找到不同字母组合的一致性? 只需要包含相同的字母即可, 顺序没有关系
需要的是一个 flag 来做记录 两个选择: 1. 类似 a1b2c3 的结构 2. 直接排序得到有序结果
- class Solution {
- public List<List<String>> groupAnagrams(String[] strs) {
- if (strs == null || strs.length == 0) {
- return new ArrayList<>();
- }
- List<List<String>> res = new ArrayList<>();
- Map<String, List<String>> map = new HashMap<>();
- int[] count = new int[26];
- for (String str : strs) {
- Arrays.fill(count, 0);
- for (char c : str.toCharArray()) {
- count[c - 'a']++;
- }
- StringBuilder sb = new StringBuilder();
- for (int i = 0; i <26; i++) {
- if (count[i] != 0) {
- sb.append((char)(i + 'a')).append(count[i]);
- }
- }
- String flag = sb.toString();
- if (!map.containsKey(flag)) {
- map.put(flag, new ArrayList<>());
- }
- map.get(flag).add(str);
- }
- return new ArrayList<>(map.values());
- }
- }
131. Palindrome Partitioning[Medium]
题目: 给出一个字符串, 找出所有的回文子串并添加到列表当中返回
思路: 动态规划来找出不同的切割方案
dp[i][j] = dp[i - 1][j + 1]
, 要写出来 DFS
- class Solution {
- public List<List<String>> partition(String s) {
- List<List<String>> res = new ArrayList<>();
- dfs(s, res, new ArrayList<String>(), 0);
- return res;
- }
- private void dfs(String s, List<List<String>> res, List<String> cur, int start) {
- if (s.length() == start) {
- res.add(new ArrayList<>(cur));
- return;
- }
- // backtracking 的添加条件 作为 isPalindrome
- for (int i = start + 1; i <= s.length(); i++) {
- if (isPalindrome(s, start, i - 1)) {
- cur.add(s.substring(start, i));
- dfs(s, res, cur, i);
- cur.remove(cur.size() - 1);
- }
- }
- }
- private boolean isPalindrome(String s, int i , int j) {
- while (i <j) {
- if (s.charAt(i) == s.charAt(j)) {
- i++;
- j--;
- } else if (s.charAt(i) != s.charAt(j)) {
- return false;
- }
- }
- return true;
- }
- }
132. Palindrome Partitioning II[Medium]
题目: 给出一个字符串 str, 返回把 str 全部切割为回文子串的最小分割数
思路: 想要找到最小分割数, 需要使分割次数尽量少, 用 dp 来求得最优解
267. Palindrome PermutationII [Medium]
思路: Permutation 如何找到? DFS + backtracking, 回文串的 permuration 是通过两个指针进行简单的镜像对称来实现的 在找到的所有的 permutation 当中判断出来哪些是 Palindrome 放到 res 当中. 效率太低.
需要判断的是字符串的奇偶性, 用一个 oneOdd 变量来做标记, 如果是奇数个, 最中间一定是一个单字符, 双指针的起点是 i-1和 i+1, 如果是偶数个, 起点为 i 和 i + 1
- public class Solution {
- public List<String> generatePalindromes(String s) {
- int[] hash = new int[256];
- for(int i = 0; i <s.length(); i++){
- int index = (int) s.charAt(i);
- hash[index] ++;
- }
- char center = '.';
- boolean oneOdd = false;
- for(int i = 0; i < 256; i++){
- if(hash[i] % 2 == 0){
- continue;
- } else {
- if(oneOdd) return new ArrayList<String>(); // 奇数字符多于一个直接 return 空字符
- oneOdd = true;
- center = (char) i;
- hash[i] --;
- }
- }
- char[] array = new char[s.length()];
- List<String> list = new ArrayList<String>();
- if(oneOdd) {
- array[s.length() / 2] = center;
- dfs(list, array, hash, s.length() / 2 - 1, s.length() / 2 + 1);
- } else {
- dfs(list, array, hash, s.length() / 2 - 1, s.length() / 2);
- }
- return list;
- }
- private void dfs(List<String> list, char[] array, int[] hash, int left, int right){
- if(left <0 || right>= array.length){
- list.add(new String(array));
- return;
- }
- for(int i = 0; i <256; i++){
- if(hash[i] <= 0) continue;
- array[left] = (char) i;
- array[right] = (char) i;
- hash[i] -= 2;
- dfs(list, array, hash, left - 1, right + 1);
- array[left] = '.';
- array[right] = '.';
- hash[i] += 2;
- }
- }
- }
相关题目:
46. Permutations [Medium]
思路: Backtracking, 使用一个辅助的 used 数组来进行判断
- class Solution {
- public List<List<Integer>> permute(int[] nums) {
- List<List<Integer>> res = new ArrayList<>();
- if (nums == null || nums.length == 0) {
- return res;
- }
- int n = nums.length;
- boolean[] used = new boolean[n];
- helper(res, new ArrayList<>(), used, nums);
- return res;
- }
- private void helper(List<List<Integer>> res, List<Integer> curr, boolean[] used, int[] nums) {
- if (curr.size() == nums.length) {
- res.add(new ArrayList(curr));
- }
- for (int i = 0; i <nums.length; i++) {
- if (!used[i]) {
- curr.add(nums[i]);
- used[i] = true;
- helper(res, curr, used, nums);
- used[i] = false;
- curr.remove(curr.size() - 1);
- }
- }
- }
- }
有重复元素
- Arrays.sort(nums) // 排序这样所有重复的数
- if (i> 0 && nums[i] == nums[i - 1] && used[i - 1]) {
- continue;
- } // 跳过会造成重复的情况
78. Subsets [Medium]
思路: for 循环的起点不同
- class Solution {
- public List<List<Integer>> subsets(int[] nums) {
- List<List<Integer>> results = new ArrayList<>();
- Arrays.sort(nums);
- helper(results, new ArrayList<>(), nums, 0);
- return results;
- }
- // 1. 递归的定义: 在 nums 中找到所有的 subset, 每个元素都有两个选择, 加入和不加入
- private void helper(List<List<Integer>> results,
- List<Integer> subset,
- int[] nums,
- int start) {
- //2. 递归的拆解 deep copy -> create new subset ArrayList
- // 每一层都加当前的新元素
- // 添加顺序: [] [1] [1,2] [1,2,3] [1,3] [2] [2,3] [3]
- results.add(new ArrayList(subset));
- for (int i = start; i <nums.length; i++) {
- //[] -> [1] or [1] -> [1, 2]
- subset.add(nums[i]);
- helper(results, subset, nums, i + 1);
- subset.remove(subset.size() - 1);
- }
- // 3. 递归的出口
- // 当 for 循环的条件不满足时, 直接什么都不执行 => return
- }
- }
来源: https://juejin.im/post/5c51823ce51d4556940c282a