面试代码记录

面试代码题

可以刷一刷CodeTop

链表是否存在环

给你一个链表的头节点 head ，判断链表中是否有环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdbool.h>
struct ListNode {
  int val;
  struct ListNode* next;
};
bool hasCycle(struct ListNode* head) {
  struct ListNode* slow = head;
  struct ListNode* fast = head;
  do {
    if (fast == NULL || fast->next == NULL) {  // 链表末尾，非环
      return false;
    }
    slow = slow->next;        // 前进一步
    fast = fast->next->next;  // 前进两步
  } while (slow != fast);
  return true;
}

C实现

字符串数组去重

将字符串数组中重复的字符串去掉。

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
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct string_array {
  char** data;
  int length;
};

struct string_array delete_repeat_string(struct string_array arr) {
  char** p = (char**)malloc(arr.length * sizeof(char*));  // 申请空间并置空
  memset(p, 0, arr.length * sizeof(char*));
  int index = 0;
  bool find_same_string;  // 是否遇到相同字符串
  for (int i = 0; i < arr.length; i++) {
    find_same_string = false;
    for (int j = 0; j < i; j++) {
      if (strcmp(arr.data[i], arr.data[j]) == 0) {
        find_same_string = true;
        break;
      }
    }
    if (!find_same_string) {
      p[index] = (char*)malloc(strlen(arr.data[i]) + 1);  // 申请空间拷贝字符串
      strcpy(p[index], arr.data[i]);
      index++;
    }
  }
  struct string_array ans = {p, index};
  return ans;
}

int main() {
  char* test[] = {"apple", "banna", "apple", "test", "test1", "test2", "banna", "test23", "test2", "test234"};
  struct string_array src = {test, sizeof(test) / sizeof(char*)};
  struct string_array res = delete_repeat_string(src);
  for (int i = 0; i < res.length; i++) {
    printf("%s\n", res.data[i]);
  }
  return 0;
}

C实现

二分查找

实现第一个大于等于，最后一个小于等于操作，见博客重载记录 二分查找

流控算法

实现一个简单的check函数，处理函数执行前调用check函数，若TPS超过MAX TPS则返回失败

1
bool check(){}

见博客重载记录 流控算法

比较版本号

165. 比较版本号

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
31
32
33
34
35
36
37
38
39
40
41
class Solution {
 public:
  // std::size_t std::__cxx11::string::find(char __c, std::size_t __pos) const noexcept
  vector<int> getVersion(string& version) {
    vector<int> ans;
    version.push_back('.');  // 在末尾加上.，统一处理
    int last_pos = 0;
    int pos;
    while ((pos = version.find('.', last_pos)) != string::npos) {
      ans.emplace_back(stoi(version.substr(last_pos, pos - last_pos)));
      last_pos = pos + 1;
      pos = version.find('.', last_pos);
    }
    return ans;
  }
  int compareVersion(string version1, string version2) {
    vector<int> v1 = getVersion(version1);
    vector<int> v2 = getVersion(version2);
    // 在尾部补齐0
    if (v1.size() > v2.size()) {
      int padding = v1.size() - v2.size();
      for (int i = 0; i < padding; i++) {
        v2.emplace_back(0);
      }
    } else {
      int padding = v2.size() - v1.size();
      for (int i = 0; i < padding; i++) {
        v1.emplace_back(0);
      }
    }
    // 比较版本号
    for (int i = 0; i < v2.size(); i++) {
      if (v1[i] > v2[i]) {
        return 1;
      } else if (v1[i] < v2[i]) {
        return -1;
      }
    }
    return 0;
  }
};

写代码时卡壳了，主要的错误在于：
1：忘记了find的参数原型

1
std::size_t std::__cxx11::string::find(char __c, std::size_t __pos) const noexcept

__c和pos的位置写反了
2：v1 v2都传入了version1

1
2
vector<int> v1 = getVersion(version1);
vector<int> v2 = getVersion(version1);

3：没有补齐操作，若共用的部分相等则长度大的版本号更大，忽略了修订号有可能为0的情况，1.0.0与1.0

优化版本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
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
class Solution {
 public:
  vector<int> getVersion(string& version) {
    vector<int> ans;
    version.push_back('.');
    int last_pos = 0;
    int pos;
    while ((pos = version.find('.', last_pos)) != string::npos) {
      ans.emplace_back(stoi(version.substr(last_pos, pos - last_pos)));
      last_pos = pos + 1;
      pos = version.find('.', last_pos);
    }
    return ans;
  }
  int compareVersion(string version1, string version2) {
    vector<int> v1 = getVersion(version1);
    vector<int> v2 = getVersion(version2);
    int i = 0;
    int j = 0;
    while (i < v1.size() || j < v2.size()) {
      int x = 0;
      int y = 0;
      if (i < v1.size()) {
        x = v1[i];
        i++;
      }
      if (j < v2.size()) {
        y = v2[j];
        j++;
      }
      if (x > y) {
        return 1;
      }
      if (x < y) {
        return -1;
      }
    }
    return 0;
  }
};

对于长度不一致的数组，采用或操作的方式进行循环遍历，减少代码量，思路有点像字符串相加中的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  string addStrings(string num1, string num2) {
    int i = num1.length() - 1;
    int j = num2.length() - 1;
    int carry = 0;
    string ans;
    while ((i >= 0) || (j >= 0) || (carry > 0)) {
      int x = (i >= 0) ? num1[i] - '0' : 0;
      int y = (j >= 0) ? num2[j] - '0' : 0;
      int sum = x + y + carry;
      ans.push_back(sum % 10 + '0');
      carry = sum / 10;
      i--;
      j--;
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

优化版本2：

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
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  int compareVersion(string version1, string version2) {
    // 末尾加.，统一处理
    version1.push_back('.');
    version2.push_back('.');
    int i = 0;
    int j = 0;
    while (i < version1.length() || j < version2.length()) {
      // 计算x y大小
      long long x = 0;
      while (i < version1.length()) {
        if (version1[i] == '.') {
          break;
        }
        x = x * 10 + version1[i] - '0';
        i++;
      }
      long long y = 0;
      while (j < version2.length()) {
        if (version2[j] == '.') {
          break;
        }
        y = y * 10 + version2[j] - '0';
        j++;
      }
      // 比较x y大小
      if (x > y) {
        return 1;
      }
      if (x < y) {
        return -1;
      }
      // 跳过.
      i++;
      j++;
    }
    return 0;
  }
};

遍历时计算数字大小并比较

字符串最长单词

给定一个字符串数组，求其中有效单词（只能包含字母）的最大长度。示例：[abc abc0 abc–d ab] answer：3

版本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
31
32
33
34
35
36
#include <bits/stdc++.h>
#include <string_view>
using namespace std;

vector<string_view> GetVaildWord(string& s) {
  vector<string_view> ans;
  s.push_back(' ');  // 末尾加上空格，统一处理
  string_view str_view(s);
  int last_pos = 0;
  int pos;
  while ((pos = str_view.find(' ', last_pos)) != string::npos) {
    string_view word = str_view.substr(last_pos, pos - last_pos);
    bool vaild = true;
    for (char c : word) {
      if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) {
        vaild = false;
        break;
      }
    }
    if (vaild) {
      ans.emplace_back(word);
    }
    last_pos = pos + 1;
  }
  return ans;
}

int main() {
  string str = "abc abc0 abc--d ab";
  auto res = GetVaildWord(str);  // 分割字符串，得到有效单词
  size_t max_len = 0;
  for (auto word : res) {
    max_len = max(max_len, word.length());  // 求单词的最大长度
  }
  cout << max_len << endl;
}

版本2：遍历时计算单词长度并判断单词是否有效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int main() {
  string str = "abc abc0 abc--d ab";
  str.push_back(' ');
  int max_len = 0;
  int len = 0;
  bool vaild = true;
  for (char c : str) {
    if (((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))) {  // 字母字符
      len++;
    } else if (c == ' ') {  // 空格
      if (vaild) {
        max_len = max(max_len, len);
      }
      len = 0;
      vaild = true;
    } else {  // 其他无效字符
      vaild = false;
    }
  }
  cout << max_len << endl;
}

LRU算法

146. LRU 缓存

使用STL list实现

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
class LRUCache {
 public:
  LRUCache(int capacity) : capacity_(capacity), size_(0) {}
  using kv = pair<int, int>;
  int get(int key) {
    if (speed_map_.count(key) == 0) {
      return -1;
    }
    list<kv>::iterator pos = speed_map_[key];
    int value = pos->second;
    if (pos != data_.begin()) {  // 移至队首
      data_.erase(pos);          // pos迭代器失效
      data_.emplace_front(key, value);
      speed_map_[key] = data_.begin();
    }
    return value;
  }

  void put(int key, int value) {
    if (speed_map_.count(key) == 0) {
      if (size_ == capacity_) {  // 淘汰队尾数据
        speed_map_.erase(data_.back().first);
        data_.pop_back();
        size_--;  // 当前大小减一
      }
      // 插入队首
      data_.emplace_front(key, value);
      speed_map_.insert({key, data_.begin()});
      size_++;  // 当前大小加一
    } else {    // 更新key-value对
      list<kv>::iterator pos = speed_map_[key];
      pos->second = value;
      if (pos != data_.begin()) {  // 移至队首
        data_.erase(pos);          // pos迭代器失效
        data_.emplace_front(key, value);
        speed_map_[key] = data_.begin();
      }
    }
  }

 private:
  int capacity_;                                      // 容量
  int size_;                                          // 当前大小
  unordered_map<int, list<kv>::iterator> speed_map_;  // key与list迭代器
  list<kv> data_;                                     // 存储key-value对
};

注意list删除后相应迭代器也失效了
简单示例：

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;

int main() {
  list<int> head;
  head.emplace_back(12);
  auto iter = head.begin();
  cout << *iter << endl;  // 12
  head.erase(iter);       //删除元素
  cout << *iter << endl;  // -17891602
}

使用自定义双向链表，更新LRU时不需要修改map

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;

struct ListNode {  // 双向链表实现
  int key;
  int value;
  ListNode* prev;
  ListNode* next;
  ListNode() = default;
  ListNode(int key1, int value1) : key(key1), value(value1) {}

  static void InsertNode(ListNode* head, ListNode* node) {  // 在头节点后插入节点
    node->next = head->next;
    node->prev = head;
    head->next->prev = node;
    head->next = node;
  }

  static void DeleteNode(ListNode* node) {  // 删除节点
    node->next->prev = node->prev;
    node->prev->next = node->next;
  }
};
class LRUCache {
 public:
  LRUCache(int capacity) : capacity_(capacity), size_(0) {
    // 初始化头节点，循环双向链表
    head_.next = &head_;
    head_.prev = &head_;
  }

  int get(int key) {
    if (speed_map_.count(key) == 0) {  // key不存在
      return -1;
    }
    ListNode* node = speed_map_[key];
    int value = node->value;
    if (head_.next != node) {  // 移至队首
      ListNode::DeleteNode(node);
      ListNode::InsertNode(&head_, node);
    }
    return value;
  }

  void put(int key, int value) {
    if (speed_map_.count(key) == 0) {  // 插入操作
      if (size_ >= capacity_) {        // 淘汰操作
        ListNode* node = head_.prev;   // 队尾节点
        ListNode::DeleteNode(node);
        speed_map_.erase(node->key);
        delete node;
        size_++;
      }
      ListNode* node = new ListNode(key, value);
      ListNode::InsertNode(&head_, node);
      speed_map_.emplace(key, node);
      size_++;
    } else {  // 更新操作
      ListNode* node = speed_map_[key];
      node->value = value;
      if (head_.next != node) {
        ListNode::DeleteNode(node);
        ListNode::InsertNode(&head_, node);
      }
    }
  }
  ~LRUCache() {  // 释放动态资源
    while (head_.next != &head_) {
      ListNode* node = head_.next;
      ListNode::DeleteNode(node);
      delete node;
    }
    size_ = 0;
  }

 private:
  int capacity_;
  int size_;
  ListNode head_;
  unordered_map<int, ListNode*> speed_map_;
};

重排链表

143. 重排链表

遇到的问题：
1：面试时根本没想到解法，面试官给出了解法后实现上又出现了一些问题
2：链表反转函数实现受反转链表 II影响使用了虚拟头节点，却没有真正理解那道题中使用虚拟头节点的意义
3：前半部和后半部的连接没有断开，导致无限循环

美团的面试官都很nice，以后要多刷链表相关的算法题了

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
 public:
  ListNode* reverseList(ListNode* head) {  // 链表反转 三指针法
    ListNode* prev = nullptr;
    ListNode* curr = head;
    ListNode* next;
    while (curr != nullptr) {
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }
  ListNode* mergeList(ListNode* node1, ListNode* node2) {  // 合并链表
    ListNode virt_head(-1);
    ListNode* node = &virt_head;
    while (node1 != nullptr || node2 != nullptr) {  // 先选择node1的节点，后选择node2的节点
      if (node1 != nullptr) {
        node->next = node1;
        node = node1;
        node1 = node1->next;
      }

      if (node2 != nullptr) {
        node->next = node2;
        node = node2;
        node2 = node2->next;
      }
    }
    return virt_head.next;
  }
  void reorderList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
      return;
    }
    ListNode virt_head(-1, head);
    ListNode* prev = &virt_head;  // 慢指针的前继节点
    ListNode* slow = head;        // 慢指针
    ListNode* fast = head;        // 快指针
    while (fast != nullptr && fast->next != nullptr) {
      prev = slow;
      slow = slow->next;
      fast = fast->next->next;
    }
    prev->next = nullptr;                       // 断掉前后链表的连接
    ListNode* latter_half = reverseList(slow);  // 将后半部链表反转
    head = mergeList(head, latter_half);        // 再次合并前后链表
  }
};

寻找后序遍历的后继节点

先进行分类讨论，处理简单的情况，再单独左子节点情况进行处理
当节点为左子节点且右子节点不为空时，需要想明白后继节点一定是叶子节点，后序遍历的顺序是左右根，那么先持续左再尝试向右，直至叶子节点

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
struct node {
  struct node *left;
  struct node *right;
  struct node *parent;
};

struct node *next_postorder(const struct node *node) {
  if (node->parent == NULL) {  // 根节点
    return NULL;
  }
  struct node *node_parent = node->parent;
  if (node_parent->right == node) {  // 为父节点的右子节点
    return node_parent;
  }

  if (node_parent->right == NULL) {  //  为父节点的左子节点，但右子节点为空
    return node_parent;
  }
  struct node *next = node_parent->right;              // 从右子节点开始
  while (next->left != NULL || next->right != NULL) {  // 不为叶子节点
    while (next->left != NULL) {                       // 持续向左
      next = next->left;
    }
    if (next->right != NULL) {  // 向右拓宽路径
      next = next->right;
    }
  }
  return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
写一个C/C++的函数供别人调用，实现以下功能
给定任意一个字符串，对其中的每个字符进行忽略字母大小写的排序
*/
#include <bits/stdc++.h>
using namespace std;
char get_equal_char(char c) {  // 全部转换成大写字母
  if (c >= 'a' && c <= 'z') {
    return c - ('a' - 'A');
  }
  return c;
}

int compare(char c1, char c2) {  // 自定义比较函数
  c1 = get_equal_char(c1);
  c2 = get_equal_char(c2);
  if (c1 > c2) {
    return 1;
  }
  if (c1 < c2) {
    return -1;
  }
  return 0;
}

int partition(char* str, int start, int end) {  // 划分函数
  char p = str[end];
  int slow = start - 1;
  for (int fast = start; fast < end; fast++) {
    if (compare(str[fast], p) == -1) {  // str[fast] < p
      slow++;
      char tmp = str[slow];
      str[slow] = str[fast];
      str[fast] = tmp;
    }
  }
  char tmp = str[slow + 1];
  str[slow + 1] = str[end];
  str[end] = tmp;
  return slow + 1;
}

void quick_sort(char* str, int start, int end) {  // 快排
  if (start >= end) {
    return;
  }
  int p = partition(str, start, end);
  quick_sort(str, start, p - 1);
  quick_sort(str, p + 1, end);
}

void my_sort(char* str, int len) { quick_sort(str, 0, len - 1); }

int main() {
  char test[] = "dcAefgkLG";
  printf("%s\n", test);
  my_sort(test, strlen(test));
  printf("%s\n", test);
}

/*
dcAefgkLG
AcdefGgkL
*/

频率前10的单词

与LeetCode 692. 前K个高频单词类似
给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

思路
用map记录各单词的出现次数，而后转到另一个map中，反向遍历，输出出现次数高的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<string> topKFrequent(vector<string>& words, int k) {
    map<string, int> ma1;  // 单词-出现次数
    for (string& word : words) {
      ma1[word]++;
    }
    map<int, set<string>> ma2;  // 出现次数-单词
    for (auto& kv : ma1) {
      ma2[kv.second].emplace(kv.first);
    }
    vector<string> ans;
    for (auto iter = ma2.rbegin(); iter != ma2.rend(); ++iter) {  // 反向遍历，出现次数高的在前面
      for (const string& str : iter->second) {                    // 字典序输出结果
        ans.emplace_back(str);
        if (ans.size() == k) {
          return ans;
        }
      }
    }
    return ans;
  }
};

另一种实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  using Info = pair<string, int>;
  vector<string> topKFrequent(vector<string>& words, int k) {
    unordered_map<string, int> ma;  // 单词-出现次数
    for (string& word : words) {
      ma[word]++;
    }
    vector<Info> vec(ma.begin(), ma.end());
    auto cmp = [](const Info& info1, const Info& info2) -> bool { return info1.second > info2.second || (info1.second == info2.second && info1.first < info2.first); };  // 出现次数高的，字典序小的排前面
    sort(vec.begin(), vec.end(), cmp);
    int size = min<int>(k, vec.size());
    vector<string> ans(size);
    for (int i = 0; i < size; i++) {
      ans[i] = vec[i].first;
    }
    return ans;
  }
};

树的最大权重和

对于一个树，每条边都有一个权重，求根节点到叶子节点的最大权重和

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
  vector<pair<int, int>> childs;	// 子节点-边权重
};
void dfs(const vector<TreeNode>& nodes, int cur_node, int cur_w, int& max_w) {  // cur_node：当前遍历节点  cur_w：当前权重和  max_w： 最大权重和
  if (nodes[cur_node].childs.empty()) {                                         // 叶子节点
    max_w = max(max_w, cur_w);                                                  // 记录最大权重和
    return;
  }
  for (const auto& [next_node, w] : nodes[cur_node].childs) {  // 尝试下一节点
    dfs(nodes, next_node, cur_w + w, max_w);
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<TreeNode> nodes(n);
  vector<bool> is_child(n, false);
  // 构建树结构
  for (int i = 0; i < m; i++) {
    int parent, child, w;
    cin >> parent >> child >> w;
    is_child[child] = true;
    nodes[parent].childs.emplace_back(child, w);
  }
  // 找到根节点
  int root = -1;
  for (int i = 0; i < n; i++) {
    if (is_child[i] == false) {
      root = i;
      break;
    }
  }
  // 深度优先遍历
  int ans = -(1 << 30);
  dfs(nodes, root, 0, ans);
  cout << ans << endl;
}

/*
输入：
节点数目  边数
父节点 子节点 边权重
*/

反转链表 II

反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

思路：
这个题目我之前LeetCode写过故基本思路比较清晰，使用虚拟头节点统一处理，注意左侧节点前继节点，左侧节点，右侧节点，右侧节点后继节点的位置关系即可。==不过问题是需要自己写完整的程序（构建链表，反转链表，输出链表等）==，本来功能实现，样例都没啥问题，但面试官说需要多测试几个样例，便直接复制粘贴语句，但忘了复制构造链表的语句，导致第二个样例反转的链表是第一次样例的结果，使得结果非常诡异。当时以为是我实现有问题，调了10多分钟，刚找到原因的时候面试官结束了面试。

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
class Solution {
 public:
  ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (left == right || head->next == nullptr) {  // 翻转区间为空或链表大小为1
      return head;
    }
    ListNode virt_head(-1, head);
    ListNode* left_prev = &virt_head;  // 左侧节点前继节点
    for (int i = 1; i < left; i++) {
      left_prev = left_prev->next;
    }
    ListNode* prev = left_prev->next;
    ListNode* curr = prev->next;
    ListNode* next;
    for (int i = left; i < right; i++) {
      next = curr->next;
      curr->next = prev;

      prev = curr;
      curr = next;
    }

    left_prev->next->next = next;  // 左侧节点指向右侧节点后继节点
    left_prev->next = prev;        // 左侧节点前继节点指向右侧节点
    return virt_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
26
27
28
29
30
class Solution {
 public:
  ListNode* reverseBetween(ListNode* head, int left, int right) {
    if (head->next == nullptr) {  // 只有一个节点
      return head;
    }
    ListNode virt_head(-1, head);  // 虚拟头节点，便于统一处理
    // 迭代至正确的左节点前置节点
    ListNode* left_node_prev = &virt_head;
    for (int i = 1; i < left; i++) {
      left_node_prev = left_node_prev->next;
    }
    ListNode* left_node = left_node_prev->next;
    ListNode* prev = left_node;
    ListNode* curr = left_node->next;  // 处理左节点后继节点
    ListNode* next;
    for (int i = left; i < right; i++) {
      next = curr->next;  // 保存后继节点
      curr->next = prev;  // 转向
      // 向前移动
      prev = curr;
      curr = next;
    }
    // 此时curr next为right node后继节点，prev为right node
    // 连接反转链表的头尾
    left_node->next = curr;
    left_node_prev->next = prev;
    return virt_head.next;
  }
};

memmove实现

估计是我前面问题答的挺好的（自我感觉），面试官出了一个简单题，实现memmove函数功能，避免src与dst重叠时错误的内存拷贝，但我把这个问题想复杂了，以为是什么判断区间重叠之类的问题，并且很久我都没有get到src与dst区间重叠会出现啥问题（有可能面试写代码有点紧张），导致我40分钟都没有写出一个简单题，难顶

相关博客
仰视源码，实现memmove

实际上这就是一个简单的分类讨论，只在dst大于src且有重叠区域时需要逆序拷贝，其余情况都要memcpy就可以了。

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
31
32
33
34
35
36
37
38
39
40
#include <string.h>
#include <stdio.h>

void* my_memmove(void* dst, void* src, size_t cnt) {
  char* dest = (char*)dst;
  char* source = (char*)src;
  if (dest < source || dest > source + cnt) {
    memcpy(dest, source, cnt);
  } else {
    for (int i = cnt - 1; i >= 0; i--) {
      dest[i] = source[i];
    }
  }

  return dst;
}
int main() {
  char data[20];
  for (int i = 0; i < 20; i++) {
    data[i] = 'a' + i;
  }
  char* src = &data[0];
  char* dest = &data[5];
  printf("src content\n");
  for (int i = 0; i < 10; i++) {
    printf("%c ", src[i]);
  }
  printf("\ndest content\n");
  for (int i = 0; i < 10; i++) {
    printf("%c ", dest[i]);
  }

  printf("\ncall memmove\n");
  my_memmove(dest, src, 10);

  printf("dest content\n");
  for (int i = 0; i < 10; i++) {
    printf("%c ", dest[i]);
  }
}

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

思路：刚开始想用下一个相同元素位置的方法，以为是优化的方法，后面想想有点问题，就用最简单的set计算无重复字符串的子串长度

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
class Solution {
 public:
  int lengthOfLongestSubstring(string s) {
    int ans = 0;
    int start = 0;
    unordered_set<char> tmp;
    for (int i = 0; i < s.length(); i++) {
      if (tmp.count(s[i]) == 0) {  // 无重复字符，直接加入
        tmp.emplace(s[i]);
      } else {
        // 记录无重复字符子串最大长度
        ans = max<int>(ans, tmp.size());
        // 持续删除字符直到该重复字符位置
        while (s[start] != s[i]) {
          tmp.erase(s[start]);
          start++;
        }
        // 再向前移一位
        start++;
      }
    }
    ans = max<int>(ans, tmp.size());
    return ans;
  }
};

连续的子数组和

思路：在写的时候使用了前缀和的方式便于计算连续子数组和，但没想到使用map计算余数为x的序号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  bool checkSubarraySum(vector<int>& nums, int k) {
    map<int, int> tmp;
    long long sum = 0;
    tmp.emplace(0, -1);
    for (int i = 0; i < nums.size(); i++) {
      sum += nums[i];
      sum = ((sum % k) + k) % k;
      if (tmp.count(sum) != 0) {  // 存在特定余数
        if (i - tmp[sum] >= 2) {  // 下标之差大于等于2
          return true;
        }
      } else {  // 记录该余数第一次出现的下标
        tmp.emplace(sum, i);
      }
    }
    return false;
  }
};

字符串中不同单词的数目（不区分大小写）

使用status遍历记录当前遇到英文字符状态，遍历时顺带将小写字母转换为大写字母，使用set记录不同单词的数目

IP点分地址转换成数字

需同时判断IP地址是否合法，存在其他字符

① 使用状态机遍历字符串（例如：状态1 预期遇到空格 点号 数字，状态2 预期遇到数字 状态3 预期不遇到任何字符）

② 首先将IP地址按点号分割，而后进行处理

相似题目：[编程题]整数与IP地址间的转换

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
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

vector<string> SplitStr(string& s) {
    s.push_back('.');
    vector<string> ans;
    int last_pos = 0;
    int pos;
    while ((pos = s.find('.', last_pos)) != string::npos) {
        ans.emplace_back(s.substr(last_pos, pos - last_pos));
        last_pos = pos + 1;
    }
    return ans;
}

int main() {
    string s;
    while (cin >> s) {

        if (s.find('.') != string::npos) {
            vector<string> nums = SplitStr(s);
            long long int value = 0;
            for (string& num : nums) {
                value = value * 256 + atoi(num.c_str());
            }
            cout << value << endl;
        } else {
            long long int value = atol(s.c_str());
            for (int i = 3; i > 0; i--) {
                cout << value / (long long int)pow(256, i);
                cout << ".";
                value %= (long long int)pow(256, i);
            }
            cout << value << endl;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
相关函数方法
// 字母大小写
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
  string s = "ABCDEFG";
  string result;

  transform(s.begin(), s.end(), s.begin(), ::tolower);
  cout << s << endl;
  return 0;
}
// 数字 字符串转换

int atoi(const char *__nptr)
long atol(const char *__nptr)
std::string to_string(int __val)
int std::__cxx11::stoi(const std::string &__str, std::size_t *__idx = (std::size_t *)0, int __base = 10)