力扣｜2023华为秋招冲刺

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;
    }
};

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;
    }
};