LeetCode中《程序员面试金典》编程题
时间 | 记录内容 | 备注 |
---|---|---|
2020年2月17日 | 开始着手刷题 | 起步 |
本仓库链接:https://github.com/guyongpu/LeetCode_LCCI.git 本仓库为LeetCode刷题记录,网址为:https://leetcode-cn.com/problemset/lcci/ ,点击跳转到LeetCode中文题库 每个题的代码放在src中,在main.cpp设置prob_num的值,prob_num为题目编号,然后运行测试函数即可,例如需要运行题1时,在main.cpp中设置prob_num=1即可:
#include <iostream>
#include "src/P0000_Solutions.h"
using namespace std;
int main() {
int prob_num = 2;
P0000_Solutions obj;
obj.test(prob_num);
cout << "Probelem " << prob_num << " run finish!" << endl;
return 0;
}
然后点击运行即可,题1结果如下:
0
1
Probelem 1 run finish!
Process finished with exit code 0
文件名 | 内容描述 |
---|---|
P0000_CommonHead.h | 用于声明一些公用的结构体或者函数,如树节点、链表节点等,在需要的时候引用. |
P0000_Solutions.h | 用于测试的头文件,则其中引入各个文件的头文件,用于创建各个问题的类. |
P0000_Solutions.cpp | 用于测试的源程序,在switch函数中创建并调用各个问题类的test()函数进行运行测试. |
Pxxxx_*******.h | 表示编号为xxxx问题的类的头文件. |
Pxxxx_*******.cpp | 表示编号为xxxx问题的类的头文件相对应的源程序. |
题号 | 题目名 | 完成日期 | 描述 | 备注 |
---|---|---|---|---|
P0001_01 | 判定字符是否唯一 | 2020.2.17 | 描述:实现一个算法,确定一个字符串 s 的所有字符是否全都不同. 思路:可以使用排序,集合方法做,此处采用排序方法,未使用额外内存. |
基础题 |
P0001_02 | 判定是否互为字符重排 | 2020.2.17 | 描述:给定两个字符串 s1 和 s2,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串. 思路:法1,直接排序后比较;法2,可以通过HashMap的方法比较s1和s2中字符出现次数是否相等. |
掌握法1和法2 |
P0001_03 | URL化 | 2020.2.18 | 描述:URL化。编写一种方法,将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的“真实”长度. 思路:在原数组上进行操作,由少变多,从后开始遍历,双指针法,先计算newLength,再遍历替换. |
在末位要加上'\0',C++11标准 |
P0001_04 | 回文排列 | 2020.2.18 | 描述:给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一. 思路:法1,采用hash方法,统计每个字符出现的次数;法2,排序后计算每个字符出现的次数是否为偶数,只能出现一次奇数. |
掌握法1和法2 |
P0001_05 | 一次编辑 | 2020.2.18 | 描述:字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串,编写一个函数判定它们是否只需要一次(或者零次)编辑. 思路:先判断是否相等,再判断长度,情况1,长度相等则替换一个,情况2,不相等则双指针操作,替换一个. |
注意细节 |
P0001_06 | 字符串压缩 | 2020.2.18 | 描述:字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能,若“压缩”后的字符串没有变短,则返回原先的字符串. 思路:一次遍历,顺序计算字符出现的次数,最后比较压缩前后的长度. |
要仔细些 |
P0001_07 | 旋转矩阵 | 2020.2.19 | 描述:给定一幅由N × N矩阵表示的图像,其中每个像素的大小为4字节,编写一种方法,将图像旋转90度. 思路:matrix[i][j]旋转后为matrix[j][n-i],所以先i,j交换,再左右交换. |
掌握分析方法 |
P0001_08 | 零矩阵 | 2020.2.19 | 描述:编写一种算法,若M × N矩阵中某个元素为0,则将其所在的行与列清零. 思路:法1.将行列用set存储,第二次遍历时清零;法2.用第一行和第一列存储,然后对matrix[0][0]特殊处理. |
掌握法1和2 |
P0001_09 | 字符串轮转 | 2020.2.20 | 描述:字符串轮转。给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成. 思路:法1.s1必定包含在s2+s2中,如:s1=xyz,s2=yzx,则s2在xyzxyz中;法2.s1循环模拟旋转,与s2比较. |
掌握法1和2 |
P0002_01 | 移除重复节点 | 2020.2.20 | 描述:移除未排序链表中的重复节点。保留最开始出现的节点. 思路:法1.使用set或者数组标记节点是否出现,再保留不重复节点;法2.检查每个节点是否出现,然后删除重复节点. |
法1.节省时间;法2.节省空间 |
P0002_02 | 返回倒数第 k 个节点 | 2020.2.20 | 描述:实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值. 思路:双指针法,index_2先走K-1步,然后index_1再走,知道index_2指向最后一个节点,则index_1为结果. |
双指针法 |
P0002_03 | 删除中间节点 | 2020.2.20 | 描述:实现一种算法,删除单向链表中间的某个节点. 思路:使用覆盖值的方法,用后面的值覆盖前面的值. |
掌握方法 |
P0002_04 | 分割链表 | 2020.2.20 | 描述:编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的 节点之前,内部顺序无要求. 思路:法1.使用两个新链表节点,将两部分分别挂到链表上;法2.使用双指针,符合条件时进行交换. |
掌握法1和2 |
P0002_05 | 链表求和 | 2020.2.21 | 描述:给定两个用链表表示的整数,每个节点包含一个数位,这些数位是反向存放的,也就是个位排在链表首部,编写函数对这两个整数求和,并用链表形式返回结果. 思路:遍历两个链表,将各个节点的值相加即可,注意处理最后的进位. |
如果头为最高位,则可以用栈进行处理 |
P0002_06 | 回文链表 | 2020.2.21 | 描述:编写一个函数,检查输入的链表是否是回文的. 思路:先计算链表长度,然后对后半段进行反转,最后再分别遍历前后半段比较. |
掌握方法 |
P0002_07 | 链表相交 | 2020.2.21 | 描述:给定两个(单向)链表,判定它们是否相交并返回交点. 思路:使用快慢指针,先计算长度,然后长的先走dif步,再一起遍历比较. |
注意细节 |
P0002_08 | 环路检测 | 2020.2.21 | 描述:给定一个有环链表,实现一个算法返回环路的开头节点. 思路:快慢指针,1.快指针每次2步,慢指针每次1步,最后step步后相遇则有环;2.快指针先走step步,然后一起走,第一次相遇则为入口节点. |
注意细节 |
P0003_01 | 三合一 | 2020.2.22 | 描述:三合一。描述如何只用一个数组来实现三个栈. 思路:定义stackSize,stack,top三个变量,实现栈的操作,top记录栈的元素个数,stack为数组,前中后三段. |
注意细节即可 |
P0003_02 | 栈的最小值 | 2020.2.22 | 描述:请设计一个栈,除了常规栈支持的pop与push函数以外,还支持min函数,该函数返回栈元素中的最小值. 思路:使用两个vector,一个存储元素,另一个保存最小值,在push和pop的时候需要注意细节. |
注意细节 |
P0004_04 | 检查平衡性 | 2020.3.12 | 描述:实现一个函数,检查二叉树是否平衡. 思路:计算每个节点的左右子树深度,然后递归计算. |
要复习这个题 |
P0004_05 | 合法二叉搜索树 | 2020.3.13 | 描述:实现一个函数,检查一棵二叉树是否为二叉搜索树. 思路:法1,使用递归中序遍历;法2,使用迭代中序遍历;法3,直接比较leftright,且父节点满足要求. |
掌握三种方法 |
P0005_01 | 插入 | 2020.3.10 | 描述:给定两个32位的整数N与M,以及表示比特位置的i与j.编写一种方法,将M插入N,使得M从N的第j位开始,到第i位结束.. 思路:先构造掩码,将N的i-j位置为0,然后通过或运算,使用M替换N的i-j位.. |
也可以用bitset做,更简单 |
P0005_02 | 二进制数转字符串 | 2020.3.9 | 描述:给定一个介于0和1之间的实数,类型为double,打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示,则打印“ERROR”. 思路:将小数部分逐位转化为二进制,当计算次数超过32,则返回ERROR. |
仔细处理 |
P0005_03 | 翻转数位 | 2020.3.8 | 描述:给定一个32位整数 num,你可以将一个数位从0变为1。请编写一个程序,找出你能够获得的最长的一串1的长度. 思路:将连续的1记录成线段,(起点,终点,长度),然后再遍历计算,整个过程需要遍历两次. |
使用bitset实现 |
P0005_04 | 下一个数 | 2020.3.8 | 描述:下一个数。给定一个正整数,找出与其二进制表达式中1的个数相同且大小最接近的那两个数(一个略大,一个略小). 思路:大数,将01转化为10,并将低位的1移到最右侧;小数,将10转化为01,并将低位的1移到最左侧. |
使用bitset,数据的低位在左边 |
P0005_06 | 整数转换 | 2020.3.7 | 描述:整数转换。编写一个函数,确定需要改变几个位才能将整数A转成整数B. 思路:step1:先对符合进行处理;step2:将AB化为正数;step3:异或,计算结果1的个数. |
注意对符号位优先处理 |
P0005_07 | 配对交换 | 2020.3.7 | 描述:配对交换.编写程序,交换某个整数的奇数位和偶数位,尽量使用较少的指令. 思路:使用掩码分别取出奇数位和偶数位,然后奇数位左移,偶数位右移,再或运算,注意偶数位右移后去掉符号位. |
注意在右移后去掉符号位 |
|P000||2020.3.9|描述:.
思路:.||
|P000||2020.3.9|描述:.
思路:.||
|P000||2020.3.14|描述:.
思路:.||