leetCode 编程学习

[zw398430866]

1. isalnum可以用来判断是否为字母或者数字

   char ch = 'A'; // 'a'  '1' 
   bool isA = isalnum(ch);  //isA=true

   islower 判断小写字母， isupper 判断大写字母 ，isalpha 判断是否为字母

[zw398430866]

2. std::transform(itB, itE, *itB, ::tolower) 可以用来转换为小写，保存到itB中，::toupper是转换为大写

   #include <algorithm>
   string first = "abcdefg";  
   string second(first);  
   std::transform(first.begin(), first.end(), second.begin(), ::toupper);  // second=ABCDEFG

[zw398430866]

3 string的常用用法。 1)翻转，reverse

    string str = "abcdefg";
    reverse(str.begin(), str.end());

2)删除字符

//删除单个元素 
str.erase(iter);//删除迭代器iter指定的元素 
//删除区间元素 
str.erase(first_iter, last_iter)//删除迭代器[first,second)之间的元素
str.erase(pos,length)//删除下标pos开始的长度为length的区间元素 

    string str = "abcdefg";
    str.erase(str.begin());

3)查找某字符 find (逆序查找是rfind)

    string str = "abcdefg";
    string::iterator itr;
    itr = find(str.begin(), str.end(), '1'); //输出对应的迭代指针位置
    bool isEnd = (itr == str.end());

    string str1 = "abc";
    cout<<str.find(str1)<<endl;  //输出2

4)距离函数 distance

    string str = "abcdefg";
    string::iterator itr;
    itr = find(str.begin(), str.end(), 'g');
    int dis = distance(str.begin(), itr);

5)插入字符串string.insert

    string str = "abcdefg";
    string addStr = "abc";
    str.insert(3, addStr );

6)遍历

    string str = "abcdefg";
    for (auto ch:str){
        cout<<ch<<endl;
    }

7)子字符串

    string str = "abcdefg";
    cout<<str.substr(1,3)<<endl;

8)排序

string s
sort(s.begin(), s.end()); 升序排列
sort(s.begin(), s.end(), greater<int>());  降序排序

9)字符串插入 string str = "abc"; str.insert(0, "efg"); // 在位置0上插入字符串“efg”

[zw398430866]

vector的用法 -- vector创建2维当数组使用

    vector<vector<int>> matrix;//假设这是一个4*3的矩阵
    int row=4,col=3;
    matrix.resize(row);
    for(int i=0;i<matrix.size();i++)
    matrix[i].resize(col);
    //接下来就可以用下标运算访问了
    matrix[1][2]=233;
    matrix[0][0]=422;

[zw398430866]

map的用法 -- map或者unordered_map当数组使用

    map<int, map<int, string>> mp;
    mp[1][-1] = "abc";
    mp[2][0] = "ccc";

    map<string, int> mp2;
    mp2["111"] = 2;

[zw398430866]

53. 最大子序和 https://leetcode-cn.com/problems/maximum-subarray/ 用暴力法解的时候，涉及到两层循环。如果用的是vector的迭代器来遍历，会超时。但是用for循序来遍历，则会省很多时间。

[zw398430866]

98. 验证二叉搜索树 https://leetcode-cn.com/problems/validate-binary-search-tree/ 解题1： 中序遍历后，判断是否升序即可，思路比较清晰，难点在中序遍历的应用。 解题2： 判断每个节点在一个min,max之间，其中左子树刷最大值，右子树刷最小值。层层递归。 二刷的时候用解题2做下。

[zw398430866]

102. 二叉树的层序遍历 https://leetcode-cn.com/problems/binary-tree-level-order-traversal/ 解题1：对二叉树遍历，同时记录当前是读到第几层，读第几层就把树的节点放到二维vector中第几层中。 解题2：广度优先搜索，通过栈的形式来实现。对树进行先入先出，出栈的时候同时把子树也加入到栈中。 二刷的时候需要掌握解题2的方法，因为这个是典型的广度优先算法模板。

[zw398430866]

3. 无重复字符的最长子串 https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/ 解题1：暴力遍历，记录下每个字符串对应的最长不重复长度。 解题2：滑动优化，每找到一个不重复长度，下一个起点从重复的字符+1开始。 解题2相比解题1，会优化一部分耗时，二刷的时候用解题2试试。另外可以再看看有没有其他解法

[zw398430866]

1038. 从二叉搜索树到更大和树 https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 解题1：两次循环，一次得到所有值，一次改写树。但是这样树是二叉搜索树的特点就没利用上。 解题2：先遍历右子树，再遍历左子树，层层递归，中序遍历的逆序，这样记录一个和，这个值恰好就是大于等于该节点的值。 二刷的时候，用解题2来做。

前序，中左右 中序，左中右 后续，左右中 理解的时候，把中放在对应的位置即可。

[zw398430866]

29. 两数相除 https://leetcode-cn.com/problems/divide-two-integers/ 暴力法失败，耗时，且会有很多场景考虑不到。 二分法，还要考虑溢出问题，这道题后面可以再做一次。溢出的时候，主要是考虑-2147483648的翻转是超过了2147483647的。同时临界值的判断要多考虑几个用例。把分子分母都用临界值写一遍用例。后续要再做一次。

[zw398430866]

215. 数组中的第K个最大元素 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ 利用容器拍个序就可以了。

[zw398430866]

sort自定义排序，可以自己写一个比较函数，在sort中调用

static bool lessValue(const Solution &slu1, const Solution &slu2) 
{
    return slu1.value < slu2.value;
}
sort(vecSlu.begin(), vecSlu.end(), lessValue);

bool operator< (const Solution &slu1, const Solution &slu2)
{
    return slu1.value < slu2.value;
}
sort(vecSlu.begin(), vecSlu.end());

[zw398430866]

反转每对括号间的子串：按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串 本题自己再解的时候，用了递归的思路，翻转最外层的需要翻转次外层的，一层层的，先翻转最里面。然后遍历所有的最外层，实现起来比较麻烦。 后来讨论的时候，发现别人用的栈，先进后出的方式来实现，遇到反括号)就弹出直到(，这个思路就很清晰，做一下。 例：输入a(bcdefghijkl(mno)p)q，返回apmnolkjihgfedcbq

[zw398430866]

5. 最长回文子串 https://leetcode-cn.com/problems/longest-palindromic-substring/ 我用的暴力法，优化了下，但是解题时间会超时，最后的用例过不去。 比较优秀的解法是o(n2)的中心扩展法，求每个字符对应的最长回文数，这样只需要遍历2次即可。 用新的思路写了下，效果还可以。