文章目录
- 第一关：2023 年 7 月面试题挑战
- 第二关：2023 年 6 月面试题挑战
- 第三关：2023 年 5 月面试题挑战
第一关：2023 年 7 月面试题挑战
class Solution {
public:
void reverseWord(vector<char>& s,int l,int r){
for(int i=l,j=r;i<=j;i++,j--){
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
void reverseWords(vector<char>& s) {
int l = 0;
for(int i=0;i<s.size();i++){
if(s[i]==' ')
reverseWord(s,l,i-1),l=i+1;
}
reverseWord(s,l,s.size()-1);
reverseWord(s,0,s.size()-1);
}
};
第二关：2023 年 6 月面试题挑战
遇到边界或者已经走过的点，修改方向。直至修改方向后依旧存在问题，则跳出循环♻️。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int dirx[] = {0,1,0,-1};
int diry[] = {1,0,-1,0};
int order_dir = 0;
int cols = matrix[0].size();
int rows = matrix.size();
bool used[rows+6][cols+6];
memset(used, 0, sizeof(used));
int curx = 0,cury = 0;
vector<int> ans;
while(!used[curx][cury]){
ans.push_back(matrix[curx][cury]);
used[curx][cury] = 1;
int nx,ny;
nx = curx + dirx[order_dir];
ny = cury + diry[order_dir];
if(nx<0||nx>=rows||ny<0||ny>=cols||used[nx][ny]){
order_dir = (order_dir+1)%4;
nx = curx + dirx[order_dir];
ny = cury + diry[order_dir];
if(nx<0||nx>=rows||ny<0||ny>=cols||used[nx][ny]){
break;}
}
curx = nx;
cury = ny;
}
return ans;
}
};
class Solution {
public:
bool used[30];
int anslen = 0;
int getcnt(){
int res = 0;
for(int i=0;i<=25;i++)
res += used[i];
return res;
}
bool check(string &s)
{
int cnt[26];
memset(cnt,0,sizeof(cnt));
for(int i=0;i<s.length();i++){
cnt[s[i]-'a']++;
if(cnt[s[i]-'a']>=2) return false;
}
return true;
}
void dfs(int pos,vector<string>& arr){
if(pos>=arr.size()){
anslen = max(anslen,getcnt());
return ;
}
if(!check(arr[pos])){
dfs(pos+1,arr);
return ;
}
bool flag = 0;
for(int i=0;i<arr[pos].size();i++)
{
if(used[arr[pos][i]-'a']==1){
flag = 1;
break;
}
}
if(flag){
dfs(pos+1,arr);
return ;
}
for(int i=0;i<arr[pos].size();i++)
used[arr[pos][i]-'a']=1;
dfs(pos+1,arr);
for(int i=0;i<arr[pos].size();i++)
used[arr[pos][i]-'a']=0;
dfs(pos+1,arr);
}
int maxLength(vector<string>& arr) {
dfs(0,arr);
return anslen;
}
};
dp[i][j][k]代表处理到第i个房子，当前第i的房子偷没偷的情况为j，且第一个房子偷没偷的情况为k
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==3) return max(nums[0],max(nums[1],nums[2]));
if(nums.size()==1) return nums[0];
int dp[105][2][2];//dp[i][j][k]代表处理到第i个房子，当前第i的房子偷没偷的情况为j，且第一个房子偷没偷的情况为k
memset(dp,0,sizeof(dp));
dp[0][0][0] = 0;
dp[0][1][1] = nums[0];
dp[1][1][0] = nums[1];
dp[1][0][1] = nums[0];
for(int i=2;i<nums.size()-1;i++)
{
dp[i][0][0] = max(dp[i-1][0][0],dp[i-1][1][0]);
dp[i][0][1] = max(dp[i-1][0][1],dp[i-1][1][1]);
dp[i][1][0] = dp[i-1][0][0]+nums[i];
dp[i][1][1] = dp[i-1][0][1]+nums[i];
}
int tot = nums.size();
return max(max(dp[tot-2][1][0],dp[tot-2][1][1]),max(dp[tot-2][0][1],dp[tot-2][0][0]+nums[tot-1]));
}
};
块内排序，重新组成，再排序。
class Solution {
public:
struct node{
int val,label;
};
static bool cmp(node &a,node &b){
return a.val>b.val;
}
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int numWanted, int useLimit) {
int cur_id = 0;
map<int,int> id;
vector<node> vec[20050],fin;
for(int i=0;i<labels.size();i++){
if(id[labels[i]]==0) id[labels[i]] = ++cur_id;
node tmp;
tmp.val = values[i];
tmp.label = labels[i];
vec[id[labels[i]]].push_back(tmp);
}
node tmp;
for(int i=1;i<=cur_id;i++){
sort(vec[i].begin(),vec[i].end(),cmp);
for(int j=0;j<min(int(vec[i].size()),useLimit);j++)
{
tmp.val = vec[i][j].val;
tmp.label = vec[i][j].label;
fin.push_back(tmp);
}
}
sort(fin.begin(),fin.end(),cmp);
int ans = 0;
int limit = min(numWanted,int(fin.size()));
for(int i=0;i<limit;i++)
ans += fin[i].val;
return ans;
}
};
第三关：2023 年 5 月面试题挑战
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int len1 = 0;
int len2 = 0;
ListNode* tmp1 = l1;
ListNode* tmp2 = l2;
ListNode* pre;
while(tmp1) len1++,tmp1 = tmp1->next;
while(tmp2) len2++,tmp2 = tmp2->next;
if(len2>len1){
tmp1 = l1;
l1 = l2;
l2 = tmp1;
}
tmp1 = l1;
tmp2 = l2;
int add = 0;
while(tmp1){
pre = tmp1;
if(tmp2){
int num = tmp1->val + tmp2->val + add;
tmp1->val = num%10;
add = num/10;
tmp1 = tmp1->next;
tmp2 = tmp2->next;
}else{
int num = tmp1->val + add;
tmp1->val = num%10;
add = num/10;
tmp1 = tmp1->next;
}
}
while(add){
pre->next = new ListNode();
pre->next->val = add%10;
pre->next->next = nullptr;
pre = pre ->next;
add /=10;
}
return l1;
}
};
