文章来源:https://www.uudwc.com/A/R62x8/
1167 Cartesian Tree
题意:要的大概就是:中序 -> 数组序(层序遍历),中序不能唯一确定,但本题有前置添加:该二叉树是小顶堆
思考:那么最小的数值,一定是顶根,再分别找最小,第二根。。。但是这里会发现一个问题,就是中序我们按深度遍历如何能知道当前层的数目呢,可以用“填充法”,不管有没有子节点,只有有这一层就当满二叉树填了,最后输出判断即可(但是这里的N最大30,2的29次方去填一个数组太大了,所以这里用map去存,不过要按键顺序输出就得用TreeMap)
——JAVA实现
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
Map<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
dfs(map, arr, 0, n - 1, 0);
int i = 1;
for (Integer value : map.values()) {
System.out.print(value);
if (i++ < n) System.out.printf(" ");
}
}
private static void dfs(Map<Integer, Integer> map, int[] arr, int l, int r, int cen) {
if (l > r) return;
int curIndex = checkMin(arr, l, r);
map.put(cen, arr[curIndex]);
dfs(map, arr, l, curIndex - 1, cen * 2 + 1);
dfs(map, arr, curIndex + 1, r, cen * 2 + 2);
}
// 获取[left, right]范围内最小索引
private static int checkMin(int[] arr, int left, int right) {
int minV = arr[left];
int minIndex = left;
for (int i = left + 1; i <= right; i++) {
if (minV > arr[i]) {
minV = arr[i];
minIndex = i;
}
}
return minIndex;
}
}
——C++实现
#include<iostream>
#include<map> // C++中std::map是一关联容器,会根据键顺序自动排序(类似Java中的TreeMap)
using namespace std;
const int N = 31;
int arr[N];
map<int, int> treeMap;
int checkMin(int l, int r) {
int minValue = arr[l];
int minIndex = l;
for (int i = l + 1; i <= r; i++) {
if (minValue > arr[i]) {
minValue = arr[i];
minIndex = i;
}
}
return minIndex;
}
void dfs(int l, int r, int cen) {
if (l > r) return;
int curIndex = checkMin(l, r);
treeMap[cen] = arr[curIndex];
dfs(l, curIndex - 1, cen * 2 + 1);
dfs(curIndex + 1, r, cen * 2 + 2);
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> arr[i];
dfs(0, n - 1, 0);
int k = 1;
for (auto i : treeMap) {
printf("%d", i.second);
if (k++ < n) printf(" ");
}
return 0;
}
遍历Map
Java中,可以用以下方法遍历 HashMap 的键或值:
- 遍历 键:使用 keySet() 方法获取所有的键。
- 遍历 值:使用 values() 方法获取所有的值。
- 遍历 键值对:使用 entrySet() 方法获取所有的键值对(getKey() getValue() 获取键值,遍历类型为 Map.Entry<key_type, value_type>)
for (Integer key : hashMap.keySet()) {
System.out.println(key);
}
// 遍历值
System.out.println("遍历值:");
for (String value : hashMap.values()) {
System.out.println(value);
}
// 遍历键值对
System.out.println("遍历键值对:");
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
// 假设K-V为Integer-String
C++中,可以用以下方法遍历 unordered_map 的键或值:
迭代器遍历
#include<iostream>
#include<unordered_map>
using namespace std;
int main() {
unordered_map<string, int> hash = {{"xi", 1}, {"ll", 2}};
for (unordered_map<string, int>:iterator i = hash.begin; i != hash.end(); i++) {
cout << "Key: " << i->first << ", Value: " << i->second << endl;
}
}
for循环遍历
#include<iostream>
#include<unordered_map>
using namespace std;
int main() {
unordered_map<string, int> hash = {{"xi", 1}, {"ll", 2}};
for (auto i : hash) {
cout << "Key: " << i.first << ", Value: " << i.second << endl;
}
}
1166 Summit
题意:
如果在这个休息区每个人都互相是直接朋友,并且没有朋友漏掉(即没有其他人是这个休息区每个人的直接朋友),就输出Area X is OK.
如果在这个休息区每个人都是每个人的直接朋友,但在不破坏理想安排的情况下,可能还会邀请一些其他领导人,就输出Area X may invite more people, such as H. H是可以被邀请的领导人的最小编号。
如果该休息区的安排不理想,则输出Area X needs help. (有不是有直接关系的)
思路:
邻接矩阵接受,代表有关系,然后遍历关系,依次和set比较,比较没有的直接输出need
有了再遍历N比较,比较有的,invite,全部没有 OK
——C++实现
#include<iostream>
#include<set>
using namespace std;
const int N = 201;
bool near[N][N];
int main() {
int n, m, k;
cin >> n >> m;
while (m-- > 0) {
int k1, k2;
cin >> k1 >> k2;
near[k1][k2] = near[k2][k1] = true;
}
cin >> k;
for (int i = 1; i <= k; i++) {
int l;
cin >> l;
set<int> set_;
bool bo = true;
while (l-- > 0) {
int cur;
cin >> cur;
if (bo) {
for (auto s : set_) {
if (!near[cur][s]) {
bo = false;
printf("Area %d needs help.\n", i);
break;
}
}
set_.insert(cur); // C++是insert,Java是add
}
}
if (bo) {
for (int j = 1; j <= n; j++) {
if (set_.count(j) == 0) { // C++用数量判断是否存在,Java直接用API contains
bool bo2 = true;
for (auto s : set_) {
if (!near[s][j]) {
bo2 = false;
break;
}
}
if (bo2) {
bo = false;
printf("Area %d may invite more people, such as %d.\n", i, j);
break;
}
}
}
if (bo) {
printf("Area %d is OK.\n", i);
}
}
}
return 0;
}
——JAVA实现(只能跑过22/25,哎)
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
boolean[][] near = new boolean[n + 1][n + 1];
for (int i = 0; i < m; i++) {
int k1 = sc.nextInt();
int k2 = sc.nextInt();
near[k1][k2] = near[k2][k1] = true;
}
int k = sc.nextInt();
for (int i = 1; i <= k; i++) {
int k0 = sc.nextInt();
Set<Integer> set = new HashSet<>();
boolean bo = true;
while(k0-- > 0) {
int cur = sc.nextInt();
if (bo) {
for (Integer s : set) {
if (!near[s][cur]) {
bo = false;
System.out.printf("Area %d needs help.\n", i);
break;
}
}
set.add(cur);
}
}
// 都满足关系的情况,看是否还有直接的
if (bo) { // 复用bo
for (int l = 1; l <= n; l++) {
if (!set.contains(l)) {
boolean bo2 = true;
for (Integer s : set) {
if (!near[s][l]) {
bo2 = false;
break;
}
}
if (bo2) {
System.out.printf("Area %d may invite more people, such as %d.\n", i, l);
bo = false;
break;
}
}
}
if (bo) {
System.out.printf("Area %d is OK.\n", i);
}
}
}
}
}
1165 Block Reversing
(1)结构体数组 获取值,索引为地址
(2)构建链表
(3)按k数存入二维数组链表块
(4)反向读取二维数组,然后顺序取,不需对next地址复制
(5)错位读取,next地址直接读下一位的地址即可,到n-2位即可,n-1位手搓-1
#include <iostream>
#include <vector>
using namespace std;
struct node {
int data, next; // 数字位,下一位地址
}A[100001]; // 结构体数组(索引为地址)
vector<int> L, ans, E[100001]; // 链表,结果
int s, n, k, a, t, cnt, c;
int main() {
cin >> s >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a;
cin >> A[a].data >> A[a].next;
}
// vector构建链表
t = s;
while (t != -1) {
L.push_back(t);
t = A[t].next;
}
// 按3个入二维数组
n = L.size();
for (int i = 0; i < n; i++) {
E[c].push_back(L[i]); // 依次存入1 2 3 / 4 5 6 / 7 8
cnt++;
if (cnt == k && i != n - 1) { // 第二个判断的原因是,后续要用这个c,必须保持它可用
cnt = 0;
c++;
}
}
// 显示
for (int i = c; i >= 0; i--) // 反向读取顺序拿, 7 8 / 4 5 6 / 1 2 3 (当前位置是没问题,那么下一位怎么办)
for (auto it : E[i])
ans.push_back(it);
for (int i = 1; i < n; i++)
printf("%05d %d %05d\n", ans[i - 1], A[ans[i - 1]].data, ans[i]); // 直接从下一位的地址拿,不需更新值
printf("%05d %d -1", ans.back(), A[ans.back()].data);
return 0;
}
Java实现(超时问题,只能通过22/25)
import java.util.*;
class Node{
int data;
int next;
Node(int data,int next) {
this.data = data;
this.next = next;
}
}
class Main{
public static void main(String args[]) {
Node[] A = new Node[100001];
ArrayList<Integer> L = new ArrayList<>(), res = new ArrayList<>();
ArrayList<ArrayList<Integer>> E = new ArrayList<>();
Scanner sc = new Scanner(System.in);
int first = sc.nextInt();
int n = sc.nextInt();
int k = sc.nextInt();
for (int i = 0; i < n; i++) A[sc.nextInt()] = new Node(sc.nextInt(), sc.nextInt());
// 构建链表
int t = first;
while (t != -1) { // 这里不能用n,因为可能有一些断开的节点
L.add(t);
t = A[t].next;
}
// 放入二维数组链表块
n = L.size(); // 这里不能用n,因为可能有一些断开的节点
int c = 0, cnt = 0;
E.add(new ArrayList<Integer>());
for (int i = 0; i < n; i++) {
E.get(c).add(L.get(i)); // 1 2 3 \ 4 5 6 \ 7 8
cnt++;
if (cnt == k && i != n - 1) {
E.add(new ArrayList<Integer>());
cnt = 0;
c++;
}
}
// 反序读顺序取 7 8 / 4 5 6 / 1 2 3
for (int i = c; i >= 0; i--) {
for (Integer num : E.get(i)) {
res.add(num);
}
}
// 读取
for (int i = 0; i < n - 1; i++) {
System.out.printf("%05d %d %05d\n", res.get(i), A[res.get(i)].data, res.get(i + 1));
}
System.out.printf("%05d %d -1\n", res.get(n - 1), A[res.get(n - 1)].data);
}
}
/*
(1)结构体数组 获取值,索引为地址
(2)构建链表
(3)按k数存入二维数组链表块
(4)反向读取二维数组,然后顺序取,不需对next地址复制
(5)错位读取,next地址直接读下一位的地址即可,到n-2位即可,n-1位手搓-1
*/
复杂的思路(连续反转(整体反转+部分反转)用例 21/25)
import java.util.*;
class ListNode {
int val;
String loc;
String nextLoc;
ListNode next;
ListNode() {}
ListNode(String loc) {this.loc = loc;}
ListNode(int val, String loc, String nextLoc) {
this.val = val;
this.loc = loc; // 从链表开始遍历,就需要这个去找key
this.nextLoc = nextLoc;
}
}
class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
String headPosi = sc.next();
int n = sc.nextInt();
int k = sc.nextInt();
HashMap<String, ListNode> map = new HashMap<>(); // map
for (int i = 0; i < n; i++) {
String cur = sc.next();
int index = sc.nextInt();
String next = sc.next();
map.put(cur, new ListNode(index, cur, next));
}
// 构建链表
ListNode befo = new ListNode("-1"); // 头指针
ListNode head = map.get(headPosi); // 头节点
befo.next = head;
while (!head.nextLoc.equals("-1")) {
ListNode next = map.get(head.nextLoc);
head.next = next;
head = next;
}
// 链表反转
// 整体反转
befo.next = reverse(befo.next);
// 部分反转
ListNode front = befo;
ListNode tail = befo.next;
int k1 = n % k;
int i = 0;
while (tail.val != 0) {
if (k1 == 0) k1 = k;
ListNode start = front.next; // 8 6 3
while (--k1 > 0) tail = tail.next; // 7 4 1
// 截断尾吧,记录尾巴后
ListNode tailTemp = tail.next; // 6 3 0
tail.next = null;
// 接上前后
ListNode newHead = reverse(front.next);
tail = tailTemp;
front.next = newHead;
front.nextLoc = newHead.loc;
start.next = tail; // 6 3 0
start.nextLoc = tail.loc;
// 接下一次循环
front = start; // 8 6 3
}
// 显示(最后一次使用头指针)
while(befo.next != null) {
befo = befo.next;
ListNode ln = map.get(befo.loc);
System.out.printf("%s %d %s\n", ln.loc, ln.val, ln.nextLoc);
}
}
private static ListNode reverse(ListNode head) {
ListNode front = new ListNode("-1");
while (head != null) {
ListNode temp = head.next;
head.next = front;
head.nextLoc = front.loc;
front = head;
head = temp;
}
return front;
}
}
/*
数组存序号摆放顺序(用地址,便于map构建链表时,寻找下一位)
类构建链表(序号-当前位,下一位)
链表反转(先整体反转再部分反转) -> 更新map
map存k-v为 序号-链表节点
按数组序获取map value依次显示
*/
1164 Good in C
做法:数组哈希表
数组做hash表 26个字母
值为二维数组,显示
C++
#include <iostream>
using namespace std;
char a[26][7][5], out[7][100];
string s;
int main() {
for (int i = 0; i < 7; i++)
for (int j = 0; j < 100; j++)
out[i][j] = ' ';
for (int i = 0; i < 26; i++)
for (int j = 0; j < 7; j++)
for (int k = 0; k < 5; k++)
cin >> a[i][j][k];
getchar();
getline(cin, s);
// 开始遍历
for (int i = 0, j, flag = 0; i < s.size(); i++) {
j = i;
while (j < s.size() && s[j] >= 'A' && s[j] <= 'Z') j++; // 将j移动到一个单词末尾,若j位非大写字母,则不动
if (i == j) continue; // 跳过非大写字母
// 遍历单词
for (int k = i; k < j; k++)
for (int l = 0; l < 7; l++)
for (int m = 0; m < 5; m++)
out[l][m + (k - i) * 6] = a[s[k] - 'A'][l][m]; // 单词序存入out中
if (flag) cout << '\n';
// 按行输出
for (int k = 0; k < 7; k++) {
flag = 1;
for (int l = 0; l < 6 * (j - i) - 1; l++) cout << out[k][l];
cout << '\n';
}
i = j;
}
return 0;
}
JAVA做法超时(17/20)
import java.util.*;
class Main{
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
ArrayList<ArrayList<String>> hash = new ArrayList<>(26);
for (int i = 0; i < 26; i++) {
ArrayList<String> arr = new ArrayList<>(7);
for (int j = 0; j < 7; j++) {
arr.add(sc.next());
}
hash.add(arr);
}
// 格式获取(按单词分隔)
String showStr = "";
while (sc.hasNextLine()) {
String line = sc.nextLine();
showStr += line;
}
ArrayList<String> shows = new ArrayList<>();
int l = 0;
for (int i = 0; i < showStr.length(); i++) {
char c = showStr.charAt(i);
if (c < 'A' || c > 'Z') {
if (i > l) shows.add(showStr.substring(l, i));
l = i + 1;
}
}
if (l < showStr.length()) shows.add(showStr.substring(l, showStr.length()));
// 显示
int kk = 1;
for (String s : shows) {
for (int i = 0; i < 7; i++) { // 按行
int k = 1;
for (int j = 0; j < s.length(); j++) { // 再按字母
System.out.printf("%s", hash.get(s.charAt(j) - 'A').get(i));
if (k++ < s.length()) System.out.print(" "); // 控制行尾空格
}
System.out.println();
}
if (kk++ < shows.size()) System.out.println();
}
}
}
1163 Dijkstra Sequence
偏暴力,一个一个序列最短路判断。// 首次进入distance是大值,因此会直跑到这里,按now值即源点更新,那么首次的distance就是直接距源点最近的值,那么下个递归必须就是这个值,再从后续第二最近第三最近扩散
C++
#include <iostream>
#include <vector>
using namespace std;
int V, E, K, Start, End, a, b, d;
int Edge[1002][1002], Distance[1002], flag, book[1002]; // 邻接矩阵
void deal(int x, int index, vector<int> Path) {
for(int k = 1; k <= V; k++) { // 遍历所有点
int Min = 9999999, now = Path[index];
// 找到距离最小的未确定最短距离的顶点
for(int i = 1; i <= V; i++) {
if(Distance[i] != 9999999 && !book[i] && Distance[i] <= Min) {
if(Distance[i] < Min) {
if(i == now) flag = 1;
else flag = 0; // 不满足迪杰斯特拉斯序列了
} else if(Distance[i] == Min) {
if(i == now) flag = 1;
}
Min = Distance[i];
}
}
if(!flag) return;
++index;
if(index > V) return;
// 首次进入distance是大值,因此会直跑到这里,按now值即源点更新,那么首次的distance就是直接距源点最近的值,那么下个递归必须就是这个值,再从后续第二最近第三最近扩散
book[now] = 1; // 将当前顶点标记为已确定最短距离
for(int i = 1; i <= V; i++)
// 顶点i的最短距离还未确定 & 可更新最小 & 顶点now和顶点i之间有边
if(!book[i] && Distance[i] > Distance[now] + Edge[now][i] && Edge[now][i] != 0)
Distance[i] = Distance[now] + Edge[now][i];
}
}
int main() {
cin >> V >> E;
for(int i = 0; i < E; i++) {
cin >> a >> b >> d;
Edge[a][b] = Edge[b][a] = d;
}
cin >> K;
for(int i = 0; i < K; i++) {
vector<int> Path(V); // 当前需要判断的序列
flag = 1;
fill(book, book + 1002, 0); // book标记确定好最短距离的点。
fill(Distance, Distance + 1002, 9999999); // 最短路径起点到各个点的最短距离,
for(int j = 0; j < V; j++) cin >> Path[j];
Start = Path[0], End = Path[V - 1];
Distance[Start] = 0;
deal(Start, 0, Path); // 核心处理逻辑
if(flag) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
1162 Postfix Expression
#include<iostream>
using namespace std;
int n, root = 1, lc[32], rc[32], mark[32]; // lc中存储左孩子下标,rc中存储右孩子下标,mark用来标记一个结点是否是别人的结点
string Data[32]; // 结点信息
void deal(int x) {
cout<< '(';
if (lc[x] * rc[x] > 1) { // 不含空节点,则直接往下遍历
deal(lc[x]);
deal(rc[x]);
}
cout << Data[x];
if (lc[x] * rc[x] < 0) deal(rc[x]); // 有空节点,那么左一定为空,那么往下遍历右,(语法树不会存在只有左子树没有右子树的情况)
cout << ')';
}
int main() {
// 输入
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> Data[i] >> lc[i] >> rc[i];
mark[lc[i]] = mark[rc[i]] = 1;
}
while(mark[root]) root++; // 为什么如此操作,因为不能以根节点为 r-child或l-child,所以必定能遍历到不是的那一个,即为根
deal(root);
return 0;
}
文章来源地址https://www.uudwc.com/A/R62x8/