CSDN话题挑战赛第2期 参赛话题：学习笔记
刷题打卡，第八天
- 题目一、409. 最长回文串
- 题目二、144. 二叉树的前序遍历
- 题目三、589. N 叉树的前序遍历
题目一、409. 最长回文串
原题链接：409. 最长回文串
题目描述：
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。 在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。 / 示例 1: 输入:s = “abccccdd” 输出:7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。 / 示例 2: 输入:s = “a” 输入:1
解题思路： 对于字符串出现的每个字符，我们可以使用该字符 v / 2 * 2 次，回文串平分两半，每半分得 v / 2 个字符 ，其中 / 为整数除法。如：9 / 2 = 4；1 / 2 = 0（v为字符出现的次数）
如果有任何一个字符出现奇数次，我们选出现的第一个字符，取其一个单字符作为唯一的回文中心，因为最多只能有一个字符作为回文中心。
为了做到出现的首个奇数次元素作为唯一回文中心，我们需要满足条件：回文长度为偶数，且字符出现奇数次； 满足条件，回文长度加一，回文长度就变成奇数，保证只有一个或没有回文中心。
我用了HashMap集合来记录字符出现的次数，再用迭代器遍历。（用时和内存都比较多）
代码：
代码语言：javascript复制class Solution {
public int longestPalindrome(String s) {
char[] arr = s.toCharArray();//字符串转为数组，每个元素都是字符串中的一个字符
Map<Character,Integer> map = new HashMap<>();//创建双列集合map
for(char c :arr ){//增强for循环，遍历数组
if(map.containsKey(c)){//如果字符存在，出现次数value值 1
map.replace(c,map.get(c).intValue() 1);
}else{//如果字符不在集合中，创建集合，主键为字符，value值为出现次数1
map.put(c,1);
}
}
int len = 0;//表示回文串长度
//实用迭代器Iterator遍历集合元素
Iterator<Map.Entry<Character,Integer>> iterator = map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry<Character,Integer> entry = iterator.next();
len = entry.getValue()/2*2;//可以使用该字符 v / 2 * 2 次
if(len%2==0 && entry.getValue()%2 ==1)//第一个出现的奇数次的元素作为回文串唯一中心
len ;
}
return len;
}
}提交结果：
。。。
思路相同，用数组遍历： （将字符作为数组下标，数组识别的下标为字符的ASCII码值）
代码（快贼多）：
代码语言：javascript复制class Solution {
public int longestPalindrome(String s) {
int[] count = new int[128];
int length = s.length();
for (int i = 0; i < length; i) {
char c = s.charAt(i);
count[c] ;
}
int ans = 0;
for (int v: count) {
ans = v / 2 * 2;
if (v % 2 == 1 && ans % 2 == 0) {
ans ;
}
}
return ans;
}
}提交结果：
题目二、144. 二叉树的前序遍历
原题链接：144. 二叉树的前序遍历
题目描述：
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 /
输入：root = [1,null,2,3] 输出：[1,2,3] / 示例 2： 输入：root = [] 输出：[] / 示例 3： 输入：root = [1] 输出：[1] /
输入：root = [1,2] 输出：[1,2] /
输入：root = [1,null,2] 输出：[1,2]
解题思路： 先序遍历，就是从根节点开始，先遍历左孩子，再遍历右孩子； 当根节点为空的时候，直接返回空即可； 存在根节点，我们可以使用栈结构，先进后出的特点，将根节点以及一路而下的左孩子压栈，当没有左孩子，我们就能让栈顶元素出栈，同时获取出栈节点右孩子。 循环地重复上述操作，就可以完成二叉树的先序遍历。
提交代码：
代码语言：javascript复制/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List list = new ArrayList(); //创建list集合，用于存放先序遍历的节点元素
if(root == null) return list; //如果根节点为空，直接返回空的集合
TreeNode node = root; //获取根节点
//创建堆结构
Deque<TreeNode> stack = new LinkedList<>();
//当堆不为空或二叉树节点不为空时
while(!stack.isEmpty() || node != null){
while(node != null){ //树节点不为空
list.add(node.val); //节点元素传入集合
stack.push(node); //同时节点如栈
node = node.left; //堆节点左孩子重复操作
//当左子树所有的左孩子入栈，代表遍历完左子树的所有子节点
}
//堆顶节点出栈
node = stack.pop();
//循环遍历出栈节点的右孩子
node = node.right;
}
return list; //返回存放先序遍历节点顺序的集合
}
}提交结果：
题目三、589. N 叉树的前序遍历
原题链接：589. N 叉树的前序遍历
题目描述：
给定一个 n 叉树的根节点
root，返回 其节点值的前序遍历。 n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
输入：root = [1,null,3,2,4,null,5,6] 输出：[1,3,5,6,2,4]
输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
解题思路： 先序遍历n叉树，思路与先序遍历二叉树的思路是相似的，都是先遍历左孩子再右孩子，再通过相同操作遍历其余子树的节点。 我们使用堆结构，每次出栈的堆顶元素就是先序遍历的下一个节点，所以我们需要在某个父节点出栈并且被记录后，从右向左地将其孩子节点入栈，以此达到出栈节点为先序遍历顺序的目的； 而这个操作中，每个出栈节点被记录后，其子节点都会从右向左入栈，从而将整棵树遍历，直到最后一个节点出栈，栈为空就停止。 最后返回记录出栈节点的集合，就是先序遍历后的n叉树节点顺序
提交代码：
代码语言：javascript复制/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<Integer> preorder(Node root) {
List list = new ArrayList(); //创建集合存放先序遍历后的节点
if(root == null) return list;//根节点为空，直接返回空集合
Deque<Node> stack = new LinkedList<>();//创建堆结构
stack.push(root); //根节点入栈
while(!stack.isEmpty()){ //只要栈不为空
Node curr = stack.pop(); //堆顶元素出栈
list.add(curr.val); //同时记录进集合
//将出栈节点的子节点按照逆序入栈，当下一次出栈时，记录的就是左孩子
for(int i = curr.children.size()-1;i>=0;--i){
stack.push(curr.children.get(i));
}
//重读操作
}
return list;
}
}提交结果：
贵在坚持：
