狸猫的笔试——镜像字符串（二叉树法）

喜欢ヅ旅行 2022-07-26 06:18 95阅读 0赞

输入一串字符串，获取其中最长的镜像字符串

例如

cabecbad

对与子串:abecba  除去c 剩下 abeba即为最长的镜像字符串 长度为5

算法思想：

对于每一个字符，都可以选择加入子串或者舍弃 然后判断是否是镜像字符串

package myWork;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class Mirror {
    	private static int len = 0;
    
    	public static void main(String args[]) {
    		List<Character> chars = new ArrayList<>();
    		String s = "cabecbad";
    		mirror(s, 0, chars);
    		System.out.println(len);
    	}
    
    	public static void mirror(String s, int index, List<Character> chars) {
    		// 已取完字符
    		if (index >= s.length()) {
    			// 判断是否是镜像
    			for (int i = 0; i < chars.size() / 2; i++) {
    				if (chars.get(i) != chars.get(chars.size() - i - 1)) {
    					return;
    				}
    			}
    			if (chars.size() > len) {
    				len = chars.size();
    				return;
    			}
    		} else if (s.length() - index + chars.size() < len) {
    			//剪支
    			return;
    		} else {
    			List<Character> charsCopyone = new ArrayList<>();
    			charsCopyone.addAll(chars);
    			mirror(s, index + 1, charsCopyone);
    
    			List<Character> charsCopytwo = new ArrayList<>();
    			charsCopytwo.addAll(chars);
    			charsCopytwo.add(s.charAt(index));
    			mirror(s, index + 1, charsCopytwo);
    		}
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，95人围观）

还没有评论，来说两句吧...

相关阅读

相关二叉树的镜像

题目描述操作给定的二叉树，将其变换为源二叉树的镜像。比如：源二叉树 8 / \

喜欢ヅ旅行/ 2023年01月13日 09:52/ 0 赞/ 127 阅读

相关狸猫的笔试——查找

输入：一个递增排序的数组一个数字S 要求：在数组中查找两个数，使他们的和正好是S，如果有多对数字的和是S，则输出两个数乘积最小的输出：两个数

短命女/ 2022年07月26日 09:03/ 0 赞/ 133 阅读

相关狸猫的笔试——镜像字符串（二叉树法）

输入一串字符串，获取其中最长的镜像字符串例如 cabecbad 对与子串:abecba 除去c 剩下 abeba即为最长的镜像字符串长度为5 算法思想：

喜欢ヅ旅行/ 2022年07月26日 06:18/ 0 赞/ 96 阅读

相关狸猫的笔试——集合

1.计算1+2+3+……+n。不使用乘法。分析：这道题有三种思路。 1.用for循环从一加到n。虽然简单，但是时间最长。 2.根据等差数列公式有（1+n）\n/2

旧城等待，/ 2022年07月17日 02:12/ 0 赞/ 132 阅读

相关二叉树的镜像

剑指offer面试题19：请完成一个函数，输入一个二叉树，该函数输出它的镜像 void MirrorRecursively(BinaryTreeNode pHead)

àì夳堔傛蜴生んèń/ 2022年06月17日 05:57/ 0 赞/ 116 阅读

相关二叉树的镜像

![这里写图片描述][70] class TreeNode { int val = 0; TreeNode left = null;

小鱼儿/ 2022年05月25日 00:04/ 0 赞/ 135 阅读

相关二叉树的镜像

![这里写图片描述][70] class TreeNode { int val = 0; TreeNode left = null;

浅浅的花香味﹌/ 2022年05月24日 22:36/ 0 赞/ 123 阅读

相关二叉树的镜像

[二叉树的镜像][Link 1] 题目描述操作给定的二叉树，将其变换为源二叉树的镜像。思路：思路很明了，设置一个新结点，左右孩子交换，递归下去。

柔光的暖阳◎/ 2022年03月25日 15:26/ 0 赞/ 183 阅读

相关二叉树的镜像

时间限制：1秒空间限制：32768K 热度指数：221841 算法知识视频讲解题目描述操作给定的二叉树，将其变换为源二叉树的镜像。输入描述: 二叉树的

àì夳堔傛蜴生んèń/ 2022年03月10日 01:37/ 0 赞/ 155 阅读

相关二叉树之二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。二叉树的镜像定义：源二叉树 8 / \ 6

Bertha 。/ 2021年09月18日 04:56/ 0 赞/ 293 阅读