# code **Repository Path**: liwei9292/code ## Basic Information - **Project Name**: code - **Description**: No description available - **Primary Language**: Unknown - **License**: Apache-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2022-05-08 - **Last Updated**: 2022-05-26 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 算法题整理 ## 链表 ### 反转链表 时间复杂度 o(n) ```java public ListNode ReverseList(ListNode head) { if(head==null){ return head; } ListNode cur=head,pre=null; while(cur!=null){ ListNode temp=cur.next; cur.next=pre; pre=cur; cur=temp; } return pre; } ``` ### 链表内指定区间反转 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。 时间复杂度 ```java public ListNode reverseBetween (ListNode head, int m, int n) { // write code here ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; // 移动到m-1的位置 for (int i = 0; i < m - 1; i++) { pre = pre.next; } // ListNode cur = pre.next; ListNode curNext; // 移动中间的这些几点 for (int i = 0; i < n - m; i++) { curNext = cur.next; cur.next = curNext.next; curNext.next = pre.next; pre.next = curNext; } return dummy.next; } ``` ### 链表中的节点每k个一组翻转 将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表 如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样 你不能更改节点中的值，只能更改节点本身。 时间复杂度o(n) ```java /** * k 个一组翻转链表 * * @param head * @param k * @return */ public ListNode reverseKGroup(ListNode head, int k) { // write code here ListNode dummy = new ListNode(0); dummy.next = head; ListNode pre = dummy; // 前驱 ListNode end = dummy; // 最后一个节点 while (end.next != null) { for (int i = 0; i < k && end != null; i++) { end = end.next; } if (end == null) { break; } ListNode start = pre.next; ListNode next = end.next; end.next = null; // 将end这里截断 pre.next = reverse(start); // 这里翻转 start.next = next; // 翻转后将start.next=next pre = start; // 前驱变为start end = start; //end 也变为start ,下一次继续循环即可 } return dummy.next; } // 链表翻转 private ListNode reverse(ListNode head) { ListNode pre = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; } ``` ### 合并两个排序的链表 输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。 数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ```java public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode pre = new ListNode(-1); ListNode cur = pre; while (list1 != null || list2 != null) { if (list1 == null) { cur.next = list2; break; } if (list2 == null) { cur.next = list1; break; } // if (list1.val > list2.val) { cur.next = list2; list2 = list2.next; } else { cur.next = list1; list1 = list1.next; } cur = cur.next; } return pre.next; } ``` ### 判断链表中是否有环 判断给定的链表中是否有环。如果有环则返回true，否则返回false。 ```java 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 (slow == fast) { return true; } } return false; } ``` ### 链表中环的入口结点 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。 ```java public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow = pHead; ListNode fast = pHead; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (slow == fast) { break; } } // 没有环 if (fast == null || fast.next == null) { return null; } // 慢指针回到头节点， 再次相遇时则是环的入口 slow = pHead; while (slow != fast) { slow = slow.next; fast = fast.next; } return fast; } ``` ### 链表中倒数最后k个结点 输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。 如果该链表长度小于k，请返回一个长度为 0 的链表。 ```java public ListNode FindKthToTail(ListNode pHead, int k) { // write code here if (pHead == null) { return pHead; } ListNode dummy = new ListNode(-1); dummy.next = pHead; ListNode right = dummy; // 移动到k的位置 while (k-- > 0) { // 这里需要判断为null 的情况，右边走到底为null了 right = right.next; if(right==null){ return null; } } ListNode left = dummy; while (right.next != null) { left = left.next; right = right.next; } // left下一个节点就是 return left.next; } ``` ### 删除链表的倒数第n个节点 给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针 例如， 给出的链表为: 1\to 2\to 3\to 4\to 51→2→3→4→5, n= 2n=2. 删除了链表的倒数第 nn 个节点之后,链表变为1\to 2\to 3\to 51→2→3→5. 空间 O(n) 时间o(1) ```java /** * 标签：链表 * 整体思路是让前面的指针先移动n步，之后前后指针共同移动直到前面的指针到尾部为止 * 首先设立预先指针 pre，预先指针是一个小技巧，在第2题中进行了讲解 * 设预先指针 pre 的下一个节点指向 head，设前指针为 start，后指针为 end，二者都等于 pre * start 先向前移动n步 * 之后 start 和 end 共同向前移动，此时二者的距离为 n，当 start 到尾部时，end 的位置恰好为倒数第 n 个节点 * 因为要删除该节点，所以要移动到该节点的前一个才能删除，所以循环结束条件为 start.next != null * 删除后返回 pre.next，为什么不直接返回 head 呢，因为 head 有可能是被删掉的点 * 时间复杂度：O(n)O(n) * * @param head * @param n * @return */ public ListNode removeNthFromEnd(ListNode head, int n) { ListNode pre = new ListNode(-1); pre.next = head; ListNode start = pre, end = pre; // while (n-- > 0) { start = start.next; } // while (start.next != null) { start = start.next; end = end.next; } end.next = end.next.next; return pre.next; } ``` ### 链表相加（二） 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。 给定两个这种链表，请生成代表两个整数相加值的结果链表。 数据范围：0 \le n,m \le 10000000≤n,m≤1000000，链表任意值 0 \le val \le 90≤val≤9 要求：空间复杂度 O(n)，时间复杂度 O(n) 思路： 1、先翻转链表 2、然后一个一个取出来相加，记得有一个进位 3、构建新的链表从末尾往头构建。 solution: ```java public ListNode addInList(ListNode head1, ListNode head2) { // write code here ListNode reverse1 = reverse(head1); ListNode reverse2 = reverse(head2); // 链表是从后面往前走 ListNode newListNode = null; ListNode last = null; int carry = 0; while (reverse1 != null || reverse2 != null || carry != 0) { int x = reverse1 == null ? 0 : reverse1.val; int y = reverse2 == null ? 0 : reverse2.val; int sum = x + y + carry; carry = sum / 10; newListNode = new ListNode(sum % 10); newListNode.next = last; last = newListNode; if (reverse1 != null) { reverse1 = reverse1.next; } if (reverse2 != null) { reverse2 = reverse2.next; } } return last; } private ListNode reverse(ListNode listNode) { if (listNode == null) { return listNode; } ListNode pre = null, cur = listNode; while (cur != null) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } ``` ### 单链表的排序 给定一个节点数为n的无序单链表，对其按升序排序。 时间复杂度 O(nlogn) 空间复杂度o(n) ```java public ListNode sortInList(ListNode head) { // write code here PriorityQueue listNodes = new PriorityQueue<>((a, b) -> a.val - b.val); while (head != null) { listNodes.add(head); head = head.next; } ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (listNodes.size() > 0) { // peek 为第一个元素 cur.next = listNodes.peek(); listNodes.poll(); cur = cur.next; } cur.next = null; return dummy.next; } ``` ### 判断一个链表是否为回文结构 给定一个链表，请判断该链表是否为回文结构。 回文是指该字符串正序逆序完全一致。 时间复杂度：O(n)，其中nnn为链表的长度，遍历链表转化数组为O(n)，双指针遍历半个数组为O(n) 空间复杂度 o(n) ,记录元素的辅助数组 ```java public boolean isPail (ListNode head) { // write code here List nodeList = new ArrayList<>(); ListNode cur = head; while (cur != null) { nodeList.add(cur.val); cur = cur.next; } // 使用双指针判断是否回文 int front = 0; int back = nodeList.size() - 1; while (front < back) { if (!nodeList.get(front).equals(nodeList.get(back))) { return false; } front++; back--; } return true; } ``` ### 链表的奇偶重排 给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。 注意是节点的编号而非节点的数值。 空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n) ```java ```java public ListNode oddEvenList(ListNode head) { if (head == null) { return head; } ListNode evenHead = head.next; // odd 扫描奇数节点 even 扫描偶数节点 ListNode odd = head, even = evenHead; while (even != null && even.next != null) { // 奇数节点的next =偶数的next odd.next = even.next; odd = odd.next; // 偶数 。next=奇数的next even.next = odd.next; even = even.next; } // 奇数的next =偶数的头 odd.next = evenHead; return head; } ``` ### 删除有序链表中重复的元素-I 删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次 例如： 给出的链表为1\to1\to21→1→2,返回1 \to 21→2. 给出的链表为1\to1\to 2 \to 3 \to 31→1→2→3→3,返回1\to 2 \to 31→2→3. ```java public ListNode deleteDuplicates(ListNode head) { // write code here if (head == null || head.next == null) { return head; } ListNode cur = head; while (cur.next != null) { if (cur.val == cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; } ``` ### 删除有序链表中重复的元素-II 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。 例如： 给出的链表为1 \to 2\to 3\to 3\to 4\to 4\to51→2→3→3→4→4→5, 返回1\to 2\to51→2→5. 给出的链表为1\to1 \to 1\to 2 \to 31→1→1→2→3, 返回2\to 32→3. ```java public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } ListNode dummy = new ListNode(-1000, head); ListNode cur = dummy; // while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { int x = cur.next.val; // 开始一个一个移除 直接将cur nex -> next.next, while (cur.next != null && cur.next.val == x) { cur.next = cur.next.next; } } else { cur = cur.next; } } return dummy.next; } ``` ### 旋转链表 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 ```java /** * 链表旋转 * 遍历链表两次，快慢指针 * * * @param head * @param k * @return */ public ListNode rotateRight(ListNode head, int k) { if (k == 0 || head == null || head.next == null) { return head; } ListNode cur = head; int len = 0; // 统计链表长度： while (cur != null) { len++; cur = cur.next; } // 对k 简化 k %= len; if (k == 0) { return head; } ListNode fast = head; // 快指针 fast 先走k步： while (k-- > 0) { fast = fast.next; } // 快慢指针一起前进到末尾 ListNode slow = head; while (fast.next != null) { fast = fast.next; slow = slow.next; } /** * s f * i i i i i i * newHead */ ListNode newHead = slow.next; slow.next = null; fast.next = head; return newHead; } ``` ### 两个链表的第一个公共结点 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的） 数据范围： n \le 1000n≤1000 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ```java public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null || headB==null){ return null; } ListNode pa=headA,pb=headB; // while (pa!=pb){ pa=pa==null?headB:pa.next; pb=pb==null?headA:pb.next; } return pb; } ``` ### 两两交换链表中的节点 solution pre start end * * * ```java public ListNode swapPairs(ListNode head) { if (head == null) { return null; } if (head.next == null) { return head; } ListNode pre = new ListNode(-1); pre.next = head; ListNode temp = pre; while (temp.next != null && temp.next.next != null) { ListNode start = temp.next; ListNode end = temp.next.next; temp.next = end; start.next = end.next; end.next = start; temp = start; } return pre.next; } ``` ### 单链表在时间复杂度为O(1)删除链表结点 ```java 解题思路： solution: public ListNode delete(ListNode head, ListNode toBeDelete){ if(head==null ||head.next==null){ return null; } // 删除的节点在末尾 if(toBeDelete.next!=null){ ListNode index=head; while (index.next!=toBeDelete){ index=index.next; } index.next=toBeDelete.next; }else { //不在末尾 ,直接改数值， toBeDelete.val=toBeDelete.next.val; toBeDelete.next=toBeDelete.next.next; } return head; } 复杂度分析： 对于n-1个非尾部结点而言删除的时间复杂度为O（1），对于尾部结点删除而言，仍然需要O（n）的时间复杂度。 但是平均时间复杂度是：[ ( n - 1 ) * O( 1 ) + O( n ) ] / n，结果还是O（1）。 ``` ### 两个链表的第一个公共节点 ### 合并k个已排序的链表 ## 树 ### 二叉树的前序遍历 ```java /** * 前序遍历 stack来实现 * * @param root * @return */ public List preorderTraversal2(TreeNode root) { Stack stack = new Stack<>(); TreeNode node = root; List result = new ArrayList(); while (node != null || !stack.empty()) { // 直接将当前的值放进去 if (node != null) { result.add(node.val); stack.push(node); node = node.left; } else { TreeNode tem = stack.pop(); node = tem.right; } } return result; } ``` ### 二叉树的中序遍历 ```java public List inorderTraversal(TreeNode root) { List result = new ArrayList<>(); Stack stack = new Stack<>(); while (!stack.isEmpty() || root != null) { //不断往左子树方向走，每走一次就将当前节点保存到栈中 //这是模拟递归的调用 if (root != null) { stack.push(root); root = root.left; } else { //当前节点为空，说明左边走到头了，从栈中弹出节点并保存 //然后转向右边节点，继续上面整个过程 TreeNode pop = stack.pop(); result.add(pop.val); root = pop.right; } } return result; } ``` ### 二叉树的后续遍历 ```java public List postOrder(TreeNode root) { List result = new LinkedList<>(); if (root == null) { return new LinkedList<>(); } Stack stack = new Stack<>(); TreeNode pre = null; while (root != null || !stack.isEmpty()) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); // 右子树为空 或者右节点被访问过了 ，每次访问的节点用pre 表示，如果右节点存在 // ，那么上次已访问的节点==right,则说明访问过了 // 否则，将root 在此入栈 ,同时root=null，继续弹出下一个 if (root.right == null || root.right == pre) { result.add(root.val); pre = root; root = null; } else { stack.push(root); root = root.right; } } return result; } ``` ### 二叉树的层序遍历 ```java public List bfs(TreeNode root) { if (root == null) { return null; } List result = new ArrayList<>(); Queue queue = new ArrayDeque<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode poll = queue.poll(); result.add(poll.val); if (poll.left != null) { queue.add(poll.left); } if (poll.right != null) { queue.add(poll.right); } } return result; } ``` ### 按之字形顺序打印二叉树 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替） ```java public ArrayList > Print(TreeNode pRoot) { TreeNode head = pRoot; ArrayList > res = new ArrayList>(); if(head == null) //如果是空，则直接返回空list return res; //队列存储，进行层次遍历 Queue temp = new LinkedList(); temp.offer(head); TreeNode p; boolean flag = true; while(!temp.isEmpty()){ //记录二叉树的某一行 ArrayList row = new ArrayList(); int n = temp.size(); //奇数行反转，偶数行不反转 flag = !flag; //因先进入的是根节点，故每层节点多少，队列大小就是多少 for(int i = 0; i < n; i++){ p = temp.poll(); row.add(p.val); //若是左右孩子存在，则存入左右孩子作为下一个层次 if(p.left != null) temp.offer(p.left); if(p.right != null) temp.offer(p.right); } //奇数行反转，偶数行不反转 if(flag) Collections.reverse(row); res.add(row); } return res; } ``` ### n叉树的前序遍历 ```java public List preOrder(Node root) { List result = new LinkedList<>(); if (root == null) { return result; } Stack stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { Node pop = stack.pop(); result.add(pop.val); List children = pop.children; if (children != null) { for (int i = children.size() - 1; i >= 0; --i) { stack.push(children.get(i)); } } } return result; } ``` ### n叉树的后序遍历 ```java public List postOrder(Node root) { List res = new LinkedList<>(); if (root == null) { return res; } Stack stack = new Stack<>(); stack.push(root); Set visited = new HashSet<>(); while (!stack.isEmpty()) { // 这里如果不用peek 那后面还要push Node pop = stack.peek(); // /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */ if (pop.children.size() == 0 || visited.contains(pop)) { // 弹出 stack.pop(); res.add(pop.val); continue; } for (int i = pop.children.size() - 1; i >= 0; i--) { stack.push(pop.children.get(i)); } visited.add(pop); } return res; } ``` ### 二叉树的最大深度 求给定二叉树的最大深度， 深度是指树的根节点到任一叶子节点路径上节点的数量。 最大深度是所有叶子节点的深度的最大值。 ```java // dfs public int maxDepth(TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } ``` ### 二叉树的最小深度 ```java public int minDepth(TreeNode root) { if(root == null) return 0; //这道题递归条件里分为三种情况 //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可 if(root.left == null && root.right == null) return 1; //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度 int m1 = minDepth(root.left); int m2 = minDepth(root.right); //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1; if(root.left == null || root.right == null) return m1 + m2 + 1; //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可 return Math.min(m1,m2) + 1; } ``` ### 二叉树的最大宽度 给定一个二叉树，请你求出此二叉树的最大宽度。 本题中树第 i 层的宽度定义为：第 i 层最左边的节点到最右边之间的距离，中间空节点也计入距离。 bfs ```java public int maxDepth(TreeNode root) { if(root == null) return 0; List queue = new LinkedList<>() {{ add(root); }}, tmp; int res = 0; while(!queue.isEmpty()) { tmp = new LinkedList<>(); for(TreeNode node : queue) { if(node.left != null) tmp.add(node.left); if(node.right != null) tmp.add(node.right); } queue = tmp; res++; } return res; } ``` ### 二叉树中和为某一值的路径(一) 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n ```java public boolean hasPathSum (TreeNode root, int sum) { if(root==null){ return false; } if(root.left==null&& root.right==null && sum==root.val){ return true; } return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val); } ``` ### 二叉树中和为某一值的路径(二) [niuke](https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=117&tqId=37718&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=undefined&judgeStatus=undefined&tags=583&title=) 输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n ### 二叉树中和为某一值的路径(三) 给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。 1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点 2.总节点数目为n 3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1) ### 对称的二叉树 ```java public boolean isSymmetric(TreeNode root) { return root == null ? true : recur(root.left, root.right); } boolean recur(TreeNode L, TreeNode R) { if(L == null && R == null) return true; if(L == null || R == null || L.val != R.val) return false; return recur(L.left, R.right) && recur(L.right, R.left); } ``` ### 合并二叉树 已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替 ```java public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if(t1==null || t2==null) { return t1==null? t2 : t1; } return dfs(t1,t2); } TreeNode dfs(TreeNode r1, TreeNode r2) { // 如果 r1和r2中，只要有一个是null，函数就直接返回 if(r1==null || r2==null) { return r1==null? r2 : r1; } //让r1的值 等于 r1和r2的值累加，再递归的计算两颗树的左节点、右节点 r1.val += r2.val; r1.left = dfs(r1.left,r2.left); r1.right = dfs(r1.right,r2.right); return r1; } ``` ### 二叉树的镜像 操作给定的二叉树，将其变换为源二叉树的镜像 ```java public TreeNode mirrorTree(TreeNode root) { if(root == null) return null; TreeNode tmp = root.left; root.left = mirrorTree(root.right); root.right = mirrorTree(tmp); return root; } ``` ### 判断是不是二叉搜索树 给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。 二叉搜索树满足每个节点的左子树上的所有节点均严格小于当前节点且右子树上的所有节点均严格大于当前节点。 ```java public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean isValidBST(TreeNode node, long lower, long upper) { if (node == null) { return true; } if (node.val <= lower || node.val >= upper) { return false; } return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper); } ``` ### 判断是不是完全二叉树 给定一个二叉树，确定他是否是一个完全二叉树。 完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点） ### 二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先. 2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值 3.所有节点的值都是唯一的。 4.p、q 为不同节点且均存在于给定的二叉搜索树中。 ```java /** * 二叉树的公共祖先 * * 解题思路： * 1、 首先判断root 为p或者q, 那么root 就是祖先， * 2、 如果root不是， 那么分别做左右子树分别找p,q * 3、 如果其中一方找不到，那么说明，pq在同一个子树中， 并且pq其中就是祖先 * 4、 都找不到，那么root就是 * * 采用递归的方法 * @param root * @param p * @param q * @return */ public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null|| root==p||root==q){ return root; } TreeNode leftRoot=lowestCommonAncestor(root.left,p,q); TreeNode rightRoot=lowestCommonAncestor(root.right,p,q); if(leftRoot==null){ return rightRoot; } if(rightRoot==null){ return leftRoot; } return root; } ``` ### 重建二叉树 给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示 ### 输出二叉树的右视图 请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图 ### 二叉树每层的最大值 ```java /** * 每一层的最大值 * 利用队列 广度优先 *

* 每一层比较Max * * @param root * @return */ public List largestValues(TreeNode root) { List result = new LinkedList<>(); Queue queue = new LinkedList<>(); if (root == null) { return result; } queue.add(root); while (!queue.isEmpty()) { int num = Integer.MIN_VALUE; int size = queue.size(); // 这一层一个一个弹出 for (int i = 0; i < size; i++) { TreeNode treeNode = queue.poll(); num = Math.max(treeNode.val, num); if (treeNode.left != null) { queue.add(treeNode.left); } if (treeNode.right != null) { queue.add(treeNode.right); } } result.add(num); } return result; } ``` ### 二叉搜索树的第k大节点 ```java /** * 找到第k大的数 * * @param root * @param k * @return */ private int kth; private int k; public int kthLargest(TreeNode root, int k) { this.k = k; dfs(root); return kth; } private void dfs(TreeNode root) { if (root == null) { return; } dfs(root.right); if (--k == 0) { kth = root.val; return; } dfs(root.left); } ``` ### 二叉树根节点到叶子节点的所有路径和 [ 牛客](https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId=117&tqId=37715&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D117&difficulty=undefined&judgeStatus=undefined&tags=583&title=) 给定一个二叉树的根节点root，该树的节点值都在数字\ 0-9 0−9 之间，每一条从根节点到叶子节点的路径都可以用一个数字表示。 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点 2.叶子节点是指没有子节点的节点 3.路径只能从父节点到子节点，不能从子节点到父节点 4.总节点数目为n ### 修剪叶子 有一棵有\mathit nn个节点的二叉树，其根节点为\mathit rootroot。修剪规则如下: 1.修剪掉当前二叉树的叶子节点，但是不能直接删除叶子节点 2.只能修剪叶子节点的父节点，修剪了父节点之后，叶子节点也会对应删掉 3.如果想在留下尽可能多的节点前提下，修剪掉所有的叶子节点。请你返回修剪后的二叉树。 ## 堆/栈/队列 ### 用两个栈实现队列 用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。 ```java Stack stack1 = new Stack(); Stack stack2 = new Stack(); public void push(int node) { stack1.push(node); } public int pop() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } ``` ### 包含min函数的栈 ```java /** * 包含min函数的栈 */ class MinStack { Stack A, B; public MinStack() { A = new Stack<>(); B = new Stack<>(); } public void push(int x) { A.add(x); // 如果x<=B 栈顶的元素，则需要压榨，这里可以避免重复最小值被弹出，重复的值也会压栈 if (B.isEmpty() || x <= B.peek()) { B.add(x); } } public void pop() { //将b弹出，表示最小值已经弹出 if (A.pop().equals(B.peek())) { B.pop(); } } public int top() { return A.peek(); } public int min() { return B.peek(); } } ``` ### 有效括号序列 ### 寻找第K大 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。 ```java /** * 找到第k大的元素 * 小顶堆 * * @param a * @param n * @param K * @return */ public int findKth(int[] a, int n, int K) { // write code here PriorityQueue priorityQueue = new PriorityQueue<>(); for (int num : a) { if(priorityQueue.size()B *

* M= size(A)+size(B), M是所有的元素， 规定 当M为奇数，A 多存一个元素， M为偶数，A，B存的元素一样多 *

* 中位数： M为偶数（size(A)=size(B)）, MID=pop(A)+pop(B)/2.0 * M为奇数数，mid=POP(A); */ class MedianFinder { private PriorityQueue a; private PriorityQueue b; /** * initialize your data structure here. */ public MedianFinder() { a = new PriorityQueue<>((o1, o2) -> o1 - o2); b = new PriorityQueue<>((o1, o2) -> o2 - o1); } public void addNum(int num) { if(a.size()!=b.size()){ // 需要将元素加给b a.add(num); b.add(a.poll()); }else{ // 偶数，需要将元素加给a b.add(num); a.add(b.poll()); } } public double findMedian() { // 注意这里不能用poll return a.size()!=b.size()?a.peek():(a.peek()+b.peek())/2.0; } } ``` ### 滑动窗口的最大值 ### 表达式求值 ## 递归、回溯 ### 没有重复项数字的全排列 给出一组数字，返回该组数字的所有排列 例如： [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. （以数字在数组中的位置靠前为优先级，按字典序排列输出。） ### 有重复数字的全排列 给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。 ## 动态规划 ### 斐波那契数列 大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。 斐波那契数列是一个满足 fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.fib(x)={ 1 fib(x−1)+fib(x−2) ​ x=1,2 x>2 ​ 的数列 数据范围：1\leq n\leq 401≤n≤40 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n) ，本题也有时间复杂度 O(logn)O(logn) 的解法 o(n) ```java public int fib(int n) { if(n==0||n==1){ return n; } // a b 分别代表f(n-1)和f(n-2） int a = 0, b = 1, sum=a+b; for(int i = 2; i < n; i++){ a = b; b = sum; sum = (a + b) % 1000000007; } return sum; } ``` ### 跳台阶 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 ```java /** * 跳台阶 * @param target * @return */ public int jumpFloor(int target) { if (target <= 2) { // 1 和2 return target; } int fn1 = 1, fn2 = 2; int result = 0; for (int i = 3; i <= target; i++) { result = fn1 + fn2; fn1 = fn2; fn2 = result; } return result; } ``` ### 最小花费爬楼梯 给定一个整数数组 cost \cost ，其中 cost[i]\cost[i] 是从楼梯第i \i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费 ```java /** * 最小花费爬楼梯 * @param cost * @return */ public int minCostClimbingStairs(int[] cost) { int minCost0 = 0; int minCost1 = Math.min(cost[0], cost[1]); int minCost = 0; for (int i = 2; i < cost.length; i++) { minCost = Math.min(minCost1 + cost[i], minCost0 + cost[i - 1]); minCost0 = minCost1; minCost1 = minCost; } return minCost; } ``` ### 连续子数组的最大和 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。 时间复杂度o(n) ```java /** * 连续子数组的最大和 *

* 解题思路： * pre=Math.max(pre+x,x); * 1、 最大子数组之和= Math.max(pre,maxNum) * * @param nums * @return */ public int maxSubArray(int[] nums) { int pre = 0, max = nums[0]; for (int i : nums) { pre = Math.max(pre + i, i); max = Math.max(pre, max); } return max; } ``` ### 无重复字符的最长子串 ```java /** * 无重复字符的最长子串 *

* 解题思路： 使用滑动窗口，每次将left的位置滑动 * * @param s * @return */ public int lengthOfLongestSubstring(String s) { if(s.length()==0){ return 0; } Map map = new HashMap<>(); int left = 0, max = 0; char[] chars = s.toCharArray(); for (int i = 0; i < chars.length; i++) { if (map.containsKey(chars[i])) { // a b c b a 这种情况， // 像左移动一个字符 left = Math.max(map.get(chars[i])+1, left); } // 更新最新的char的位置 map.put(chars[i],i); // 这里要加1 因为index 从0开始算， 1-0， 长度应该为2 max = Math.max(max, i - left+1); } return max; } ``` ### 最长公共子串 给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。 空间复杂度o(n2)时间 o(n2) ### 买卖股票的最好时机(一) 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天 2.如果不能获取到任何利润，请返回0 3.假设买入卖出均无手续费 ```java /** * 买卖股票的最佳时机 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 *

* 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 *

* 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 *

* 解题思路： * 1、 定义一个min值指针，遍历时每次都比较 * 2、 定义一个maxProfit指针，用单前遍历的值去减min， 然后定义max * * @param prices * @return */ public int maxProfit(int[] prices) { int min = Integer.MAX_VALUE; int maxProfit = 0; for (int i : prices) { min = Math.min(min, i); maxProfit = Math.max(maxProfit, i - min); } return maxProfit; } ``` ## 二分查找/排序 ### 二分查找 请实现无重复数字的升序数组的二分查找 给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1 ```java public int search (int[] nums, int target) { int l = 0; int r = nums.length - 1; //从数组首尾开始，直到二者相遇 while(l <= r){ //每次检查中点的值 int m = (l + r) / 2; if(nums[m] == target) return m; //进入左的区间 if(nums[m] > target) r = m - 1; //进入右区间 else l = m + 1; } //未找到 return -1; } ``` ### 请实现有重复数字的升序数组的二分查找 ```java public int search (int[] nums, int target) { int l = 0; int h = nums.length-1; int mid = 0; while(l<=h){ mid = (l+h)/2; if(nums[mid] == target){ while(mid != 0 && nums[mid]==nums[mid-1]){ mid--; } return mid; } else if(nums[mid]>target){ h = mid-1; } else{ l = mid+1; } } return -1; //查找失败 } } ``` ### 二维数组中的查找 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数 ```java public boolean Find(int target, int [][] array) { // 最右上开始 int col = array.length - 1, row = 0; while (col >= 0 && row < array[0].length) { if (array[col][row] > target) { col--; } else if (array[col][row] < target) { row++; } else { return true; } } return false; } ``` ###　统计数在排序数组中出现次数 ```java /** * 统计数在排序数组中出现次数 * 1、暴力解法，直接遍历 *

* 2、 二分查找第一次和最后一次出现的地方 * * @param array * @param k * @return */ public int getNumberOfK(int[] array, int k) { int left = 0, right = array.length - 1; int firstPlace = getFirstPlace(array, k, left, right); int lastPlace = getLastPlace(array, k, left, right); return lastPlace - firstPlace + 1; } private int getFirstPlace(int[] array, int k, int left, int right) { // 递归 int mid = (left + right) / 2; int midVal = array[mid]; if (midVal > k) { // 继续向前找 return getFirstPlace(array, k, left, mid - 1); } else if (midVal < k) { // 向后找 return getFirstPlace(array, k, mid + 1, right); } else if (mid - 1 > 0 && array[mid - 1] == k) { return getFirstPlace(array, k, left, mid - 1); } else { return mid; } } private int getLastPlace(int[] array, int k, int left, int right) { // 用循环 while (left < right) { int mid = (left + right) / 2; if (array[mid] > k) { right = mid - 1; } else if (array[mid] < k) { left = mid + 1; } else if (mid + 1 < array.length && array[mid + 1] == k) { left = mid + 1; } else { return mid; } } return -1; } ``` ### 求平方根 ```java public int sqrt (int x) { // write code here int res = 0; // 注意转换为 long, 否则会产生溢出 while ((long)res * res <= x) { ++res; } return --res; } ``` ### 在旋转过的有序数组中寻找目标值 ###　旋转数组的最小数字 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。 ```java ```java /** * 题目描述 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 *

* 给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。   *

* 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 * * @param numbers * @return 解题思路： 使用二分法， 这个翻转之后的数组是形成了两个排序好的数组， *

* left num[right]时，那一定是右边 * left=mid+1 * 3、 num[mid]==num[right] * 相等的情况下， 只能取消right * right=right-1; */ public int minArray(int[] numbers) { if (numbers == null) { return -1; } int length = numbers.length; int right = length - 1; int left = 0; while (left < right) { int mid = (left + right) >>> 1; if (numbers[mid] == numbers[right]) { right = right - 1; } else if (numbers[mid] < numbers[right]) { right = mid; } else { left = mid + 1; } } // 最后left=right return numbers[left]; } ``` ## hash ###两数之和 ```java public int[] twoSum (int[] numbers, int target) { // write code here HashMap map = new HashMap<>(); //遍历数组 for (int i = 0; i < numbers.length; i++) { //将不包含target - numbers[i]，装入map中，包含的话直接返回下标 if(map.containsKey(target - numbers[i])) return new int[]{map.get(target - numbers[i])+1, i+1}; else map.put(numbers[i], i); } throw new IllegalArgumentException("No solution"); } ``` ###数组中出现次数超过一半的数字 ```java /** * 数组中出现次数超过一半的数字 * 思路： 摩尔投票法， x为票数，vnotes为票数， * 每次抵消之后一定还有剩余 * * @param array * @return */ public int MoreThanHalfNum_Solution(int[] array) { int x = 0, vnotes = 0; for (int num : array) { if (vnotes == 0) { x = num; } vnotes += num == x ? 1 : -1; } return x; } ``` ### 数组中只出现一次的两个数字 一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 ```java public int[] FindNumsAppearOnce (int[] array) { // write code here // write code here // 用于返回结果 int[] res = new int[2]; // 创建一个哈希表 HashMap set = new HashMap<>(); for(int i = 0; i < array.length; i++){ // 如果已经被当作key了，那就直接remove掉 if(set.containsKey(array[i])){ set.remove(array[i],null); }else{ // 否则就添加进去 set.put(array[i],null); } } int i = 0; // 最后拿出来放进返回结果的数组中进行返回 for(Integer num:set.keySet()){ res[i++] = num; } return res; } ``` ### 缺失的第一个正整数 给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数 进阶： 空间复杂度 O(1)，时间复杂度 O(n) 题解：https://leetcode-cn.com/problems/first-missing-positive/solution/tong-pai-xu-python-dai-ma-by-liweiwei1419/ 核心是构建一hash: 这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。 solution: ```java public int firstMissingPositive(int[] nums) { int len = nums.length; for (int i = 0; i < len; i++) { while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) { // 满足在指定范围内、并且没有放在正确的位置上，才交换 // 例如：数值 3 应该放在索引 2 的位置上 swap(nums, nums[i] - 1, i); } } // [1, -1, 3, 4] for (int i = 0; i < len; i++) { if (nums[i] != i + 1) { return i + 1; } } // 都正确则返回数组长度 + 1 return len + 1; } private void swap(int[] nums, int index1, int index2) { int temp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = temp; } ``` ### 最长无重复子数组 给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组 ```java public int maxLength(int[] arr) { int left = 0, right = 0, max = 0; Set set = new HashSet<>(); while (right < arr.length) { if (set.contains(arr[right])) { set.remove(arr[left++]); } else { set.add(arr[right++]); max = Math.max(max, set.size()); } } return max; } ``` ## 数组 ## 字符串 ### 最长公共前缀 给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。 ```java /** * 最长公共前缀 * 解题思路：纵向查找 * 1、 取出 str[0] 作为第一个字符串，用这个字符串的每一个字符逐个和 剩下的字符串的这个位置进行比较。 * 2、 如果比较到了j的末尾，或者该位置的字符不相同 * 放回 str[0].subString(0,i); * 3、全部匹配上那str[0]就是最长的前缀 * @param strs * @return */ public String longestCommonPrefix(String[] strs) { if(strs==null){ return ""; } int count=strs.length; int length=strs[0].length(); for(int i=0;i 0; i--) { int sum = s.charAt(i - 1)-'0' + t.charAt(i - 1)-'0' + carry; carry = sum / 10; sb.insert(0,sum%10); } if(carry>0){ sb.insert(0,carry); } return sb.toString(); } private static String insertZero(String s, int zeroSize) { StringBuilder sb = new StringBuilder(s); for (int i = 0; i < zeroSize; i++) { sb.insert(0, "0"); } return sb.toString(); } ``` ### 验证IP地址 编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址 IPv4 地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255， 用(".")分割。比如，172.16.254.1； 同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。 IPv6 地址由8组16进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。 然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。 同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。 说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。 ```java /** * 验证IP地址 * @param IP string字符串 一个IP地址字符串 * @return string字符串 */ public String solve (String IP) { // write code here return validIPv4(IP) ? "IPv4" : (validIPv6(IP) ? "IPv6" : "Neither"); } private boolean validIPv4(String IP) { String[] strs = IP.split("\\.", -1); if (strs.length != 4) { return false; } for (String str : strs) { if (str.length() > 1 && str.startsWith("0")) { return false; } try { int val = Integer.parseInt(str); if (!(val >= 0 && val <= 255)) { return false; } } catch (NumberFormatException numberFormatException) { return false; } } return true; } private boolean validIPv6(String IP) { String[] strs = IP.split(":", -1); if (strs.length != 8) { return false; } for (String str : strs) { if (str.length() > 4 || str.length() == 0) { return false; } try { int val = Integer.parseInt(str, 16); } catch (NumberFormatException numberFormatException) { return false; } } return true; } ``` ### 是否回文数字 ```java /** * 是否回文数字 * 解题思路： * 取出后半段数字翻转进行比较 *

* 如果取出后半段数字了翻转了， * 1、 先%10, 的到最后一位数字， 然后用这个数+ *10 *判断 x 是不是小于 revertNum ，当它小于的时候，说明数字已经对半或者过半了 * 最后，判断奇偶数情况：如果是偶数的话，revertNum 和 x 相等；如果是奇数的话，最中间的数字就在revertNum 的最低位上，将它除以 10 以后应该和 x 相等。 * @param x * @return */ public boolean isPalindrome(int x) { if (x < 0 || (x % 10 == 0 && x != 0)) { return false; } int reverseNum = 0; while (x > reverseNum) { reverseNum = reverseNum * 10 + x % 10; x /= 10; } return reverseNum == x || reverseNum / 10 == x; } ``` ### 有效的括号 ```java private static final Map map = new HashMap(){{ put('{','}'); put('[',']'); put('(',')'); put('?','?'); }}; /** * 是不是有效的括号 * @param s * @return */ public boolean isValid(String s) { // 不是已左括号开头 if(s.length()>0&& !map.containsKey(s.charAt(0))){ return false; } Stack stack = new Stack(); // 占位 stack.push('?'); for(Character c:s.toCharArray()){ if(map.containsKey(c)){ stack.push(c); }else { Character pop = stack.pop(); // 如果括号不能匹配，则直接false if(!map.get(pop).equals(c)){ return false; } } } return stack.size()==1; } ``` ##双指针 ### 判断是否为回文字符串 给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。 字符串回文指该字符串正序与其逆序逐字符一致。 ```java public boolean judge (String str) { //首指针 int left = 0; //尾指针 int right = str.length() - 1; //首尾往中间靠 while(left < right){ //比较前后是否相同 if(str.charAt(left) != str.charAt(right)) return false; left++; right--; } return true; } ``` ### 合并两个有序的数组 给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组 数据范围： 0 \le n,m \le 1000≤n,m≤100，|A_i| <=100∣A i ​ ∣<=100， |B_i| <= 100∣B i ​ ∣<=100 注意： 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印 3. A 数组在[0,m-1]的范围也是有序的 ```java public void merge(int A[], int m, int B[], int n) { int p1 = 0, p2 = 0; //新开一个M+n大小的数组 int[] sorted = new int[m + n]; int cur; //循环选择 while (p1 < m || p2 < n) { if (p1 == m) { cur = B[p2++]; } else if (p2 == n) { cur = A[p1++]; } else if (A[p1] < B[p2]) { cur = A[p1++]; } else { cur = B[p2++]; } sorted[p1 + p2 - 1] = cur; } //移动 后台程序会预先将A扩容为[4,5,6,0,0,0] for (int i = 0; i != m + n; ++i) { A[i] = sorted[i]; } } ```