法1：重载比较运算符 如果字符串a拼接b的得到的数字大于b拼接a，那么肯定b应该排在a的前面，我们要就按照这样的次序将排序的比较重载就可以了。 PS：重载比较运算符，如何确定是升序还是降序？1. 核心规则 升序：当 a < b 返回 true 时，排序算法会将 a 放在 b 前面（即 a 比 b 小，按从小到大排列）。 降序：当 a > b …

感觉像是模拟题，法1，暴力遍历，时间复杂度应该是On class Solution { public: int get1(int x){ int sum = 0; while(x){ if(x % 10 == 1){ sum++; } x = x / 10; } return sum; } int NumberOf1Between1AndN_Sol…

动态规划 方法1，可以通过暴力On^2的方法，循环两次求出每个子数组的和对比。 法2.DP 设dp[i]，dp[i]代表以array[i]为结尾的连续子数组最大和。 转移方程为，dp[i] = max(array[i]，dp[i-1] + array[i])，理解如下： 因为以第n个数为结尾，所以array[n]是必然被选择的 基于dp[n-1]的…

要求空间复杂度On，时间复杂度O(nlogk)。 一般我们说 topK 问题，就可以用大顶堆或小顶堆来实现 最大的 K 个：小顶堆 最小的 K 个：大顶堆 堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。注意！大顶堆or小顶堆并非是从大到小的序列，因此才需要堆排序！ 堆可以分为大顶堆和…

感觉面试会考 有两种常规方法，哈希表与排序。但是做不到空间复杂度O1，时间复杂度On。 投票法： 核心思想是，如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。 选择一个cnt初始化为0，选择一个res 遍历数组，如果cnt为0的时候，就选择当前数字作为res 若cnt不为0，re…

类似dfs全排列问题。 有一道相似的题目，可以参考acwing的解析：AcWing 842. 排列数字--深度优先遍历代码+注释 - AcWing，题目如下： 给定一个整数 nn，将数字 1∼n排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。 算法： 用 path 数组保存排列，当排列的长度为 n 时，是一种方案，输出。 …

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n^2)要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 二叉搜索树：左<根<右 法1：中序遍历将二叉搜索树进行中序遍历可以得到由小到大的…

涉及一个知识点，深拷贝与浅拷贝。 特性深拷贝 (Deep Copy)浅拷贝 (Shallow Copy)定义创建一个新对象，并递归复制所有成员及其指向的资源仅复制指针值，新旧对象共享同一块内存内存管理新旧对象完全独立，修改互不影响修改任一对象会影响另一个（可能导致双重释放或内存泄漏）性能较慢（需分配新内存并复制数据）极快（仅复制指针）使用场景需要完…