考研算法题

反转链表
题目链接

方法一:
双指针:在遍历链表同时修个节点next的指向。
时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(1)}

typedef sturct ListNode{
    int data;
    struct ListNode *next;
}ListNode;

ListNode* reverseList(ListNode* head) {
        struct ListNode *pre = NULL, *cur = head, *t;
        while(cur){
            t = cur -> next;    //暂存后继节点
            cur -> next = pre;  //修改引用指针
            pre = cur;  //暂存当前节点
            cur = t;    //访问下一节点
        }
        return pre;
    }

方法二:
递归:
当越过表尾节点的时候终止递归,回溯时修改各节点next指向

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

 ListNode* reverseList(ListNode* head) {
        return dfs(head, NULL);
    }

 ListNode* dfs(ListNode *cur, ListNode *pre){
        if(cur == NULL) return pre; //递归终止条件
        ListNode* t = dfs(cur -> next, cur);    //递归后继节点
        cur -> next = pre;  //修改节点指向
        return t;   //返回反转链表头节点
    }

删除链表倒数的第n个节点
题目链接

方法:
双指针,假设有当前有m个元素,要删除倒数第n个,也就是正数第m-n+1个,也就是指针要在m-n上,所以我们将一个指针先移动n步,之后一个指针移动的次数就是m-n,遍历一遍即可找到位置。

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(1)}

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p = head, *q = head;
        while(p != NULL){
            if(n < 0)   q = q -> next;
            n --;
            p = p -> next;
        }
        if(n == 0)  return head -> next;
        q -> next = q -> next -> next;
        return head;
    }

删除有序数组中的重复项

题目链接

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(1)}

方法:双指针遍历一遍即可。

int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0)    return 0;
        int len = 1;
        int l = 0, r = 1;
        while(r < nums.size()){
            while(nums[l] != nums[r] && r < nums.size()){
                nums[++ l] = nums[r];
                r ++;
                len ++;
                if(r == nums.size())    break;
            }
            r ++;
        }
        return len;
    }

验证是否是一颗有效的二叉搜索树

题目链接

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

递归时更新每个区间端点值,
当在节点的左子树时,更新上界
挡在节点的右子树时,更新下界

bool isValidBST(TreeNode* root) {
        return dfs(root, LONG_MIN, LONG_MAX);
    }

    bool dfs(TreeNode* root, long mi, long mx){
        if(root == NULL)    return true;
        if(root->val <= mi || root->val >= mx)    return false;
        return dfs(root -> left, mi, root->val) && dfs(root -> right, root->val, mx);
    }

在排序数组中查找元素的第一个和最后一个位置

题目链接

二分搜索模板题目,不解释,太简单了。

时间复杂度\mathcal{O(logn)}
空间复杂度\mathcal{O(1)}

vector<int> searchRange(vector<int>& nums, int target) {
     vector<int> ans;
     int n = nums.size();
     if(n == 0){
         ans.push_back(-1);
         ans.push_back(-1);
         return ans;
     }
     int l = 0, r = n - 1;
     while(l < r){
         int mid = (l + r) >> 1;
         if(nums[mid] >= target)    r = mid;
         else   l = mid + 1;
     }
     if(nums[r] != target){
         ans.push_back(-1);
         ans.push_back(-1);
         return ans;
     }
     else{
         ans.push_back(r);
         l = 0, r = n - 1;
         while(l < r){
             int mid = (l + r + 1) >> 1;
             if(nums[mid] <= target)    l = mid;
             else   r = mid - 1;
         }
         ans.push_back(l);
         return ans;
     }
    }

判断是否是高度平衡的二叉树

简单题,不解释。

题目链接

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

 int dfs(TreeNode *root){
        if(root == NULL)    return 0;
        int left = dfs(root -> left);
        int right = dfs(root -> right);
        if(left != -1 && right != -1 && abs(left - right) < 2){
            return left > right ? left + 1 : right + 1;
        }
        else{
            return -1;
        }
    }

    bool isBalanced(TreeNode* root) {
        int ans = dfs(root);
        return ans == -1 ? false : true;
    }

判断两棵树是否相同

题目链接

简单题,不解释。

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

 bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL)  return true;
        else if(p == NULL || q == NULL) return false;
        else if(p -> val != q -> val)  return false;
        else{
            return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right);
        }
    }

二叉树第k层节点个数

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode;

int Get_K_Level_Number(BTNode *root, int k){
  if(root == NULL || k == 0)  return 0;
  if(k == 1)  return 1;
  return Get_K_Level_Number(root -> lchild, k + 1) + Get_K_Level_Number(root -> rchild, k + 1);
}

给定一棵二叉树和其中的一个节点,找出中序遍历序列的下一个节点?树中的节点除了有两个分别指向左、右子节点的指针,还有一个指向父节点的指针。

根据中序遍历的性质:
如果给定的节点有右子树,该节点的下一个节点就是右子树的最左子节点。
如果给定的节点没有右子树,那么根据指向父节点的指针往上回溯,直到找到有个节点(包括该给定节点)是它的父节点的左子节点,它的父节点就是给定节点的下一个节点。

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

typedef struct TreeNode{
  int data;
  struct TreeNode *lchild;
  struct TreeNode *rchild;
  struct TreeNode *parent;
}TreeNode;


TreeNode* GetNext(TreeNode* node){
  if(node == NULL){
    return NULL;
  }
  //如果当前节点有右子树,找右子树的最左节点
  TreeNode* Pnext = NULL:
  if(node -> rchild != NULL){
    Pnext = node -> rchild;
    while(Pnext -> lchild != NULL){
      Pnext = Pnext -> lchild;
    }
    return Pnext;
  }

  //没有右子树,往上找某结点A,A是其父节点B的左节点,父节点B则是下一个节点
  else{
    TreeNode Prenode = node -> parent;
    while(Prenode != NULL && node == Prenode -> rchild){
      node = Prenode;
      Prenode = node -> parent;
    }
    return Prenode;
  }
}

二叉树的最小深度

题目链接

简单题。

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

int minDepth(TreeNode* root) {
        if(root == NULL)    return 0;
        if(root -> left == NULL && root -> right == NULL)   return 1;
        int mi = INT_MAX;
        if(root -> left != NULL)    mi = min(mi, minDepth(root -> left));
        if(root -> right != NULL)   mi = min(mi, minDepth(root -> right));
        return mi + 1;
    }

二叉搜索树的第k大节点

题目链接

树中第k大节点可以 转换成求 中序遍历倒序的第k大节点

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

    int res;
    int kthLargest(TreeNode* root, int k) {
        dfs(root, k);
        return res;
    }
    void dfs(TreeNode* root, int &k){
        if(root == NULL)    return;
        dfs(root -> right, k);
        k --;
        if(k == 0){
            res = root -> val;
            return;
        }
        dfs(root -> left, k);
    }

递归实现合并两个升序链表

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(n)}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL || l2 == NULL)    return l1 ? l1 : l2;
        if(l1 -> val < l2 -> val){
            l1 -> next = mergeTwoLists(l1 -> next, l2);
            return l1;
        }
        else{
            l2 -> next = mergeTwoLists(l1, l2 -> next);
            return l2;
        }
    }

图的深度优先遍历判断邻接表存储的有向图中是否存在vi-vj的路径

时间复杂度\mathcal{O(n+e)}
空间复杂度\mathcal{O(n)}

typedef struct ArcNode{
  int adjex;
  struct ArcNode *next;
}ArcNode;

typdef struct VNode{
  int data;
  ArcNode *firstarc;
}VNode;

typedef struct AGraph{
  VNode VList[maxn];
  int n;
  int e;
}AGraph;

int flag = 0;
int vis[maxn];

void dfs(AGraph G, int i, int j, int vis[]){
  ArcNode *p;
  vis[i] = 1;
  if(i == j){
    found = 1;
    return ;
  }
  else{
    p = G.VList[i].firstarc;
    whlie(flag == 0 && p != NULL){
      if(vis[p -> adjex] == 0){
        dfs(G, p -> adjex, j, vis);
      }
      p = p -> next;
    }
  }
}

int FindPath(AGraph G, int i, int j){
  for(int i = 0; i < G.n; i ++){
    vis[i] = 0;
  }
  if(i == j)  return 0;
  dfs(G, i, j, vis);
  return flag;
}

DFS判断有向图是否存在环

时间复杂度\mathcal{O(n+e)}
空间复杂度\mathcal{O(n)}

const int maxn = 1000;

typedef struct ArcNode{
  int adjex;
  struct ArcNode *next;
}ArcNode;

typdef struct VNode{
  int data;
  ArcNode *firstarc;
}VNode;

typedef struct AGraph{
  VNode VList[maxn];
  int n;
  int e;
}AGraph;

int flag = 0;
int vis[maxn];

void dfs(AGraph G, int i){
  ArcNode *p;
  vis[i] = 1;//1 表示正在访问
  p = G.VList[i].firstarc;
  while(p != NULL){
    if(vis[p -> adjex] == 0){
      dfs(G, p -> adjex);//如果该节点未访问 继续访问其邻接节点
    }
    else if(vis[p -> adjex] == 1){//访问到标记节点,说明有环
      flag = 1;
    }
    p = p -> next;
  }
  vis[i] = 3;//3 表示该点访问结束
}

bool Has_Circle(AGraph G){
  for(int i = 0; i < G.n; i ++){
    vis[i] = 0;
  }
  for(int i = 0; i < G.n; i ++){
    if(vis[i] == 0){
      dfs(G, i);
    }
  }
  return flag ? true : false;
}

爬楼梯,一共n个台阶,一次可以爬1或2个台阶,一共有多少种爬法

题目链接

简单题

时间复杂度\mathcal{O(n)}
空间复杂度\mathcal{O(1)}

int climbStairs(int n) {
        int c = 0, a = 0, b = 1;
        for(int i = 1; i <= n; i ++){
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注