日常练习:C++编程题

1.数对 

• 纯数学,推公式

2.除自身数组以外的乘积

•  数组before记录每个数字之前的积
• 数组end记录每个数字之后的积

3.圣诞树

• 这道题的特殊情况不好解决，用了个int m = n，后面用m--控制特殊情况的个数 

4.超级圣诞树 

• 有一点难 

5.回型矩阵 

• a[i][++j],                 a[++i][j],                  a[i][--j] ,                 a[--i][j] 
• while控制循环,i和j来回交替变化

6.蛇形矩阵

•  while控制循环,i和j来回交替变化

7.小q的数列

•  f(n) = 这个数二进制中1的个数
• n` = 2 * (这个数二进制中1的个数) - 1

8.大吉大利，今晚吃鸡

• 动归问题,重点是状态转义方程 dp[i] = dp[i-1] * 3 + 2;

9.配对交换

•  将一个数 & 0x55555555 得到奇数位
• 将一个数 & 0xaaaaaaaa 得到偶数位

10.阶乘尾数

• int count = 0;// 记录5^i出现的个数
• 要产生10,100,1000,必定会出现5,25,125

11.求1+2+3+...+n 

• 用变长数组和C++中类的构造函数就可以解决问题

12.数列 

• 用输入项的最大值作为边界,只建立一次vector

13.搜索旋转排序数组 

• 先判断左半段是否有序
• 如果目标值在左半段则r = mid - 1,锁定左半段
• 如果目标值不在左半段则l = mid + 1,

14.从链表中删去总和值为零的连续节点

• 这里需要自己设计一个哨兵位,使用unordered_map

15.从根到叶的二进制数之和 

•  二进制转换成整数的关键: sum = sum * 2 + root->val;

16.二叉树的坡度 

• 在这道题中, 需要返回根和左右子树

17.奇偶树 

• 层次遍历，将每一层的数据都入列。对每一层的数据分析是否满足条件即可
• 创建数组queue，分别用front和rear来维护队列的首尾，k表示奇偶，flag表示单调
• push进去元素后，rear++,相当于元素入列
• front = rear（++之前的），相当于元素出列

18.字符串相乘

• 这道题需要模拟实现乘法的过程，逆置->一个一个的乘->不断的累加 

19. 杨辉三角

•  resize开空间和初始化，front返回第一个元素的引用，back返回最后一个元素的引用

20.电话号码的字母组合 

•  通过循环控制递归

21.最小栈 

•  一个普通的栈
• 一个最小栈,保留每次插入的数比栈顶元素小于或等于的数
• 在使用栈.top()时,栈的元素必须不为空,否则报错

22.栈的压入、弹出序列 

23. 逆波兰表达式求值

         

•  操作数入栈
• 操作符,取栈中的两个操作数进行运算,然后再放回栈中

23.字符串相乘

•  只需要在一个string中操作就行了,并解决2个特殊情况

24.二叉搜索树与双向链表 

•  需要定义一个prev找节点的上一个

25.二叉树的最近公共祖先 

•  利用栈存节点的路径,找到了直接返回

• 一个节点的左右子树中都没有目标节点,则在路径中去掉这个节点

26. 任务调度器

• 利用桶的思想, 最短时间 = max(情况一,情况二)

27.适龄的朋友

•  桶排序,将年龄相同的放入一个桶中,
• 先算年龄相同的,再计算桶间的(利用条件一,二的范围)

28.快照数组 

使用数据结构:unordered_map<int, map<int, int>> mp; // 分别存储索引，快照号,修改之后的值 

• 定义一个数组存放每个下标在每个snap下的值
• 初始化数组为0
• set数组时, 将对应的下标和snap的值进行修改
• snap时,只增加snap_id
• get是, 使用二分法,查找对应下标下的小于等于snap_id的值.

28.LRU缓存  

 

 

•  使用哈希链表解决,哈希查找O(1),链表插入删除O(1)

29.Excel表格名称

• 这是一道从 1 开始的 26进制转换题。 

• 进制转化前: 先执行减一操作，从而实现整体偏移。