/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector printListFromTailToHead(ListNode* head) {
        vector ans;
          // 从头节点开始进行遍历
        while(head){
            // 将每个节点的权值放入动态数组里面
            ans.push_back(head->val);
            // 指针后移动
            head=head->next;
        }
        // 反转整个数组
        reverse(ans.begin(),ans.end());
        return ans;
    }
};
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* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        // 检测是否符合范围
        if(pHead==NULL)return 0;
        ListNode* cur = pHead;
        int count = 0;
        while(cur){
            cur = cur->next;
            count++;
        }
        if(count<k)return 0;
        // 开始找倒数第k个节点
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while(k--){
            fast = fast->next;
        }
        
        while(fast){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
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

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        //空链表
        if(pHead == NULL) 
            return NULL;
        ListNode* res = new ListNode(0);
        //在链表前加一个表头
        res->next = pHead; 
        ListNode* cur = res;
        while(cur->next != NULL && cur->next->next != NULL){ 
            //遇到相邻两个节点值相同
            if(cur->next->val == cur->next->next->val){ 
                int temp = cur->next->val;
                //将所有相同的都跳过
                while (cur->next != NULL && cur->next->val == temp) 
                    cur->next = cur->next->next;
            }
            else 
                cur = cur->next;
        }
        //返回时去掉表头
        return res->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

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        //空链表
        if(pHead == NULL) 
            return NULL;
        unordered_map mp;
        ListNode* cur = pHead;
        //遍历链表统计每个节点值出现的次数
        while(cur != NULL){ 
            mp[cur->val]++;
            cur = cur->next;
        }
        ListNode* res = new ListNode(0);
        //在链表前加一个表头
        res->next = pHead; 
        cur = res;
        //再次遍历链表
        while(cur->next != NULL){ 
            //如果节点值计数不为1
            if(mp[cur->next->val] != 1) 
                //删去该节点
                cur->next = cur->next->next; 
            else
                cur = cur->next; 
        }
        //去掉表头
        return res->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

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (!pRoot) return 0;
        int lval = TreeDepth(pRoot->left);
        int rval = TreeDepth(pRoot->right);
        return max(lval, rval) + 1;
     
    }
};
1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    vector > Print(TreeNode* pRoot) {
        vector> res;
        if(!pRoot)return res;
        vector vec;
        queue q;
        q.push(pRoot);
        TreeNode* temp = NULL;
        int i = 1;
        while(!q.empty()){
            int size = q.size();
            vec.clear();
            for(int i = 0; i< size;i++){
                temp = q.front();
                q.pop();
                vec.push_back(temp->val);
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
            if(i%2==0)reverse(vec.begin(),vec.end());
            res.push_back(vec);
            i++;
        }
        return res;
    }
};

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

class Solution {
public:
    //记录返回的节点
    TreeNode* res = NULL;
    //记录中序遍历了多少个
    int count = 0;
    //当遍历到节点为空或者超过k时，返回
    void midOrder(TreeNode* root, int k){
        if(root == NULL || count > k) 
            return;
        midOrder(root->left, k);
        count++;
        //只记录第k个
        if(count == k)  
            res = root;
        midOrder(root->right, k);
    }
    
    int KthNode(TreeNode* proot, int k) {
        midOrder(proot, k);
        if(res)
            return res->val;
        //二叉树为空，或是找不到
        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
25
26
27

class Solution {
public:
    string split(string s){
        istringstream sin(s);
        string str;
        vector res;
        while(getline(sin,str,' ')){
            res.push_back(str);
        }
        reverse(res.begin(),res.end());
        string ret = "";
        for(int i = 0; i < res.size()-1;i++){
            ret += res[i];
            ret += " ";
        }
        ret += res[res.size()-1];
        return ret;
    }
    string ReverseSentence(string str) { 
        if(str=="") return "";
        return split(str);
    }
};
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:
//比较详细了
    /*
    1-9       9个*1
    10-99     90个*2
    100-999   900个*3
    1000-9999 9000个*4
    */
    int findNthDigit(int n) {
        // write code here
        if(n==0)return 0;
        long long start=1;//起始数
        long long digit=1;//记录位数
        long long count=9;//记录区间个数，比如9 90 900
        while(n>count){//先减去前面有规律的数
            digit++;
            n-=count;
            start*=10;
            count=digit*9*start;
        }
        //以下就是n剩余的数
        //这里我们先判断剩余的n是在哪个数
        long long number=start+(n-1)/digit;//start就是开始的第一个数字，所以后面要n-1
        //判断好是在哪个数字后，下面对数字分解
        long long temp=(n-1)%digit+1;//这个数的第几位
        for(int i=digit;i>temp;i--){//把这个数后面多余的尾巴去掉
            number/=10;
            cout<

• 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

【动态规划】

JZ42 连续子数组的最大和 有负数

可以用动态规划 或者 前缀和的思路进行解决
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GV3gXKOY-1658324510138)(vx_images/539823320236053.png =500x)]

JZ85 连续子数组的最大和(二)？？？

JZ69 跳台阶

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zeueyp7L-1658324510139)(vx_images/599713320235709.png =500x)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v203jLtm-1658324510140)(vx_images/68083420251804.png =500x)]

JZ10 斐波那契数列

JZ19 正则表达式匹配

JZ71 跳台阶扩展问题

JZ70 矩形覆盖

JZ63 买卖股票的最好时机

JZ47 礼物的最大价值

JZ48 最长不含重复字符的子字符串

JZ46 把数字翻译成字符串

【回溯】

JZ12 矩形中的路径

JZ13 机器人的运动范围

【排序】

JZ3 数组中的重复数字

JZ51 数组中的逆序对

JZ40 最小的K个数

JZ41 数据流中的中位数

【数位运算】

JZ65 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

数据范围：两个数都满足 -10 \le n \le 1000−10≤n≤1000
进阶：空间复杂度 O(1)，时间复杂度 O(1)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6Yw0HH1w-1658324510142)(vx_images/394304819235861.png =400x)]

class Solution {
public:
    int Add(int num1, int num2) {
        // add表示进位值
        int add = num2;         
        // sum表示总和       
        int sum = num1;                
        // 当不再有进位的时候终止循环
        while(add != 0) {              
            // 将每轮的无进位和与进位值做异或求和
            int temp = sum ^ add;      
            // 进位值是用与运算产生的
            add = (sum & add) << 1;    
            // 更新sum为新的和
            sum = temp;                
        }
        return sum;
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

JZ15 二进制中1的个数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-X2A7eqFO-1658324510143)(vx_images/346933120228431.png =400x)]

两种方案
1>>I -> 1*2^I n&(n-1)
C++运算符中的左移和右移 左移相当于x2 n>>1 相当于除2 （偶数可以，奇数不可以，奇数会发生截断）
https://www.imangodoc.com/137166.html
https://blog.csdn.net/qq_39790992/article/details/82313960 详细

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        //当n为0时停止比较
        while(n){  
            n &= n - 1;
            res++;
        }
        return res;
     }
};

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int  NumberOf1(int n) {
        int res = 0;
        //遍历32位
        for(int i = 0; i < 32; i++){
            //按位比较
            if((n & (1 << i)) != 0)   
                res++;
        }
        return res;
     }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

JZ16 数值的整数次方Power(x,n) 快速幂

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Dk52MUSk-1658324510145)(vx_images/463753220227588.png =500x)]

二分角度 递归 二进制角度 迭代
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9eLzldeM-1658324510146)(vx_images/226232420223738.png =500x)]

JZ56 数组中只出现一次的两个数字

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c2ZjWzWV-1658324510149)(vx_images/164233920246267.png =500x)]

方法一：异或运算（扩展思路）

class Solution {
public:
    vector FindNumsAppearOnce(vector& array) {
        vector res(2, 0);
        int temp = 0;
        //遍历数组得到a^b
        for(int i = 0; i < array.size(); i++) 
            temp ^= array[i];
        int k = 1;
        //找到两个数不相同的第一位
        while((k & temp) == 0) 
            k <<= 1;
        for(int i = 0; i < array.size(); i++){
            //遍历数组，对每个数分类
            if((k & array[i]) == 0) 
                res[0] ^= array[i];
            else
                res[1] ^= array[i];
        }
        //整理次序
        if(res[0] < res[1]) 
            return res;
        else
            return {res[1], res[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

方法二：哈希表(推荐使用)

思路：
既然有两个数字只出现了一次，我们就统计每个数字的出现次数，利用哈希表的快速根据key值访问其频率值。

具体做法：
step 1：遍历数组，用哈希表统计每个数字出现的频率。
step 2：然后再遍历一次数组，对比哈希表，找到出现频率为1的两个数字。
step 3：最后整理次序输出。

class Solution {
public:
    vector FindNumsAppearOnce(vector& array) {
        unordered_map mp;
        vector res;
        //遍历数组
        for(int i = 0; i < array.size(); i++) 
            //统计每个数出现的频率
            mp[array[i]]++; 
        //再次遍历数组
        for(int i = 0; i < array.size(); i++) 
            //找到频率为1的两个数
            if(mp[array[i]] == 1) 
                res.push_back(array[i]);
        //整理次序
        if(res[0] < res[1]) 
            return res;
        else
            return {res[1], res[0]};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

打印从1到最大的n位数

两种情况 ： 不需要考虑大数越界 需要考虑大数越界（全排列）
数字转为字符串 可以用 string s; s[i] = a+’0’; stoi函数的使用 s.substr(起始位置，个数)
String 类型常用函数总结
字符串转整型数字：std::stoi, std::stol, std::stoll 字符串转浮点数：stod,stof,stold to_string()
https://blog.csdn.net/zhaitianbao/article/details/118993685
https://blog.csdn.net/luolaihua2018/article/details/109238559 全面
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xtiDJv5Z-1658324510151)(vx_images/392512420242893.png =600x)]

数组中数字出现的次数

进行异或操作，可以去除两两重复的数字，剩下的就是两个只出现一次的数字，然后再按照异或结果的位为1位置对原先数组进行分组，对两个组各自进行异或操作，结果就是两个数字。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-g4BWXjID-1658324510152)(vx_images/53062520222545.png =500x)]

数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
出现3次，则所有相同的数字加起来 对应位置上的1 为3的倍数，可以统计所有位置上1的个数，然后%3，结果就是最终的答案
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VJg0WUdY-1658324510154)(vx_images/151422520220991.png =500x)]

JZ64 求1+2+3+…+n ??

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

class Solution {
public:
    int res = 0;
    int Sum_Solution(int n) {
        n && (n += Sum_Solution(n - 1)); //要判断n是否为整数
        return n;
    }
};

1
2
3
4
5
6
7
8
9

【模拟】

JZ29 顺时针打印矩阵

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nnzbnMrM-1658324510155)(vx_images/593781115222043.png =500x)]

JZ61 扑克牌顺子

现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：

1. A为1，J为11，Q为12，K为13，A不能视为14
2. 大、小王为 0，0可以看作任意牌
3. 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
4. 数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]

题解一:排序+遍历
顺子牌的特点：
1、顺子一定没有相等的牌；
2、顺子中两张相邻的扑克牌的数值差为1，即满足interrapt=numbers[i + 1] - numbers[i] - 10;
3、当interrapt不为0，代表需要在顺子中插入对应interrapt张牌；
4、只有两张王牌；
主要思路：
1、排序五张牌；
2、遍历5张牌，并求出大小王的数量zero_num，与interrapt的大小；
3、判断interrapt的大小。
(1)interrapt0,除大小王之外的牌本来就是顺子，大小王随便补齐在头部或者尾部；
(2)interrapt<=zero_num,除大小王之外的牌不是顺子，可以通过大小王变成特定的牌补在其中，使其成为顺子；
(2)interrapt>zero_num,除大小王之外的牌不是顺子,即使有大小王也补不成顺子。

核心
记录max到min的距离

class Solution {
public:
    bool IsContinuous( vector numbers ) {
        sort(numbers.begin(), numbers.end());
        int zero_num = 0;//统计大小王数量
        int i = 0;
        while (numbers[i] == 0)zero_num++,i++;
        int interrapt = 0;//记录五张牌中最大值max到最小值min的距离
        for (; i < numbers.size()-1; ++i) {
            if (numbers[i] == numbers[i + 1])return false;//出现相同的扑克牌
            interrapt += numbers[i + 1] - numbers[i] - 1;//计算距离
        }
        if (zero_num >= interrapt) return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

JZ67 把字符串转换成整数(atoi)

思路：
既然是将字符串转化为数字，那我们可以遍历字符串，一个字符串，一个字符地检查，然后取出掉无用的，取出数字，利用如下代码，一个数字一个数字地转换，前面的扩大十倍加上后面一位。

res = res * 10 + sign * (c - ‘0’);

具体做法：
step 1：遍历字符串，用index记录全程的下标。
step 2：首先要排除空串，然后越过前导空格，以及前导空格后什么都没有就返回0.
step 3：然后检查符号，没有符号默认为正数。
step 4：再在后续遍历的时候，将数字字符转换成字符，遇到非数字则结束转换。
step 5：与Int型最大最小值比较，检查越界情况。

class Solution {
public:
    int StrToInt(string s) {
        int res = 0;
        int index = 0;
        int n = s.length();
        //去掉前导空格，如果有
        while(index < n){ 
            if(s[index] == ' ')
                index++;
            else
                break;
        }
        //去掉空格就什么都没有了
        if(index == n) 
            return 0;
        int sign = 1;
        //处理第一个符号是正负号的情况
        if(s[index] == '+')
            index++;
        else if(s[index] == '-'){
            index++;
            sign = -1;
        }
        //去掉符号就什么都没有了
        if(index == n) 
            return 0;
        while(index < n){
            char c = s[index];
            //后续非法字符，截断
            if(c < '0' || c > '9')  
                break;
            //处理越界
            if(res > INT_MAX / 10 || (res == INT_MAX / 10 && (c - '0') > INT_MAX % 10))
            
                return INT_MAX;
            if(res < INT_MIN / 10 || (res == INT_MIN / 10 && (c - '0') > -(INT_MIN % 10)))
                return INT_MIN;
            res = res * 10 + sign * (c - '0');
            index++;
        }
        return res;
    }
};


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

JZ20 表示数值的字符串

请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。
描述
请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。

科学计数法的数字(按顺序）可以分成以下几个部分:
1.若干空格
2.一个整数或者小数
3.（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数(可正可负)
4.若干空格

小数（按顺序）可以分成以下几个部分：
1.若干空格
2.（可选）一个符号字符（‘+’ 或 ‘-’）
3. 可能是以下描述格式之一:
3.1 至少一位数字，后面跟着一个点 ‘.’
3.2 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
3.3 一个点 ‘.’ ，后面跟着至少一位数字
4.若干空格

整数（按顺序）可以分成以下几个部分：
1.若干空格
2.（可选）一个符号字符（‘+’ 或 ‘-’)
3. 至少一位数字
4.若干空格

例如，字符串[“+100”,“5e2”,“-123”,“3.1416”,“-1E-16”]都表示数值。
但是[“12e”,“1a3.14”,“1.2.3”,“±5”,“12e+4.3”]都不是数值。

【其他】

JZ66 构建乘积数组

给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B 的元素 B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。
（注意：规定 B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2]）
对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vIM1U7d6-1658324510157)(vx_images/156292921230613.png =500x)]

如上图所示，矩阵中由对角线1将其分成了上三角和下三角。我们先看下三角，如果我们累乘的时候，B[1]是在B[0]的基础上乘了新增的一个A[0]，B[2]是在B[1]的基础上乘了新增的一个A[1]，那我们可以遍历数组的过程中不断将数组B的前一个数与数组A的前一个数相乘就得到了下三角中数组B的当前数。同理啊，我们在上三角中，用一个变量存储从右到左的累乘，每次只会多乘上一个数字。这样，两次遍历就可以解决。

class Solution {
public:
    vector multiply(const vector& A) {
        //初始化数组B
        vector B(A.size(), 1);
        //先乘左边，从左到右
        for(int i = 1; i < A.size(); i++)
            //每多一位由数组B左边的元素多乘一个前面A的元素
            B[i] = B[i - 1] * A[i - 1];
        int temp = 1;
        //再乘右边，从右到左
        for(int i = A.size() - 1; i >= 0; i--){
            //temp为右边的累乘
            B[i] *= temp;
            temp *= A[i];
        }
        return B;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

JZ50 第一个只出现一次的字符

在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map mp;
        //统计每个字符出现的次数
        for(int i = 0; i < str.length(); i++) 
            mp[str[i]]++;
        //找到第一个只出现一次的字母
        for(int i = 0; i < str.length(); i++) 
            if(mp[str[i]] == 1)
                return i;
        //没有找到
        return -1; 
    } 
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

JZ5 替换空格

class Solution {
public:
    string replaceSpace(string s) {
        string res = "";
        //遍历字符串
        for(int i = 0; i < s.length(); i++){ 
            //非空格直接复制
            if(s[i] != ' ') 
                res += s[i];
            //空格就替换
            else 
                res += "%20"; 
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

JZ21 调整数组顺序使奇数位于偶数前面(一)

输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

step 1：遍历数组，统计奇数出现的次数，即找到了偶数开始的位置。
step 2：准备一个和原数组同样长的新数组承接输出，准备双指针，x指向奇数开始的位置，y指向偶数开始的位置。
step 3：遍历原数组，遇到奇数添加在指针x后面，遇到偶数添加在指针y后面，直到遍历结束。

class Solution {
public:
    vector reOrderArray(vector& array) {
        int n = array.size();
        vector res(n);
        //统计奇数个数
        int odd = 0; 
        //遍历统计
        for(int i = 0; i < n; i++){ 
            if(array[i] % 2)
                odd++;
        }
        //x与y分别表示答案中奇偶数的坐标
        int x = 0, y = odd; 
        for(int i = 0; i < n; i++){
            //奇数在前
            if(array[i] % 2){ 
                res[x] = array[i];
                x++;
            //偶数在后
            }else{ 
                res[y] = array[i];
                y++;
            }
        }
        return res;
    }
};

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

JZ39 数组中出现次数超过一半的数字

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

方法一：哈希法
根据题目意思，显然可以先遍历一遍数组，在map中存每个元素出现的次数，然后再遍历一次数组，找出众数。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector numbers) {
        unordered_map mp;
        for (const int val : numbers) ++mp[val];
        for (const int val : numbers) {
            if (mp[val] > numbers.size() / 2 ) return val;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11

方法二：排序法
可以先将数组排序，然后可能的众数肯定在数组中间，然后判断一下。

class Solution {
public:
    int MoreThanHalfNum_Solution(vector numbers) {
        sort(numbers.begin(), numbers.end());
        int cond = numbers[numbers.size() / 2];
        int cnt = 0;
        for (const int k :numbers) {
            if (cond == k) ++cnt;
        }
        if (cnt > numbers.size() / 2) return cond;
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

JZ43 整数中1出现的次数（从1到n整数中1出现的次数）

输入一个整数 n ，求 1～n 这 n 个整数的十进制表示中 1 出现的次数
例如， 1~13 中包含 1 的数字有 1 、 10 、 11 、 12 、 13 因此共出现 6 次

注意：11 这种情况算两次

进阶：空间复杂度 O(1) \O(1) ，时间复杂度 O(lognn) \O(lognn)

方法一：暴力统计

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        //遍历1-n
        for(int i = 1; i <= n; i++){ 
            //遍历每个数的每一位
            int j = i;
            while(j){
                if(j%10==1)
                    res++;
                j=j/10;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：按位统计法（推荐使用）
step 1：准备一个基础变量，记录位数，从1开始，每轮循环扩大10倍。
step 2：从1开始，即个位开始，直到基础变量大于n，每次按照公式统计相应位置1的个数。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        //MulBase = 10^i
        long long MulBase = 1;
        //每位数按照公式计算
        for(int i = 0; MulBase <= n; i++){ 
            //根据公式添加
            res += (n / (MulBase * 10)) * MulBase + 
                        min(max(n % (MulBase * 10) - 
                        MulBase + 1, (long long)0), MulBase);
            //扩大一位数
            MulBase *= 10; 
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

JZ45 把数组排成最小的数

只考虑首字符的大小不可靠，但是如果字符串a拼接b的得到的数字大于b拼接a，那么肯定b应该排在a的前面，我们要就按照这样的次序将排序的比较重载就可以了。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9Ay0Bkrl-1658324510160)(vx_images/556874022249422.png =400x)]

step 1：优先判断空数组的特殊情况。
step 2：将数组中的数字元素转换成字符串类型。
step 3：重载排序比较为字符串类型的x + y < y + x，然后进行排序。
step 4：将排序结果再按照字符串拼接成一个整体。

class Solution {
public:
    //重载排序比较方式
    static bool cmp(string& x, string& y){
        //叠加
        return x + y < y + x;
    }
    string PrintMinNumber(vector numbers) {
        string res = "";
        //空数组的情况
        if(numbers.size() == 0)
            return res;
        vector nums;
        //将数字转成字符
        for(int i = 0; i < numbers.size(); i++)
            nums.push_back(to_string(numbers[i]));
        //排序
        sort(nums.begin(), nums.end(), cmp);
        //字符串叠加
        for(int i = 0; i < nums.size(); i++)
            res += nums[i];
        return res;
    }
};

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

JZ49 丑数

基础数学 二分

把只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

方法一：
step 1：第一个丑数1加入数组。
step 2：使用i、j、k三个索引表示该数字有无被乘2、乘3、乘5.
step 3：后续继续找n−1n-1n−1个丑数，每次取当前丑数索引乘2、乘3、乘5的最小值加入数组，并计数。
step 4：若是该丑数为相应索引乘上某个数字，则对应的索引往后一位。

class Solution {
public:
    //寻找三个数中的最小值
    int findMin(int x, int y, int z){  
        int res = x; 
        res = y < res ? y : res;
        res = z < res ? z : res;
        return res;
    }
    int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0; 
        //按顺序记录丑数
        vector num; 
        num.push_back(1);
        //记录这是第几个丑数
        int count = 1; 
        //分别代表要乘上2 3 5的下标
        int i = 0, j = 0, k = 0; 
        while(count < index){
            //找到三个数中最小的丑数
            num.push_back(findMin(num[i] * 2, num[j] * 3, num[k] * 5)); 
            count++;
            //由2与已知丑数相乘得到的丑数，那该下标及之前的在2这里都用不上了
            if(num[count - 1] == num[i] * 2)
                i++; 
            //由3与已知丑数相乘得到的丑数，那该下标及之前的在3这里都用不上了
            if(num[count - 1] == num[j] * 3)
                j++; 
            //由5与已知丑数相乘得到的丑数，那该下标及之前的在5这里都用不上了
            if(num[count - 1] == num[k] * 5)
                k++; 
        }
        return num[count - 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38

方法二：最小堆（推荐使用）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YiTbp66p-1658324510161)(vx_images/248335722244530.png =600x)]

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        //排除0
        if(index == 0)
            return 0; 
        //要乘的因数
        vector factors = {2, 3, 5}; 
        //去重
        unordered_map mp; 
        //小顶堆
        priority_queue, greater> pq; 
        //1先进去
        mp[1LL] = 1; 
        pq.push(1LL);
        long res = 0;
        for(int i = 0; i < index; i++){ 
            //每次取最小的
            res = pq.top(); 
            pq.pop();
            for(int j = 0; j < 3; j++){
                //乘上因数
                long next = res * factors[j]; 
                //只取未出现过的
                if(mp.find(next) == mp.end()){  
                    mp[next] = 1;
                    pq.push(next);
                }
            }
        }
        return (int)res;
    }
};
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

JZ74 和为S的连续正数序列

知识点 穷举

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U0xWtYLm-1658324510163)(vx_images/324960023252041.png =700x)]

输入：9
返回值：[[2,3,4],[4,5]]

方法一：滑动窗口（推荐使用）

class Solution {
public:
    vector > FindContinuousSequence(int sum) {
        vector > res;
        vector temp;
        //从1到2的区间开始
        int l = 1, r = 2;
        while(l < r){ 
            //计算区间内的连续和
            int sum1 = (l + r) * (r - l + 1) / 2; 
            //如果区间内和等于目标数
            if(sum1 == sum){ 
                temp.clear();
                //记录区间序列
                for(int i = l; i <= r; i++) 
                    temp.push_back(i);
                res.push_back(temp);
                //左区间向右
                l++; 
            //如果区间内的序列和小于目标数，右区间扩展
            }else if(sum1 < sum) 
                r++;
            //如果区间内的序列和大于目标数，左区间收缩
            else 
                l++;
        }
        return res;
    }
};
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

JZ57 升序数组中和为S的两个数字

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xfhMGUnz-1658324510164)(vx_images/328051123251052.png =600x)]

方法一：双指针

class Solution {
public:
    vector FindNumbersWithSum(vector array,int sum) {
        vector res;
        //左右双指针
        int left = 0, right = array.size() - 1;
        //对撞双指针
        while(left < right){
            //相加等于sum，找到目标
            if(array[left] + array[right] == sum){
                res.push_back(array[left]);
                res.push_back(array[right]);
                break;
            //和太大，缩小右边
            }else if(array[left] + array[right] > sum)
                right--;
            //和太小，扩大左边
            else
                left++;
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：map

class Solution {
public:
    vector FindNumbersWithSum(vector array,int sum) {
        vector res;
        //创建哈希表,两元组分别表示值、下标
        unordered_map mp; 
        //在哈希表中查找sum-array[i]
        for(int i = 0; i < array.size(); i++){
            int temp = sum - array[i];
            //若是没找到，将此信息计入哈希表
            if(mp.find(temp) == mp.end()){ 
                mp[array[i]] = i;
            }
            else{
                //取出数字添加
                res.push_back(temp);   
                res.push_back(array[i]);
                break;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

JZ58 左旋转字符串

字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc”
将给定字符串循环左移n位
即最左边的nnn位按照顺序整体接到右边末尾

方法一：拼接

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int m = str.length();
        //特殊情况
        if(m == 0)
            return "";
        //取余，因为每次长度为m的旋转数组相当于没有变化
        n = n % m;
        string res = "";
        //先遍历后面的，放到前面
        for(int i = n; i < m; i++)
            res += str[i];
        //再遍历前面的放到后面
        for(int i = 0; i < n; i++)
            res += str[i];
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法二：三次旋转

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int m = str.length();
        //特殊情况
        if(m == 0)
            return "";
        //取余，因为每次长度为m的旋转相当于没有变化
        n = n % m;
        //第一次逆转全部数组元素
        reverse(str.begin(), str.end());
        //第二次只逆转开头m个
        reverse(str.begin(), str.begin() + m - n);
        //第三次只逆转结尾m个
        reverse(str.begin() + m - n, str.end());
        return str;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

JZ62 孩子们的游戏(圆圈中最后剩下的数)

首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0… m-1报数…这样下去…直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢？

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OqIHqVQu-1658324510165)(vx_images/8654017238393.png =600x)]

方法一：模拟的思路

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n < 1 || m < 1)
            return -1;

        vector circle;
        for(int i=0; i 1){
            start = (start + m - 1) % n;
            circle.erase(circle.begin() + start);
            n--;
        }
        return circle[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

JZ75 字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g” 。当从该字符流中读出前六个字符 “google" 时，第一个只出现一次的字符是"l"。

class Solution
{
public:
    unordered_map mp;
    //记录输入的字符串
    string s;
    //Insert one char from stringstream
    void Insert(char ch) {
        //插入字符
        s += ch;  
        //哈希表记录字符出现次数
        mp[ch]++; 
    }
    //return the first appearence once char in current stringstream
    char FirstAppearingOnce() {
        //遍历字符串
        for(int i = 0; i < s.length(); i++) 
            //找到第一个出现次数为1的
            if(mp[s[i]] == 1) 
                return s[i];
        //没有找到
        return '#'; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

JZ14 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m] 。请问 k[1]k[2]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4YYS7Y0k-1658324510171)(vx_images/232054018225384.png =600x)]

class Solution {
public:
    int cutRope(int number) {
        //不超过3直接计算
        if(number <= 3) 
            return number - 1;
        //dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        vector dp(number + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        //遍历后续每一个长度
        for(int i = 5; i <= number; i++)
            //可以被分成两份
            for(int j = 1; j < i; j++)
                //取最大值
                dp[i] = max(dp[i], j * dp[i - j]);
        return dp[number];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

JZ81 调整数组顺序使奇数位于偶数前面(二)

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

要求：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)

class Solution {
public:
    vector reOrderArrayTwo(vector& array) {
        //双指针
        int i = 0;
        int j = array.size() - 1; 
        //向中间聚合
        while(i < j){ 
            //左右都是奇数，左移右不动
            if(array[i] % 2 == 1 && array[j] % 2 == 1) 
                i++;
            //左奇数右偶数，左右都向中间缩
            else if(array[i] % 2 == 1 && array[j] % 2 == 0)
                i++, j--;
            //左偶右奇数
            else if(array[i] % 2 == 0 && array[j] % 2 == 1) 
                //交换
                swap(array[i], array[j]); 
            //左右都是偶数，只移动右指针
            else 
                j--;
        }
        return array;
    }
};

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

JZ83 剪绳子（进阶版）

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m] 。请问 k[1]k[2]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

由于答案过大，请对 998244353 取模。
进阶：空间复杂度 O(1)O(1) ， 时间复杂度 O(logn)

JZ17 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

class Solution {
public:
    vector printNumbers(int n) {
        string s="";
        for(int i = 0; i < n; i++)
            s += '9';
        int max = stoi(s);
        vector res;
        for(int j = 1; j <= max; j++)
            res.push_back(j);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

Leetcode 部分

剑指 Offer 58 - I. 翻转单词顺序

双指针法，进行切片，定义一个指针指向末尾，遇到非空格就另存，然后将其前向移动，再次遇到空格停止
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-prYKGukM-1658324510171)(vx_images/452532820250809.png =500x)]

剑指 Offer 57. 和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
双指针解法即可
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kASoCOud-1658324510172)(vx_images/527142820229743.png =500x)]

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 滑动窗口法
当窗口的值大于target 右指针+1 小于 target 左指针+1
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Qi01YXHc-1658324510174)(vx_images/7842920229645.png =600x)]

剑指 Offer 58 - II. 左旋转字符串

指定k 将前k个字符移动到后面，
先翻转整体，然后翻转 前n-k个 后K个字符
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CNJE8cwI-1658324510175)(vx_images/82462920239967.png =500x)]

剑指 Offer 59 - I. 滑动窗口的最大值

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QjoORExU-1658324510176)(vx_images/170902920243351.png =750x)]

剑指 Offer 65. 不用加减乘除做加法

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4HAsITUy-1658324510177)(vx_images/281712920248149.png =500x)]

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-keaUgYDO-1658324510180)(vx_images/349692920244508.png =700x)]

剑指 Offer 43. 1～n 整数中 1 出现的次数

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HBBwSc96-1658324510182)(vx_images/373483020236593.png =800x)]