替换后的最长重复字符
题目：给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意:字符串长度 和 k 不会超过 104。
示例 1:
输入:
s = "ABAB", k = 2
输出:
4
解释:
用两个'A'替换为两个'B',反之亦然。
示例 2:
输入:
s = "AABABBA", k = 1
输出:
4
解释:
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
思路：这个题，我觉得不算难，尤其是没有任何的时间空间限制条件。我个人的话，第一反应是双层for循环遍历。滑动窗口应该也可以，反正双层for循环是最直接的一个写法，但是性能肯定不会太好了，我先去试试能不能实现
回来了，代码ac了，性能和我预计的差不多，只超过百分之五的人，我直接贴代码：
class Solution {
public int characterReplacement(String s, int k) {
if(k>=s.length()) return s.length();
int max = 0;
char[] c = s.toCharArray();
for(int i = 0;i<c.length;i++){
if(i!=0 && c[i]==c[i-1]) continue;
int l = k;
char cur = c[i];
for(int j = i+1;j<c.length;j++){
if(c[j]!=c[i]){
if(l>0){
l--;
}else{
max = Math.max(max,j-i);
break;
}
}
if(j==c.length-1){
max = Math.max(max,c.length-i+l);
}
}
}
return max>c.length?c.length:max;
}
}
反正就是逻辑还是挺好理解的，就是代码墨迹点，我审完题后就觉得应该是有别的更好的解决办法，但是为了早ac所以没想。但是这个题真的让我觉得应该用滑窗，我再去想想怎么做。
刚刚说的滑窗是没啥问题的，我先贴代码：
public int characterReplacement(String s, int k) {
int match = 0, res = 0;
int[] helper = new int[26];
char[] chars = s.toCharArray();
int left = 0, right = 0;
int charMax = 0;
while (right < chars.length&& left<=right) {
char temp = chars[right];
helper[temp-'A']++;
right++;
charMax = Math.max(charMax, helper[temp-'A']);
if(right-left-charMax > k) {
helper[chars[left]-'A']--;
left++;
}
}
return right-left;
}
这个就是滑动窗口的写法，分两种情况，一种是满足条件（包括相同的字符和k可以替换）一种是不满足条件。满足条件是窗口扩张，不满足是窗口滑动。
我们维护一个数组int[26]来存储当前窗口中各个字母的出现次数，left表示窗口的左边界，right表示窗口右边界
窗口扩张：left不变，right++
窗口滑动：left++, right++。
每次循环right都要往后不说了，如果发现不满足条件则left++。
另外有一个很有意思的情况：我看了性能排行第一的代码，我这里是if判断，所以是5ms执行时间，但是如果改成while就是3ms，性能超过百分百的人，我也不知道是什么原因。
反正这个题就这样了，下一题。
N叉树的层序遍历
题目：给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
思路：这个题怎么说呢，可能是因为我以前二叉树那块觉得比较简单，我感觉这个题也很简单啊，暂时的想法就是逐层，用队列。以前二叉树的时候用过。我去实现下。
额，两次过了，第一次卡住是因为没有判空，和想的一样简单，二叉树啥样多叉树就啥样。我直接贴代码：
/*
// 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<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root==null) return res;
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<Integer>();
int size = queue.size();
for(int i = 0;i<size;i++){
Node r = queue.poll();
list.add(r.val);
for(Node n:r.children){
queue.offer(n);
}
}
res.add(list);
}
return res;
}
}
性能没太达到预想的，我去看看优化或者换种思路：
我直接附上性能排行第一的代码：
class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
if (root != null)
dfs(root, 0);
return res;
}
private void dfs(Node root, int level) {
if (res.size() <= level) {
res.add(new ArrayList<>());
}
res.get(level).add(root.val);
for (Node n : root.children) {
dfs(n, level + 1);
}
}
}
就是标准的前序递归，只不过这里多了一个层数保证逐层，没啥说的，直接下一题吧。
扁平化多级双向链表
题目：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
示例 1：
输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：
输入的多级列表如下图所示：
image.png
扁平化后的链表如下图：
image.png
示例 2：
输入：head = [1,2,null,3]
输出：[1,3,2]
解释：
输入的多级列表如下图所示：
1---2---NULL
|
3---NULL
示例 3：
输入：head = []
输出：[]
如何表示测试用例中的多级链表？
以 示例 1 为例：
1---2---3---4---5---6--NULL
|
7---8---9---10--NULL
|
11--12--NULL
序列化其中的每一级之后：
[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]
为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]
合并所有序列化结果，并去除末尾的 null 。
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
提示：
节点数目不超过 1000
1 <= Node.val <= 10^5
**思路：这个题怎么说呢，题目很复杂，我看了两三遍才隐隐看懂。然后字数还多，真的是审题本身就是个问题。但是理解了还是很好理解的。首先每一行是根据null结尾的，而一个null后面到下一个数字之前的null，都是下一行的开始。从上一层的第一个开始，有几个null往下顺几个元素，将子节点挂在相应的位置。我直接去代码实现了。对于这种没有任何时间空间限制的题目我习惯于先用最暴力的形式实现，然后再去一点点优化什么的，首先要保证思路没问题嘛。
**
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
if (head == null) return null;
Node cur = head;
// 向后遍历
while (cur != null) {
// 存在子链表，进行递归
if (cur.child != null) {
// 保留 next 节点
Node next = cur.next;
// 得到扁平化后的子链表，与之相连
Node child = flatten(cur.child);
cur.next = child;
child.prev = cur;
cur.child = null;
// 连接原 next
if (next != null) {
while (cur.next != null) {
cur = cur.next;
}
cur.next = next;
next.prev = cur;
}
}
cur = cur.next;
}
return head;
}
}
其实这个就是一个单纯的是遍历。我也是做了才发现，这个所谓的孩子节点不过是树中树而已。所以用递归实现。不过我这个代码理解起来容易，但是不知道为什么性能不咋地，我记得看过这么一句话，递归就是隐式的栈（好像有点出入，大概是这个意思）就是说只要能递归实现的，其实用栈也都可以实现。。不清楚是不是不用递归能性能好些，我直接去看看性能排行第一的代码吧。
我先贴代码：
/*
// Definition for a Node.
class Node {
public int val;
public Node prev;
public Node next;
public Node child;
};
*/
class Solution {
public Node flatten(Node head) {
if (head == null) return head;
Node pseudoHead = new Node(0, null, head, null);
Node cur, pre = pseudoHead;
Deque<Node> stack = new ArrayDeque<>();
stack.push(head);
while (!stack.isEmpty()) {
cur = stack.pop();
pre.next = cur;
cur.prev = pre;
if (cur.next != null) stack.push(cur.next);
if (cur.child != null) {
stack.push(cur.child);
// don't forget to remove all child pointers.
cur.child = null;
}
pre = cur;
}
pseudoHead.next.prev = null;
return pseudoHead.next;
}
}
我简直觉得我现在的嘴是开了光了的，居然真的是用栈实现的。。反正咋说呢，其实只要理解了原理是很容易想到的，我觉得这个代码也不是很复杂，就这样吧。
这篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利!
