1 概述 1.1 数据结构 数组 链表 二叉树 树 栈 队列 图 1.2 算法 问题 1.2 解法 2 数组 2.1 所有0移动到数组的末尾 2.2 移除数组指定元素 2.3 移除数组重复元素 2.4 移除数组数量大于2的元素 2.5 数组重复元素排序 2.6 第K个最大数 2.7 最大的K个数 2.8 两数之和 参考 1 概述 1.1 数据结构 数组 排序 滑动窗口 去重 碰撞指针：回文串 链表 反转链表 二叉树 递归 树 b树：一个节点存多个值 降低树高度，结和IO机制，降低IO次数 b+树：只有叶子节点存数据 高效：中间节点不存数据，可存更多节点 稳定：查找次数一致 有序：叶子节点组成链表，方便批量查询 b-link树：节点指向右兄弟；每个节点存储High-key 并发：根据High-key，并发场景下，可判断节点是否发生分裂，无需加锁 栈 队列 图 1.2 算法 动态规划 功能：用表记录所有结果，避免重复计算（斐波那契、最长公共子序列） 问题 回溯：枚举 + 剪枝 分治 贪心 ...
https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13 链表 从尾到头打印链表 栈 递归 链表反转 栈 双指针 1 -> 2 -> 3 -> 4 1 <- 2 -> 3 -> 4 递归 合并两个有序链表 迭代 递归 两个链表的第一个公共结点 1 -> 2 -> 3 | 4 -> 5 |-> 6 -> 7 栈 双指针：先计算长度，再找起点 map：第一个cnt > 1的节点 链表中环的入口节点 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ^ ^ 环 相遇（相遇时，快指针多走了1个环） 快指针：1 2 3 4 5 6 7 8 3 4 5 6 （前后长度一定相等：1 2 和 7 8） 慢指针：1 2 3 4 5 6 快指针：1 2 3 4 5 2 3 4 满指针：1 2 3 4 map：第一个cnt > 1的节点 快慢指针：首先，找到相遇节点；然后，慢指针接着走，新指针从头走（一次一步），再次相遇。 链表倒数第K个节点 双指针：前指针先走K步 栈 复杂链表的复制 1 -> 2 -> 3 -> 4 -> 5 3 5 * 2 * 1 _1 2 _2 3 _3 4 _4 5 _5 # 1. 复制后的新节点放在旧节点之后 3 5 * 2 * # 2. 找到旧节点的旧random节点 _3 _5 * _2 * # 3. 旧random节点的下一个节点即为新random节点 # 4. 拆分链表 双指针 哈希表：hash(旧节点) = 新节点 删除链表中重复节点 ...
1 概述 1.1 衡量标准 1.2 分类 算法 思想 最好时间复杂度 最坏时间复杂度 时间复杂度 空间复杂度 稳定性 冒泡排序 比较、交换 O(n) O(n^2) O(n^2) O(1) 稳定，值相等不交换 插入排序 比较、移动 O(n) O(n^2) O(n^2) 选择排序 比较、交换 归并排序 快速排序 堆排序 桶排序 计数排序 基数排序 /* 冒泡排序 */ void sort_bubble(int *arr, int arrlen) { int end; int tmp; int i; end = arrlen - 1; for (end = arrlen - 1; end > 1; end--) { for (i = 0; i < end - 1; i++) { if (arr[i] < arr[i + 1]) { tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; } } } }
1 图的介绍 1.1 定义 G = (V, E) 一组节点V 一组边E 节点的度：相邻节点的数量 完备图：所有节点都有n-1个相邻节点，即任意2节点间可达 1.2 分类 根据边分类 无向图 n1 ---- n2 | | | | n3 ---- n4 有向图 --> n2 n1 --> n4 --> n3 带权有向图 3 ---> n2 6 n1 ---> n4 ---> n3 5 图的性质分类 同构图：G和H，通过重新标记G的节点产生H。阶相等，顶点度数相等 异构图 1.3 表示 邻接矩阵 如果节点间ni,nj之间有弧，则[ni, nj] = 1 n1 n2 n3 n4 +------------+ n1 | 0 1 1 0 | n2 | 0 0 0 1 | n3 | 0 0 0 1 | n4 | 0 0 0 0 | +------------+ 无向图的斜下半部分是多余的 ...
今天的每日一题：1202. 从根到叶的二进制数之和。 简单来说，就是给定一颗层序遍历的数组，表示一颗树，例如： 输入：root = [1,0,1,0,1,0,1] 输出：22 解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22 可以表示为： 1 / \ 0 1 / \ / \ 0 1 0 1 思路就是使用dfs来遍历这个树，代码为： /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int dfs(TreeNode *root, int val) { if (root == nullptr) return 0; val = val << 1 | root->val; if (root->left == nullptr && root->right == nullptr) return val; return dfs(root->left, val) + dfs(root->right, val); } int sumRootToLeaf(TreeNode* root) { return dfs(root, 0); } }; 拿到这个题就知道用dfs，但是这个计算的方式确实没想到，二进制移位操作，并且使用局部变量保存临时结果，就不需要复杂的字符串拼接然后转换10进制了，例如上例： ...