48. 旋转图像
给定一个 _n_ × _n_ 的二维矩阵 `matrix` 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 **[原地](https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95)** 旋转图像，这意味着你需要直接修改输入的二维矩阵。**请不要** 使用另一个矩阵来旋转图像。
- 找到每个点旋转后位置的规律
581. 最短无序连续子数组
给你一个整数数组 `nums` ，你需要找出一个 **连续子数组** ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 **最短** 子数组，并输出它的长度。
- 总结:从左往右，找到比左边最大值还小的最右下标，从右往左，找到比右边最小值还大的最左下标
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
int maxn = INT_MIN, right = -1;
int minn = INT_MAX, left = -1;
for (int i = 0; i < n; i++) {
if (maxn > nums[i]) {
right = i;
} else {
maxn = nums[i];
}
if (minn < nums[n - i - 1]) {
left = n - i - 1;
} else {
minn = nums[n - i - 1];
}
}
return right == -1 ? 0 : right - left + 1;
}
};
41. 缺失的第一个正数
给你一个未排序的整数数组 `nums` ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 `O(n)` 并且只使用常数级别额外空间的解决方案。
- 这题目的巧妙之处就在于可以修改原来的数组,使得这个数字是多少就直接放到对应的位置就可以了(当然这部分需要循环放置)
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
swap(nums[nums[i] - 1], nums[i]);
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
};
米哈游笔试二题
两个字符串,只能向第一个字符串按顺序插入或者删除m,h,y三个字符,一定是按顺序且插满或者删满三个对应字符,是否最后可以变为第二个字符串
- 两个字符串删除所有mhy之后是否相等就是结果
- 删除mhy的方法是使用双栈(先m栈,到h栈)
142. 环形链表 II
给定一个链表的头节点 `head` ，返回链表开始入环的第一个节点。 _如果链表无环，则返回 `null`。_
如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（**索引从 0 开始**）。如果 `pos` 是 `-1`，则在该链表中没有环。**注意：`pos` 不作为参数进行传递**，仅仅是为了标识链表的实际情况。
**不允许修改** 链表。
- 数学问题,龟兔赛跑,快慢指针,指针相遇的位置就是结果的位置
2982. 找出出现至少三次的最长特殊子字符串 II
给你一个仅由小写英文字母组成的字符串 `s` 。
如果一个字符串仅由单一字符组成，那么它被称为 **特殊** 字符串。例如，字符串 `"abc"` 不是特殊字符串，而字符串 `"ddd"`、`"zz"` 和 `"f"` 是特殊字符串。
返回在 `s` 中出现 **至少三次** 的 **最长特殊子字符串** 的长度，如果不存在出现至少三次的特殊子字符串，则返回 `-1` 。
**子字符串** 是字符串中的一个连续 **非空** 字符序列。
- 隐藏的有点深的差分数组,涉及到数组范围批量更改的都直接上差分数组
for (int i = 0; i < s.size(); i++) {
if (i!=0) {
if (s[i]==s[i-1]) {
arr[i]=arr[i-1]+1;
}else {
arr[i]=1;
}
}else {
arr[i]=1;
}
words[s[i]-'a'][1]++;
words[s[i]-'a'][arr[i]+1]--;
}
int result=-1;
for (auto& word : words) {
int now=0;
for (int i = 1; i < word.size(); i++) {
now+=word[i];
if (now>=3) {
result=max(i,result);
}
}
}
995. K 连续位的最小翻转次数
给定一个二进制数组 `nums` 和一个整数 `k` 。
**k位翻转** 就是从 `nums` 中选择一个长度为 `k` 的 **子数组** ，同时把子数组中的每一个 `0` 都改成 `1` ，把子数组中的每一个 `1` 都改成 `0` 。
返回数组中不存在 `0` 所需的最小 **k位翻转** 次数。如果不可能，则返回 `-1` 。
**子数组** 是数组的 **连续** 部分
- 这题是差分数组,不是很好想,实际上就是走到一个0就翻转,然后到最后康康还有没有剩下的,翻转用的是差分数组
class Solution {
public:
int minKBitFlips(vector<int>& nums, int k) {
vector<int> arr(nums.size()+1,0);
int now=0,result=0;
for (int i = 0; i< nums.size(); i++) {
now+=arr[i];
if (i+k>nums.size()) {
if ((nums[i]==0&&now%2==0)||(nums[i]==1&&now%2==1)) {
return -1;
}
continue;
}
if ((nums[i]==0&&now%2==0)||(nums[i]==1&&now%2==1)) {
result++;
now+=1;
arr[i+k]-=1;
}
}
return result;
}
};
质数欧拉筛
- 一种快速找质数的方法,核心方法是使用枚举,将所有质数的倍数都标记为合数,剩下的就是质数
vector<int> arr(right+1,1);
arr[1]=0;
for (long long i = 2; i < right+1; i++) {
if (arr[i]) {
for (long long j = i*i; j < right+1; j+=i) {
arr[j]=0;
}
}
}
牛顿迭代法
- 设函数f(x)在x0处可导，且f(x)在x0处的一阶导数f′(x0)存在，且f′(x0)≠0，则称x0是方程f(x)=0的一个牛顿迭代点，记作x0∈R，且称函数f(x)在x0处的切线方程为
f(x)=f(x0)+f′(x0)(x−x0)
- 若x1是方程f(x)=0的一个牛顿迭代点，且x1满足
x1=x0−f(x0)f′(x0),则称x1 是方程f(x)=0的一个牛顿迭代点，记作x1∈R，且称函数f(x)在x1 处的切线方程为f(x)=f(x1)+f′(x1)(x−x1) - 方程为
xn+1=xn−f(xn)f′(xn) - 底层是通过切线和x交点越来越接近零点的原理
位运算
136. 只出现一次的数字
给你一个 **非空** 整数数组 `nums` ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
- 通过两个相同的数字异或为0,0和任何数字异或原来数字不变
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto e: nums) ret ^= e;
return ret;
}
};
面试
一共N个数,求最大的n个数
- 将N个数分割分布在每台机器上,使用堆的实现,求出每部分最大的最大n个数字,在进行整合得到最大的n个数
大规模数据去重问题
- 大部分是直接通过bitmap标识,每个数据占据一个bit,通过01判断是否存在
分布式大量数据下载处理
- 使用mapreduce,参考分布式架构 > MapReduce
赛马问题
25匹马，5条赛道，不计时，问至少要赛多少场才能保证找出前三？
- 7次确实是一定可行的，就25匹马5个一组，比5次，淘汰掉10匹，然后这5次的冠军比一次，获得第4第5的两组全部淘汰（淘汰6匹），第3的组里淘汰2匹，第2的组淘汰1匹，第1的那个确定是所有马里最快的。这样总共已经淘汰了10+6+2+1=19匹，还有1匹确定最快，还剩下5匹比一次就够了。