链表中倒数最后k个结点：最直观的想法是，快慢指针，在没有使用头结点的情况下，快指针使用倒数第一个作为标准，慢指针使用倒数第k个作为标准，快慢指针相差k-1，所以快指针先走k-1步，如果还没走完就已经为空指针，则表示链表长度小于k，并返回空节点nullptr，反之快慢指针一起走，当快指针到达最后一个结点时，返回慢指针，其即为链表中倒数最后k个结点。注意，之所以选择最后一个结点作为快指针的标准，是因为考虑链表长度正好等于k这种特殊情况，慢指针本身起始就指向第一个结点，倒数第链表长度个结点时其是不用走的。 ListNode* FindKthToTail(ListNode* pHead, int k)...

调整数组顺序使奇数位于偶数前面(一)：最直观的想法是，如果是仅仅调整数组顺序使奇数位于偶数前面，那么就使用双指针，一个指针从前往后遍历寻找数组中的偶数，一个指针从后往前遍历寻找数组中的奇数，然后交换两者，但是题目中要求保证奇数和奇数、偶数和偶数之间的相对位置不变，那么双指针的想法就有点不可行了，于是就想到从前往后遍历数组，奇数就存在odd数组中，偶数就存在even数组中，然后再将even数组追加到odd数组后面，并返回odd数组即可。 vector<int> reOrderArray(vector<int>& array) { vector<int> odd...

表示数值的字符串：最直观的想法是，判断是否可以将字符串str转换为浮点数float，此处可以调用python中的内置函数float，如果发现异常则返回false，否则返回true。注意，虽然C++中的stof函数也能够把字符串转换成浮点数，但是其是读取到不满足即停止，比如字符串"1.2.3"，stof会将其转换为1.2，但实际上整体是不能转换的。注意，python代码注意缩进。 def isNumeric(self , str: str) -> bool: try: float(str) except: return False return True 正则匹配：其实，该题描述，数字、空...

正则表达式匹配：最直观的想法是，递归，由于*比较特殊，其表示前面的字符重复0次、1次、多次，故需要分情况讨论。首先判断pattern是否为空，如果其为空，str也为空，那么可以匹配，反之如果str不为空，那么不可以匹配；接着我们使用first来表示pattern和str的第一位是否匹配，由于前面pattern为空时会返回，故到这里pattern肯定不为空，此时pattern和str第一位匹配的条件是str不为空，并且pattern[0]等于str[0]或者pattern[0]等于'.'；然后我们根据'*'来分情况讨论，由于'*'不能单独使用，其前面至少要有一个字符，所以每次都是判断patter...

删除链表的节点：最直观的想法是，将删除链表的节点分为两类，一类是删除的就是头节点，那么就直接返回头节点的下一个节点，另一类是删除的不是头节点，那么就利用被删除节点的前驱来删除对应的节点，注意对节点的判空。 ListNode* deleteNode(ListNode* head, int val) { //保存头节点信息用于使用 ListNode *p=head; //要删掉的是头节点 if(p->val==val) return p->next; //要删掉的不是头节点 通过节点的前驱来实现删除 while(p&&p->next) { if(p->next->va...

打印从1到最大的n位数：最直观的想法是，先求出最大的n位数，一般来说是n个9，那么不妨设maxn初始为0，然后for循环n次，每次maxn=maxn*10+9，最后即可得maxn值，再进行for循环maxn次，将从1、2、3……maxn依次加入结果数组res中即可。 vector<int> printNumbers(int n) { int maxn=0; for(int i=1;i<=n;i++) maxn=maxn*10+9; vector<int> res(maxn); for(int i=1;i<=maxn;i++) res[i-1]=i; retu...

数值的整数次方：最直观的想法是，求a的b次方，使用for循环直接循环b次。更快求数值的整数次方的方法是快速幂，其基本思想是：如果b是偶数，那么ab就分为ab/2×ab/2；如果b是奇数，那么ab就分为ab-1×a。举一个通俗易懂的例子，比如求55，则55=54×5，54=52×52，52=51×51。如果使用计算机来实现的话，可以使用二进制来判断，当指数大于0时进入循环，首先判断指数的最后一位是否为1，如果是则将其乘入结果，同时每次循环中还需要对底数进行自乘并将指数右移一位，为下次循环做准备。 double Power(double base, int exponent) { double r...

二进制中1的个数：最直观的想法是，将n与1进行位运算，这样有两种方法，一种是左移1，一种是右移n，两者均是判断n的每一位与1的位运算，如果是左移1，此时结果不为0即表明n当前为1，如果右移n，此时结果为1则表明n当前为1。for循环进行32次。 int NumberOf1(int n) { int res = 0; for (int i = 0; i < 32; i++) { if ((n & (1 << i)) != 0) res++; } return res; }  int NumberOf1(int n) { int res = 0; for (int i = 0; ...

剪绳子：最直观的想法是，长度为n的绳子分为m段，由于绳子长度越接近乘积越大，那么每一段长度为n/m，假设乘积为y，则y=(n/m)m，两边进行取对数，则lny=mln(n/m)，两边对m进行求导，则可得y'1/y=ln(n/m)+mm/n(-n/m2)，即y'=(ln(n/m)-1)(n/m)m，令y'=0，则m=n/e，故绳子长度为n/m=e，e约等于2.7，又绳子长度为整数，故取3最大。由于将绳子长度分为1时，只会减少长度，而不会增加乘积，又m>1，故n=2时分为1和1结果为1，n=3时分为2和1结果为2，当n>=4时，如果n%3==0，则结果为3的n/3次方，如果n%3==1...

机器人的运动范围：最直观的想法是，使用一个divide数组保存数字的数位和，使用一个dp数组保存元素是否被访问过，然后从下标[0,0]开始进行dfs遍历。其中dfs遍历的过程如下，首先是处理不合法下标以及不合法数位和以及重复访问，然后是标记访问并且计算当前结果res并返回，其计算公式为上下左右四个方向的dfs结果加上当前该元素的访问之和。如果内存超出限制的话，检查一下是否是没有标记访问，从而导致的重复访问。 int dfs(vector<vector<bool>>& dp, vector<int>& divide, int threshold, int ro...

矩阵中的路径：最直观的想法是，首先使用stxy变量存放矩阵matrix中出现的所有word起始位置元素的下标，然后以这些下标为起始开始dfs遍历，并使用tfxy变量存放矩阵matrix中的元素是否被访问，判断是否存在一条字符串路径，如果存在则直接返回true，如果所有均遍历完后仍不存在，则返回false。其中dfs遍历是这样的，首先判断字符串word是否已经访问结束，如果是则返回true，然后判断矩阵下标是否合法，如果不合法则返回false，接着判断矩阵元素是否等于字符串元素，如果是则记录元素已访问，并且返回上下左右四个方向的遍历。 bool dfs(vector<vector<c...

旋转数组的最小数字：最直观的想法是，遍历一遍整个数组，使用Minx来获取最小值。 int minNumberInRotateArray(vector<int> rotateArray) { int Minx=INT_MAX; for(int i=0;i<rotateArray.size();i++) Minx=rotateArray[i]<Minx?rotateArray[i]:Minx; return Minx; } 优化：写完上述方法后我就有一个疑问，这样的方法适合任何一个数组，但是题目为什么特意强调旋转数组呢？是不是有什么信息尚未用到？于是我又看到了题目标签上写着...

斐波那契数列：最直观的想法是，由于fib(x)=fib(x-1)+fib(x-2)，其中x>=3，当x=1或者2时，fib(x)=1，那么我们不妨令a=1，b=1，c=1，其中循环从3开始直到n，不断交替变换，使得c=a+b，a=b，b=c，如此最后c即是我们想要的结果。 int Fibonacci(int n) { int a=1,b=1,c=1; for(int i=3;i<=n;i++) { c=a+b; a=b; b=c; } return c; } idea：由于题目直接给出了递推公式，那么我们也可以使用递归来做。 int Fibonacci(int n) { int f...

用两个栈实现队列：最直观的是，一个栈stack1作为入栈，一个栈stack2作为出栈，栈是先进后出，队列是先进先出，所以一个栈无法实现队列，我们需要两个栈来实现，先进后出再先进后出就是先进先出啦。在队列尾部插入整数(push)即直接向stack1中插入元素即可；在队列头部删除整数(pop)即首先判断stack2是否为空，如果不为空则直接从stack2中弹出元素，反之则将stack1中的元素全部弹出来压入stack2中，待到stack1为空时，从stack2中弹出最后一个元素即可，记得要先判断stack2是否为空，这样才不会打乱顺序。 class Solution { public: void ...