关于数据结构的题目(会更新)
一、顺序表
二、链表
1.链表分割
链接
java">import java.util.*;/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
//思路：
//1.分为两个链表,一个链表放小于x的节点，一个链表放大于等于x的节点
//2.连接两个链表
public class Partition {public ListNode partition(ListNode pHead, int x) {// write code here//分为两个链表,一个链表放小于x的节点，一个链表放大于等于x的节点ListNode bs = null;//bs-->beforeStartListNode bf = null;//bf-->beforeFinishListNode as = null;//as-->afterStartListNode af = null;//af-->afterFinishif(pHead == null){return null;}while(pHead != null){if(pHead.val < x){//bs为null时if(bs == null){bs = pHead;bf = pHead;}else{bf.next = pHead;bf = bf.next;}}else{//as为null时if(as == null){as = pHead;af = pHead;}else{af.next = pHead;af = af.next;}}pHead = pHead.next;}//两个进行连接、//后面为空if(as == null){return bs;}//若前面为null，去连接就会空指针异常if(bs == null){return as;}bf.next = as;af.next = null;//最后一个next域要为nullreturn bs;}
}
2.链表的回文结构
链接
java">class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
public class PalindromeList {public boolean chkPalindrome(ListNode A) {if(A==null||A.next==null){return true;}ListNode fast=A;ListNode slow=A;//找到中点while(fast!=null&&fast.next!=null){fast=fast.next.next;slow=slow.next;}//翻转ListNode cur=slow.next;while(cur!=null){ListNode curNext=cur.next;cur.next=slow;slow=cur;cur=curNext;}//对比while(A!=slow){if(A.val!=slow.val){return false;}if(A.next==slow){return true;}A=A.next;slow=slow.next;}return true;}
}3.相交链表
链接
java">/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA==null&&headB==null) {return null;}ListNode pl = headA;ListNode ps = headB;int lenA = 0 , lenB = 0;while(pl!=null) {lenA++;pl = pl.next;}while(ps!=null) {lenB++;ps = ps.next;}pl = headA;ps = headB;int len = lenA-lenB;if(len<0) {pl = headB;ps = headA;len = lenB-lenA;}while(len!=0) {pl = pl.next;len--;}while(pl!=ps) {pl = pl.next;ps = ps.next;}if(ps == null) {return null;}return ps;}
}4.环形链表
链接
java">/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while(fast!=null&&fast.next!=null) {fast = fast.next.next;slow =slow.next;if(fast==slow) {return true;}}return false;}
}5.环形链表的入环点
链接
java">/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast!=null&&fast.next!=null) {fast = fast.next.next;slow = slow.next;if(fast==slow) {break;}}if(fast==null||fast.next==null) {return null;}ListNode cur = head;while(cur!=slow) {cur = cur.next;slow = slow.next;}return cur;}
}三、栈
1.括号的匹配
括号的匹配
java">class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i = 0;i<s.length();i++) {char ch = s.charAt(i);if(ch=='('||ch=='['||ch=='{') {stack.push(ch);}else {if(stack.empty()) {return false;}char topL = stack.peek();if(topL=='('&&ch==')'||topL=='['&&ch==']'||topL=='{'&&ch=='}') {stack.pop();}else {return false;}}} if(!stack.empty()) {return false;}return true;}
}2.逆波兰表达式求值
逆波兰表达式
java">class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(int i=0;i<tokens.length;i++) {String tmp = tokens[i];if(!isOperations(tmp)) {stack.push(Integer.parseInt(tmp));}else {int val2 = stack.pop();int val1 = stack.pop();switch(tmp) {case "+":stack.push(val1+val2);break;case "-":stack.push(val1-val2);break;case "*":stack.push(val1*val2);break;case "/":stack.push(val1/val2);break;}}}return stack.pop();}private boolean isOperations(String tmp) {if(tmp.equals("+")||tmp.equals("-")||tmp.equals("*")||tmp.equals("/")) {return true;}return false;}
}3.栈的压入、弹出序列
链接
java">import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;for(int i=0;i<pushV.length;i++) {stack.push(pushV[i]);while(j<popV.length && !stack.empty()&& stack.peek()==popV[j]) {stack.pop();j++;}}return stack.empty();}
}4.最小栈
链接
java">class MinStack {private Stack<Integer> stack;private Stack<Integer> minstack;public MinStack() {stack = new Stack<>();minstack = new Stack<>();}public void push(int val) {stack.push(val);if(minstack.empty()) {minstack.push(val);}else {if(val<=minstack.peek()) {minstack.push(val);}}}public void pop() {//比较的是地址// if(stack.peek()==minstack.peek()) {// minstack.pop();// }if(stack.peek().equals(minstack.peek())) {minstack.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {return minstack.peek();}
}四、队列
1.循环队列
链接
浪费一个空间判断:
java">class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {elem = new int[k+1];}//入队列public boolean enQueue(int val) {if(isFull()) {return false;}elem[rear] = val;rear = (rear+1)% elem.length;return true;}public boolean isFull() {return (rear+1)%elem.length==front;}public boolean isEmpty() {return rear==front;}//出队列public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;return true;}//获取队头元素public int Front() {if(isEmpty()) {return -1;}return elem[front];}//获取队元素public int Rear() {if(isEmpty()) {return -1;}int index = (rear==0)?elem.length-1:rear-1;return elem[index];}
}使用usedSize判断:
java">class MyCircularQueue {public int[] elem;public int front;public int rear;public int usedSize = 0;public MyCircularQueue(int k) {elem = new int[k];}//入队列public boolean enQueue(int val) {if(isFull()) {return false;}elem[rear] = val;rear = (rear+1)% elem.length;usedSize++;return true;}public boolean isFull() {return usedSize==elem.length;}public boolean isEmpty() {return usedSize==0;}//出队列public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;usedSize--;return true;}//获取队头元素public int Front() {if(isEmpty()) {return -1;}return elem[front];}//获取队元素public int Rear() {if(isEmpty()) {return -1;}int index = (rear==0)?elem.length-1:rear-1;return elem[index];}
}flag判断：
java">class MyCircularQueue {public int[] elem;public int front;public int rear;public boolean flg = false;public MyCircularQueue(int k) {elem = new int[k];}//入队列public boolean enQueue(int val) {if(isFull()) {return false;}elem[rear] = val;rear = (rear+1)% elem.length;flg = true;return true;}public boolean isFull() {if(front == rear && flg) {return true;}return false;}public boolean isEmpty() {if(front == rear && !flg) {return true;}return false;}//出队列public boolean deQueue() {if(isEmpty()) {return false;}front = (front+1)%elem.length;flg = false;return true;}//获取队头元素public int Front() {if(isEmpty()) {return -1;}return elem[front];}//获取队元素public int Rear() {if(isEmpty()) {return -1;}int index = (rear==0)?elem.length-1:rear-1;return elem[index];}
}
五、二叉树
1.相同的树
链接
java">/*** 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 boolean isSameTree(TreeNode p, TreeNode q) {//1.一个为空，一个不为空if((p == null && q != null) || (p != null && q == null)) return false;//2.此时 都不为空 或者都为空if(p == null && q == null) return true;if(p.val != q.val) return false;//return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}2.另一颗树的子树
链接
java">/*** 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 boolean isSameTree(TreeNode p,TreeNode q) {if((p == null && q != null) || (p != null && q ==null)) return false;if(p == null && q == null) return true;if(p.val != q.val ) return false;return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null) return false;if(isSameTree(root,subRoot)) return true;return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}
}3.翻转二叉树
链接
java">/*** 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 TreeNode invertTree(TreeNode root) {if(root == null) return null;TreeNode ret = root.left;root.left = root.right;root.right = ret;invertTree(root.left);invertTree(root.right);return root;}
}4.平衡二叉树
链接
一棵树是平衡二叉树，那么这棵树的每棵子树的高度差都不超过1
O(n^2)
java">/*** 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 int getHeight(TreeNode root) {if(root == null) return 0;int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}public boolean isBalanced(TreeNode root) {if(root == null) return true;int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left) &&isBalanced(root.right);}
}O(n)
java">/*** 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 int getHeight(TreeNode root) {if(root == null) return 0;int leftHeight = getHeight(root.left);if(leftHeight < 0) return -1;int rightHeight = getHeight(root.right);if(Math.abs(leftHeight - rightHeight) <= 1 && leftHeight >=0 && rightHeight >=0) {return Math.max(leftHeight,rightHeight) + 1;}else {return -1;}}public boolean isBalanced(TreeNode root) {if(root == null) return true;return getHeight(root) >= 0;}
}5.对称二叉树
链接
java">/*** 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 boolean isSymmetric(TreeNode root) {if(root == null) return true;return isSymmetricCilk(root.left,root.right);}public boolean isSymmetricCilk(TreeNode leftNode,TreeNode rightNode) {if((leftNode == null && rightNode != null)|| (leftNode != null && rightNode == null)) return false;if(leftNode == null && rightNode == null) return true;if(leftNode.val != rightNode.val) return false;return isSymmetricCilk(leftNode.left,rightNode.right)&& isSymmetricCilk(leftNode.right,rightNode.left);}
}6.1层序遍历
链接
java">/*** 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<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> lists = new ArrayList<>();if(root == null) return lists;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> list = new ArrayList<>();int size = queue.size();while (size != 0) {TreeNode cur = queue.poll();size--;list.add(cur.val);if (cur.left != null)queue.offer(cur.left);if (cur.right != null)queue.offer(cur.right);}lists.add(list);}return lists;}
}6.2层序遍历2
链接
java"> public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> lists = new ArrayList<>();if (root == null) return lists;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new ArrayList<>();while (size != 0) {TreeNode cur = queue.poll();list.add(cur.val);if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);size--;}lists.add(list);}
//反转listsCollections.reverse(lists);return lists;}7.二叉树遍历
链接
java">import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
class TreeNode {public char value;public TreeNode left;public TreeNode right;public TreeNode(char value) {this.value = value;}
}
public class Main {public static int i = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();TreeNode root = createTree(str);inOrder(root);}}public static TreeNode createTree(String str) {TreeNode root = null;if (str.charAt(i) != '#') {root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);}else {i++;}return root;}public static void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);System.out.print(root.value + " ");inOrder(root.right);}
}8.二叉树的最近公共祖先
链接
java">/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left; n* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return root;if(root == p ||root == q) return root;TreeNode lefttree = lowestCommonAncestor(root.left,p,q);TreeNode righttree = lowestCommonAncestor(root.right,p,q); if(lefttree != null && righttree != null) {return root;}else if(lefttree != null) {return lefttree;}else {return righttree;}}
}java">/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Stack<TreeNode> stackP =new Stack<>();Stack<TreeNode> stackQ =new Stack<>();getPath(root,p,stackP);getPath(root,q,stackQ);int sizeP = stackP.size();int sizeQ = stackQ.size();if(sizeP > sizeQ) {int size = sizeP - sizeQ;while(size!=0) {size--;stackP.pop(); }}else {int size = sizeQ- sizeP;while(size!=0) {size--;stackQ.pop();}}while(!stackP.isEmpty() && !stackQ.isEmpty()) {TreeNode val1 = stackP.pop();TreeNode val2 = stackQ.pop();if(val1 == val2) {return val1;}}return null;}private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {if(root == null) return false;stack.push(root);if(root == node) return true;boolean flg = getPath(root.left,node,stack);if(flg) return true;flg = getPath(root.right,node,stack);if(flg) return true;stack.pop();return false;}
}9.从前序与中序遍历序列构造二叉树
链接
java">/*** 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 int preIndex = 0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChilde(preorder, inorder, 0, inorder.length - 1);}public TreeNode buildTreeChilde(int[] preorder, int[] inorder, int inbegin, int inend) {if(inbegin > inend) return null;TreeNode root = new TreeNode(preorder[preIndex]);int rootIndex = findVal(inorder,inbegin,inend,preorder[preIndex]);preIndex++;root.left = buildTreeChilde(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChilde(preorder,inorder,rootIndex+1,inend);return root;}private int findVal(int[] inorder, int inbegin, int inend, int key) {for(int i = inbegin;i <= inend; i++) {if(inorder[i] == key) {return i;}}return -1;}
}10.从中序与后序遍历序列构造二叉树
链接
java">/*** 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 int postIndex = 0;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length - 1;return buildTreeChilde(inorder,postorder,0,inorder.length-1);}public TreeNode buildTreeChilde(int[] inorder, int[] postorder, int inbegin, int inend) {if(inbegin>inend) return null;TreeNode root = new TreeNode(postorder[postIndex]);int rootIndex = findVal(inorder,inbegin,inend,postorder[postIndex]);postIndex--;root.right = buildTreeChilde(inorder,postorder,rootIndex+1,inend);root.left = buildTreeChilde(inorder,postorder,inbegin,rootIndex-1);return root;}private int findVal(int[] inorder,int inbegin, int inend, int key) {for(int i = inbegin;i<=inend;i++) {if(inorder[i] == key) {return i;}}return -1;}
}11.根据二叉树创建字符串
链接
java">/*** 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 String tree2str(TreeNode root) {StringBuilder stringBuilder = new StringBuilder();tree2strChild(root,stringBuilder);return stringBuilder.toString();}public void tree2strChild(TreeNode root,StringBuilder stringBuilder) {if(root == null) return;stringBuilder.append(root.val);if(root.left!=null) {stringBuilder.append("(");tree2strChild(root.left,stringBuilder);stringBuilder.append(")");}else {if(root.right==null) {return;}else {stringBuilder.append("()");}}if(root.right!=null) {stringBuilder.append("(");;tree2strChild(root.right,stringBuilder);stringBuilder.append(")");}else {return;}}
}12.二叉树前序非递归遍历实现
链接
java">/*** 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<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if (root == null) {return list;}TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);list.add(cur.val);cur = cur.left;}cur = stack.pop();cur = cur.right;}return list;}
}13.二叉树中序非递归遍历实现
链接
java">/*** 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> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if(root == null) return list;TreeNode cur = root;while(cur!=null || !stack.isEmpty()) {while(cur!=null) {stack.push(cur);cur = cur.left;}cur = stack.pop();list.add(cur.val);cur = cur.right;}return list;}
}14.二叉树后序非递归遍历实现
链接
java">/*** 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> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();if(root == null) return list;TreeNode cur = root;TreeNode prev = null;while(cur!=null || !stack.isEmpty()) {while(cur!=null) {stack.push(cur);cur = cur.left;}TreeNode top = stack.peek();if(top.right==null || top.right==prev) {stack.pop();list.add(top.val);prev = top;}else {cur = top.right;}}return list;}
}六、优先级队列(堆)
1.最小K个数
链接
时间复杂度：O(n*logn)
java">class Solution {public int[] smallestK(int[] arr, int k) {if(arr == null || k == 0) return new int[0];PriorityQueue<Integer> minHead = new PriorityQueue<>();for (int i = 0; i < arr.length; i++) {minHead.offer(arr[i]);}int[] ret = new int[k];for (int i = 0; i < k; i++) {ret[i] = minHead.poll();}return ret;}
}1.先把前K个元素创建为大小为K的大根堆
2.从第K+1个元素开始，每个元素都与堆顶元素进行比较
3.如果堆顶元素大于当前i下标的元素，那么出堆，把当前i下标的元素入堆
4.最后堆中的元素，就是前K个最小的元素
（且堆顶元素就是第K小元素）
时间复杂度O(N*logK)
七、Map和Set
1.只出现一次的数字
链接
java">class Solution {public int singleNumber(int[] nums) {Set<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; i++) {if (!set.contains(nums[i])) {set.add(nums[i]);} else {set.remove(nums[i]);}}for (int i = 0; i < nums.length; i++) {if (set.contains(nums[i])) {return nums[i];} }return -1;}
}2.随机链表的复制
链接
java">/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();Node cur = head;while(cur!=null) {Node node = new Node(cur.val);map.put(cur,node);cur = cur.next;}cur = head;while(cur!=null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}
}3.宝石与石头
链接
java">class Solution {public int numJewelsInStones(String jewels, String stones) {Set<Character> set = new HashSet<>();int count = 0;for(int i = 0;i<jewels.length();i++) {char ch = jewels.charAt(i);set.add(ch);}for(int i = 0;i<stones.length();i++) {char ch = stones.charAt(i);if(set.contains(ch)) {count++;}}return count;}
}4.坏键盘打字
链接
java">import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str1 = in.nextLine();String str2 = in.nextLine();func(str1, str2);}}public static void func(String str1, String str2) {str1 = str1.toUpperCase();str2 = str2.toUpperCase();Set<Character> set = new HashSet();Set<Character> setBroken = new HashSet();for (char ch : str2.toCharArray()) {set.add(ch);}for (char ch : str1.toCharArray()) {if (!set.contains(ch) && !setBroken.contains(ch)) {System.out.print(ch);setBroken.add(ch);}}}
}5.前K个高频词
链接
八、二叉搜索树
1.二叉搜索树与双向链表
链接
非递归：
java">import java.util.*;
/**
public class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}}
*/
public class Solution {public TreeNode Convert(TreeNode pRootOfTree) {TreeNode root = pRootOfTree;if(root == null) return null;Queue<TreeNode> queue = new LinkedList<>();queue = inorderTraversal(root);root = queue.poll();TreeNode prev = root;while(!queue.isEmpty()) {TreeNode cur = queue.poll();prev.right = cur;cur.left = prev;prev = cur;}return root;}public Queue<TreeNode> inorderTraversal(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();if(root == null) return queue;TreeNode cur = root;while(cur!=null || !stack.empty()) {while(cur!=null) {stack.push(cur);cur = cur.left;}cur = stack.pop();queue.offer(cur);cur = cur.right;}return queue;}
}递归：
java">public class Solution {//返回的第一个指针，即为最小值，先定为nullpublic TreeNode head = null; //中序遍历当前值的上一位，初值为最小值，先定为nullpublic TreeNode pre = null; public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTree == null)//中序递归，叶子为空则返回return null; //首先递归到最左最小值 Convert(pRootOfTree.left); //找到最小值，初始化head与preif(pre == null){ head = pRootOfTree;pre = pRootOfTree;}//当前节点与上一节点建立连接，将pre设置为当前值else{ pre.right = pRootOfTree;pRootOfTree.left = pre;pre = pRootOfTree;}Convert(pRootOfTree.right);return head;}
}
