- 227. 基本计算器 II
- 230. 二叉搜索树中第K小的元素
- 234. 回文链表
- 236. 二叉树的最近公共祖先
- 237. 删除链表中的节点
- 238. 除自身以外数组的乘积
- 239. 滑动窗口最大值
- 240. 搜索二维矩阵 II
- 242. 有效的字母异位词
- 268. 丢失的数字
给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
- 1 <= s.length <= 3 * 105
- s 由整数和算符 (’+’, ‘-’, ‘*’, ‘/’) 组成,中间由一些空格隔开
- s 表示一个有效表达式
- 表达式中的所有整数都是非负整数,且在范围 [0, 231 - 1] 内
- 题目数据保证答案是一个 32-bit 整数
示例:
输入:s = " 3+5 / 2 " 输出:5 输入:s = "3+2*2" 输出:7
解题思路:使用栈,将数字前面的算符记录下来,如果数字前面的算符是+,则直接将当前数字入栈,如果数字前面的算符是-,则将当前数的相反数入栈,如果数字前面的算符是 *,则将当前数字与栈顶元素做乘,并将结果入栈,如果数字前面的算符是 /,则将当前数字与栈顶元素左除,并将结果入栈。遍历完字符串后,此时将栈中的所有元素相加,即为表达式的值。
public int calculate(String s) { Stack230. 二叉搜索树中第K小的元素stack = new Stack<>(); int num = 0; char preSign = '+'; int len = s.length(); for(int i = 0;i < len; i++){ if(Character.isDigit(s.charAt(i))){ num = num * 10 + s.charAt(i)-'0'; } if(i == len - 1 || s.charAt(i) != ' ' && !Character.isDigit(s.charAt(i))){ switch (preSign){ case '+': stack.push(num); break; case '-': stack.push(-num); break; case '*': stack.push(stack.pop() * num); break; default: stack.push(stack.pop() / num); } preSign = s.charAt(i); num = 0; } } int ans = 0; while(!stack.isEmpty()){ ans += stack.pop(); } return ans; }
给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。
示例:
输入:root = [5,3,6,2,4,null,null,1], k = 3 输出:3
- 树中的节点数为 n 。
- 1 <= k <= n <= 104
- 0 <= Node.val <= 104
方法一:中序遍历
解题思路:使用中序遍历树,并记录遍历的个数,当为k个最小值,则返回。
// 记录遍历的个数 int index = 0; // 记录结果 int res = 0; public int kthSmallest(TreeNode root, int k) { // 中序遍历找打第 K 个数 dfs(root,k); return res; } public void dfs(TreeNode root,int k){ if(root == null){ return; } // 左 dfs(root.left,k); index++; // 中 if(index == k){ res = root.val; return; } // 右 dfs(root.right,k); }
方法二:二分法,对树的子树求个数,判断第 k个最小的元素在左子树还是右子树。进行递归查找
public int kthSmallest(TreeNode root, int k) { // 得到右边子树的个数 int leftNum = findChild(root.left); if(k <= leftNum){ // 第k个最小的元素在左边 return kthSmallest(root.left,k); } else if(leftNum + 1 == k){ // 当前元素是第k个最小的元素 return root.val; }else{ // 第k个最小的元素在右边 return kthSmallest(root.right,k-leftNum-1); } } public int findChild(TreeNode root){ if(root == null){ return 0; } return findChild(root.left)+findChild(root.right)+1; }234. 回文链表
给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例:
输入:head = [1,2,2,1] 输出:true
提示:
- 链表中节点数目在范围[1, 105] 内
- 0 <= Node.val <= 9
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
解题思路:快慢指针,使用快指针和慢指针,快指针走两步,慢指针走一步,等快指针到结尾,慢指针到中间位置。然后将后半部分链表反转,再判断是否为回文串。
public boolean isPalindrome(ListNode head) { ListNode fast,slow; fast = slow = head; if(fast.next == null){ return true; } while(fast.next != null && fast.next.next != null){ fast = fast.next.next; slow = slow.next; } // 此时 slow为链表的中间节点,将 slow.next置为null,将链表分割为两个子链表。 ListNode tmp,reversalHead = slow.next; slow.next = null; slow = reversalHead.next; reversalHead.next = null; // 将后半部分链表反转。 while(slow != null){ tmp = slow.next; slow.next = reversalHead; reversalHead = slow; slow = tmp; } // 比较两个链表 while(reversalHead != null){ if(reversalHead.val != head.val){ return false; } reversalHead = reversalHead.next; head = head.next; } return true; }236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出:3 解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出:5 解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
解题思路:对二叉树做递归遍历。先从最左边的节点考虑,如果该节点的左子树,或右子树分别包含其中一个元素,则该元素为最近公共祖先。或者该节点是其中一个节点,并且子树包含另一个节点,则该元素为最近公共祖先。
// ans 保存最近公共祖先。 TreeNode ans = null; public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { dfs(root,p,q); return ans; } public boolean dfs(TreeNode root,TreeNode p,TreeNode q){ if (root == null) return false; if( ans != null ){ return false; } boolean lson = dfs(root.left, p, q); boolean rson = dfs(root.right, p, q); // 子树包含两个元素或本身为其中一个元素,子树包含另一个。 if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) { ans = root; } // 返回是否包含其中一个元素,包含其中一个,或本身是另一个。 return lson || rson || (root.val == p.val || root.val == q.val); }237. 删除链表中的节点
请编写一个函数,用于删除单链表中某个特定节点 。在设计函数时需要注意,你无法访问链表的头节点 head ,只能直接访问要被删除的节点 。题目数据保证需要删除的节点不是末尾节点 。
示例:
输入:head = [4,5,1,9], node = 5 输出:[4,1,9] 解释:指定链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9
解题思路:将下一个节点的值,赋值给当前节点的值,将链表的最后一个节点删除。
public void deleteNode(ListNode node) { ListNode next = node.next; while(next.next != null){ // 将下一个节点的值赋给当前节点。 node.val = next.val; node = node.next; next = next.next; } node.val = next.val; // 将最后一个节点删除 node.next = null; }238. 除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4] 输出: [24,12,8,6]
提示:题目数据保证数组之中任意元素的全部前缀元素和后缀(甚至是整个数组)的乘积都在 32 位整数范围内。
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。
解题思路:new一个结果数组,对求解数组进行两次遍历求解,先求出每个元素的右边的乘积的和,然后再求出每个元素左边的所有元素的乘积的和,相加即可。返回结果数组。
public int[] productExceptSelf(int[] nums) { int[] output = new int[nums.length]; Arrays.fill(output,1); // 计算每个元素所有右边的和 for(int n = nums.length - 1;n > 0;n--){ output[n - 1] = nums[n] * output[n]; } // 计算每个元素所有左边的和,并加上所有右边的和,即为,除了自身整个数组的和。 int tmp = 1; for(int n = 1;n < nums.length; n++){ tmp *= nums[n - 1]; output[n] *= tmp; } return output; }239. 滑动窗口最大值
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例 :
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 ----------------------------------------- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
解题思路:使用单调队列,在队列中维护单调递减的属性,队列的头节点值最大,队列的尾节点值最小。
public int[] maxSlidingWindow(int[] nums, int k) { // 单调队列 Deque240. 搜索二维矩阵 IIdeque = new linkedList<>(); int[] ans = new int[nums.length - k + 1]; int right,left = 0; // 先将滑动窗口初始化,考虑数组中的前k个元素。 for(right = 0;right < k;right++){ // 维护一个单调队列,将元素按从大到小排序。 // 将比当前元素小的删除,因为不可能是滑动窗户的最大值。 while (!deque.isEmpty() && nums[right] >= nums[deque.peekLast()]) { deque.removeLast(); } // 将元素的下标放入队列 deque.addLast(right); } // 队列首元素就是滑动窗口的最大值。 ans[left] = nums[deque.peekFirst()]; for(;right < nums.length;right++){ while (!deque.isEmpty() && nums[right] >= nums[deque.peekLast()]) { deque.removeLast(); } deque.addLast(right); // 滑动窗口的左边界,每次加一 left++; // 如果当前队列的最大值不在滑动窗口内,出队列 if(left > deque.peekFirst()){ deque.removeFirst(); } // 将滑动窗口的最大元素放入结果集。 ans[left] = nums[deque.peekFirst()]; } return ans; }
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
输入:matrix = [[1,4,7,11,15], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 5 输出:true
解题思路:从右上角开始搜索,若值大于目标值,则向左搜索,若值小于目标值,则向下搜索。若数组越界,则说明矩阵中没有目标值。
public boolean searchMatrix(int[][] matrix, int target) { int m = matrix.length; int n = matrix[0].length; int i,j; i = 0; j = n-1; // 从 matrix[0][n-1]开始搜索,目标值大于该值,则向下搜索,小于则向左搜索。 while(i < m && j >= 0){ if(matrix[i][j] == target){ return true; }else if(matrix[i][j] > target){ j--; }else{ i++; } } return false; }242. 有效的字母异位词
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
示例 :
输入: s = "anagram", t = "nagaram" 输出: true
提示:
- 1 <= s.length, t.length <= 5 * 104
- s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
解题思路:哈希表,遍历字符串s,统计s中的每一个字符出现的次数,将字符出现的次数存储到哈希表中,然后遍历字符串 t,统计 t 中的每一个字符出现的次数。对比是否一致。
public boolean isAnagram(String s, String t) { int[] num = new int[26]; int i; for(i = 0;i268. 丢失的数字 给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例:
输入:nums = [9,6,4,2,3,5,7,0,1] 输出:8 解释:n = 9,因为有 9 个数字,所以所有的数字都在范围 [0,9] 内。 8 是丢失的数字,因为它没有出现在 nums 中。提示:
- n == nums.length
- 1 <= n <= 104
- 0 <= nums[i] <= n
- nums 中的所有数字都 独一无二
进阶:你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?
方法一:使用高斯公式求和,然后使用和减去数组中的每一个元素,最后的结果就是缺失的元素。
public int missingNumber(int[] nums) { int n = nums.length; // 数学,高斯公式 int missSum = n*(n+1)/2; for(int i = 0;i方法二:位运算,使用异或符号,对同一个数异或两次结果为0,分别对 0 - n进行异或,再对数组中的元素异或,最后的值就是缺失的元素。
public int missingNumber(int[] nums) { int xor = 0; int n = nums.length; for (int i = 0; i <= n; i++) { xor ^= i; } for (int i = 0; i < n; i++) { xor ^= nums[i]; } return xor; }欢迎分享,转载请注明来源:内存溢出
评论列表(0条)