LeetCode刷题笔记和想法（C++）

主要用于记录在LeetCode刷题的过程中学习到的一些思想和自己的想法，希望通过leetcode提升自己的编程素养 :p

　　高效leetcode刷题小诀窍（这只是目前对我自己而言的小方法，之后会根据自己的切身经历更新）：

　　算法不是纯粹拼智商的，智商高，就一定很厉害，不够聪明，就一定不行。算法是一种技能，是可以通过科学合理的方式训练出来的能力。目前国内大厂的算法考察，基本不会超过leetcode 中等难度，上限难度基本都是leetcode 中等题里面的中等难度基本的算法数据结构是有限的。比如说链表，二叉树，二分查找，动态规划，哈希表。。。我喜欢按算法的分类来选题和刷题，比如一个时间段，只刷链表题，待刷得差不多的时候，接下来再刷二叉树的题。。。这种做法可以极大的提高刷题的速度，而且能带来更好的效果。

/*****************************************************************************************

注：这个可能不更了，以后按照分类来更，二叉树、链表、二分查找、动态规划、哈希表

****************************************************************************************/

类型top100中的典型问题和解决办法

226.翻转二叉树

　　二叉树的问题首先要搞清楚二叉树的遍历方式：递归（感觉递归就是为二叉树设计的），前序、中序、后续遍历其实就是根节点的位置，根左右（前序），左根右（中序），左右根（后续）{然而并没有感觉有啥子用处} :p 递归的返回值挺重要的。

strcut TreeNode　　//二叉树结构
{
　　int val;
　　TreeNode *left;
　　TreeNode *right;
　　TreeNode(int x):val(x),left(NULL),right(NULL) {}
}；
TreeNode* invertTree(TreeNode* root) 
{
　　if(root)
　　{
　　　　TreeNode *tmp;
　　　　tmp = root->left;
       root->left=root->right;
       root->right=tmp;
       invertTree(root->left);
       invertTree(root->right);
    }
  　return root;
}

206.反转链表

　　链表的特点：有下一个节点的指针，很方便进行遍历，但是想要反转链表还需要当前节点的前一个节点才行，因此我们需要定义一个变量用来存储前面（pre）节点就可以了；

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x), next(NULL) {} 
};

ListNode* reverseList(ListNode* head)
{
     ListNode *pre = NULL;
     ListNode *cur = head;
     while(cur)
     {
          ListNode *tmp=pre; //临时存储pre指针
          pre=cur;
          cur=cur->next;
          pre->next=tmp;      //注意这个顺序，这个必须在上一行后面。
    }
    return pre;
}

136.数组中只出现一次的数字

给定一个非空数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个出现一次的元素。

位运算：共有6种位运算符 &与运算 |或运算 ^异或运算 ~非运算（求补） >>右移 $x2$ <<左移

a^0=a a^a=0

int singleNumber(vector<int>& nums) 
{
    //最简单的异或操作  a^0=a;a^a=0;
    int ret=0;
    int len=nums.size();
    for(int i=0;i<len;i++)
    {
        ret=nums[i]^ret;
    }
    return ret;
}

169.多数元素

map的结构和用法：c++的map相对于python简直就是太难用了；

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) 
    {
        int len=nums.size();
        int n=len/2;
        map<int,int> m;
        map<int,int>::iterator it_m;
        for(int i=0;i<len;i++)
        {
            if(m.find(nums[i])==m.end())    //c++ 判断map中key的一种方法
            {
                m[nums[i]]=1;
            }
            else
            {
                m[nums[i]]+=1;
            }
        }
        for(it_m=m.begin();it_m!=m.end();it_m++)    //c++ map 使用迭代器的遍历方法
        {
            if(it_m->second > n) return it_m->first;
        }
        return 0;
    }
};

21.合并两个有序链表

递归函数总是返回小的链表头，小的链表头会在每次迭代时更新为next

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        if(l1 == NULL)
        {
            return l2;
        }
        else if(l2 == NULL)
        {
            return l1;
        }
        else if(l1->val < l2->val)
        {
           l1->next=mergeTwoLists(l1->next,l2);
           return l1;
        }
        else
        {
            l2->next=mergeTwoLists(l1,l2->next);
            return l2;
        }
    }
};