LCR 155、将二叉搜索树转为排序的双向链表——树、DFS
用head记录头节点，pre记录当前已建立的排序双向链表的尾节点。中序遍历二叉树，遍历的结果即排序的数字，当pre为空时，说明还没建立任何节点，则让head等于当前节点，然后让pre等于当前节点，否则让pre的后继指针指向当前节点，当前节点的前驱指针指向pre节点即可。
建立完成后，pre即为尾节点，建立尾节点与头节点之间的关系并返回head
代码语言：javascript复制/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
private Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null){
return null;
}
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
private void dfs(Node root){
if(root == null){
return;
}
dfs(root.left);
if(pre == null){
head = root;
}else{
pre.right = root;
root.left = pre;
}
pre = root;
dfs(root.right);
}
}LCR 148、验证图书取出顺序——栈
主要思路就是判断takeOut是不是takeIn可能的取出序列。
一个指针记录当前准备放入的书，一个指向准备取出的书，如果当前栈顶的书等于准备取出的书，则一直取出直到栈为空或者栈顶的书不等于准备取出的书，然后移动in指针。
代码语言：javascript复制class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
int in = 0, out = 0;
Stack<Integer> s = new Stack<>();
while(in < putIn.length){
s.push(putIn[in]);
while(!s.isEmpty() && s.peek() == takeOut[out]){
out ;
s.pop();
}
in ;
}
return s.isEmpty();
}
}平均数为k的最长连续子数组
每次输入时减k，那么问题就变成了和为0的最长子数组。在输入遍历的过程中，记录当前的前缀和，如果之前存在相同的前缀和，则说明这两个前缀和之间的子数组和为0，否则将前缀和和下标存入哈希表。
代码语言：javascript复制#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
#define ll long long
int main() {
int res = -1;
int n, k;
cin>>n>>k;
vector<int> nums(n, 0);
ll prefix = 0;
unordered_map<ll, int> map;
map[0] = -1;
for (int i = 0; i < n; i) {
cin >> nums[i];
nums[i] -= k;
prefix = nums[i];
if(map.find(prefix) != map.end()){
res = max(res, i - map[prefix]);
}else{
map[prefix] = i;
}
}
cout<<res<<endl;
}
// 64 位输出请用 printf("%lld")小球投盒——集合
一个集合用来存放操作类型一放入的，一个集合用来存放操作类型二未放入的。
如果集合一大小等于n或者集合二存在x，说明放满了；如果集合二大小大于1或者集合一存在x，也说明放满了。
代码语言：javascript复制#include <bitset>
#include <cmath>
#include <iostream>
#include <unordered_set>
using namespace std;
int main() {
int res = -1;
int m, n;
cin >> n >> m;
int t, x;
unordered_set<int> put;
unordered_set<int> unput;
int cnt = 0;
while(m--){
cnt ;
cin >> t >> x;
if(x <= n && x >= 1){
if(t == 1){
put.insert(x);
if(put.size() == n || unput.find(x) != unput.end()){
cout<<cnt<<endl;
return 0;
}
}else{
unput.insert(x);
if(unput.size() > 1 || put.find(x) != put.end()){
cout<<cnt<<endl;
return 0;
}
}
}
}
cout<<-1<<endl;
return 0;
}
// 64 位输出请用 printf("%lld")小红结账
略
代码语言：javascript复制#include <iostream>
#include <vector>
#define ll long long
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<ll> moneys(m, 0);
int k, c;
while(n--){
cin >> k >> c;
int money = c / k;
if(c % k != 0){
money ;
}
int p;
for(int i = 0; i < k - 1; i ){
cin >> p;
moneys[p-1] = money;
}
}
for (ll& money: moneys) {
cout << money << " ";
}
cout<<endl;
}
// 64 位输出请用 printf("%lld")合法IP地址
略
代码语言：javascript复制#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
string ip;
cin >> ip;
bool valid = true;
vector<string> seg;
string tmp;
for (auto& ch : ip) {
if (ch == '.') {
seg.push_back(tmp);
if (seg.size() > 3 || tmp.size() == 0 || tmp.size() > 3 ||
(tmp.size() > 1 && tmp[0] == '0') || stoi(seg.back()) > 255) {
valid = false;
break;
}
tmp.clear();
continue;
}
if (ch < '0' || ch > '9') {
valid = false;
break;
}
tmp = ch;
}
if(tmp.length() > 0){
seg.push_back(tmp);
}
if(seg.size() < 4){
valid = false;
}
if (valid) {
int f = stoi(seg[0]);
if (f >= 128 && f <= 191) {
cout << "B_address" << endl;
} else if (f >= 192 && f <= 223) {
cout << "C_address" << endl;
} else if (f >= 1 && f < 126) {
cout << "A_address" << endl;
}else if(f == 126 && stoi(seg[1]) == 0 && stoi(seg[2]) == 0 && stoi(seg[3]) == 0){
cout << "A_address" << endl;
}
else {
cout << "other" << endl;
}
} else {
cout << "invalid" << endl;
}
}
// 64 位输出请用 printf("%lld")小美的游戏——贪心
其实就是取出最大的k个数相乘得到num，然后剩下k-1个数都为1，一个数为num，最后将这些数和优先级队列中的相加
代码语言：javascript复制#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#define ll long long
using namespace std;
int main() {
int n, k;
cin >> n >> k;
priority_queue<ll> queue;
int tmp;
for (int i = 0; i < n; i ) {
cin >> tmp;
queue.push(tmp);
}
ll ret = k;
ll num = 1;
while (k--) {
num *= queue.top();
num = num % 1000000007;
queue.pop();
}
num *= queue.top();
num = num % 1000000007;
queue.pop();
ret = num;
ret = ret % 1000000007;
while (!queue.empty()) {
ret = queue.top();
queue.pop();
ret = ret % 1000000007;
}
cout<<ret<<endl;
}
// 64 位输出请用 printf("%lld")
