Leetcode: 367.有效的完全平方数
367. 有效的完全平方数
解题思路： 这题主要是优化的方法采取了二分法的方法，是可以作为一些题目中遍历搜索的优化解的。其余的就是注意int的乘法会造成越界，结果应该转换为long类型来存储。
以下是C++代码：
123456789101112131415161718192021class Solution {public: bool isPerfectSquare(int num) { //二分法思路优化 int left=0; int right=num; int half; while(left<=right){ half=(left+right)/2; long temp=(long)half*half; if(num==temp){ return true; }else if(num<temp){ ...
Leetcode: 575.分糖果
575. 分糖果
解题思路： 这题比较简单，一共有两种解题思路。
用hash表记录下当前糖果种类，在其与平均分数目之间取最小值
模拟整个分配过程，现将第一个分给妹妹，后续用leftCount记录下剩余可以分配的数量，并且在排序后通过candyType[i]>candyType[i-1]判断是否是新种类
以下是C++代码：
1234567891011121314151617181920212223242526272829303132class Solution {public: int distributeCandies(vector<int>& candyType) { //方法1： //用hash表记录下当前糖果种类 // unordered_map<int,int> m; // for(auto type:candyType){ // ++m[type]; // } // int t ...
Leetcode 500.键盘行
500. 键盘行
解题思路： 这题主要就是用哈希表记录下对应字符的行数，而后遍历所有的words判断字符串是否在同一行即可，时间复杂度为O(n*m)（n为words长度，m为单个word长度）
以下为C++代码：
123456789101112131415161718192021222324class Solution {private: int ch2line[26]={ 2,3,3,2,1,2,2,2,1,2,2,2,3,3,1,1,1,1,2,1,1,3,1,3,1,3 };public: vector<string> findWords(vector<string>& words) { int length=words.size(); vector<string> res; for(int i=0;i<length;i++){ string word=words[i]; ...
Leetcode 260:只出现一次的数字 III
260. 只出现一次的数字 III
解题思路： 这题首先最简单的方法肯定是遍历+哈希表记录次数的方法，主要说第二种优化了空间复杂度的方法。
遍历nums的所有元素并进行异或处理，得到temp
获取temp的最低位1，由此就可以将恰好出现一次的两个元素分成两组
temp^(-temp)的方法获取最低位1（-temp其实对应二进制的取反+1，若原位为1则变为0，+1后&为1，若原位为0则变为1，+1后向前进位且&结果为0，因此恰好可以获取到最低位1）
设定lowOne=1，while(lowOne&temp==0) lowOne<<=1; （也就是逐步左移判断）
遍历nums的所有元素，根据得到得到lowOne*nums[i]判断所在组，同组的所有元素再进行异或操作，就能得到两个结果，返回即可。
以下是C++代码：
123456789101112131415161718192021222324252627282930class Solution {public: vector<int> singleNum ...
Leetcode: 335.路径交叉
335. 路径交叉
解题思路： 这种归纳的题目是真的不太熟且感觉意义不大。。，根据题解，最多只需要关注最近所画的五条边即可，且总共具有四种可能的情况，如下图所示，分别根据四种可能的情况列出if的判断式子即可。
以下为C++代码：
12345678910111213141516class Solution {public: bool isSelfCrossing(vector<int>& distance) { //一道类似归纳的题目 //只需要关注近5条边即可 int length=distance.size(); for(int i=3;i<length;i++){ //第一种情况 if (distance[i-1]<=distance[i-3]&&distance[i]>=distance[i-2]) return true; if (i>=4&&a ...
869. 重新排序得到2的幂
869. 重新排序得到 2 的幂
解题思路： 这题是可以说是把两道题混合在了一起，分别是47. 全排列 II和231. 2 的幂，先通过前者求出全排列（回溯），当判断出现了符合要求的数后对后续进行剪枝操作即可。
注意Swap交换数字位置进行迭代之后要再通过Swap进行还原
以下是C++代码：
123456789101112131415161718192021222324252627282930313233343536373839404142class Solution {private: bool isSucc;public: bool reorderedPowerOf2(int n) { //求全排列后逐个判断是否是2的幂 isSucc=false; string str=to_string(n); sort(str.begin(),str.end()); //先进行排序(减少无用的匹配次数) GetAllOrder(str,0,str.size()); r ...
Leetcode: 301 删除无效的括号
301. 删除无效的括号
解题思路： 这题采用了BFS的思路，因为题目要求中需要删除最少的无效括号来满足要求。所以我们采用了层级划分的方法。
每次递归都会遍历删除相同数量的括号所有字符串，判断其是否合法，合法则将其加入到结果res的向量中
每次递归都会在第一步后判断ans的数量是否大于0，大于则表示当前层级是删除最少的无效括号的情况，直接return即可
若无ans，则用nextSet记录下下一个层级的所有可能字符串(用str.substr(0,i)+str.substr(i+1)来进行切割)，△注意这里即便判断了s[i]==s[i-1]执行continue，还是需要set来进行去重操作，因为在最后只剩下一个括号时会导致重复情况。
以下是C++代码：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950class Solution {public: vector<string> ans; vector<st ...
Leetcode: 496 下一个更大元素 I
496. 下一个更大元素 I
解题思路： 这题通过暴力法的话时间复杂度为O(nums1.length*nums2.length)。
但是能引出一种时间复杂度为O(nums1.length+nums2.length)的思路，即单调栈+哈希表的方法。
整体思路(s为栈,m为哈希表,res为结果向量)：
反向遍历nums2，每次遍历时在栈中令s.top()和nums2[i]进行比较，排出栈中所有比nums2[i]小的元素，将栈顶元素结果存储在m[nums2[i]]中，并在最后将nums2[i]加入到栈中
遍历nums1，每次遍历时将其在m中对应结果加入到res中（即res.push_back(m[nums1[i]])）;
△这种思路同样能引用于在vector中寻找第一个满足于某个条件的元素，只需要通过单调栈+反向遍历的方式即可，在遍历时循环判断若当前栈顶元素满足时遍历元素是否一定满足，若是则弹出栈顶元素即可。最后再将遍历元素加入到栈顶元素中。
以下为C++代码：
1234567891011121314151617181920212223242526class ...
Leetcode: 240 搜索二维矩阵 II
240. 搜索二维矩阵 II
解题思路： 这道题的关键是找到右上角作为起始点，这样的话整个矩阵就能看做是一个二叉搜索树。
以n,m为行列，判断情况如下：
如果target<matrix[n][m]，则取二叉搜索树中的左子树，即n–
如果target>matrix[n][m]，则取二叉搜索树中的右子树，即m++
如果target==matrix[n][m]，则直接返回true
以下为C++代码：
1234567891011121314151617class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { //从右上角开始二叉树搜索 int n=0,row=matrix.size(),m=matrix[0].size()-1; while(n<row&&m>=0){ if(target<ma ...
Leetcode: 638大礼包（记忆化DFS）
638. 大礼包
解题思路：基础代码： 近期花时间比较长的一道题，一开始以为是动态规划的题目，后面发现思路走不通换成DFS的思路。主要还是通过深搜+剪枝来获取所有可能的情况，而后通过min()来获取其最小值。
用minPrice来作为最小值的记录，在最外层for循环结束（即当前层级的所有可能性结束后）返回
记录下lastPrice，其作为递归向下寻找可能性的依据，需要作为参数单独传入dfs函数中,一开始是把minPrice传进去，思路肯定是不对的（这样的话totalPrice就没办法保存下来了）。
记录下curPackagePrice，表示当前购买礼包所花费的价钱，根据其和needs计算后续的总价格totalPrice。
在每次循环过后要对needs和curPackagePrice进行还原
注意：minPrice仅代表当前DFS层级上的最小价格。
以下为C++代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 ...