我家自动化

这个屌丝很懒，什么也没留下！

热门标签

程序员面试金典-刷题笔记_程序员刷面试题

作者：我家自动化 | 2024-05-07 12:16:23

踩

程序员刷面试题

面试题 01.01. 判定字符是否唯一
方法一：哈希表
比较原数组和哈希表的长度，如果相等，说明没有重复元素；

class Solution {
public:
    bool isUnique(string astr) {
        int n=astr.size();
        unordered_set<char> ret;
        for(auto c:astr){
            ret.insert(c);
        }
        return ret.size()==n;
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度O(N)
空间复杂度O(N)

方法二：位运算可以利用一个int类型的变量(mask)

class Solution {
public:
    bool isUnique(string astr) {
        int mask = 0;
        for (char& i : astr) {
            if (mask & (1 << (i - 'a'))) return false;
            mask |= (1 << (i - 'a'));
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度O(N) 空间复杂度O(1)

面试题 01.02. 判定是否互为字符重排

方法一：先排序再判断是否相等

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        sort(s1.begin(),s1.end());
        sort(s2.begin(),s2.end());
        return s1==s2;
    }
};
1
2
3
4
5
6
7
8

面试题 01.03. URL化

方法一：在原数组上修改先遍历数组计算非空格字符的数量num ，然后计算空格数length-num，然后扩充数组的长度，最后利用双指针遍历遇到空格就插入“%20”；

class Solution {
public:
    string replaceSpaces(string S, int length) {
        int num=0;
        for(int i=0;i<length;i++){
            if(S[i]!=' ') num++;
        }
        int kong=length-num;
        S.resize(num+kong*3);
        int j=S.size()-1;
        for(int i=length-1;i>=0;i--){
            if(S[i]!=' ')S[j--]=S[i];
            else{
                S[j--]='0';
                S[j--]='2';
                S[j--]='%';
            }  
        }
       return S;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度O(N) 空间复杂度O(1)

面试题 01.04. 回文排列

方法一：哈希表

class Solution {
public:
    bool canPermutePalindrome(string s) {
        unordered_set<char> st;
        for(auto c: s){
            if(st.count(c)) st.erase(c);
            else st.insert(c);
        }
    return st.size()<=1;
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度O(N) 空间复杂度O(N)

面试题 01.05. 一次编辑

方法一：一次遍历

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int n1=first.size();
        int n2=second.size();
        if(abs(n1-n2)>1) return false;
        if(first==second) return true;
        int count=0;
        int i=0,j=0;
        while(i <n1 && j <n2){
            if(first[i++] == second[j++]){
                continue;
            }
            count++;
            if(count > 1) return false;
            if( n1> n2){
                j--;
            }else if(n1<n2){
                i--;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度O(N) 空间复杂度O(1)

面试题 01.06. 字符串压缩

方法一：一次遍历

class Solution {
public:
    string compressString(string S) {
      if(S.size()==0) return S;
      string ans="";
      int cnt=1;
      char ch=S[0];
      for(int i=1; i < S.size();i++){
          if(ch ==S[i]) cnt++;
          else {
              ans+=ch+to_string(cnt);
              ch=S[i];
              cnt=1;
          }
      }
    ans+=ch+to_string(cnt);
    return ans.size()>=S.size() ? S:ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度O(N) 空间复杂度O(1)

面试题 01.07. 旋转矩阵

方法一：翻转代替旋转首先进行对角线翻转然后进行竖轴翻转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n/2;j++)
            swap(matrix[i][j],matrix[i][n-1-j]);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度O(N^2) 空间复杂度O(1)

方法二：原地旋转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n/2;i++){
            for(int j=0;j<(n+1)/2;j++){
                int temp = matrix[i][j];
                matrix[i][j]=matrix[n-j-1][i];
                matrix[n-j-1][i]=matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                matrix[j][n-i-1]=temp;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度O(N^2) 空间复杂度O(1)

面试题 01.08. 零矩阵

方法一：先用数组将零元素的坐标存下来然后修改为0；

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.size() ==0 || matrix[0].size()==0) return ;
        vector<pair<int,int>> ret;
        for(int i=0;i<matrix.size();i++){
        for(int j=0;j<matrix[0].size();j++){
            if(matrix[i][j]==0) ret.push_back({i,j});
        }
        }
        for(int i=0;i<ret.size();i++){
            int n1=ret[i].first;
            int n2=ret[i].second;
            for(int j=0;j<matrix[0].size();j++){
                matrix[n1][j]=0;
            }
            for(int k=0;k<matrix.size();k++){
                matrix[k][n2]=0;
            }

        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度O(NM)

面试题 01.09. 字符串轮转

方法一：将s1和s1拼接然后在拼接后的s1中找s2

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if(s1.size() != s2.size()) return false;
        s1+=s1;
        int n1=0,n2=0;
        while( n1 < s1.size() && n2 < s2.size()){
            if(s1[n1]==s2[n2]){
                n1++;
                n2++;
            }
            else {
                n2=0;
                n1=n1-n2+1;
            }
        }
    return n2==s2.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度O(N) 空间复杂度O(1)

方法二：使用标记数组

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size();
        int n=matrix[0].size();
        vector<int> row(m),col(n);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]==0)
                row[i]=col[j]=true;
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(row[i] || col[j])
                matrix[i][j]=0;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度O(MN) 空间复杂度O（M+N）

面试题 02.01. 移除重复节点

方法一：哈希表

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if(!head) return nullptr;
        unordered_set<int> st;
        ListNode* curr=head;
        st.insert(curr->val);
        while(curr->next){
            if(st.count(curr->next->val)){
                curr->next=curr->next->next;
            }else{
                st.insert(curr->next->val);
                curr=curr->next;
            }
        }
    return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度O(N) 空间复杂度O(N)

方法二：双循环

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if(!head) return nullptr;
        ListNode* curr=head;
        while(curr){
            ListNode* pre=curr;
            while(pre->next){
                if(pre->next->val==curr->val){
                    pre->next=pre->next->next;
                }else{
                    pre=pre->next;
                }
            }
            curr=curr->next;
        }
    return head;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度O(N^2) 空间复杂度O(1)

面试题 02.02. 返回倒数第 k 个节点

方法一：双指针前指针先走k步，后指针开始走；当前指针走到末尾，则后指针就是倒数第k个指针

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        if(!head) return -1;
        ListNode* pre=head,*curr=head;
        while(k--){
            pre=pre->next;
        }
        while(pre){
            pre=pre->next;
            curr=curr->next;
        }
      return curr->val;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度O(N) 空间复杂度O(1)

面试题 02.03. 删除中间节点

方法一：将下一个节点赋值给当前节点然后删除下一个节点

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
    }
};
1
2
3
4
5
6
7

面试题 02.04. 分割链表

方法一：分割链表

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* smallhead=new ListNode(0);
        ListNode* small=smallhead;
        ListNode* largehead=new ListNode(0);
        ListNode* large=largehead;
        while(head){
            if(head->val<x){
                small->next=head;
                small=small->next;
            }else{
                large->next=head;
                large=large->next;
            }
            head=head->next;
        }
        large->next=nullptr;
        small->next=largehead->next;
        return smallhead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度O(N) 空间复杂度O(1)

面试题 02.05. 链表求和

方法一：递归

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return addcore(l1,l2,0);
    }
    ListNode* addcore(ListNode* l1,ListNode* l2,int carry){
        if(!l1 && !l2 && carry==0) return nullptr;
        int val = carry + (l1? l1->val : 0) + (l2? l2->val : 0);
        carry = val / 10;
        ListNode* res = new ListNode (val%10);
        res -> next=addcore(l1 ? l1->next: nullptr,l2? l2->next:nullptr,carry);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：迭代先对应节点求和再加上进位

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    if(!l1 && !l2) return nullptr;
    ListNode* head=new ListNode(-1),*p=head;
    int carry=0;
    while(l1 || l2 || carry){
        int sum=0;
        if(l1){
            sum+=l1->val;
            l1=l1->next;
        }
        if(l2){
            sum+=l2->val;
            l2=l2->next;
        }
        sum+=carry;
        ListNode* node=new ListNode(sum%10);
        carry=sum/10;
        p->next=node;
        p=p->next;
    }
    return head->next;
   }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度O(N)

面试题 02.06. 回文链表

方法一：先将值复制到数组中后用双指针法

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vals;
        while (head != nullptr) {
            vals.emplace_back(head->val);
            head = head->next;
        }
        for (int i = 0, j = (int)vals.size() - 1; i < j; ++i, --j) {
            if (vals[i] != vals[j]) {
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度O(N) 空间复杂度O(N)

方法二：快慢指针用快慢指针找到中点然后将后半段反转

面试题 02.08. 环路检测

方法一：哈希表

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> visited;
        while (head != nullptr) {
            if (visited.count(head)) {
                return head;
            }
            visited.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度O(N) 空间复杂度O(N)

方法二：快慢指针

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head) return nullptr;
        ListNode *fast=head,*slow=head;
        while(fast){
          slow=slow->next;
          if(fast->next==nullptr){
              return nullptr;
          }
          fast=fast->next->next;
          if(slow==fast){
              ListNode* node=head;
              while(node!=slow){
                  node=node->next;
                  slow=slow->next;
              }
              return node;
          }
        } 
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度O(N) 空间复杂度O(1)

面试题 04.01. 节点间通路

方法一：深度优先遍历 利用一个visited的数组来记录是否遍历了边每次遍历：1.看是否能直接转到 2.如果不到就考虑这一条是target的情况，然后更新新的target 3然后回溯

class Solution {
public:
    bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) {
        int k=graph.size();
        vector<bool> visite(k,false);
        for(int i=0;i<k;i++){
            if(graph[i][0]==start && graph[i][1]==target){
                return true;
            }
        }
        return dfs(visite,graph,start,target);
    }
    bool dfs(vector<bool>& visite,vector<vector<int>>& graph,int start,int target){
        for(int i=0;i<graph.size();i++){
            if(!visite[i]){
                if(graph[i][0]==start && graph[i][1]==target) return true;
                visite[i]=true;
                if(graph[i][1]==target && dfs(visite,graph,start,graph[i][0])) return true;
                visite[i]=false;
            }
        }
    return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

面试题 04.02. 最小高度树

方法一：迭代算法先序遍历

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0) return nullptr;
        return sortA(nums,0,nums.size()-1);
    }
    TreeNode* sortA(vector<int>& nums,int low,int high){
        if(low>high) return nullptr;
        int mid=(low+high)>>1;
        TreeNode* tmp=new TreeNode(nums[mid]);
        tmp->left=sortA(nums,low,mid-1);
        tmp->right=sortA(nums,mid+1,high);
        return tmp; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度O(N) 空间复杂度O(logN)

面试题 04.03. 特定深度节点链表

方法：广度优先搜索

class Solution {
public:
    vector<ListNode*> listOfDepth(TreeNode* tree) {
        vector<ListNode*> res;
        if(!tree) return {};
        queue<TreeNode*> q;
        q.push(tree);
        while(!q.empty()){
            int n=q.size();
            ListNode* tmp=new ListNode(0);
            ListNode* ret=tmp;
            for(int i=0;i<n;i++){
                TreeNode* node=q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
                ListNode* temp=new ListNode(node->val);
                ret->next=temp;
                ret=ret->next;        
            }
            res.push_back(tmp->next);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度O(N) 空间复杂度O(N)

面试题 04.05. 合法二叉搜索树

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        return dechose(root,LONG_MIN,LONG_MAX);
    }
    bool dechose(TreeNode* node,long long low,long long high){
        if(!node) return true;
        if(node->val <=low || node->val >=high){
            return false;
        }
        return dechose(node->left,low,node->val) && dechose(node->right,node->val,high);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度O(N) 空间复杂度O(N)

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        if(!root) return true;
        long long inorder=LONG_MIN;

        while(!st.empty() || root!=nullptr){
            while(root != nullptr){
                st.push(root);
                root=root->left;
            }
            root=st.top();
            st.pop();
            if(root->val <=inorder) return false;
            inorder=root->val;
            root=root->right;
        }
       return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度O(N) 空间复杂度O(N)

面试题 04.06. 后继者

思路：迭代法

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == nullptr || p == nullptr)
            return nullptr;
        if (p->val >= root->val)
            return inorderSuccessor(root->right, p);
        else {
            TreeNode* left = inorderSuccessor(root->left, p);
            return left ? left : root;
        }        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度O(N) 空间复杂度O(1)

思路：首先查找root->val

class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if(!root) return nullptr;
        TreeNode* pre=nullptr;
        while(root->val !=p->val){
            if(root->val <p->val)
              root=root->right;
            else {
                pre=root;
                root=root->left;
            }
        }

        if(root->right ==nullptr) return pre;
        else{
            root=root->right;
            while(root->left != nullptr){
                root=root->left;
            }
        return root;
        }      
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度O(N)

面试题 04.08. 首个共同祖先

思路：如果root为空，或rootp或rootq，返回root；分别将root->left、root->right作为根节点、调用自身，得到返回值left、right；若left为空，若right不为空，返回root，否则返回left；否则返回right。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr || root==p || root==q) return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left != nullptr){
            return right ? root : left;
        }
        else return right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度O(N) 空间复杂度O(N)

思路：存储父节点

面试题 04.10. 检查子树

思路：迭代算法

class Solution {
public:
    bool checkSubTree(TreeNode* t1, TreeNode* t2) {
        if(t1==nullptr || t2==nullptr) return false;
        return recure(t1,t2) || checkSubTree(t1->left,t2) || checkSubTree(t1->right,t2);
    }

    bool recure(TreeNode* A ,TreeNode* B){
        if(B==nullptr) return true;
        if(A==nullptr || A->val!=B->val) return false;
        return recure(A->left,B->left) && recure(A->right,B->right); 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度O(MN) 空间复杂度O(M)

面试题 04.12. 求和路径

class Solution {
    private: 
    int Depth(TreeNode* root){
        if(!root) return 0;
        return max(Depth(root->left),Depth(root->right))+1;
    }

public:
    int ret=0;
    int pathSum(TreeNode* root, int sum) {
        if(root==nullptr) return ret;
        int depth = Depth(root);
        int path[depth];
        memset(path,0,sizeof(int)*depth);
        dfs(root,sum,path,0);
        return ret;
    }

 void dfs(TreeNode* curr,int sum,int* path,int level){
     if(curr == nullptr) return;
     path[level] = curr->val;
     int currSum=0;
     for(int i=level;i>=0;i--){
         currSum +=path[i];
         if(currSum == sum) ++ret;
     }
        dfs(curr->left, sum, path, level+1);
        dfs(curr->right, sum, path, level+1);
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

面试题 08.01. 三步问题

思路：动态规划

class Solution {
public:
    int waysToStep(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        int  ret=0,first=1,second=2,third=4;

        for(int i=3;i<n;i++){
            ret=((first+second)%1000000007+third)%1000000007;
            first=second;
            second=third;
            third=ret;
        }
    return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

面试题 08.02. 迷路的机器人

面试题 08.03. 魔术索引

普通遍历

class Solution {
public:
    int findMagicIndex(vector<int>& nums) {

        for(int i=0;i<nums.size();i++){
            if(nums[i]==i) return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10

时间复杂度O（N）空间复杂度O（1）

思路：二分法

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/549166