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...
HOT100-2-二叉树最近公共祖先
题目描述给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例 1： 123输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出：3解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 具体见题目链接。 算法思路 ...
HOT100-1-相交链表
题目描述给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。 图示两个链表在节点 c1 开始相交 ： 如图所示，则输出C1；具体见题目链接：题目链接 题目思路这道题目我是不会的……我只能想到暴力破解，就是通过两层循环进行遍历，找到最开始的地址相同的节点，伪代码差不多是这样：： 1234567891011tmpA = headA;while(tmpA != NULL) { tmpB = headB; while (tmpB != NULL) { if (tmpA != tmpB) { return tmpA; } tmpB = tmpB->next; }} return NULL; ...
argcxiang's first blog
Hello, there is argcxiang, I am testing my blog on GitHub! I come from Wuhan University, majoring in Information Security, and I am interesting with some technology skills. The reason why I created this Blog is to record some experience in coding exercise, which is for next year’s summer camp, I hope all we can enter to our dream school. Thanks!