408算法题

常用数据结构

单链表

cpp

typedef struct Node {
  int data;
  struct Node *next;
} Node, *LinkList;

int getLength(LinkList head) {
  Node *p = head->next;
  int len = 0;

  while (p != NULL) {
    len++;
    p = p->next;
  }

  return len;
}

求绝对值

cpp

int abs(int a) { return a > 0 ? a : -a; }

2000年

算法思想

C++ 描述

cpp

时间和空间复杂度

时间复杂度为：$O(n)$

空间复杂度为：$O(1)$

2009年

算法思想

定义两个指针变量p和q，初始时均指向头结点的下一个节点。

p指针沿链表移动，当移动到第k个节点时，q指针开始与p指针同步移动；

当p指针移动到最后一个节点时，q指针所指示的节点为倒数第k个节点。

以上过程仅需对链表扫描一次。

算法详细实现步骤

开始时定义两个指针p和q，均指向头结点的下一个节点。计数器count = 0
p首先沿着链表移动，当count==k后，q指针同步移动。直到p为空为止。
如果count >= k, 说明q指针指向的就是倒数第k个节点，输出该节点的data值。返回1。
如果count < k，则说明k的值不在合法范围内，查找失败，返回0

C++ 描述

cpp

// 需要扫描两遍链表
int solve(LinkList head, int k) {
  Node *p = head->next;

  // 计算单链表的长度，不计入头结点
  int len = 0;
  while (p != NULL) {
    len++;
    p = p->next;
  }

  // 找到倒数第k个位置
  p = head;
  int pos = len - k + 1;
  while (p != NULL && pos--) {
    p = p->next;
  }

  if (p != NULL) {
    printf("%d\n", p->data);
    return 1;
  }

  return 0;
}

cpp

// 使用双指针，只需要扫描一遍
int solvePro(LinkList list, int k) {
  // 开始时定义两个指针，均指向头结点的下一个节点
  Node *p = list->next, *q = list->next;
  int count = 0;

  // p首先沿着链表移动，当count==k后，q指针同步移动
  while (p != NULL) {
    p = p->next;
    if (count >= k) {
      q = q->next;
    }
    count++;
  }

  // 如果count >= k, 说明q指针指向的就是倒数第k个节点
  if (count >= k) {
    printf("%d", q->data);
    return 1;
  }

  // 如果count < k，则说明k的值不在合法范围内，查找失败，返回0
  return 0;
}

2010年

算法思想

对数组进行三次逆置

先将整个数组[0，n-1)逆置一遍；
将数组的前部分区间[0，p-1)进行逆置；
将数组的后部分区间[p，n-1)进行逆置；

C++描述

cpp

void reverse(int* arr, int start, int end) {
  int temp = 0;
  // 交换前后对应元素实现逆置
  while (start != end && start < end) {
    temp = arr[start];
    arr[start++] = arr[end];
    arr[end--] = temp;
  }
}

void solve(int* arr, int len, int p) {
  //将整个数组逆置
  reverse(arr, 0, len - 1);
  // 将数组前p个元素逆置
  reverse(arr, 0, p - 1);
  // 将数组后n-p个元素逆置
  reverse(arr, p, len - 1);
}

时间和空间复杂度

时间复杂度为：$O(n)$

空间复杂度为：$O(1)$

2011年

算法思想

分别求两个升序序列的 A、B 的中位数 a 和 b，

① 若 a = b, 则已找到两个序列的中位数，返回a

② 若 a < b, 则舍弃序列 A 中较小的一半，舍弃序列 B 中较大的一半

③ 若 a > b, 则舍弃序列 A 中较大的一半，舍弃序列 B 中较小的一半

重复过程 ① 到 ③ 直到两个序列均只含一个元素为止，返回较小者。

C++ 描述

cpp

// 时间复杂度O(n)，空间复杂度O(1)
int solve(int* arr1, int* arr2, int len) {
  int p = 0, q = 0;  // 两个序列的下标
  // 只需比较len-1次
  for (int i = 0; i < len - 1; ++i) {
    arr1[p] > arr2[q] ? q++ : p++;
  }
  // 返回二者当中较小的，就是中位数
  return arr1[p] > arr2[q] ? arr1[q] : arr2[p];
}

cpp

// 时间复杂度O(logn)，空间复杂度O(1)
int midNum(int* a, int* b, int n) {
  int s1 = 0, d1 = n - 1, s2 = 0, d2 = n - 1;
  int m1, m2;

  while (s1 != d1 || s2 != d2) {
    m1 = (s1 + d1) / 2;
    m2 = (s2 + d2) / 2;

    if (a[m1] == b[m2]) {
      return a[m1];
    } else if (a[m1] < b[m2]) {
      if ((s1 + d1) % 2 == 0) {  // 元素个数为奇数
        s1 = m1;                 // 保留中间点
        d2 = m2;                 // 保留中间点
      } else {                   // 元素个数为偶数
        s1 = m1 + 1;             // 不保留中间点
        d2 = m2;                 // 保留中间点
      }
    } else {
      if ((s2 + d2) % 2 == 0) {  // 元素个数为奇数
        s2 = m2;                 // 保留中间点
        d1 = m1;                 // 保留中间点
      } else {                   // 元素个数为偶数
        s2 = m2 + 1;             // 不保留中间点
        d1 = m1;                 // 保留中间点
      }
    }

  }  // end of while

  return (a[s1] < b[s2]) ? a[s1] : b[s2];
}

时间和空间复杂度

时间复杂度为：$O(logn)$

空间复杂度为：$O(1)$

2012年

算法思想

首先求得str1和str2的长度，分别为m、n
将两个链表以表尾对齐：令指针mp，np分别直线str1和str2头结点的下一个节点。
若m>n，则mp先走，使得mp指向表中第m-n个节点（不算头结点）。
若m<n，则np先走，使得np指向表中第n-m个节点（不算头结点）。
3,4使得mp和np所指节点到表尾长度相等，此时反复将两个指针同步向后移动，直到二者相等，则是共同后缀的起始地址。

C++ 描述

cpp

// 时间复杂度O(n^2)，空间复杂度O(1)
LinkList solve(LinkList str1, LinkList str2) {
  Node *head1 = str1->next;
  Node *head2 = str2->next;

  while (head1 != NULL) {
    while (head2 != NULL) {
      if (head1 == head2) return head1;
      head2 = head2->next;
    }
    head1 = head1->next;
    head2 = str2->next;
  }

  return NULL;
}

cpp

// 时间复杂度O(len1, len2)，空间复杂度O(1)
LinkList solvePro(LinkList str1, LinkList str2) {
  // 获取str1和str2的长度
  int m = getLength(str1);
  int n = getLength(str2);

  Node *mp = str1->next;
  Node *np = str2->next;

  // 将两个链表以表尾对齐
  while (m < n && np != NULL) {
    np = np->next;
    n--;
  }
  while (m > n) {
    mp = mp->next;
    m--;
  }

  // 将指针mp和np同步向后移动，并比较是否相等
  while (mp != NULL && mp != np) {
    mp = mp->next;
    np = np->next;
  }

  // 返回共同后缀其实地址，如果没有则返回NULL
  return mp;
}

时间和空间复杂度

时间复杂度为：$O(max(len1, len2))$

空间复杂度为：$O(1)$

2013年

算法思想

创建一个辅助数组t，大小为n，模拟map。

遍历所给数组arr，由于数组arr中各元素值均不大于n。则用arr元素值作为数组t的下标，统计所有元素出现次数。

最后选取次数最高元素，进行比较判断。

C++ 描述

cpp

// 时间复杂度O(n)，空间复杂度O(n)
void solve(int* arr, int len) {
  // 创建大小为n的辅助空间
  int* t = new int[len]{0};
  int ans = 0;

  // 统计各元素出现次数
  for (int i = 0; i < len; ++i) {
    t[arr[i]]++;
  }

  // 寻找出现次数最高的元素
  for (int i = 0; i < len; ++i) {
    if (t[i] > ans) ans = t[i];
  }

  printf("%d\n", ans > len / 2 ? ans : -1);
  delete t;
}

cpp

//摩尔投票法思想：如果某元素是主元素的话，
//那么他与剩下的其他元素一一抵消的话他也会胜出
//时间复杂度O(n)，空间复杂度O(1)
void moleVote(int* arr, int len) {
  // 选择第一个元素作为临时主元，计数器初始化1
  int ans = arr[0], count = 1;
  for (int i = 1; i < len; ++i) {
    // 如果遇到的元素和临时主元相等，计数器加1，否则抵消减1
    ans == arr[i] ? count++ : count--;

    // 如果计数器为0，则选择当前元素为新的主元
    if (count == 0) {
      ans = arr[i];
      count++;
    }
  }

  count = 0;
  // 统计最后剩下来的临时主元出现次数
  for (int i = 0; i < len; ++i) {
    if (ans == arr[i]) count++;
  }

  printf("%d\n", count > len / 2 ? ans : -1);
}

时间和空间复杂度

时间复杂度为：$O(n)$

空间复杂度为：$O(1)$

2014年

算法思想

基于先序递归遍历的算法思想是用一个static变量记录wpl，把每个节点的深度作为递归函数的一个参数传递，算法步骤如下：

若该结点为空，则返回上一层调用。

若该结点时叶子节点，则变量wpl加上该结点的深度与权值之积

若该结点是非叶结点，则递归调用左右子树。

最后返回计算出的wpl

数据类型定义

cpp

typedef struct BiNode {
  int weight;                      // 数据域
  struct BiNode *lchild, *rchild;  // 左右孩子指针
} BiNode, *BiTree;

C++ 描述

cpp


/*
             1
        2        3
     4    5         6
  7         8

*/

int solve(BiTree root, int layer) {
  // 定义一个static变量存储wpl
  static int wpl = 0;
  // 递归边界
  if (root == NULL) {
    return wpl;
  }

  // 如果是叶子结点则累加权值
  if (root->lchild == NULL && root->rchild == NULL) {
    wpl += root->weight * layer;
  }

  // 递归遍历左右子树
  solve(root->lchild, layer + 1);
  solve(root->rchild, layer + 1);

  return wpl;
}

2015年

算法思想

算法的核心思想是用牺牲空间换取时间。使用辅助标记数组visited记录链表中是否已出现过该数值，从而只需要对链表进行一遍扫描。

因为$|data| \le n$ 所以辅助数组visited大小只需要设置为n+1，初始化均为false。

遍历整个链表，如果visited[|data|]为true则删除该节点；否则保留该节点，并令visited[|data|] = true。

C++ 描述

cpp

// 时间复杂度O(m)，空间复杂度O(n)
void solve(LinkList &head, int n) {
  Node *pre = head;
  Node *p = head->next;

  // 申请n+1个辅助空间，标记是否已访问过该元素
  bool *visited = new bool[n + 1]{false};

  while (p != NULL) {
    // 如果该节点的data已经访问过，则删除该节点
    if (visited[abs(p->data)]) {
      Node *t = p;
      p = p->next;
      pre->next = p;
      delete t;
    } else {
      // 否则保留该节点，并标记已访问
      visited[abs(p->data)] = true;
      pre = p;
      p = p->next;
    }
  }
}

时间和空间复杂度

时间复杂度为：$O(m)$，其中m为链表长度

空间复杂度为：$O(n)$

2016年

算法思想

由题意，将最小的$\lfloor n/2 \rfloor$ 个元素放在A1中，其余元素放在A2中，分组结果即可满足题目要求。

仿照快速排序思想，基于枢轴将n个元素划分为两个子集。根据划分后枢轴所处的位置分别处理：

若i = $\lfloor n/2 \rfloor$ ，则分组完成，算法结束
若i < $\lfloor n/2 \rfloor$ ，则枢轴及之前的所有元素均属于A1，继续对i之后的元素进行划分。
若i > $\lfloor n/2 \rfloor$ ，则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分。

基于该设计思想实现的算法，无须对全部元素进行全排序，其平均时间复杂度为$O(n)$，空间复杂度为$O(1)$

C++ 描述

cpp

// 时间复杂度O(n)，空间复杂度O(1)
int solve(int* arr, int n) {
  int pivot, mid = n / 2;       // 枢轴元素，和中间位置
  int left = 0, right = n - 1;  // 边界游标

  // 边界游标索引，保存每次划分后的游标位置，逐渐逼近中间位置
  int lindex = left, rindex = right;

  // 定义标志
  int flag = 1, s1 = 0, s2 = 0;

  while (flag) {
    pivot = arr[left];

    while (left < right) {
      while (left < right && arr[right] >= pivot) right--;
      arr[left] = arr[right];
      while (left < right && arr[left] <= pivot) left++;
      arr[right] = arr[left];
    }
    arr[left] = pivot;

    // 判断是否继续划分
    if (left < mid) {
      lindex = ++left;
      right = rindex;
    } else if (left > mid) {
      rindex = --right;
      left = lindex;
    } else {
      flag = 0;
    }
  }

  for (int i = 0; i < mid; ++i) {
    s1 += arr[i];
  }
  for (int i = mid; i < n; ++i) {
    s2 += arr[i];
  }

  return s2 - s1;
}

时间和空间复杂度

时间复杂度为：$O(n)$

空间复杂度为：$O(1)$

2017年

算法思想

表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。

除了根结点和叶子结点，遍历到其他结点的时候，在遍历左子树之前加左括号，遍历完右子树后加上右括号。

C++ 描述

cpp

void solve(BTree* root, int layer) {
  if (root == NULL) {
    return;
  }

  // 若为叶节点则直接输出操作数，不加括号
  if (root->left == NULL && root->right == NULL) {
    printf("%s", root->data);
  } else {
    // 若不是叶节点，且不是所处层数大于1，则需要加相应的括号
    if (layer > 1) {
      printf("(");
    }
    solve(root->left, layer + 1);
    printf("%s", root->data);
    solve(root->right, layer + 1);
    if (layer > 1) {
      printf(")");
    }
  }
}

2018年

算法思想

要求在时间上尽可能高效，因此采用牺牲空间换取时间的方法。

如果数组A长度为n，则数组A中最小未出现的正整数肯定不超过n+1。则可创建一个辅助标记数组T，用来记录A中是否出现了[1,n]中的正整数，为了防止溢出，可以申请稍微比n大一点的内存。

T[1]对一个正整数1，T[n]对应正整数n。T[1] = 1，表示出现了正整数1。

初始化T中全部为0。遍历数组A对T进行标记。最后遍历T寻找最小未被标记的正整数。

C++ 描述

cpp

// 时间复杂度O(n)，空间复杂度O(n)
int solve(int* arr, int len) {
  // 定义最大值，比数组长度稍大一些，防止溢出
  const int maxn = len + 10;
  // 定义辅助标记数组
  int* t = new int[maxn]{0};

  // 将数组arr中出现的[1, len]区间内的正整数进行标记
  for (int i = 0; i < len; ++i) {
    if (arr[i] > 0 && arr[i] <= len) t[arr[i]] = 1;
  }

  // 寻找最小未出现的正整数
  for (int i = 1; i < maxn; ++i) {
    if (t[i] == 0) return i;
  }

  return -1;
}

时间和空间复杂度

时间复杂度为：$O(n)$

空间复杂度为：$O(n)$

2019年

算法思想

C++ 描述

cpp

void reverseList(LinkList &head) {
  Node *p = head->next;
  Node *tmp = NULL;

  // 每次都断掉p的下一个节点，头插法插入到最前
  // 直到p所指节点成为最后一个节点，则逆序完成
  while (p->next != NULL) {
    // 获取p的下一个节点
    tmp = p->next;
    p->next = p->next->next;

    // 头插法
    tmp->next = head->next;
    head->next = tmp;
  }
}

void solve(LinkList &L) {
  Node *p = L->next;
  Node *midp = L;
  Node *tmp = NULL;

  int len = getLength(L);
  int mid = (len + 1) / 2;

  // 移动到中间节点
  while (mid--) {
    midp = midp->next;
  }

  // 原地逆置后半段链表
  reverseList(midp);
    
  // 无论链表节点个数是奇数还是偶数
  // 采用此方法p均会和midp重合
  while (p != midp) {
    tmp = midp->next;
    midp->next = midp->next->next;

    tmp->next = p->next;
    p->next = tmp;

    p = p->next->next;
  }
}

时间和空间复杂度

时间复杂度为：$O(n)$

空间复杂度为：$O(1)$

2020年

算法思想

https://blog.csdn.net/qq_28468707/article/details/104328840

C++ 描述

cpp

// 时间复杂度O(n^3)，空间复杂度O(1)
void solve(int* arr1, int len1, int* arr2, int len2, int* arr3, int len3) {
  int ans = 65535;
  for (int i = 0; i < len1; ++i) {
    for (int j = 0; j < len2; ++j) {
      for (int k = 0; k < len3; ++k) {
        int t = abs(arr1[i] - arr2[j]) + abs(arr1[i] - arr3[k]) +
                abs(arr2[j] - arr3[k]);
        if (t < ans) ans = t;
      }
    }
  }

  printf("%d\n", ans);
}

时间和空间复杂度

时间复杂度为：$O(n^3)$

空间复杂度为：$O(1)$

408算法题 ​

常用数据结构 ​

单链表 ​

求绝对值 ​

2000年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2009年 ​

算法思想 ​

算法详细实现步骤 ​

C++ 描述 ​

2010年 ​

算法思想 ​

C++描述 ​

时间和空间复杂度 ​

2011年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2012年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2013年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2014年 ​

算法思想 ​

数据类型定义 ​

C++ 描述 ​

2015年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2016年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2017年 ​

算法思想 ​

C++ 描述 ​

2018年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2019年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

2020年 ​

算法思想 ​

C++ 描述 ​

时间和空间复杂度 ​

408算法题

常用数据结构

单链表

求绝对值

2000年

算法思想

C++ 描述

时间和空间复杂度

2009年

算法思想

算法详细实现步骤

C++ 描述

2010年

算法思想

C++描述

时间和空间复杂度

2011年

算法思想

C++ 描述

时间和空间复杂度

2012年

算法思想

C++ 描述

时间和空间复杂度

2013年

算法思想

C++ 描述

时间和空间复杂度

2014年

算法思想

数据类型定义

C++ 描述

2015年

算法思想

C++ 描述

时间和空间复杂度

2016年

算法思想

C++ 描述

时间和空间复杂度

2017年

算法思想

C++ 描述

2018年

算法思想

C++ 描述

时间和空间复杂度

2019年

算法思想

C++ 描述

时间和空间复杂度

2020年

算法思想

C++ 描述

时间和空间复杂度