码不停题

Array

2D Array

String

Two-Pointer : Reverse the elements in an array

Two pointers : different steps


汇总

题号 解答
[1] 两数之和 1. umap.find(target - nums[i])
2. umap.count(target-nums[i]) 👍
[7] 整数反转 stack, overflow,INT_MAX,INT_MIN
[14] 最长公共前缀 1.sort,比较第一个和最后一个的公共前缀。👍
2.2Darray。纵向遍历。优化版,substr
3. 2Darray。纵向遍历。
[26] 删除排序数组中的重复项 双指针,一个指向老数组,一个指向新数组。如果老数组指针的值不等于新数组指针的值,新数组向前移一格
[27] 移除元素 双指针,一个指向老数组,一个指向新数组。如果老数组指针的值不等于target,新数组向前移一格
[28] 实现strStr() 1. 暴力搜索法。O(m(m-n+1))=O(m*n)
2. kmp
[46] 全排列 1. 递归. 分层布局。1.交换第一个数字。2.第一个数固定。后面的排列。3.交换归位。
2. 递归。回溯。填空格法。访问数组标记。
[47] 全排列ii set。去重。递归。交换。
[51] N皇后 回溯。排序。基于条件对string进行排序。H
[52] N皇后ii 回溯。计数。跟51题一样。
[53] 最大子序和 1. 2*O(n/2)+O(1)=O(n)。分治法。max(divide,merge)。
2. O(n)。Kadane’s algorithm。DP。分为子问题。
3.二周目,dp
4.二周目,分治法
[54] 螺旋矩阵 上右下左四个方向,依次打印。每次打印完一行后更新变量,判断越界。
[59] 螺旋矩阵 II 跟54螺旋矩阵一样,只不过是逆向思维,套路还是上右下左遍历,更新行列号,判断越界break。
[66] 加一 1.迭代O(1)space,O(n)time👍
2. 递归O(n)space,O(n)time
[67] 二进制求和 字符串链接,动态规划,二进制进位
[77] 组合 1. 公式法:C(K,N)=C(K-1,N-1)+C(K,N-1)。
2. 回溯法。递归+循环。M
[80] 删除排序数组中的重复项 II 双指针,一个遍历原来的,一个更新新数组。并且计数,只更新2以内的数字,如果遇到不重复的将计数设为1,否则计数加一。
[94] 二叉树的中序遍历 1. 中序遍历。递归。E
2. 中序遍历。1个栈。M。👍
3. 中序遍历。O1,非递归+不用栈。线索二叉树。H。
[104] 二叉树的最大深度 dfs.递归。E
[105] 从前序与中序遍历序列构造二叉树 递归。二分查找。mid.start.end. pos=distance(.begin,find( , , ))
[111] 二叉树的最小深度 dfs.递归。E
[118] 杨辉三角 1. 初始化外部容器,每行内部容器resize(row+1),头尾(尾是row)是1,中间是上层的和.但是太慢了。
2.动态规划。空容器返空。初始化第0行[1]。从第一行开始到numrows-1行开始,每行构建个子容器:第一个塞1,中间塞和,最后塞1.👍
[119] 杨辉三角 II 1. dp.迭代。清空,塞1,塞中间,塞1,sub=ret
2. 想象成一个栈,从后res[rowIndex]往前迭代,每次更新为前一个数加自身的和。.cpp)
[121] 买卖股票的最佳时机 dp
[122] 买卖股票的最佳时机II dp+greedy
[125] 验证回文串 Two pointers
[136] 只出现一次的数字 1. 位运算O(n)time O(1)space
2. unordered_map O(1)time O(n)space
[138] 复制带随机指针的链表 链表/复制原始(copy,link,next)/复制随机(copy,next)/分离。M
[141] 环形链表 快慢指针。fast&&fast->next一起判空。有环必走不到空,指针相遇就有环。
[142] 环形链表 II 1. 快慢指针,计数
2. 三个指针!环状检测算法!👍
[144] 二叉树的前序遍历 1. 递归
2. 迭代+栈👍
[145] 二叉树的后序遍历 1. 递归
2. 迭代+1个栈👍
3. 迭代+2个栈
[151] 翻转字符串里的单词 👍 1. Two Pointers
2.stringstream+getline👍
3. stringstream+>>👍
[167] 两数之和 II - 输入有序数组 双指针O(n)
[169] 求众数 1. 快排。找中位数。O(nlogn)
2. 不修改数组的方法O(n) 👍
[172] 阶乘后的零 1. 数学。递归。
2. 数学。迭代。
[179] 最大数 字符串排序,sort.lambda.string
[189] 旋转数组 1. Reverse,双指针
2.Reverse,stl
3.STL.push_back.erase.超时
[209] 长度最小的子数组 1. O(n).双指针
2. 分治法
[215] 数组中的第K个最大元素 1. O(nlogn)。快排sort()。reverse()。会修改数组。
2. O(n)。快排in-place partition/one way。会修改数组。
3. O(nlogk)。priorityqueue-default-maxheap。基于堆。所有元素放入pq,弹出k-1次堆顶,返回pq.top()。不需要修改数组,适用于处理海量数据。
4. O(nlogk)。multiset-default-minheap。基于rbt,设置一个大小为k的最小堆。最后弹出*set.begin()。不需要修改数组,适用于处理海量数据。.cpp)
[217] 存在重复元素 1. sort
2. unordered_map
[219] 存在重复元素II unordered_map
[233] 数字1的个数 数学。T:O(logn),S:O(1)
1. 公式法:n/(10d)d + min(d,max(0,n\%(10d)-d+1))
2.划分法。满二进一位(满载),如果量级的最后一位是1,要加上余数+1
[263] 丑数 数学。迭代。
[264] 丑数ii 动态规划.3个指针
[283] 移动零 Two Pointers
[295] 数据流的中位数 1. 增删O(logn),查O(1).maxheap,两个stl::pq,一个放前一半大的数,一个放后一半大的负数。
2. AVL。maxheap和minheap。优先队列。
[297] 二叉树的序列化与反序列化 1. bfs/queue/stringstream
2. dfs递归/stringstream in(str)/obj.str()返回值
[344] 反转字符串 双指针 O(1) space
[387] 字符串中的第一个唯一字符 无序关联式容器,哈希表,计数。unordered_map>
[400] 第N个数字 迭代。数学。tostring(int)。(string)char。stoi(const string&)
[426] 把二叉搜索树转化为有序双向链表 分治法。递归。指针引用。中序遍历。M
[463] 岛屿的周长 1. 岛屿边界处:在数组最左边,或者左边格子没有岛屿
2. 先假设算4个边,判断左边和上边是否有岛屿 👍
[485] 最大连续1的个数 1. two pointers
2. count
3. sum
[498] 对角线遍历 iteration:对角线索引 = 对角线坐标和;根据对角线index奇偶i,swap坐标;越界跳出
[541] 反转字符串 II 1. 双指针
2.stl:reverse(begin(),end())
[557] 反转字符串中的单词 III 1. two pointers
2.stringstream
[561] 数组拆分 I 贪心。排序
[680] 验证回文字符串 Ⅱ two pointers
[700] 二叉搜索树的查找 1. 递归。BST。E
2. 迭代。BST。E。
[701] 二叉搜索树的插入 1. 递归。BST。
2. 迭代。BST。break。
[705] 设计哈希集合 hashset。二维数组。value=0或者1.代表集合中是否存在。E。
[706] 设计哈希映射 hashmap。key-value。映射。初值为-1。E。
[724] 寻找数组的中心索引 1. 计算不含nums[i]的leftsum,如果leftsum== total - leftsum -nums[i],返回i
2. left=0,right=total;right-sum[i],if(==),return i;left+nums[i];return -1
[747] 至少是其他数字两倍的最大数 第一遍找到最大并记录索引。第二遍如果又发现不符合条件的返-1。否则返index
[804] 国际摩尔斯密码 unordered_set。hash。E。
[876] 链表的中间结点 快慢指针。链表。
Thanks for Support.