华为机考准备，适合新手，大佬请略过~轻喷。
先说下华为实习或秋招的软件机考类型，总共3道题，分值100+200+300，每题按照通过的用例数比例算分累加。可以使用ide，但是不能开其他网页和历史工程代码。考试系统是华为的时习知（类似牛客网acm模式），前期可以用力扣刷题，后期熟悉下牛客网的环境。
华为实习大约在三月底或四月初机考，算法类型约10个左右，一周发两种算法练习。实际上机考题目很简单，第一第二题理论上暴力解法能解决，但是我们多刷点题掌握点技巧会做的更有信心，无论应聘华为实习秋招还是其他公司都是有益的，后面题目都按照力扣来说的https://leetcode-cn.com/problemset/all/
华为机考acm模式，可以去牛客刷：https://www.nowcoder.com/exam/oj/ta?tpId=37
前期可以去力扣分专题刷：
1.真没必要追求题量，理解才是最重要的，举一反三，往往一个系列就都会了
2.很多题都是最优解问题，首先找到约束条件是什么，理解这个条件，到底是让你干什么，有可能看着是让你开飞机，实际上是让你开航母，知道题目真正考什么，再用代码实现，其次找完约束条件就要按这个筛选可行解了，这个是关键，需要练习，贪心呀，动态规划呀，都是在这一步，最后就是在众多可行解里，挑一个让题目的目标函数取最大/最小值，这个就是最优解。
3.把比较热门的题目都刷一遍，因为面试不是竞赛，不会考难题怪题，所以一般都是常见的题。
4.分专题刷一方面容易规划，查缺补漏也方便，另一方面便于掌握某一类题
5.之前看到的一个刷题方法
第一遍，看题目，想解法，如果十几分分想不出来直接看题解，看看别人的解法，最好能够默写出来
第二遍，自己尝试写出
第三遍，隔几天后再次写一下，体会+上自己的优化
第四遍，一周过去后，再来一一遍
第五遍，复习，例如面试前。 (不一定是五遍，而是要做出来自己的体会和思考才是最重要的。) 如果有小手指，帮忙点点。上面的方法是收到，覃超老师的指导的方法。
刻意练习不是简单重复，而是跳出自己的舒适圈，不断扩大自己的舒适圈，同时在练习的过程也是需要不断反馈和改进。
【一、单调栈】739 、503 、901 （有同学想掌握困难模式可以刷力扣 84 、42 、239）】
接雨水和最大矩形面积高频考察题目
知乎帖子，讲的很好：https://zhuanlan.zhihu.com/p/26465701
class Solution {
public:
vector dailyTemperatures(vector& temperatures) {
int n = temperatures.size();
stacksta;
vectorres(n);
for(int i = n-1; i >= 0; i--){
while(!sta.empty() && temperatures[sta.top()] <= temperatures[i]){
sta.pop();
}
res[i] = sta.empty()? 0 : sta.top()-i;
sta.push(i);
}
return res;
}
};
503.下一个更大元素https://leetcode.cn/problems/next-greater-element-ii/
循环数组注意要用取余来实现
class Solution {
public:
vector nextGreaterElements(vector& nums) {
int n = nums.size();
stacksta;
vectorres(n,-1);
for(int i = 2*n-1; i >= 0; i--){
while(!sta.empty() && nums[sta.top()] <= nums[i%n]){
sta.pop();
}
res[i%n] = sta.empty()? -1 : nums[sta.top()];
sta.push(i%n);
}
return res;
}
};
741. 股票价格跨度https://leetcode.cn/problems/online-stock-span/
这里感觉要用两个栈来做，后面发现可以一个栈用pair保存两个值，价钱以及这个价钱跨度多少 其实直接一个键值对就好了，pair非常好用，最近用到好几次
class StockSpanner {
public:
stack>sta;
StockSpanner() {
sta = stack>();
}
int next(int price) {
pairp(price,1);
while(!sta.empty() && price >= sta.top().first){
p.second += sta.top().second;
sta.pop();
}
sta.push(p);
return p.second;
}
};
742. 柱状图中最大的矩形https://leetcode.cn/problems/largest-rectangle-in-histogram/
class Solution {
public:
int largestRectangleArea(vector& heights) {
int n = heights.size();
vectorleft(n,0);
stacksta;
for(int i = 0; i < n; i++){
while(!sta.empty() && heights[sta.top()] >= heights[i]){
sta.pop();
}
if(sta.empty()){
left[i] = -1;
}else{
left[i] = sta.top();
}
sta.push(i);
}
sta = stack();
vectorright(n,0);
for(int i = n-1; i >= 0; i--){
while(!sta.empty() && heights[sta.top()] >= heights[i]){
sta.pop();
}
if(sta.empty()){
right[i] = n;
}else{
right[i] = sta.top();
}
sta.push(i);
}
int res = 0;
for(int i = 0; i < n; i++){
res = max(res,(right[i]-left[i]-1)*heights[i]);
}
return res;
}
};
744. 接雨水https://leetcode.cn/problems/trapping-rain-water/
单调栈解法费劲，不如动态规划清晰。
class Solution {
public:
int trap(vector& height) {
int ans = 0;
stack stk;
int n = height.size();
for (int i = 0; i < n; ++i) {
while (!stk.empty() && height[i] > height[stk.top()]) {
int top = stk.top();
stk.pop();
if (stk.empty()) {
break;
}
int left = stk.top();
int currWidth = i - left - 1;
int currHeight = min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stk.push(i);
}
return ans;
}
};
动态规划比较好理解，逻辑清晰
class Solution {
public:
int trap(vector& height) {
int n = height.size();
vectorleft(n);
for(int i = 0; i < n; i++){
if(i == 0){
left[i] = height[i];
}else{
left[i] = max(left[i-1],height[i]);
}
}
vectorright(n);
for(int i = n-1; i >= 0; i--){
if(i == n-1){
right[i] = height[i];
}else{
right[i] = max(right[i+1],height[i]);
}
}
int res = 0;
for(int i = 0; i < n; i++){
res += min(left[i],right[i])-height[i];
}
return res;
}
};
239 滑动窗口最大值https://leetcode.cn/problems/sliding-window-maximum/
曾经数据结构期末考试的最后一题
优先队列做应该是最佳解法，单调栈有点差强人意
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
priority_queue> q;
for (int i = 0; i < k; ++i) {
q.emplace(nums[i], i);
}
vector ans = {q.top().first};
for (int i = k; i < n; ++i) {
q.emplace(nums[i], i);
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};
单调队列
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
int n = nums.size();
deque q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
};
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
第二周 前缀和和差分
1094、1109、121、122、253
1109 航班预定 https://leetcode.cn/problems/corporate-flight-bookings/我之前刷差分时，刷了两题得出的总结是：差分本质是个数学题，一般读完题会把等差数列公式写出来，例如a[i+1] -a[i] = d[i]
,然后求公差数组d，根据输入数据，注意d的左右边界如何处理，一趟循环下来d就出来了。再然后一趟循环根据d求出原来的数列a[i] =
a[i-1] + d[i] (这个循环可以优化)，注意公差和数列的边界处理。
差分数组可以推出来原数组，差分数组的作用就是一些同增同减的变化差分数组来改动是O1复杂度，原数组可能得On 1109这个题很形象。
差分数组d[i] = num[i]-num[i-1]
差分数组的作用就是忽略中间的变化，同增同减就可以认为没有变化
这道题里原数组是
0 0 0 0
差分数组
0 0 0 0
当对0到2的航班订2个位置
原数组变化是
2 2 2 0
而差分数组只需要变成
2 0 0 -2
差分数组又可以推导出原数组
2 2+0 2+0+0 2+0+0+（-2）
因为差分数组变化简单，所以用差分数组
class Solution {
public:
vector corpFlightBookings(vector>& bookings, int n) {
vector nums(n);
for (auto& booking : bookings) {
nums[booking[0] - 1] += booking[2];
if (booking[1] < n) {
nums[booking[1]] -= booking[2];
}
}
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
};
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/corporate-flight-bookings/solution/hang-ban-yu-ding-tong-ji-by-leetcode-sol-5pv8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1094 拼车 https://leetcode.cn/problems/car-pooling/
会议室改版
class Solution {
public:
bool carPooling(vector>& trips, int capacity) {
vector>car;
int n = trips.size();
for(int i = 0; i < n; i++){
pairp1(trips[i][1],trips[i][0]);
pairp2(trips[i][2],-trips[i][0]);
car.push_back(p1);
car.push_back(p2);
}
sort(car.begin(),car.end());
int maxNumpassengers = 0;
int res = 0;
for(int i = 0; i < 2*n; i++){
maxNumpassengers += car[i].second;
if(maxNumpassengers > capacity){
return false;
}
}
return true;
}
};
253 会议室 https://leetcode.cn/problems/meeting-rooms-ii/
这道题4399笔试考过
公交车上下车思路：
class Solution {
public:
int minMeetingRooms(vector>& intervals) {
vector>res;
int n = intervals.size();
for(int i = 0; i < n; i++){
res.push_back(pair(intervals[i][0],1));
res.push_back(pair(intervals[i][1],-1));
}
sort(res.begin(),res.end());
int ans = 0;
int sum = 0;
for(int i = 0; i < 2* n; i++){
sum += res[i].second;
ans = max(ans,sum);
}
return ans;
}
};
121 122解法很多，显不出差分特性所以只是拿来参考一下
121 买卖股票最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
122 买卖股票最佳时机2 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
我们再学习两个算法，这周先掌握“滑动窗口”，力扣刷题：1208、 209、2、1004 可选会员题：340、1151、159、1100
做完看看官方题解。 核心：嵌套循环，外层遍历内层判断中间处理，一点点的向结尾滑动，注意边界处理。
滑动窗口介绍：https://zhuanlan.zhihu.com/p/61564531
1208 尽可能使字符串相等 https://leetcode.cn/problems/get-equal-substrings-within-budget/这个题就是：
先死命的加，直到加超了
再死命的减
再死命的加
再死命的减
加减之间，滑动窗口移动，就解决问题了
比较困惑的是，这样真能保证不遗漏组合可能性吗
比如 1 1 2 3 2 1 1 1 2 3 4 这个数组，要求和不能大于7求最大连续长度
按上面思路滑动窗口变化过程：
1 maxlen = 1
1 1 maxlen = 2
1 1 2 maxlen = 3
1 1 2 3 maxlen = 4
1 1 2 3 2停下来
按思路是减start
即
1 2 3 2
2 3 2
这样只考虑两种情况
那其他情况有没有被遗漏呢
先看1 1 2 3肯定是满足的，那1 1 2 3内的任意子串也是符合条件的
1 1 2 3 2不符合
1 1 2 3符合
只能去掉第一个看1 2 3 2是否符合
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int n = s.size();
vectordiff(n);
for(int i = 0; i < s.size(); i++){
diff[i] = abs(s[i] - t[i]);
}
int end = 0;
int start = 0;
int maxlen = 0;
int len = 0;
while(end < n){
while(end < n && len <= maxCost){
maxlen = max(maxlen,end-start);
len += diff[end];
end++;
}
while(start < n && len > maxCost){
len -= diff[start];
start++;
}
maxlen = max(maxlen,end-start);
}
return maxlen;
}
};
209. 长度最小的子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/
换个题目就不会了
class Solution {
public:
int minSubArrayLen(int s, vector& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= s) {
ans = min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == INT_MAX ? 0 : ans;
}
};
2 .两数相加 https://leetcode.cn/problems/add-two-numbers/
敏捷开发，先实现最基本的功能
加int sumval = cur1->val + cur2->val+carry;
if(sumval >= 10){
curRes->val = sumval-10;
carry = 1;
}else{
curRes->val = sumval;
carry = 0;
}
原链表需要遍历，返回链表需要新建next
cur1 = cur1->next;
cur2 = cur2->next;
if(cur1 && cur2){
curRes->next = new ListNode(0);
curRes = curRes->next;
}
判断语句是控制循环只发生在对齐的部分
处理没有对齐的部分
curRes->next = cur1? cur1: cur2;
1 2 3 4
1 1 1
会变成
2 3 4 4
1 1 1 1
1 2 3
会变成
2 3 4 1
9
9 9 1 1 1
不处理的话结果是：8 9 1 1 1
没有考虑18的进位
所以要考虑这个
while(curRes->next){
curRes = curRes->next;
int sumval = curRes->val+carry;
if(sumval >= 10){
curRes->val = sumval-10;
carry = 1;
}else{
curRes->val = sumval;
carry = 0;
}
}
还有一个特殊情况
9 9 9
9
不考虑最后进位是
8 0 0
但最后还有进位
所以carry等于1再加个next
if(carry==1){
curRes->next = new ListNode(1);
}
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* cur1 = l1;
ListNode* cur2 = l2;
ListNode* res = new ListNode(0);
ListNode* curRes = res;
int carry = 0;
while(cur1 && cur2){
int sumval = cur1->val + cur2->val+carry;
if(sumval >= 10){
curRes->val = sumval-10;
carry = 1;
}else{
curRes->val = sumval;
carry = 0;
}
cur1 = cur1->next;
cur2 = cur2->next;
if(cur1 && cur2){
curRes->next = new ListNode(0);
curRes = curRes->next;
}
}
curRes->next = cur1? cur1: cur2;
while(curRes->next){
curRes = curRes->next;
int sumval = curRes->val+carry;
if(sumval >= 10){
curRes->val = sumval-10;
carry = 1;
}else{
curRes->val = sumval;
carry = 0;
}
}
if(carry==1){
curRes->next = new ListNode(1);
}
return res;
}
};
1004. 最大连续1的个数 III https://leetcode.cn/problems/max-consecutive-ones-iii/
主要是判断前后，就是差一个坐标就错了，for循环while循环做不到实时更新检查是否满足，所以要么加break，要么就是改变在判断之前，循环体内可以放心变更。
class Solution {
public:
int longestOnes(vector& nums, int k) {
int n = nums.size();
int zeronum = 0;
int onenum = 0;
int end = 0;
int start = 0;
int maxOnenum = 0;
while(end < n){
if(nums[end] == 0){
zeronum++;
}
if(zeronum <= k){
maxOnenum = max(maxOnenum,end -start + 1);
}
while(start < n &&zeronum > k){
if(nums[start] == 0){
zeronum--;
}
start++;
}
maxOnenum = max(maxOnenum,end -start + 1);
end++;
}
return maxOnenum;
}
};
340 至多包含 K 个不同字符的最长子串 https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/
目前用哈希表移除做，时间复杂度较高容易理解
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int n = s.size();
int start = 0;
int end = 0;
unordered_mapmap;
int maxSubstr = 0;
while(end < n){
map[s[end]]++;
if(map.size() <= k){
maxSubstr = max(maxSubstr,end - start + 1);
}
while(map.size() > k){
map[s[start]]--;
if(map[s[start]] == 0)map.erase(s[start]);
start++;
}
maxSubstr = max(maxSubstr,end - start + 1);
end++;
}
return maxSubstr;
}
};
维护哈希表下标做
class Solution {
public:
int diffCharNum(unordered_map& window){ //统计滑动窗口中不同字符的个数
int count = 0;
for(auto win : window){
count += win.second >= 1 ? 1 : 0;
}
return count;
}
int lengthOfLongestSubstringKDistinct(string s, int k) {
int n = s.size(), maxLen = 0;
int left = 0, right = 0;
unordered_map window; //字符及其次数
while(right < n){
window[s[right]]++;
while(diffCharNum(window) > k){
window[s[left]]--;
left++;
}
maxLen = max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
};
1151 最少交换次数来组合所有的 1https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together/
这个做出来还是非常有成就感的
class Solution {
public:
int minSwaps(vector& data) {
int n = data.size();
int onenum = 0;
for(int i = 0; i < n; i++){
if(data[i] == 1){
onenum++;
}
}
int zeronum = 0;//当前字符串0数目
int curonenum = 0;//当前字符串1数目
int begin = 0;
int end = 0;
int minCount = INT_MAX;
while(end < n){
if(data[end] == 1){
curonenum++;
}else{
zeronum++;
}
if(onenum - curonenum == zeronum){
minCount = min(zeronum,minCount);
}
while(onenum - curonenum <= zeronum){
if(data[begin] == 1){
curonenum--;
}else{
zeronum--;
}
begin++;
}
if(onenum - curonenum == zeronum){
minCount = min(zeronum,minCount);
}
end++;
}
return minCount;
}
};
1100 长度为 K 的无重复字符子串 https://leetcode.cn/problems/find-k-length-substrings-with-no-repeated-characters
class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
int n = s.size();
unordered_mapmap;
if(s.size() < k)return 0;
int end = 0;
int begin = 0;
int res = 0;
while(end < n){
map[s[end]]++;
if(end > k-1){
map[s[begin]]--;
if(map[s[begin]] == 0){
map.erase(s[begin]);
}
begin++;
}
res += (map.size() == k);
end++;
}
return res;
}
};
159. 至多包含两个不同字符的最长子串https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/
模板套就完事，这时间复杂度不行呀
class Solution {
public:
int lengthOfLongestSubstringTwoDistinct(string s) {
int n = s.size();
int end = 0;
int begin = 0;
int maxLen = 0;
unordered_mapmap;
while(end < n){
map[s[end]]++;
if(map.size() <= 2){
maxLen = max(maxLen,end-begin+1);
}
while(map.size() > 2){
map[s[begin]]--;
if(map[s[begin]] == 0){
map.erase(s[begin]);
}
begin++;
}
maxLen = max(maxLen,end-begin+1);
end++;
}
return maxLen;
}
};
第四周 前缀和和哈希
560、 523、974 hash接口使用可以看这个博客：blog.csdn.net/a123441/article/details/89045293
560. 和为 K 的子数组 https://leetcode.cn/problems/subarray-sum-equals-k
这里有个概念转换，题目叫我们求连续子数组的和，我们把它转换成求两个连续数组之差，从而用前缀和加哈希来做
mp[0] = 1，0是前缀和为0，1是前缀和为0出现1次，主要是存在
1 1 1 k = 2这样的用例
前缀和数组是1 2 3
2应该是满足题意的，但这里2 - 2 = 0，哈希表里没有，所以我们加一个mp[0] = 1,理解成没有任何数相加，就是0
class Solution {
public:
int subarraySum(vector& nums, int k) {
int n = nums.size();
unordered_mapmp;
int pre = 0;
int sum = 0;
int res = 0;
mp[0] = 1;
for(auto num : nums){
pre += num;
if(mp.count(pre - k)){
res += mp[pre-k];
}
mp[pre]++;
}
return res;
}
};
523. 连续的子数组和https://leetcode.cn/problems/continuous-subarray-sum
这里要注意我们要刻意保留最早出现的那个可行解，因为它是觉得最后是否满足条件的决定因素，只要有一个满足数组长度大于1就可以了，而我们只要减去最早出现的那个如果它大于1，就保证有一个正确答案，可以返回true，如果它都不大于1，那肯定后面的也不行
class Solution {
public:
bool checkSubarraySum(vector& nums, int k) {
int n = nums.size();
unordered_mapmp;
int pre = 0;
mp[0] = -1;
for(int i = 0; i < n; i++){
pre += nums[i];
if(mp.count(pre%k)){
if(i - mp[pre%k] > 1){
return true;
}
}else mp[pre%k] = i;
}
return false;
}
};
974. 和可被 K 整除的子数组https://leetcode.cn/problems/subarray-sums-divisible-by-k
注意这个和之前区别是加入了负数，负数取模不太一样
c++里涉及负数的取模，余数符号与被除数符号保持一致。
class Solution {
public:
int subarraysDivByK(vector& nums, int k) {
int n = nums.size();
unordered_mapmp;
int pre = 0;
int res = 0;
mp[0] = 1;
for(int i = 0; i < n; i++){
pre += nums[i];
int modulus = (pre % k + k) % k;
if(mp.count(modulus)){
res += mp[modulus];
}
mp[modulus]++;
}
return res;
}
};
第五周 字典树 820、1231、648、208
从这周开始难度就开始上升了
再接再厉！！！绝不放弃！！！
贪心算法核心是找到最优选择准则，直接局部最优到全局最优，而动态规划是不一定能找到最优选择标准，得一步一步试
1231 分享巧克力https://leetcode.cn/problems/divide-chocolate 435. 无重叠区间 https://leetcode.cn/problems/non-overlapping-intervals 1247. 交换字符使得字符串相同https://leetcode.cn/problems/minimum-swaps-to-make-strings-equal 621. 任务调度器https://leetcode.cn/problems/task-scheduler 45. 跳跃游戏 IIhttps://leetcode.cn/problems/jump-game-ii 376. 摆动序列https://leetcode.cn/problems/wiggle-subsequence
