LeetCode 1164, 125, 94

2024-06-20 22:20
文章标签 leetcode 125 94 1164

本文主要是介绍LeetCode 1164, 125, 94,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1164. 指定日期的产品价格
    • 题目链接
    • 要求
    • 知识点
    • 思路+代码
  • 125. 验证回文串
    • 题目链接
    • 标签
    • 简单版
      • 思路
      • 代码
    • 复杂版
      • 思路
      • 代码
  • 94. 二叉树的中序遍历
    • 题目链接
    • 标签
    • 递归
      • 思路
      • 代码
    • 迭代
      • 思路
      • 代码

1164. 指定日期的产品价格

题目链接

1164. 指定日期的产品价格

  • Products的字段为product_idnew_pricechange_date

要求

  • 编写一个解决方案,找出在 2019-08-16 时全部产品的价格,假设所有产品在修改前的价格都是 10 。
  • 任意顺序 返回结果表。

知识点

  1. in:有一次限制多个字段的功能。例如:
where(id, num)
in (selectid,numfromtb_stock
)

此语句将idnum限制到从tb_stock表中查询到的结果,注意 ()中的字段数 与 子表查询到的字段数 必须是相同的。

  1. max():求最大值的函数。
  2. ifnull():共传入两个参数,如果第一个参数是null,则返回第二个参数。例如ifnull(null, 'no')将会返回no
  3. left join:左连接,将 左表的所有数据 和 右表与左表的交集数据 查询出来。
  4. distinct:对字段的相同值进行去重。

思路+代码

找出在 2019-08-16 时全部产品的价格,
所以需要先查出更新的产品的在 2019-08-16 之前的最迟更新日期max_change_date

selectproduct_id,max(change_date) max_change_date
fromProducts
wherechange_date <= '2019-08-16'
group byproduct_id

然后再求出这些产品在最迟更新日期max_change_date更新的价格new_price

selectproduct_id,new_price
fromProducts
where (product_id,change_date
) in (selectproduct_id,max(change_date) max_change_datefromProductswherechange_date <= '2019-08-16'group byproduct_id
)

最后查出所有的产品id,然后将查到new_price的产品的价格返回,将没有查到new_price的产品按价格为10返回。注意,由于要查出所有的产品id,然后再与 查到new_price部分产品id 进行多表查询,所以得使用 外连接,本题使用了 左外连接 left join

selectid_cnt.product_id,ifnull(new_price, 10) price
from (selectdistinct product_idfromProducts) id_cnt
left join (selectproduct_id,new_pricefromProductswhere (product_id,change_date) in (selectproduct_id,max(change_date) max_change_datefromProductswherechange_date <= '2019-08-16'group byproduct_id)) price_cnt
onid_cnt.product_id = price_cnt.product_id

125. 验证回文串

题目链接

125. 验证回文串

标签

双指针 字符串

简单版

思路

本题的思路很明确,先将所有大写字符转换为小写字符,并移除所有非字母数字字符,然后再对剩下的字符串进行是否是回文串的判断。

是否是回文串可以使用双指针的做法,左指针left从字符串头部向尾部遍历,右指针right从字符串尾部向头部遍历,直到 两个指针相遇 或 左指针的值 比 右指针的值 大,如果发现左指针和右指针指向的字符不相同,则返回false;若能退出遍历,则说明这个字符串是一个回文串,返回true

代码

class Solution {public boolean isPalindrome(String s) {s = s.toLowerCase(); // 将所有大写字符转换为小写字符s = removeNonAlphaOrDight(s); // 移除所有非字母数字字符char[] chars = s.toCharArray();int left = 0, right = chars.length - 1;while (left < right) {if (chars[left] != chars[right]) {return false;}left++;right--;}return true;}// 移除字符串s中的所有非字母数字字符private String removeNonAlphaOrDight(String s) {char[] chars = s.toCharArray();StringBuilder builder = new StringBuilder();for (char ch : chars) {if (Character.isLetterOrDigit(ch)) {builder.append(ch);}}return builder.toString();}
}

复杂版

思路

简单版的执行用时比较长,因为对源字符串进行了 转换 和 移除 的操作。如果不想浪费这些时间,就得在 指针 和 判断 这两个点下功夫:当指针指向 非字符数字字符(空格也是非字符数字字符) 时跳过这个字符,并且需要 在判断左右指针指向的字符是否相等前 将字符转化为小写。

代码

class Solution {public boolean isPalindrome(String s) {char[] chars = s.toCharArray();int left = 0, right = chars.length - 1;while (left < right) {if (!Character.isLetterOrDigit(chars[left])) {left++;continue;}if (!Character.isLetterOrDigit(chars[right])) {right--;continue;}char leftChar = Character.toLowerCase(chars[left]);char rightChar = Character.toLowerCase(chars[right]);if (leftChar != rightChar) {return false;}left++;right--;}return true;}
}

94. 二叉树的中序遍历

题目链接

94. 二叉树的中序遍历

标签

栈 树 深度优先搜索 二叉树

递归

思路

中序遍历就是先遍历本节点的左子节点,然后处理本节点的值,最后遍历本节点的右子节点

例如对于下面这个二叉树:
二叉树

中序遍历这个二叉树的结果是[1, 2, 3, 4, 5, 6, 7],过程为:

从节点4开始
往节点2走
往节点1走
往节点1的左子节点走,发现是null
返回到节点1,输出节点1的值
往节点1的右子节点走,发现是null
返回到节点1,返回到节点2,输出节点2的值
往节点3走
往节点3的左子节点走,发现是null
返回到节点3,输出节点3的值
往节点3的右子节点走,发现是null
返回到节点2,返回到节点4,输出节点4的值
往节点6走
往节点5走
往节点5的左子节点走,发现是null
返回到节点5,输出节点5的值
往节点5的右子节点走,发现是null
返回到节点6,输出节点6的值
往节点7走
往节点7的左子节点走,发现是null
返回到节点7,输出节点7的值
往节点7的右子节点走,发现是null
返回节点6,返回节点4,完毕

理解如上的过程后就清晰了,使用递归将此过程模拟一遍就是如下代码:

代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();inorder(root, res);return res;}private void inorder(TreeNode curr, List<Integer> res) {if (curr == null) { // 如果遇到空节点return; // 直接返回}inorder(curr.left, res); // 先遍历左子节点res.add(curr.val); // 再处理本节点的值inorder(curr.right, res); // 最后遍历右子节点}
}

迭代

思路

使用递归能做出来的题,使用迭代也可以,只不过迭代比较难罢了

对二叉树的前序遍历、中序遍历和后序遍历本质上都是深度优先搜索,即遍历时不是一层一层遍历,而是顺着一个方向走到头,然后再回过头来处理这些值。对于这样的遍历,可以使用 将递归转化为迭代:顺着一个方向走时先将这些节点存起来,然后再弹出最近保存的节点进行处理。

递归的思想和迭代的思想是一样的,只不过实现方式不同,迭代时得分类讨论

当遍历的节点curr不为null时,就先将本节点curr加入栈stack中,然后往左子节点curr.left遍历;

否则遍历的节点currnull,此时还得根据 最近一次加入栈的节点peek = stack.peek() 的右子节点的不同进行分类讨论。

只有在没遍历右子节点时才需要对本节点进行操作(这是中序遍历的思想),当它的右子节点peek.right不是最近一次弹出栈的节点pop时,说明此时还没有遍历右子节点,应该操作本节点,然后弹出并记录本节点pop = stack.pop();当它的右子节点peek.rightnull时,也可以将其看作没有遍历右子节点的情况,操作本节点,然后弹出并记录本节点pop = stack.pop();如果不是以上两种情况,则是peek.right是最近一次弹出栈的节点pop的情况,这意味着已经遍历过右子节点了,只需要弹出并记录本节点pop = stack.pop()即可。

分类讨论到处结束,如果还不是很懂,就看看代码吧。

代码

class Solution {public List<Integer> inorderTraversal(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> res = new ArrayList<>();TreeNode curr = root; // 当前节点TreeNode pop = null; // 最近一次弹出栈的节点while (!stack.isEmpty() || curr != null) {if (curr != null) { // 如果这个节点不为nullstack.push(curr); // 将这个节点保存到栈中curr = curr.left; // 让节点往左子节点走} else { // 此时对应某节点的左子节点为null的情况TreeNode peek = stack.peek(); // 查看最近一次加入栈中的节点if (peek.right == null) { // 没有右子节点 也算 右子节点没有遍历res.add(peek.val); // 处理本节点的值pop = stack.pop(); // 将本节点从栈中弹出,并保存它} else if (peek.right != pop) { // 此时还没有遍历右子节点res.add(peek.val); // 处理本节点的值curr = peek.right; // 将本节点从栈中弹出,并保存它} else { // 此时 最近一次弹出栈的节点 是 最近一次加入栈的节点的右子节点,表示已经处理完了右子节点pop = stack.pop(); // 将本节点弹出,并保存它}}}return res;}
}

这篇关于LeetCode 1164, 125, 94的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1079419

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

【JavaScript】LeetCode:21-25

文章目录 21 最大子数组和22 合并区间23 轮转数组24 除自身以外数组的乘积25 缺失的第一个正数 21 最大子数组和 贪心 / 动态规划贪心:连续和(count)< 0时,放弃当前起点的连续和,将下一个数作为新起点,这里提供使用贪心算法解决本题的代码。动态规划:dp[i]:以nums[i]为结尾的最长连续子序列(子数组)和。 dp[i] = max(dp[i - 1]