开始刷LeetCode了，思考了很多东西，学习所有东西都不要畏惧，刚入门都是会很痛苦的，但是多总结，多思考，多练习，我认为总会从陌生到熟悉的，所以晚开始补入早开始，从今天开始刷LeetCode，我相信只要坚持一个月后回头看就不会恐慌了，加油少年！！！这篇博客主要记录刷题过程中遇到的问题。
程序最容易出错的地方：(以后在比赛或做题时就可以从这几个方面进行检查)
<1> 数组类型的端点判断总容易出现错误，很容易出现越界或者漏掉最后一个或第一个元素的判断。
<2> 逻辑判断符出错，可能出现想当然的使用，这是一定要严谨推导，才能避免错误。
<3> 二分法的使用时，要分清是那种情况，是普通二分法，寻找第一个大于等于的数的情况还是找第一个大于该数的情况，这几种情况的结束判断标准不一样，一定要仔细分析。
LeetCode-7
整型的最大值和最小值的问题
1.INT_MAX,INT_MIN数值大小
因为int占4字节32位，根据二进制编码的规则，INT_MAX = 2^31-1，INT_MIN= -2^31.C/C++中，所有超过该限值的数，都会出现溢出，出现warning，但是并不会出现error。如果想表示的整数超过了该限值，可以使用长整型long long 占8字节64位。
2.关于INT_MAX INT_MIN的运算
由于二进制编码按原码、补码和反码的规则进行运算，所有程序中对INT_MAX和INT_MIN的运算应当格外注意，在出现溢出的时候，不遵循数学规则。
INT_MAX + 1 = INT_MIN
INT_MIN - 1 = INT_MAX
abs(INT_MIN) = INT_MIN
比较有趣的是，INT_MAX + 1 < INT_MAX， INT_MIN - 1 > INT_MIN, abs(INT_MIN) < 0.
3.此题的题意是将整数翻转，当翻转过后可能会出现超界问题，需要用到整形的最大值和最小值问题，具体的判断是：1
2if (rev>INT_MAX/10||(rev==INT_MAX/10&&pop>7)) return 0;
if (rev<INT_MIN/10||(rev==INT_MIN/10&&pop<-8)) return 0;
其中变量rev是翻转过程中的数，pop是取的最近一位的数。
LeetCode-14
题目的问题是寻找几个字符串最长的相同前缀，我第一用STL库写所以不熟练，但是写了过后也没有觉得有多难，所以学习新东西的时候自己一定要有信心，all is well。
然后遇到的问题是，始终输出不了函数的返回值，经过调了很久，才发现问题的所在，就是在string类型的应用上：
当定义string类型的变量时，要在字符串后面添加元素时只能用push_back(),不能用“+”和“append()”，也不能直接用“=”赋值，我就犯了这个错误，因为在延长字符串时，后面的存储空间还没有给出来，所以没有地址，所以不要傻不拉几的用“=”一个一个给字符串元素赋值。
这里给一个详细网址里面有string类型封装好的所有函数的介绍string。
LeetCode-35
题目要求解决的问题是：search insert position
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
我做这道题的时候用的方法是二分法，刚开始的时候，很古板的套用二分法的方法，然后对书上二分法的理解也不深刻，所以总是不能包括所有的情况，但是经过回顾了二分法的方法以后，找到了一点规律，这个题应该套用改进型的“寻找第一个大于等于x的值”的情况。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int searchInsert(vector<int>& nums, int target) {
vector<int>::iterator left;
vector<int>::iterator right;
vector<int>::iterator mid;
left=nums.begin();
right=nums.end();
while(left<right)
{
mid=left+(right-left)/2;//为了防止left+right太大超界所以用这种方法
//if(target==*mid) return mid-nums.begin();
else if(target>*mid)
{
left=mid+1;
}
else
{
right=mid;
}
}
return left-nums.begin();
//注意这里返回的不是mid的index二是left指针的index，因为当循环执行到结束的时候有三种情况:一种是在最右端点的情//况，此时又分为target值大于最右边的值，另一个是target等于最右边的值，这个时候因为有left=mid+1，所以两种情况//都能满足；要插入的值在中间位置时又有两种情况：一是target的值和其中一个值相等，由于循环终止条件是left<right，//所以这个left是会和mid的位置重合于相同的这个值上，所以解决问题；另一种是，这个值在两个数中间时，mid最终会停留//在小于target的值的位置上，当left+1时就满足条件。三是在左端点的情况，左端点时无论哪种情况三个指针都将重合于左//端的位置，所以解决问题。
}
//需要仔细总结二分法的精髓，分三种情况，这种情况属于如何找到第一个大于等于target的值的位置。
需要对二分法理解更深入，不过真的二分法的时间复杂度真的低，竟然只运行了四秒，强。所以熟练掌握查找的方法很重要的。
LeetCode-26 LeetCode-271
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int removeElement(vector<int>& nums, int val) {
vector<int>::iterator it;
it=nums.begin();
while(it!=nums.end())
{
if(val==*it)
{
nums.erase(it);
continue;//这一步就是为了跳过下面自加的步骤
}
it++;
}
return nums.size();
}
};
注意当使用vector模板中的erase()函数时，注意一旦删除这个节点，vector向量就会改变，此时it迭代器指向的值已经是删除的这个元素的下一个元素了，所以不要直接就it++，这样会出现runtime error的问题，当终止循环的条件是while(it!=nums.end())时，当it已经到向量末尾时也，如果也刚好删除最后一个元素，此时指针it已经指向nums.end()的位置了,但是会执行加一步骤，就不会遇到终止条件，就会遇到超界的问题；同时当遇到连续的值需要删除时，也会出现漏删的情况，原因和前一种情况一致。所以当调用erase(),函数后就不要直接+1。
LeetCode-28
该题目的意思是寻找第一次出现要要求子串的位置，这道题主要想记录的是就是要熟练使用模板，因为这不仅能提高编程的额效率还能提高程序运行的效率，比自己造轮子来的快。
使用STL模板1
2
3
4
5
6
7
8
9
10
11//STL模板解 4ms
class Solution {
public:
int strStr(string haystack, string needle) {
if(haystack.find(needle)!=string::npos)
{
return haystack.find(needle);
}
else return -1;
}
};
自己造轮子，代码复杂而且运行效率也不高。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24//自己造轮子是有点慢跑了348ms
class Solution {
public:
int strStr(string haystack, string needle) {
int length1=haystack.length();
int length2=needle.length();
int i=0;
if (length2==0) return 0;
for (i;i<length1;i++)
{
int j=0;
if (haystack[i]==needle[0])
{
for (j=1;j<length2;j++)
{
if(haystack[i+j]==needle[j]) continue;
else break;
}
if (j==length2) return i;
}
}
if (i==length1) return -1;
}
};
LeetCode-38
这道题是我写的最久的一道题，我想有个问题暴露在这一道题上：第一做题的习惯，应该养成复杂的题画结构图的习惯，否则写的时候大脑混乱；第二就是，自己对循环这个部分可能理解的不够深入，剖析的也不够深入，所以一定要好好理解。具体的怎么做我觉得一个题不好分析，代码的每一步都有了注释，希望回看会有帮助。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46char number[]={'0','1','2','3','4','5','6','7','8','9'};
class Solution {
public:
string countAndSay(int n) {
string num="1";//首先要将其初始化
string result;//设置结果数组是为了中间必须要交换，方法是迭代生成每一个n值所对应的结果
if (n==1) return num;
for (int i=1;i<n;i++)
{
//if(i==1) result="11";
//注意这一步不能写，否则在结果中当输入2时就出现了1111的结果，然后会影响到后面的所有结果,原因在于25,26行会继续插入值
for (int j=0;j<num.length();j++)
{
int nums=1;//初始即为1可以解决当只出现一个值的时候，向后判断没有相同值，即就为1。
while(j+1!=num.size()&&num[j]==num[j+1])
//设置两个判断条件使得可以解决最后一个值的情况和nums=1的设置是配对的，而且这道题似乎只能设置这种情况，因为涉及到顺序问题
{
nums++;
j++;
}
result.push_back(number[nums]);
result.push_back(num[j]);
}
num=result;
result.clear();//这两步是进行切换
}
return num;
}
/* string countAndSay(int n) {
if (n == 0) return "";
string res = "1";
while (--n) {
string cur = "";
for (int i = 0; i < res.size(); i++) {
int count = 1;
while ((i + 1 < res.size()) && (res[i] == res[i + 1])){
count++;
i++;
}
cur +=std::to_string(count) + res[i];
}
res = cur;
}
return res;
}*/
};
LeetCode-53
这道题是寻找连续子串的最大和的题，这类题应该属于字符串的子串类型，这一类题我认为有个最共同的特点，就是要处理子串的边界问题，这里先挖一个坑，以后这一类题做多了一定要归类总结一下。回到这道题本身，这一类题的思路是，最大子串中任意子串的和都大于0，否则就存在和更大的子串。
这里贴出一个博客我觉得思路讲的还算清晰，可供参考：参考。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res=INT_MIN,curnum=0;
for (int i=0;i<nums.size();i++)
{
curnum=max(curnum+nums[i],nums[i]);
res=max(curnum,res);
}
return res;
}
};//该算法是遍历完所有的元素的算法，所以时间复杂度为O(n)。
//贴一个网址，这里有面有详细解释：https://www.cnblogs.com/mengfanrong/p/5282042.html，就是最大值中的子串中的子串的和都不小于0。
/*
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
return helper(nums, 0, (int)nums.size() - 1);
}
int helper(vector<int>& nums, int left, int right) {
if (left >= right) return nums[left];
int mid = left + (right - left) / 2;
int lmax = helper(nums, left, mid - 1);
int rmax = helper(nums, mid + 1, right);
int mmax = nums[mid], t = mmax;
for (int i = mid - 1; i >= left; --i) {
t += nums[i];
mmax = max(mmax, t);
}
t = mmax;
for (int i = mid + 1; i <= right; ++i) {
t += nums[i];
mmax = max(mmax, t);
}
return max(mmax, max(lmax, rmax));
}
};
*/
//该方法是一个迭代方法，就是不停的去中间值，直到获得最大值，这是在对左边和右边取最大值时的方法 。该方法的时间复杂度是O(logn)。
LeetCode-58
这道题是找最后一个单词的字母的个数。这道题其实蛮简单的，容易犯错的是不容易考虑到在字符串最后面有一个空格或连续多个空格，这个容易被忽视，所以一定要在统计最后一个字母的字符个数的时候，要么删除所有的空格，要么跳过所有的空格。然后，通过这一道题，我学会了sstream类的用法，这个类的主要作用有：1.將一个字符串分割，可以先用.clear( )以及.str( )將指定字串设定成一开始的內容，再用>>把个別的资料输出。2.使用stringstream简化类型转换。具体的有两个博客可以参考：
参考1,参考2
然后贴出代码，第一个是我写的代码，没有用到sstream类，一个是用到了，对比就可以发现使用sstream类有多方便了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
int lengthOfLastWord(string s) {
if (s.length()==0||s==" ") return 0;
int length=s.length();
int i=length-1;
/*while (s[i]==' ')
{
s.erase(s.end()-1);
length=s.length();
} */
//这样只考虑了字符串后面只有一个空格的情况，但是若有多个空格就没办法解决，所以比需要要用下面的方法，跳过所有的空格在进行统计
while (s[i]==' '&&i>=0)
{
i--;
}
int num=0;
while (s[i]!=' '&&i>=0)
{
num++;
i--;
}
return num;
}
};
使用sstream。1
2
3
4
5
6int lengthOfLastWord(string s) {
stringstream ss(s);
string tmp;
while( ss >> tmp );
return tmp.size();
}
LeetCode-66
这一题是plusone，就是给出一int型数组，然后就是在最后一个值上加一，同时也要进位。我觉得这道题的难点就是在进位上面，但是由于它是数组型，所以进位也不是那么麻烦，我采用的是先加上去，然后判断该值是否大于10，如果大于10，就取余，然后给前一位加一，依次遍历当只要出现一位不用进位时，就可以停止循环了；另一个难点是首位的进位，如果没有STL模板就很难做了，但是又STL模板就直接用insert()函数就可以解决问题。然后代码中有一些具体的细节，在代码中有详细的注释。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int length=digits.size();
digits[length-1]+=1;
for(int i=length-1;i>0;i--)
//注意这里i的判断一定要大于0，不能是大于等于0，否则如果第一位大于0时，在这一步就已经被取余了，下一步就没法判断
{
if (digits[i]>=10)
{
digits[i]=digits[i]%10;
digits[i-1]=digits[i-1]+1;
}
else break;
}
if (digits[0]>=10)
{
digits[0]=digits[0]%10;
digits.insert(digits.begin(),1);
}
//digits.insert(digits.begin(),1);
return digits;
}
};
LeetCode-69
该题是一个数学问题，自己实现sqrt()函数，有两种方法一个是二分法，但是这个方法时间复杂度很高，在LeetCode上运行的时间都会超时，不过也能得出答案；另一种方法被称之为牛顿迭代法，是通过转换成f(x)=x^2-a的函数，在用其切线方程一点一点的去切出开根的值。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38class Solution {
public:
int mySqrt(int x) {
if(x == 0) return 0;
double last = 0;
double res = 1;
while( res != last ) {
last = res;
res = (res + x / res) / 2;
}
return int(res);
}
};
//数学问题，牛顿迭代法求解。另一种方法是二分法
class Solution {
public:
int mySqrt(int x) {
double left=0,right=x;
double mid,last;
mid=left+(right-left)/2;
do
{
if (mid*mid>=x)
{
last=mid;
right=mid;
}
else if(mid*mid<x)
{
last=mid;
left=mid;
}
mid=left+(right-left)/2;
}while (last!=mid);
return int(mid);
}
};
这里给出两个博客我认为对这道题的解决方法总结的很好：
参考1，参考2
LeetCode-83
是链表问题，去除值重复的节点，这个题是我做过的第二个链表问题了，做了两个之后，发现链表问题的核心是指针，无论是连接还是删除结点，指针扮演的角色都很关键，所以一定要好好巩固指针的知识；然后在指针在链表中的运用，有一个常识就是先连后断。其实很好理解，连接就是一个地址赋值的过程，如果先断开就没法在连上，因为Next->next已经不等于下一个地址值了,已经没法给当前指针赋值了，一定要谨记。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *p=head;
if (p==NULL||p->next==NULL) return head;
//第一次报错的地方，做链表题时一定要首先判断链表是否为空，如果涉及到两个指针的题，一定也要判断第二个指针是否为空
ListNode *Next=p->next;
while (p->next!=NULL)
//第二次报错的地方，结束的判断是p->next!=NULL,而不是Next->next，因为当p=p->next时Next已经指向了NULL所以不会超界
{
if (p->val==Next->val)
{
p->next=Next->next;
Next=Next->next;//一定要是先连后断
}
else
{
p=p->next;
Next=Next->next;
}
}
return head;
}
};
//链表问题
LeetCode-88
题目的意思是， 将两个有序数组合并为一个有序数组，其中第一个数组的大小为两个数组非零元素个数的和，然后合并就是要将非零元素给替换掉，刚开始我想的是重新开一个数组来存，但是发现题目的意思是把第二个数组合并进第一个数组，但是这样我就有点抓瞎了，顿时不知道怎么办，然后搜了下发现从第一个数组的最后一个元素开始替换即可，然后就大的放后面小的放前面，这样并不会影响数组的构成，因为数组本身就是有序的，在被替换前自己本身已经被替换到后面零元素的位置，或者就在原位置。直接贴代码吧，代码比较清晰。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=m+n-1;
int j=m-1;
int k=n-1;
while (i>=0)
{
if (j>=0&&k>=0)
{
if (nums1[j]>=nums2[k])
{
nums1[i]=nums1[j];
j--;
}
else
{
nums1[i]=nums2[k];
k--;
}
}
else if (j>=0)
{
nums1[i]=nums1[j];
j--;
}
else if(k>=0)
{
nums1[i]=nums2[k];
k--;
}
i--;
}
}
};
//具体这道题怎么总结才好，我也不知道，只能是多积累，这个算法的巧妙之处就是从最后一个元素入手，所以要多积累这个方法
LeetCode-118
题目的意思很简单，但是是用STL的vector模板实现的，通过这道题我对vector模板的使用更加的熟练。然后说一下总结就是：<1>vector模板的元素插入只能是push_back()或者insert()函数不能直接像数组那样每个元素赋值，因为此时还没有那个地址。<2>然后就是针对 vector<vector1
const vector<int> firstrow=vector<int> {1};
然后下面给出源码方便查看1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int> > pascal;
if (numRows==0) return pascal;
const vector<int> firstrow=vector<int> {1};
if (numRows>=1) pascal.push_back(firstrow);
for (int i=1;i<numRows;i++)
{
vector<int> row;
row.push_back(1);
for (int j=1;j<i;j++)
{
row.push_back(pascal[i-1][j]+pascal[i-1][j-1]);
}
row.push_back(1);
pascal.push_back(row);
}
return pascal;
}
};
LeetCode-125
题目的意思是实现字符串的回文字符串的判断，但是，这里有一个需要注意的事情是要注意数字的形式，很有可能被忽略，同时还要注意逻辑判断符的使用，这道题困惑我了很久，发现问题所在点确实逻辑判断符出错了。心累！1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71class Solution {
public:
bool isPalindrome(string s) {
if (s.length()<=1) return true;
for (int i=0;i<s.length();i++)
{
if (s[i]>='A'&&s[i]<='Z')
{
s[i]=s[i]+32;
}
}
int i=0;
int j=s.length()-1;
while (i<=j)
{
if((s[i]<'a'||s[i]>'z')&&(s[i]<'0'||s[i]>'9'))//注意中间一定是&&符
{
i++;
}
else if((s[j]<'a'||s[j]>'z')&&(s[j]<'0'||s[j]>'9'))
{
j--;
}
else
{
if(s[i]==s[j])
{
i++;
j--;
}
//continue;
else return false;
}
}
return true;
}
};
/*class Solution {
public:
bool isPalindrome(string s) {
int len = s.length();
if(len <= 1)return true;
int i = 0, j = len - 1;
while(i <= j) {
if(isAlphanumeric(s[i]) == false)
i++;
else if(isAlphanumeric(s[j]) == false)
j--;
else {
if(isSame(s[i], s[j]) == true)
{i++; j--;}
else return false;
}
}
return true;
}
bool isAlphanumeric(char c) {
if((c >= 'a' && c <= 'z')||(c >= 'A' && c <= 'Z')||(c >= '0' && c <= '9'))
return true;
else
return false;
}
bool isSame(char a, char b) {
if(a >= 'A' && a <= 'Z')
a += 32;
if(b >= 'A' && b <= 'Z')
b += 32;
return a == b;
}
};*/