地址：https://leetcode-cn.com/problems/majority-element 题目给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [3,2,3] 输出: 3示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2解题思路思路很简单，就是遍历数组记录每一个元素的个数，由于最终是要返回元素，所以需要将元素和其个数成对保存，我使用了 vector<pair<int, int>> 的数组来存储。 遍历数组，先到 aNums[] 中查找 num 是否已存在，如果已存在则将其个数+1；不存在，则将其添加到 aNums[] 并将其个数初始化为1。 题目已经说明“给定的数组总是存在多数元素”，所以可以确定出现次数大于 ⌊ n/2 ⌋ 的多数元素有且仅有一个。所以每遍历一个元素，我们就判断其个数是否大于 nums.size() / 2 ，一旦有一个元素的个数大于 nums.size() / 2 则说明这个元

地址：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/ 题目对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。 示例 1： 输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC"示例 2： 输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB"示例 3： 输入：str1 = "LEET", str2 = "CODE" 输出：""提示： 1 <= str1.length <= 1000 1 <= str2.length <= 1000 str1[i] 和 str2[i] 为大写英文字

地址：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/ 题目给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。 形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。 示例 1： 输出：[0,2,1,-6,6,-7,9,1,2,0,1] 输出：true 解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1示例 2： 输入：[0,2,1,-6,6,7,9,-1,2,0,1] 输出：false示例 3： 输入：[3,3,6,5,-2,2,5,1,-9,4] 输出：true 解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4提示： 3

地址：https://leetcode-cn.com/problems/diameter-of-binary-tree/ 题目给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 示例 :给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 注意：两结点之间的路径长度是以它们之间边的数目表示。 解题思路首先这个题需要注意一点，整棵树的最长路径，不一定是左右子树的深度相加，因为可能最长路径并没有经过根结点。但是可以确定的是，最长路径一定是某一个结点作为根节点的左右子树的深度相加。 所以如果求出每一个结点作为根结点的左右子树的深度，也就可以找出所有可能的最长路径，只需要不断更新最大长度即可。 代码/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *le

地址：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 题目给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。解题思路这个题其实不是第一次遇上了，初学C++的时候就做过这个题，有几个需要注意的地方是： 需要判别数组为空的情况，此时利润为0可以直接返回； 不能在买入股票前卖出股票，所以不是单纯找数组的最小值、最大值； 股票价格起伏不定，阶段性的买入卖出获得的是阶段性的最大利润，所以在

地址：https://leetcode-cn.com/problems/coin-change/ 题目给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1示例 2: 输入: coins = [2], amount = 3 输出: -1说明: 你可以认为每种硬币的数量是无限的。 解题思路解题思路参考官方题解~ 一开始的时候自己尝试做这道题，首先想到的办法是将硬币按面值从小到大排序，然后尽可能多的取面较值大的，最终将不同面值的硬币个数加起来即题解。但后来发现，其实有时候并不是面值越大的越多就符合题意，因为会有取面值小一点的才能组合成总金额的情况，所以这个思路是错误的。 然后我参考了官方的题解的自上而下的动态规划法！ 官方题解：https://leetcode-cn.com/problems/coin-change/solution/322-li

地址：https://leetcode-cn.com/problems/maximum-subarray/ 题目给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 解题思路笨办法！遍历所有可能的子序并计算其子序和，不断地更新最大子序和。 代码class Solution { public: int maxSubArray(vector<int>& nums) { int maxSum = nums[0];//子序和 for (int i = 0; i < nums.size(); i++) { //查找并更新从每一个数开始的所有可能子序的子序和 int sum = 0;//以nums[i]开头的子序的子

地址：https://leetcode-cn.com/problems/length-of-last-word/ 题目给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。 如果不存在最后一个单词，请返回 0 。 说明：一个单词是指仅由字母组成、不包含任何空格字符的最大子字符串。 示例： 输入: "Hello World" 输出: 5解题思路一开始想着就是遍历字符串，思路是每遇到一个单词的第一个字符就开始统计这个单词的长度，然后找到最后的这个单词就可以了。 后来一下子想到，反过来逆序遍历不就好了，而且只需要遍历完逆序的第一个单词即可结束遍历，实现起来很简单。 代码class Solution { public: int lengthOfLastWord(string s) { int length = 0;//单词长度 for (int i = s.length() - 1; i >= 0; i--)

地址：https://leetcode-cn.com/problems/add-binary/ 题目给定两个二进制字符串，返回他们的和（用二进制表示）。 输入为非空字符串且只包含数字 1 和 0。 示例 1: 输入: a = "11", b = "1" 输出: "100"示例 2: 输入: a = "1010", b = "1011" 输出: "10101"解题思路这个题不可避免的要处理十进制和二进制之间的转换问题，按照二进制求和的方法，从低位到高位依次相加。 定义一个 car 记录进位，默认为 0 即没有进位，有进位只可能为 1 ；定义一个 string 类型的 sum 用以保存得到的和；定义两个int型变量 cur_a 和 cur_b 保存两个字符串相同位置上的字符转为 int 型后的值，方便进行常规加法计算，若字符串为空则作 0 处理，效果等同于没有数与之相加；x 保存某一位上的相加结果，以根据其相加的结果进行进位处理。 因为是二进制加法，x 可能的取值情况

地址：https://leetcode-cn.com/problems/sqrtx/ 题目实现 int sqrt(int x) 函数。 计算并返回 x 的平方根，其中 x 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。 示例 1: 输入: 4 输出: 2示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842...，由于返回类型是整数，小数部分将被舍去。解题思路采用二分法求解。 平方根一定是 >= 0 的，则 low 取初始值为0；平方根不大于这个数的一半再+1，所以 up 取初始值为 x / 2.0 + 1.0，然后两头向中间逼近。题目要求只保留整数部分，小数部分舍去，所以平方根将最终的 mid 取整。 代码class Solution { public: int mySqrt(int x) { double low = 0;//平方根一定是 >= 0 的 double up = x / 2.0 + 1.0;//平方根不大于这个数的一半再+1 double mid;