wxg面试

一面

算法

  1. 查找小于n的二进制不含1的个数
  2. 反转left和right之间的链表

https://blog.csdn.net/kexinxin1/article/details/93016958

// // 给定一个正整数 n,找出小于或等于 n 的非负整数中,其二进制表示不包含 连续的1 的个数。

// // 示例 1:

// // 输入: 5
// // 输出: 5
// // 解释: 
// // 下面是带有相应二进制表示的非负整数<= 5:
// // 0 : 0
// // 1 : 1
// // 2 : 10
// // 3 : 11
// // 4 : 100
// // 5 : 101
// // 其中,只有整数3违反规则(有两个连续的1),其他5个满足规则。
// // 说明: 1 <= n <= 10的9次方

// #include <iostream>
// #include <vector>
// #include <string>
// using namespace std;
// string convert(int num);

//     int findIntegers(int num) {
//       if (num == 0) {
//         return 1;
//       }
//       //转换成2进制
//       string binary = convert(num);
//       int len = binary.length();
//       vector<int> res(len+1);
//       res[0] = 1;
//       res[1] = 2;
       //res[i]表示i位符合要求的二进制串的数目
//       for (int i = 2; i <= len; i++) {
//         res[i] = res[i-1]+ res[i-2];
//       }
//       int sum = 0;
//       for (int i = 0, k = len; i < len; i++, k--) {
//         if (binary[i] == '1') {
//           sum += res[k-1];
//           if (i > 0 && binary[i-1] == '1') {
//             return sum;
//           }
//         }
//       }
//       sum++;
//       return sum;
//     }
  
//     string convert(int num) {
//       string res = "";
//       if (num == 0) {
//         return "0";
//       }
//       int val = num;
//       while (num) {
//         res.insert(0, to_string(num%2));
//         num/=2;
//       }
//       return res;
//     }

// int main() {
//   cout << findIntegers(0);
//   return 0;
// }
//链表翻转
//给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。
//示例 1:
//输入:head = [1,2,3,4,5], left = 2, right = 4
//输出:[1,4,3,2,5]
//示例 2:
//输入:head = [5], left = 1, right = 1
//输出:[5]

//提示:
//链表中节点数目为 n
//1 <= n <= 500
//-500 <= Node.val <= 500
//1 <= left <= right <= n

#include <iostream>
#include <vector>
using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};


    ListNode* reverseBetween(ListNode* head, int left, int right) {
      if (left == right) {
        return head;
      }
      ListNode *dummy = new ListNode(-1);
      dummy->next = head;
      ListNode *pre = dummy;
      for (int i = 0; i < left -1; i++) {
        pre = pre->next;
      }
      ListNode *cur = pre->next;
      ListNode *next;
      for (int i = 0; i < right - left; i++) {
        next = cur->next;
        cur->next = next->next;
        next->next = pre->next;
        pre->next = next;
      }
      return dummy->next;
    }


int main() {
  ListNode *dummy = new ListNode(-1);
  ListNode *head = dummy;
  vector<int> res = {1};
  for (int i = 0; i < res.size(); i++) {
    dummy->next = new ListNode(res[i]);
    dummy = dummy->next;
  }
  ListNode *newhead = reverseBetween(head->next, 1, 1);
  while (newhead) {
    cout << newhead->val << ", ";
    newhead = newhead->next;
  }
  return 0;
}

题目

  1. mysql的组合索引,A、B、C,选择B当索引可以命中组合索引吗?
  2. 如何在堆上创建一个类对象
  3. 如何在栈上创建一个类对象
  4. 木棍分成三半,形成三角形的概率是?
  5. 长方形纸,有一个圆形洞,如何把长方形分成面积相等的两部分。。。

二面

算法

  1. 层序遍历逆序

    #include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    struct TreeNode {
     TreeNode *left;
     TreeNode *right;
     int val;
     TreeNode(): left(nullptr), right(nullptr), val(0){}
     TreeNode(int _val): left(nullptr), right(nullptr), val(_val){}
    };
    vector<vector<int>> getLevel(TreeNode *root) {
     vector<vector<int>> res;
     if (root == nullptr) {
            return res;
     }
     queue<TreeNode *> q;
     q.push(root);
     while (!q.empty()) {
         int sz = q.size();
         vector<int> tmp;
         for (int i = 0; i < sz; i++) {
             TreeNode *t = q.front();
             q.pop();
             if (t->left) {
                 q.push((t->left));
             }
             if (t->right) {
                q.push(t->right);
             }
             tmp.push_back(t->val);
         }
         res.push_back(tmp);
    }
    reverse(res.begin(), res.end());
    return res;
    }
    int main() {
    TreeNode *dummy = new TreeNode(3);
    dummy->left = new TreeNode(9);
    dummy->right = new TreeNode(20);
    dummy->right->left = new TreeNode(15);
    dummy->right->right = new TreeNode(7);
    vector<vector<int>> res = getLevel(dummy);
    for (auto x : res) {
        for (int y : x) {
            cout << y << ", ";
     }
        cout << endl;
    }
    return 0;
    }
  2. atoi的实现,考虑多个情况

    int my_atoi(char *ptr) {
    if (ptr == NULL) { 
        return 0; 
    } 
    while (*ptr == ' ') { 
        ptr++; 
    } 
    int ret = 0; 
    int sign = 1; 
    if (*ptr == '-') { 
        sign = -1; 
    } 
    while (*ptr == '-' || *ptr == '+') { 
        ptr++; 
    } 
    while (*ptr) { 
        if (*ptr >= '0' && *ptr <= '9') { 
            ret = ret * 10 + *ptr - '0'; 
            if (ret > INT_MAX) { 
                ret = INT_MAX; 
                break; 
            } 
            ptr++; 
        } else { 
            return -1;//表示有异常字符 
        } 
     }
     if (ret == INT_MAX && sign == 1) { 
        return INT_MAX; 
     } else if (ret == INT_MAX && sign == -1) { 
        return INT_MIN; 
     } 
     return sign * ret;}

问题

  1. 微信支付付款码,如何保证安全性?
  2. qq号int类型,昵称20B,500w数据,如何存储保证增删改查的效率?如果5个亿呢?
  3. 反问+为什么拒offer

评论

暂无评论