思路：队列特点是先进先出，所以将栈A依次弹出到B，那么B里存放的就是倒序的A，再将其弹出即可实现先进先出。
注意：
- deleteHead()函数中语句的顺序不能颠倒，必须先判断B是否为空，若不为空直接弹出。
- isEmpty和empty的区别在于：字符串中只有isEmpty()方法，而栈中两种方法均可以实现。
class CQueue {
LinkedList A,B;
public CQueue() {
A = new LinkedList();
B = new LinkedList();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) return B.removeLast(); //顺序不能换！先判断B是否为空
if(A.isEmpty()) return -1;
while(!A.isEmpty())
B.addLast(A.removeLast());
return B.removeLast();
}
}
30：包含min函数的栈
思路：利用两个栈，当最新插入的数字小于min栈里的首元素，则将其插入min中
- peek方法：返回栈的head元素
- add(int index,E element)可以指定添加元素的位置，默认添加到末尾，与addLast相同
- 添加到头部使用addFirst()
class MinStack {
Stack stack,min;
public MinStack() {
stack = new Stack<>();
min = new Stack<>();
}
public void push(int x) {
stack.add(x);
if(min.isEmpty() || min.peek() >= x) min.add(x);
}
public void pop() {
if(stack.pop().equals(min.peek())) min.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return min.peek();
}
}
16:从尾到头打印列表
思路：利用一个栈一个数组，将列表每个节点的值依次存入栈中，再从末尾依次弹出尾元素并存入数组中即可。
class Solution {
public int[] reversePrint(ListNode head) {
LinkedList stack = new LinkedList();
while(head != null){
stack.addLast(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i++)
res[i] = stack.removeLast();
return res;
}
}
DAY2
24：反转列表
思路：返回值要求也是节点类型。采用双指针思想，将当前指针cur的next指向前一个指针pre。
（这道题真的死活不能彻底悟透思路 555555）
最后temp和cur都指向了null
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null){
ListNode temp = cur.next; //暂存后继结点
cur.next = pre; //修改引用指向
pre = cur; //暂存当前节点
cur = temp; //访问下一个节点
}
return pre;
}
}
05：替换空格
思路：遇到空格替换成%20
注：
- StringBuilder：可变字符序列
-
str.toCharArray()：字符串转换为数组
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
for(Character c : s.toCharArray()){ //foreach循环
if(c == ' ') res.append("%20");
else res.append(c);
}
return res.toString();
}
}
58：左旋转字符串
思路：直接用截取字符串函数substring()很方便！！！
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n, s.length()) + s.substring(0, n);
}
}
DAY3
03：数组中重复的数字
思路：利用哈希表，将数组nums中的元素一次放入hash表中，若已经包含在hash表中的则为重复的数字，输出即可。
class Solution {
public int findRepeatNumber(int[] nums) {
Set hash = new HashSet<>();
for(int num : nums){
if(hash.contains(num)) return num;
hash.add(num);
}
return -1;
}
}
53：在排序数组中查找数字Ⅰ
思路：笨办法，遍历数组查匹配。
class Solution {
public int search(int[] nums, int target) {
Set hash = new HashSet<>();
int count = 0;
for(int num : nums){
if(num == target) count++;
}
return count;
}
}
53：0~n-1中缺失的数字（重点）
思路：因为是升序依次排列，所以采用二分查找效率会更高一些。首先要想到的是索引和元素不相等即为缺失的。所以设置r，l分别从头和尾开始，若索引与元素相等则说明前半部分没有错位，所以 r 移动在后半部分查询；若不相等则说明前半部分有错位，l 移动在前半部分查询。
class Solution {
public int missingNumber(int[] nums) {
//[0,1,3,4,5,6,7,8,9]
int r = 0, l = nums.length - 1;
while(r <= l){
int m = (r + l) / 2;
if(nums[m] == m) r = m+1;
else l = m-1;
}
return r;
}
}
DAY4
04：二维数组中的查找
思路：由题可知数组从左到右从上而下增大，所以从左下角开始查找效率最高。若该值大于target，那么target只存在于该值所在行的上方；若该值小于target，则target存在于该值所在列的右侧。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//从左下角开始找，小的话向上移，大的话向左移
int i = matrix.length - 1, j = 0;
while(i >= 0 && j target) i--;
else return true;
}
return false;
}
}
11：旋转数组中的最小数字
思路：利用二分查找
- 若middle小于high，则说明旋转点在左半部分
- 若middle大于high，则旋转点在右半部分
- 若相等则不能确定，可能有重复的数字，所以high--缩小范围继续二分查询
我有一点不明白就是为什么low移动后是m+1，而high移动就是m？？？好像是会造成死循环。
向下取整的时候可能会造成m左偏，所以low移动时候需要m+1，不然会使m陷在左边的循环中。
参考博文：https://blog.csdn.net/leokingszx/article/details/79464472
class Solution {
public int minArray(int[] numbers) {
int low = 0, high = numbers.length -1;
while(low != high){
int m = (low + high) / 2;
if(numbers[m] > numbers[high]) low = m + 1;
else if(numbers[m] < numbers[high]) high = m;
else high--;
}
return numbers[low];
}
}
50：第一个只出现一次的字符
思路：利用哈希表（存放字符和布尔值），遍历字符串
- 若dic中不包含c，则往dic中添加键值对（c，true），代表字符c出现次数为1
- 若dic中包含c，则修改键值对为（c，false），即字符出现次数>1
- 再遍历字符串，输出第一个是true的字符
class Solution {
public char firstUniqChar(String s) {
HashMap dic = new HashMap<>();
char[] sc = s.toCharArray();
for(char c : sc)
dic.put(c, !dic.containsKey(c));
for(char c : sc)
if(dic.get(c)) return c;
return ' ';
}
}
32-Ⅰ：从上到下打印二叉树（BFS）
思路：用队列暂存每一层的结点，动态数组添加遍历结果。
多看这道题啊！！！万物基础！
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[0];
Queue queue = new LinkedList();
List list = new ArrayList();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll(); //取出头节点
list.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
//将List转换为int数组,下面这句一样相同
//return list.stream().mapToInt(Integer::valueOf).toArray();
int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++) res[i] = list.get(i);
return res;
}
}
32-Ⅱ：从上到下打印二叉树（多看几遍！！！）
思路：返回数组是一个二维数组，每层返回一个组，用queue.size()获取长度。
这个思路牛逼就牛逼在for循环的条件，每次大循环都会把下一层的结点都存入queue中，然后将初值设置为queue的size直接i--，因为poll出根结点后queue的size会变，所以直接用递减会更好理解。妙啊妙啊
class Solution {
public List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List> res = new ArrayList<>(); //二维数组
if(root != null) queue.add(root);
while(!queue.isEmpty()){
List temp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(temp);
}
return res;
}
}
DAY5
32-Ⅲ：从上到下打印二叉树
思路：和2大同小异，只不过在将temp数组存入res数组的时候当为第奇数个元素时候用reverse反转存入，想法简单，只不过这个函数我第一次见。
class Solution {
public List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()){
List temp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--){
TreeNode node = queue.poll();
temp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
if(res.size() % 2 == 1) Collections.reverse(temp);
res.add(temp);
}
return res;
}
}
26：树的子结构（重点看，思路有点复杂）
思路：递归。分情况讨论
isSubStructure（A，B）：判断B是否为A的子树
- 以节点A为根结点的树包含B，即recur(A,B)
- B是A左子树的子结构
- B是A右子树的子结构
以上三种条件任意满足一种即可，但前提条件是A，B均不为空树。若A,B中存在空树则没有子结构。
recur（A，B）：判断以节点A为根结点的树是否包含B
- 若B为空，则匹配返回true。执行终止。
- 若A为空或节点A与B的值不相等，则不匹配，返回false。执行终止。
返回判断A和B的左右子节点是否对应相等的结果。
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B){
if(B == null) return true;
if(A == null || A.val != B.val) return false;
return recur(A.left, B.left) && recur(A.right, B.right);
}
}
27：二叉树的镜像
思路：递归，一次交换每个节点的左右节点即可得到镜像。思路比较简单，但是注意第三行一定要写，低轨道叶结点需要终止。
唉，递归写起来简单，想明白能自己写真的好难。
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null; // 这个不能少 因为到进行递归 遇到叶结点终止一次递归
//设置一个temp 类同最简单的交换ab位置
TreeNode temp = root.left;
root.left = mirrorTree(root.right);
root.right = mirrorTree(temp);
return root;
}
}
28：对称的二叉树
思路：递归。对称的条件：
- 对称的两个节点的val相等
- 对称的两个节点的左右节点满足：l.left == r.right && l.right == r.left
类同上一题
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null ? true : check(root.left, root.right);
}
public boolean check(TreeNode l, TreeNode r){
if(l == null && r == null) return true;
if(l == null || r == null || l.val != r.val) return false;
return check(l.left, r.right) && check(l.right, r.left);
}
}
树的题得好好看看！！！
