算法|二叉树剑指offer
2022-12-24 本文已影响0人
激扬飞雪
一、 剑指 Offer II 047. 二叉树剪枝
/**
* 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 {
private boolean isZero(TreeNode root) {
if (root == null) return true;
if (root.val != 0) return false;
if (!isZero(root.left)) return false;
return isZero(root.right);
}
public TreeNode pruneTree(TreeNode root) {
if (root == null) return null;
if (isZero(root)) return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
return root;
}
}
二、 剑指 Offer II 048. 序列化与反序列化二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder str = new StringBuilder();
if (root == null) {
str.append("[]");
return str.toString();
}
str.append("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
while (size -- > 0) {
TreeNode treeNode = queue.poll();
if (treeNode == null) {
str.append("null,");
continue;
}
str.append(treeNode.val + ",");
queue.offer(treeNode.left);
queue.offer(treeNode.right);
}
}
str.deleteCharAt(str.length() - 1);
str.append("]");
// System.out.println(str.toString());
return str.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
StringBuilder str = new StringBuilder(data);
str.deleteCharAt(0);
str.deleteCharAt(str.length() - 1);
System.out.println(str.toString());
if (str.isEmpty()) return null;
String[] els = str.toString().split(",");
for (int i = 0; i < els.length; i++){
System.out.println(els[i]);
}
int index = 0;
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode();
root.val = Integer.parseInt(els[index++]);
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
while (size-- > 0) {
TreeNode treeNode = queue.poll();
if ("null".equals(els[index])) {
index++;
} else {
TreeNode leftNode = new TreeNode();
leftNode.val = Integer.parseInt(els[index++]);
treeNode.left = leftNode;
queue.offer(leftNode);
}
if ("null".equals(els[index])) {
index++;
} else {
TreeNode rightNode = new TreeNode();
rightNode.val = Integer.parseInt(els[index++]);
treeNode.right = rightNode;
queue.offer(rightNode);
}
}
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
剑指 Offer II 077. 链表排序
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while (fast != null && fast.next != null){
pre = slow;
fast = fast.next.next;
slow = slow.next;
}
if (pre != null) pre.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return merger(l1, l2);
}
private ListNode merger(ListNode l1, ListNode l2){
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (l1 != null && l2 != null){
if (l1.val > l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
if (l1 != null) {
cur.next = l1;
}
if (l2 != null) {
cur.next = l2;
}
return dummy.next;
}
}
剑指 Offer II 078. 合并排序链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
private ListNode merger(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null){
if (l1.val > l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dummy.next;
}
private ListNode sortList(ListNode[] lists, int left, int right) {
if (left >= right) return lists[right];
int mid = left + (right - left) / 2;
ListNode l1 = sortList(lists, left, mid);
ListNode l2 = sortList(lists, mid + 1, right);
return merger(l1, l2);
}
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return sortList(lists, 0, lists.length - 1);
}
}
83. 删除排序链表中的重复元素
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) return head;
ListNode fast = head.next;
ListNode slow = head;
while (fast != null) {
System.out.println(fast.val + " " + slow.val);
if (slow.val != fast.val) {
slow.next = fast;
slow = fast;
}
fast = fast.next;
}
slow.next = null;
return head;
}
}
82. 删除排序链表中的重复元素 II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = head;
ListNode pre = dummy;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
pre.next = cur.next;
cur = cur.next;
} else {
pre = cur;
cur = cur.next;
}
}
return dummy.next;
}
}
147. 对链表进行插入排序
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode preNode = head;
ListNode cur = head.next;
while (cur != null) {
//不用交换
if (cur.val >= preNode.val) {
preNode = preNode.next;
cur = cur.next;
continue;
}
//找到插入点
ListNode tempPre = dummy;
while (tempPre.next != null) {
if (tempPre.next.val > cur.val) break;
tempPre = tempPre.next;
}
//删除cur节点
preNode.next = cur.next;
//添加节点
cur.next = tempPre.next;
tempPre.next = cur;
cur = preNode.next;
}
return dummy.next;
}
}
25. K 个一组翻转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode();
dummy.next = head;
ListNode cur = head;
ListNode pre = dummy;
while (cur != null) {
int n = k - 1;
ListNode temp = cur.next;
while (n-- > 0) {
if (temp == null) return dummy.next;
temp = temp.next;
}
ListNode next = temp;
n = k;
//翻转
ListNode preNode = null;
ListNode curNode = cur;
while (n-- > 0){
ListNode nextNode = curNode.next;
curNode.next = preNode;
preNode = curNode;
curNode = nextNode;
}
cur.next = next;
pre.next = preNode;
pre = cur;
cur = next;
}
return dummy.next;
}
}
61. 旋转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) return head;
int n = 1;
ListNode cur = head;
while (cur.next != null) {
n++;
cur = cur.next;
}
ListNode tail = cur;
int index = k % n;
if (index == 0) return head;
cur = head;
int b = n - index - 1;
while (b-- > 0) {
cur = cur.next;
}
ListNode newHead = cur.next;
cur.next = null;
tail.next = head;
return newHead;
}
}
86. 分隔链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) return head;
ListNode cur = head;
ListNode smallDummy = new ListNode(-1);
ListNode bigDummy = new ListNode(-1);
ListNode smallCur = smallDummy;
ListNode bigCur = bigDummy;
while (cur != null) {
if (cur.val >= x) {
bigCur.next = cur;
bigCur = bigCur.next;
} else {
smallCur.next = cur;
smallCur = smallCur.next;
}
cur = cur.next;
}
bigCur.next = null;
smallCur.next = bigDummy.next;
return smallDummy.next;
}
}
328. 奇偶链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode evenDummy = new ListNode(-1);
ListNode oddDummy= new ListNode(-1);
ListNode evenCur = evenDummy;
ListNode oddCur = oddDummy;
ListNode cur = head;
int n = 1;
while (cur != null){
if (n % 2 == 0) {
//偶数
oddCur.next = cur;
oddCur = oddCur.next;
} else {
//奇数
evenCur.next = cur;
evenCur = evenCur.next;
}
n++;
cur = cur.next;
}
evenCur.next = oddDummy.next;
oddCur.next = null;
return evenDummy.next;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null || head.next == null) return head;
//偶数
ListNode evenHead = head.next;
//奇数
ListNode odd = head;
ListNode even = evenHead;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
2. 两数相加
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1;
ListNode cur2 = l2;
int flag = 0;
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (cur1 != null || cur2 != null) {
int val1 = cur1 != null ? cur1.val : 0;
int val2 = cur2 != null ? cur2.val : 0;
int sum = val1 + val2 + flag;
flag = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
cur1 = cur1 != null ? cur1.next : null;
cur2 = cur2 != null ? cur2.next : null;
}
if (flag == 1) {
cur.next = new ListNode(1);
}
return dummy.next;
}
}
445. 两数相加 II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
Stack<ListNode> stack1 = new Stack<>();
ListNode cur1 = l1;
while (cur1 != null) {
stack1.push(cur1);
cur1 = cur1.next;
}
Stack<ListNode> stack2 = new Stack<>();
ListNode cur2 = l2;
while (cur2 != null) {
stack2.push(cur2);
cur2 = cur2.next;
}
int flag = 0;
ListNode head = null;
while (!stack1.isEmpty() || !stack2.isEmpty()) {
int val1 = stack1.isEmpty() ? 0 : stack1.pop().val;
int val2 = stack2.isEmpty() ? 0 : stack2.pop().val;
int sum = val1 + val2 + flag;
flag = sum / 10;
sum = sum % 10;
ListNode newNode = new ListNode(sum);
if (head == null) {
head = newNode;
} else {
newNode.next = head;
head = newNode;
}
}
if (flag == 1) {
ListNode newNode = new ListNode(1);
newNode.next = head;
head = newNode;
}
return head;
}
}
234. 回文链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) slow = slow.next;
//反转
ListNode cur = slow;
ListNode pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
//比较
cur = pre;
while (cur != null) {
if (head.val != cur.val) return false;
head = head.next;
cur = cur.next;
}
return true;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
private ListNode reverList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) slow = slow.next;
slow = reverList(slow);
while (slow != null) {
if (slow.val != head.val) return false;
slow = slow.next;
head = head.next;
}
return true;
}
}
148. 排序链表
归并排序
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
private ListNode meger(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while (fast != null && fast.next != null) {
pre = slow;
fast = fast.next.next;
slow = slow.next;
}
if (pre != null) pre.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return meger(l1, l2);
}
}
//插入排序
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode cur = head.next;
ListNode pre = head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
while (cur != null) {
if (cur.val > pre.val) {
pre = pre.next;
cur = cur.next;
continue;
}
ListNode temp = dummy;
while (temp.next != null) {
if (temp.next.val > cur.val) break;
temp = temp.next;
}
pre.next = cur.next;
cur.next = temp.next;
temp.next = cur;
cur = pre.next;
}
return dummy.next;
}
}
剑指 Offer II 037. 小行星碰撞
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < asteroids.length; i++){
int val = asteroids[i];
//自己是否毁了
boolean flag = true;
//发生碰撞
while (val < 0 && !stack.isEmpty() && stack.peek() > 0){
if (stack.peek() < Math.abs(val)) {
//栈顶的毁掉
stack.pop();
} else if (stack.peek() == Math.abs(val)){
//栈顶毁掉
stack.pop();
//自己也毁掉
flag = false;
break;
} else {
//自己毁掉
flag = false;
break;
}
}
if (flag) {
stack.push(asteroids[i]);
}
}
int[] result = new int[stack.size()];
int index = result.length - 1;
while (!stack.isEmpty()){
result[index--] = stack.pop();
}
return result;
}
}
剑指 Offer II 038. 每日温度
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] result = new int[temperatures.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < temperatures.length; i++){
while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
result[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
return result;
}
}
剑指 Offer II 014. 字符串中的变位词
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] a = new int[26];
int[] b = new int[26];
for (int i = 0; i < s1.length(); i++){
a[s1.charAt(i) - 'a']++;
b[s2.charAt(i) - 'a']++;
}
if (Arrays.equals(a, b)) {
return true;
}
int left = 0;
int right = s1.length();
while (right < s2.length()) {
b[s2.charAt(right) - 'a']++;
b[s2.charAt(left) - 'a']--;
if (Arrays.equals(a, b)) return true;
left++;
right++;
}
return false;
}
}
剑指 Offer II 018. 有效的回文
class Solution {
private boolean isNumOrLetter(char c){
if ((c >= 'a' && c <= 'z')
|| (c >= 'A' && c <= 'Z')
|| (c >= '0' && c <= '9')) return true;
return false;
}
public boolean isPalindrome(String s) {
char[] chs = s.toUpperCase().toCharArray();
int left = 0;
int right = chs.length - 1;
while (left < right) {
if (!isNumOrLetter(chs[left])) {
left++;
continue;
}
if (!isNumOrLetter(chs[right])) {
right--;
continue;
}
System.out.println(chs[left] + " " + chs[right]);
if (chs[left] != chs[right]) return false;
left++;
right--;
}
return true;
}
}
剑指 Offer II 019. 最多删除一个字符得到回文
class Solution {
private boolean isVail(String s, int left, int right){
while (left < right){
if (s.charAt(left) != s.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
return isVail(s, left + 1, right) || isVail(s, left, right - 1);
}
}
return true;
}
}
剑指 Offer II 059. 数据流的第 K 大数值
class KthLargest {
private PriorityQueue<Integer> priorityQueue;
private int k;
public KthLargest(int k, int[] nums) {
priorityQueue = new PriorityQueue<>();
this.k = k;
for (int i = 0; i < nums.length; i++){
priorityQueue.offer(nums[i]);
if (priorityQueue.size() > k) {
priorityQueue.poll();
}
}
}
public int add(int val) {
priorityQueue.offer(val);
if (priorityQueue.size() > k) {
priorityQueue.poll();
}
return priorityQueue.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
剑指 Offer II 085. 生成匹配的括号
class Solution {
private List<Integer> paths;
private List<List<Integer>> result;
private void backTracking(int[] nums, boolean[] uses) {
if (paths.size() == nums.length) {
result.add(new ArrayList<>(paths));
return;
}
for (int i = 0; i < nums.length; i++){
if (uses[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !uses[i - 1]) continue;
uses[i] = true;
paths.add(nums[i]);
backTracking(nums, uses);
paths.remove(paths.size() - 1);
uses[i] = false;
}
}
public List<List<Integer>> permuteUnique(int[] nums) {
paths = new ArrayList<>();
result = new ArrayList<>();
boolean[] uses = new boolean[nums.length];
Arrays.sort(nums);
Arrays.fill(uses, false);
backTracking(nums, uses);
return result;
}
}
剑指 Offer II 085. 生成匹配的括号
class Solution {
private List<String> result;
private void generateParenthesis(int n, String str, int open, int close) {
if (open > n) return;
if (close > open) return;
if (str.length() == n * 2) {
result.add(str);
return;
}
generateParenthesis(n, str + "(", open + 1, close);
generateParenthesis(n, str + ")", open, close + 1);
}
public List<String> generateParenthesis(int n) {
result = new ArrayList<>();
generateParenthesis(n, new String(), 0, 0);
return result;
}
}
剑指 Offer II 087. 复原 IP
class Solution {
private List<String> paths;
private List<String> result;
private boolean isVail(String str){
if (str.length() == 1) return true;
if (str.length() > 3) return false;
if (str.charAt(0) == '0') return false;
if (Integer.parseInt(str) > 255) return false;
return true;
}
private void backTracking(String s, int indexStart){
if (paths.size() > 4) return;
if (indexStart == s.length() && paths.size() == 4) {
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < paths.size(); i++){
stringBuilder.append(paths.get(i));
if (i != paths.size() - 1) {
stringBuilder.append(".");
}
}
result.add(stringBuilder.toString());
return;
}
for (int i = indexStart; i < s.length(); i++){
String str = s.substring(indexStart, i + 1);
if (!isVail(str)) break;
paths.add(str);
backTracking(s, i + 1);
paths.remove(paths.size() - 1);
}
}
public List<String> restoreIpAddresses(String s) {
paths = new ArrayList<>();
result = new ArrayList<>();
backTracking(s, 0);
return result;
}
}
剑指 Offer 36. 二叉搜索树与双向链表
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
private Node dummy;
private Node pre;
private void tree(Node root) {
if (root == null) return;
tree(root.left);
pre.right = root;
root.left = pre;
pre = root;
tree(root.right);
}
public Node treeToDoublyList(Node root) {
if (root == null) return root;
dummy = new Node(-1);
pre = dummy;
tree(root);
pre.right = dummy.right;
dummy.right.left = pre;
return dummy.right;
}
}
面试题 02.01. 移除重复节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
HashSet<Integer> hashSet = new HashSet<>();
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null) {
if (hashSet.contains(pre.next.val)) {
pre.next = pre.next.next;
} else {
hashSet.add(pre.next.val);
pre = pre.next;
}
}
return dummy.next;
}
}
面试题 02.04. 分割链表
//使用两个虚拟头结点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallDummy = new ListNode(-1);
ListNode bigDummy = new ListNode(-1);
ListNode smallCur = smallDummy;
ListNode bigCur = bigDummy;
ListNode cur = head;
while (cur != null) {
if (cur.val < x) {
smallCur.next = cur;
smallCur = smallCur.next;
} else {
bigCur.next = cur;
bigCur = bigCur.next;
}
cur = cur.next;
}
smallCur.next = bigDummy.next;
bigCur.next = null;
return smallDummy.next;
}
}
//快排思想
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null) return head;
ListNode right = head;
ListNode left = head;
while (right != null) {
if (right.val < x) {
//交换
int temp = left.val;
left.val = right.val;
right.val = temp;
left = left.next;
}
right = right.next;
}
return head;
}
}
面试题 02.05. 链表求和
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode cur1 = l1;
ListNode cur2 = l2;
int flag = 0;
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (cur1 != null || cur2 != null){
int val1 = cur1 != null ? cur1.val : 0;
int val2 = cur2 != null ? cur2.val : 0;
int sum = val1 + val2 + flag;
flag = sum / 10;
sum = sum % 10;
ListNode newNode = new ListNode(sum);
cur.next = newNode;
cur = newNode;
cur1 = cur1 == null ? null : cur1.next;
cur2 = cur2 == null ? null : cur2.next;
}
if (flag == 1) {
cur.next = new ListNode(1);
}
return dummy.next;
}
}
面试题 02.06. 回文链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast != null) slow = slow.next;
//翻转后半部分
ListNode cur = slow;
ListNode pre = null;
while (cur != null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
cur = pre;
while (cur != null) {
if (cur.val != head.val) return false;
head = head.next;
cur = cur.next;
}
return true;
}
}
//放入list中 双指针判断回文串
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode cur = head;
List<Integer> list = new ArrayList<>();
while (cur != null) {
list.add(cur.val);
cur = cur.next;
}
int left = 0;
int right = list.size() - 1;
while (left < right) {
if (!list.get(left).equals(list.get(right))) return false;
left++;
right--;
}
return true;
}
}
面试题 03.03. 堆盘子
class StackOfPlates {
private int cap;
private List<Stack<Integer>> list;
public StackOfPlates(int cap) {
this.cap = cap;
list = new ArrayList<>();
}
public void push(int val) {
if (cap <= 0) return;
//空或者最后一个满了 添加一个新的元素
if (list.isEmpty() || list.get(list.size() - 1).size() >= cap) {
Stack<Integer> stack = new Stack<>();
list.add(stack);
}
list.get(list.size() - 1).push(val);
}
public int pop() {
return popAt(list.size() - 1);
}
public int popAt(int index) {
if (index < 0 || index >= list.size()) return -1;
Stack<Integer> stack = list.get(index);
if (stack.isEmpty()) return - 1;
int result = stack.pop();
if (stack.isEmpty()) {
list.remove(index);
}
return result;
}
}
/**
* Your StackOfPlates object will be instantiated and called as such:
* StackOfPlates obj = new StackOfPlates(cap);
* obj.push(val);
* int param_2 = obj.pop();
* int param_3 = obj.popAt(index);
*/
面试题 04.03. 特定深度节点链表
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
if (tree == null) return null;
List<ListNode> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(tree);
while (!queue.isEmpty()){
int size = queue.size();
ListNode dummy = new ListNode();
ListNode cur = dummy;
while (size-- > 0) {
TreeNode treeNode = queue.poll();
cur.next = new ListNode(treeNode.val);
cur = cur.next;
if (treeNode.left != null) queue.offer(treeNode.left);
if (treeNode.right != null) queue.offer(treeNode.right);
}
list.add(dummy.next);
}
ListNode[] result = new ListNode[list.size()];
for (int i = 0; i < result.length; i++){
result[i] = list.get(i);
}
return result;
}
}
面试题 16.25. LRU 缓存
class LRUCache {
static class ListNode {
int val;
int key;
ListNode next;
ListNode pre;
ListNode(){
}
ListNode(int key, int val){
this.key = key;
this.val = val;
}
}
private ListNode head;
private ListNode tail;
private int capacity;
private HashMap<Integer, ListNode> hashMap;
public LRUCache(int capacity) {
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.pre = head;
this.capacity = capacity;
hashMap = new HashMap<>();
}
private void moveListNodeToHead(ListNode listNode){
//删除listNode
ListNode preNode = listNode.pre;
ListNode next = listNode.next;
preNode.next = next;
next.pre = preNode;
listNode.pre = null;
listNode.next = null;
//添加到头部
addListNodeToHead(listNode);
}
private void addListNodeToHead(ListNode listNode){
//添加到头部
ListNode nextNode = head.next;
head.next = listNode;
listNode.pre = head;
listNode.next = nextNode;
nextNode.pre = listNode;
}
public int get(int key) {
if (!hashMap.containsKey(key)) return -1;
ListNode listNode = hashMap.get(key);
moveListNodeToHead(listNode);
return listNode.val;
}
private ListNode removeLast(){
ListNode preNode = tail.pre;
ListNode prePreNode = preNode.pre;
prePreNode.next = tail;
tail.pre = prePreNode;
preNode.pre = null;
preNode.next = null;
return preNode;
}
public void put(int key, int value) {
if (hashMap.containsKey(key)) {
ListNode listNode = hashMap.get(key);
listNode.val = value;
moveListNodeToHead(listNode);
return;
}
if (hashMap.size() == capacity) {
//删除最后一个
ListNode delNode = removeLast();
hashMap.remove(delNode.key);
}
ListNode newNode = new ListNode(key, value);
hashMap.put(key, newNode);
addListNodeToHead(newNode);
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
面试题 17.12. BiNode
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode dummy;
private TreeNode cur;
private void convert(TreeNode root) {
if (root == null) return;
convert(root.left);
cur.right = root;
root.left = null;
cur = root;
convert(cur.right);
}
public TreeNode convertBiNode(TreeNode root) {
dummy = new TreeNode(-1);
cur = dummy;
convert(root);
return dummy.right;
}
}
剑指 Offer 07. 重建二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private HashMap<Integer, Integer> hashMap;
private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd){
if (preStart >= preEnd || inStart >= inEnd) return null;
int val = preorder[preStart];
int index = hashMap.get(val);
int leftIn = index - inStart;
TreeNode treeNode = new TreeNode(val);
treeNode.left = buildTree(preorder, preStart + 1, preStart + 1 + leftIn, inorder, inStart, index);
treeNode.right = buildTree(preorder, preStart + 1 + leftIn, preEnd, inorder, index + 1, inEnd);
return treeNode;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
hashMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++){
hashMap.put(inorder[i], i);
}
return buildTree(preorder, 0, preorder.length, inorder, 0, inorder.length);
}
}
剑指 Offer 27. 二叉树的镜像
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private void swap(TreeNode root) {
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
public TreeNode mirrorTree(TreeNode root) {
if (root == null) return root;
mirrorTree(root.left);
mirrorTree(root.right);
swap(root);
return root;
}
}
剑指 Offer 28. 对称的二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private boolean isSymmetric(TreeNode leftNode, TreeNode rightNode) {
if (leftNode == null && rightNode == null) return true;
if (leftNode == null || rightNode == null) return false;
if (leftNode.val != rightNode.val) return false;
if (!isSymmetric(leftNode.left, rightNode.right)) return false;
return isSymmetric(leftNode.right, rightNode.left);
}
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return isSymmetric(root.left, root.right);
}
}
剑指 Offer 32 - III. 从上到下打印二叉树 III
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int count = 0;
while (!queue.isEmpty()){
int size = queue.size();
count++;
LinkedList<Integer> list = new LinkedList<>();
while (size-- > 0){
TreeNode treeNode = queue.poll();
if (count % 2 == 0) {
//从右往左
list.addFirst(treeNode.val);
} else {
//从左往有
list.addLast(treeNode.val);
}
if (treeNode.left != null) queue.offer(treeNode.left);
if (treeNode.right != null) queue.offer(treeNode.right);
}
result.add(list);
}
return result;
}
}
剑指 Offer 33. 二叉搜索树的后序遍历序列
class Solution {
private boolean verifyPostorder(int[] postorder, int left, int right) {
if (left >= right) return true;
int m = left;
while (m < right) {
if (postorder[m] > postorder[right]) break;
m++;
}
while (m < right) {
if (postorder[m] < postorder[right]) return false;
m++;
}
return verifyPostorder(postorder, left, m - 1) && verifyPostorder(postorder, m, right - 1);
}
public boolean verifyPostorder(int[] postorder) {
if (postorder == null || postorder.length == 0) return true;
return verifyPostorder(postorder, 0, postorder.length - 1);
}
}
剑指 Offer 54. 二叉搜索树的第k大节点
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int result;
private int count;
private boolean traver(TreeNode root, int k) {
if (root == null) return false;
boolean isFind = traver(root.right, k);
if (isFind) return true;
count++;
if (count == k) {
result = root.val;
return true;
}
return traver(root.left, k);
}
public int kthLargest(TreeNode root, int k) {
if (root == null) return -1;
traver(root, k);
return result;
}
}
80. 删除有序数组中的重复项 II
class Solution {
public int removeDuplicates(int[] nums) {
int j = 0;
int count = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[j]) {
nums[++j] = nums[i];
count = 0;
} else {
count++;
if (count >= 2) {
} else {
nums[++j] = nums[i];
}
}
}
return ++j;
}
}
125. 验证回文串
class Solution {
private boolean isLeeterOrNum(char c) {
if (c >= 'a' && c <= 'z') return true;
if (c >= '0' && c <= '9') return true;
return false;
}
public boolean isPalindrome(String s) {
s = s.toLowerCase();
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (!isLeeterOrNum(s.charAt(left))) {
left++;
continue;
}
if (!isLeeterOrNum(s.charAt(right))) {
right--;
continue;
}
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
}
345. 反转字符串中的元音字母
class Solution {
private boolean isYuanYin(String str, char ch) {
return str.indexOf(ch) != -1;
}
public String reverseVowels(String s) {
String yuan = "aeiouAEIOU";
char[] ss = s.toCharArray();
int left = 0;
int right = ss.length - 1;
while (left < right) {
if (!isYuanYin(yuan, ss[left])) {
left++;
continue;
}
if (!isYuanYin(yuan, ss[right])) {
right--;
continue;
}
//交换
char temp = ss[left];
ss[left] = ss[right];
ss[right] = temp;
left++;
right--;
}
return new String(ss);
}
}
