HOT100-12-打家劫舍
题目描述你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 1： 1234输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 具体见题目描述。 算法描述这道题目我在去年备考蓝桥杯做过，用的是Python，可能还有点印象，很典型的dp问题，我们可以这样想，小偷如果偷到了第n家（第n家还没偷），那么他所要考虑的事情就是，如果偷了第n家，那么第n-1家的钱就不能偷盗了，只能偷n-2家的钱加上第n家的钱，因此，我们假定dp[i]表示偷盗到第i家所有得到的最多的钱的数目，那么就必然有： dp[i] = max(dp[i - 1], dp[i - 2] +...
HOT100-11-岛屿数量
题目描述给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 示例 1： 1234567输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ...
HOT100-10-反转链表
题目描述给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 12输入：head = [1,2,3,4,5]输出：[5,4,3,2,1] 具体见题目详解。 算法思路这是很常见的模版题，多使用几个指针指来指去（bushi）就可以了，差不多可以看这个图片，我比较懒，就直接借鉴大佬的博客了： 这相当于是一种迭代解题思路，代码如下： 1234567891011121314class Solution {public: ListNode* reverseList(ListNode* head) { ListNode * pre = nullptr; ListNode *nxt = head, *curr = head; while (nxt != nullptr) { nxt = curr->next; curr->next = pre; pre = curr; curr =...
HOT100-9-课程表
题目描述你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。 示例 1： 123输入：numCourses = 2, prerequisites = [[1,0]]输出：true解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0...
HOT100-8-实现Trie（前缀树）
题目描述Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。 请你实现 Trie 类： Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word 。 boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。 boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。 示例： 1234567891011121314输入["Trie", "insert", "search", "search", "startsWith", "insert",...
HOT100-7-数组中的第K个最大元素
题目描述给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 12输入: [3,2,1,5,6,4], k = 2输出: 5 具体见题目详解。 算法思路 这个题目要求 O(n)复杂度排序，这个其实很难想得到，一般的排序都是 $O(n^2)$或者$O(nlog_2n)$，能达到$O(n)$的只有基数排序，桶排序等等非比较算法，我首先借鉴了个桶排序算法，其主要思路是分治和快排，具体可以看这个思路。代码如下： 1234567891011121314151617181920212223242526272829303132333435class Solution { void bucketSort(vector<int>& nums, int bucketSize) { if (nums.empty()) return; ...
HOT100-6-最大正方形
题目描述在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 示例 1： 12输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：4 算法思路 这道题目很明显我是不会的！我只能暴力求解，主要思路是：对于matrix[i][j]，将其作为正方形的左上角，遍历寻找最大的正方形，复杂度是 O(mn*min(m,...
HOT100-5-翻转二叉树
题目描述给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 示例 1： 12输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1] 具体见题目描述。 算法思路 这个第一眼就很容易想到使用递归+DFS， 一直搜到最下面的叶子结点，然后对于第 n-1层，交换第 n层的两个节点即可。代码如下： 12345678910111213141516171819class Solution {public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) { return nullptr; } if (root->left == nullptr && root->right == nullptr) { return nullptr; } if...
HOT100-4-每日温度
题目描述给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。 示例 1: 12输入: temperatures = [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0] 具体见题目描述。 算法思路这道题我写的自认为是$O(n)$的复杂度，但仔细分析后其实应该接近$O(n^2)$算法很简单：直接从当前温度开始找下一个温度高的天数即可，代码如下： 123456789101112131415161718192021222324252627282930313233class Solution {public: vector<int> dailyTemperatures(vector<int>& temperatures) { vector<int> ans; if...
HOT100-3-回文链表
题目描述给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 示例 1： 12输入：head = [1,2,2,1]输出：true 具体见题目描述 算法思路 这道题想要时间复杂度O(n)是很简单的，我写了双指针和反转数组两种方法，感觉效率都还说的过去，但是空间上不行，首先看一下反转数组： 方法一：反转数组 这个很容易理解，直接把链表的值读进一个数组，再把数组倒序，如果$list = reverse(list)$，那么很容易知道这是回文的，代码如下： 123456789101112131415161718192021class Solution {public: bool isPalindrome(ListNode* head) { vector<int> val_vector; ListNode *tmp = head; if (tmp == nullptr) { return...