声明：很多是我当时刷题过程中，看到许多优秀的思路和解法，特意记录下来，也有自己的理解。

一是自用，方便回顾：二是瞻仰，既然自己菜，那就多学习大佬们优秀的想法。

前言

第一次做不出来不要紧，菜不要紧，关键你得

7.整数反转

题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

解题思路：

最大的值与最小的值为：[−2^31, 2^31 − 1]即：[-2147483648, 2147483647]

通过循环将数字x的每一位拆开，在计算新值时每一步都判断是否溢出。
溢出条件有两个，一个是大于整数最大值INT_MAX，另一个是小于整数最小值INT_MIN

设当前结果为result，下一位为pop；

从result * 10 + pop > INT_MAX 这个溢出条件来看
当出现 result > INT_MAX / 10 且 还有pop需要添加时，则一定溢出
当出现 result == INT_MAX / 10 且 pop > 7 时，则一定溢出，7是2^31 - 1的个位数
从ans * 10 + pop < INT_MIN 这个溢出条件来看
当出现 ans < INT_MIN / 10 且 还有pop需要添加 时，则一定溢出
当出现 ans == INT_MIN / 10 且 pop < -8 时，则一定溢出，8是-2^31的个位数

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int reverse(int x) {
        int result=0;
        while(x!=0)
        {
            int pop=x%10;
            //溢出判断
            if(result>INT_MAX/10||(result==INT_MAX/10&&pop>7))
                return 0;
            if(result<INT_MIN/10||(result==INT_MIN/10&&pop<(-8)))
                return 0;
            result=result*10+pop;
            x/=10; //取整数的每一位数
        }
        return result;
    }
};

9.回文数

题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

解题思路：

一开始感觉跟第7题有些类似，试着下，然后可以了。

首先负数可以第一时间排除，注意0，0也是个回文数。采用数学的方法（模运算），将每一位数拆分，先乘10再相加。最后对比结果。

注意，int型数的最大数，反正会产生溢出，所以要使用范围更大的数，如long int型

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isPalindrome(int x) {
        if(x<0)
            return false;
        int y=x;
        long int result=0;
        while(y!=0)
        {
            int pop=y%10;
            result=result*10+pop;
            y/=10;
        }
        if(result==x)
            return true;
        else return false;
    }
};

11.盛最多水的容器

题目：给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

解题思路：

经典一道双指针题目。

在初始时，左右指针分别指向数组的左右两端。我们开始移动指针，移动哪一个呢？观察发现，容纳的水量是两个指针指向的数字中较小值 × 指针之间的距离。所以移动对应数字较小的那个指针。每一次将容纳的水量记录下来，最大者则为最后结果。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans=0;//记录容纳的水量
        int i=0,j=height.size()-1;
        while(i<j)
        {
            int area=(j-i)*min(height[i],height[j]);
            if(area>ans)
                ans=area;
            if(height[i]<height[j])
                i++;
            else if(height[i]>height[j])
                j--;
            else //左右相等的时候，同时移动
            {
                i++;j--;
            }
        }
        return ans;
    }
};

解题方法来自：https://leetcode-cn.com/u/happyfire/

12.整数转罗马数字

题目：

image-20200721100907187

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
    给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

解题思路：

这题官方解答有两种思路，一是贪心，二是硬编码数字。其二者时间复杂度和空间复杂度都一样，但贪心易拓展。

首先，枚举出罗马数字与整数一一对应的表。然后从最大的符号开始

给定的整数减去最大的符合后，如果余数大于符号对应的数，则循环while，每一次取的符号加入到字符串res中，直到余数为0

举例：假如给定的整数是2222

  • 第一步：2222-1000=1222，余数大于当前符号1000，再循环while —>M

  • 第二步：1222-1000=222，余数小于当前符号1000，不循环while；—>M

  • 第三步：222-100=122，余数大于当前符号100，再循环while； —>C

  • 第四步：122-100=22，余数小于当前符号100，不循环while； —>C

  • 第五步：22-10=12，余数大于当前符号10，再循环while； —>X

  • 第六步：12-10=2，余数小于当前符号10，不循环while； —>I

  • ……

    结果为MMCCXII

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string intToRoman(int num) {
        vector<int> values={1000,900,500,400,100,90,50,40,10,9,5,4,1}; 
		vector<string> strs={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
					string res;
					for(int i = 0; i < values.size(); i++){
						while(num >= values[i])
                        {
							res += strs[i];
							num -= values[i];
						}
					}
					return res;
    }
};

第一眼，哇！真的太厉害。简洁，思路清晰！

代码来自：https://blog.csdn.net/qq_31820761/java/article/details/90646907

19.删除链表的倒数第n个节点

解题思路：

  1. 求出链表的长度

  2. 找到删除结点的前驱结点

解释x：x是作所要删除的前驱指针指针移动的次数，倒数第n个就是正数的总长-n+1，所以x=n-1=length-n-1

image-20200324113202274

代码示例：

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
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int length=1;
        ListNode* temp=head;
        while(temp->next)	//求链表的长度
        {
            temp=temp->next;
            length++;
        }
        if(n==length) //第一个的情况
            return head->next;
        int x=length-n-1;  //倒数第n个就是，长度length-n+1,
        				   //删除要找到前一个结点，所以是length-n-1
        ListNode* p=head;   //要删除的前一个节点
        ListNode* q=head->next; //要删除的节点
        while(x>0)
        {
            q=q->next;
            p=p->next;
            x--;
        }
        p->next=q->next;
        return head;
    }
};

61.旋转链表

如果是空链表或者不移动（k=0），直接返回原链表。

求出链表长度，因为k可能是个大于链表长度，所以要进行模运算。

然后将链表首尾连接，再找到length-k%length结点，进行断开，返回的链表从这个结点的下一个结点开始。

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
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(k==0||!head)
            return head;
        int length=1;
        ListNode *p=head;
        while(p->next)
        {
            p=p->next;
            length++;
        }
        if(k%length==0)
            return head;
        p->next=head;		//首尾相连，形成环状链表
        int x=length-k%length;	//找到新头结点的前驱结点的要移动的步数。
        while(x--)
        {
            p=p->next;
        }
        ListNode *res=p->next;	//新头结点
        p->next=NULL;
        return res;
    }
};

82.删除排序链表中的重复元素 II

指针是个好东西。快慢指针更是厉害

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *dummy=new ListNode(-1);	//假指针
        ListNode *fast=head;
        ListNode *slow=dummy;
        dummy->next=head;
        while(fast&&fast->next)     //快指针用于查找相同元素
        {
            if(fast->val!=fast->next->val)
            {
                if(slow->next==fast)    //快指针先前没查找到相同数
                    slow=fast;
                //先前查找到相同数，将出现相同数的前一个数连接到相同数后第一个不同数 
                else slow->next=fast->next;
            }
            fast=fast->next;
        }
        if(slow->next!=fast)
            slow->next=fast->next;
        return dummy->next;
    }
};

98.验证二叉搜索树

  • 当前节点的值是其左子树的值的上界（最大值）
  • 当前节点的值是其右子树的值的下界（最小值）

OK，有了这个想法，你可以将验证二叉搜索树的过程抽象成下图（-00代表无穷小，+00代表无穷大）：

éªŒè¯äºŒå‰æœç´¢æ ‘.png

首先来看在这道题中的终止两种终止条件：

  • 当当前节点为空时，表示这个节点已经是叶子节点，这个节点没有子节点，可以返回 True
  • 当当前节点不在 [ min_value,max_value ] 的区间时，这个节点不能同时符合二叉搜索树的两个特征，返回 False

然后看看递归方程，由于节点有两个子树，所以我们有两个递归方程要执行：

  • 对左子树：heaper(root->left,lower,root->val) 解释：当前节点是左子树的上界（你可以粗略地理解为最大值）
  • 对右子树：heaper(root->right,root->val,upper)解释同上

这个递归过程是最难理解的地方，如果不理解，你可以看一看上图中绿色剪头，你会很快理解这么递归的原因。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool heaper(TreeNode* root,long long lower,long long upper)
    {
        if(root==NULL)
            return true;
        if(root->val<=lower||root->val>=upper)
            return false;
        return heaper(root->left,lower,root->val)&&heaper(root->right,root->val,upper);
    }
    bool isValidBST(TreeNode* root) {
        return heaper(root,LONG_MIN, LONG_MAX);
    }
};

102.二叉树的层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> res;
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode* temp=q.front(); //取出队列的第一个元素
                q.pop();
                res.emplace_back(temp->val);    //将每层的节点
                //若改节点的左右孩子不为空，则将左右孩子入队
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
            ans.emplace_back(res);
        }
        return ans;
    }
};

617.合并二叉树

其实也不难，一开始脑袋昏昏，一看提交发现，原来那么简单。

递归法，到了树这一块，递归是常见又重要的解题思路了

我们可以对这两棵树同时进行前序遍历，并将对应的节点进行合并。在遍历时，如果两棵树的当前节点均不为空，我们就将它们的值进行相加，并对它们的左孩子和右孩子进行递归合并；如果其中有一棵树为空，那么我们返回另一颗树作为结果；如果两棵树均为空，此时返回任意一棵树均可（因为都是空）。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==NULL)
            return t2;
        if(t2==NULL)
            return t1;
        t1->val+=t2->val;
        t1->left=mergeTrees(t1->left,t2->left);
        t1->right=mergeTrees(t1->right,t2->right);
        return t1;
    }
};

637.二叉树的层平均值

层序遍历，就要用到队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        queue<TreeNode*> q;
        q.push(root);//广度优先遍历，先将根节点添加到队列
        while(!q.empty())//只要队列不为空就继续遍历
        {
            double sum=0;//用sum存每一层节点值的和
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode* tmp=q.front();//取出队列的第一个元素
                q.pop();
                sum+=tmp->val;//将每一层节点的值加起来
                //若该节点的左右孩子不为空，则将左右孩子入队
                if(tmp->left)   q.push(tmp->left);
                if(tmp->right)  q.push(tmp->right);
            }
            res.push_back(sum/n);
        }
        return res;
    }
};