wxg面试
文章目录
一面
算法
- 查找小于n的二进制不含1的个数
- 反转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;
}
题目
- mysql的组合索引,A、B、C,选择B当索引可以命中组合索引吗?
- 如何在堆上创建一个类对象
- 如何在栈上创建一个类对象
- 木棍分成三半,形成三角形的概率是?
- 长方形纸,有一个圆形洞,如何把长方形分成面积相等的两部分。。。
二面
算法
层序遍历逆序
#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; }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;}
问题
- 微信支付付款码,如何保证安全性?
- qq号int类型,昵称20B,500w数据,如何存储保证增删改查的效率?如果5个亿呢?
- 反问+为什么拒offer
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论