4.1-4.5算法刷题笔记
- 1. 区间和
- 2. 区间合并
- 3. 用队列实现栈(queueMain = queueTemp;)
- 4. 最小栈
- 1. 单链表模板
- 5. 单链表
- 2. 双链表模板
- 6. 双链表
- 3. 模拟栈
- 7. 模拟栈(一个数组即可)
- 8. 表达式求值
- 4. 队列 tt = -1,hh = 0;
- 9. 模拟队列
- 5. 单调栈
- 10. 单调栈
- 6. 单调队列
- 11. 滑动窗口最大值
- 7. KMP
- 12. KMP字符串
- 8. Trie树
- 13. Trie字符串统计
- 14. 最大异或对
- 9. 并查集 find merge
- 15. 合并集合
- 16. 连通块中点的数量(每个集合有多少个元素)
- 17. 食物链
1. 区间和
原题链接
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
pair[] add = new pair[n+2];
pair[] query = new pair[m];
List<Integer> arrayMap = new ArrayList<>(n+m*2);
int[] sum = new int[n+m*2];
for (int i = 0; i < n; i++) {
add[i] = new pair();
add[i].l = scanner.nextInt();
add[i].r = scanner.nextInt();
arrayMap.add(add[i].l);
}
for (int i = 0; i < m; i++) {
query[i] = new pair();
query[i].l = scanner.nextInt();
query[i].r = scanner.nextInt();
arrayMap.add(query[i].l);
arrayMap.add(query[i].r);
}
arrayMap = new ArrayList<>(new HashSet<>(arrayMap));
Collections.sort(arrayMap);
for (int i = 0; i < n; i++) {
sum[arrayMapIndexOf(add[i].l,arrayMap)] += add[i].r;
}
for (int i = 0; i < arrayMap.size(); i++) {
if(i != 0) {
sum[i] += sum[i-1];
}
}
for (int i = 0; i < query.length; i++) {
int l = arrayMapIndexOf(query[i].l,arrayMap);
int r = arrayMapIndexOf(query[i].r,arrayMap);
if (l == 0) {
System.out.print(sum[r] + "\n");
} else {
System.out.print(sum[r]-sum[l-1] + "\n");
}
}
}
static class pair {
int l;
int r;
}
private static int arrayMapIndexOf(int k,List<Integer> arrayMap) {
int l = 0,r = arrayMap.size()-1;
while (l < r) {
int mid = (l+r+1) >> 1;
if (arrayMap.get(mid) <= k) {
l = mid;
} else {
r = mid - 1;
}
}
return r;
}
}
2. 区间合并
原题链接
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
pair[] range = new pair[n];
for (int i = 0; i < n; i++) {
range[i] = new pair();
range[i].l = scanner.nextInt();
range[i].r = scanner.nextInt();
}
Arrays.sort(range,new Comparator<pair>(){
@Override
public int compare(pair o1,pair o2) {
if (o1.l == o2.l) {
return o1.r - o2.r;
} else {
return o1.l - o2.l;
}
}
});
int st = (int)-2e9-1;
int ed = (int)-2e9-1;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (ed < range[i].l) {
st = range[i].l;
ed = range[i].r;
cnt++;
} else {
ed = Math.max(ed,range[i].r);
}
}
System.out.print(cnt);
}
static class pair {
int l;
int r;
}
}
3. 用队列实现栈(queueMain = queueTemp;)
原题链接
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
class MyStack {
public Queue<Integer> queueMain;
public Queue<Integer> queueTemp;
public MyStack() {
queueMain = new LinkedList<>();
queueTemp = new LinkedList<>();
}
public void push(int x) {
queueMain.add(x);
}
public int pop() {
int x = 0;
while (!queueMain.isEmpty()) {
x = queueMain.poll();
if (!queueMain.isEmpty()) {
queueTemp.add(x);
}
}
queueMain = queueTemp;
queueTemp = new LinkedList<>();
return x;
}
public int top() {
int x = 0;
while (!queueMain.isEmpty()) {
x = queueMain.poll();
queueTemp.add(x);
}
queueMain = queueTemp;
queueTemp = new LinkedList<>();
return x;
}
public boolean empty() {
return queueMain.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
4. 最小栈
原题链接
class MinStack {
Stack<Integer> A, B;
public MinStack() {
A = new Stack<>();
B = new Stack<>();
}
public void push(int x) {
A.add(x);
if(B.empty() || B.peek() >= x)
B.add(x);
}
public void pop() {
if(A.pop().equals(B.peek()))
B.pop();
}
public int top() {
return A.peek();
}
public int getMin() {
return B.peek();
}
}
1. 单链表模板
5. 单链表
acwing链接
力扣
class MyLinkedList {
int size;
ListNode head;
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
public int get(int index) {
if (index < 0 || index >= size) {
return -1;
}
ListNode cur = head;
for (int i = 0; i <= index; i++) {
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index > size) {
return;
}
index = Math.max(0, index);
size++;
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
ListNode toAdd = new ListNode(val);
toAdd.next = pred.next;
pred.next = toAdd;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) {
return;
}
size--;
ListNode pred = head;
for (int i = 0; i < index; i++) {
pred = pred.next;
}
pred.next = pred.next.next;
}
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
import java.util.*;
public class Main {
static int[] e = new int[100010];
static int[] ne = new int[100010];
static int idx,head;
public static void init() {
idx = 0;
head = -1;
}
public static void add_head(int x) {
e[idx] = x;
ne[idx] = head;
head = idx++;
}
public static void add(int k,int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx++;
}
public static void remove(int k) {
ne[k] = ne[ne[k]];
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
init();
while(m -- > 0){
String s = scan.next();
char op = s.charAt(0);
if(op == 'H'){
int x = scan.nextInt();
add_head(x);
}else if(op == 'D'){
int k = scan.nextInt();
if(k == 0) head = ne[head];
else remove(k-1);
}else {
int k = scan.nextInt();
int x = scan.nextInt();
add(k-1,x);
}
}
for(int i = head;i != -1;i = ne[i] ){
System.out.print(e[i] + " ");
}
}
}
2. 双链表模板
void init()
{
r[0] = 1;
l[1] = 0;
idx = 2;
}
6. 双链表
原题链接
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] e = new int[N];
static int[] r = new int[N];
static int[] l = new int[N];
static int idx;
//删除第k位插入的数
public static void remove(int k){
r[l[k]] = r[k];
l[r[k]] = l[k];
}
//这是在第k位数后面插入一个数x
public static void add_all(int k,int x){
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx++;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
r[0] = 1;l[1] = 0;idx = 2;
while(m -- > 0){
String s = scan.next();
char op = s.charAt(0);
if(op == 'L'){
int x = scan.nextInt();
add_all(0,x);
}else if(op == 'R'){
int x = scan.nextInt();
add_all(l[1],x);
}else if(op == 'D'){
int k = scan.nextInt();
remove(k + 1);
}else if(s.equals("IR")){
int k = scan.nextInt();
int x = scan.nextInt();
add_all(k + 1,x);
}else {
int k = scan.nextInt();
int x = scan.nextInt();
add_all(l[k+1],x);
}
}
for(int i = r[0];i != 1; i= r[i]){
System.out.print(e[i] + " ");
}
}
}
3. 模拟栈
7. 模拟栈(一个数组即可)
原题链接
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
int[] stl = new int[100010];
int tt = 0;
while(m -- > 0){
String s = scan.next();
if(s.equals("push")){
int x= scan.nextInt();
stl[++tt] = x;
}else if(s.equals("pop")){
tt--;
}else if(s.equals("empty")){
if(tt > 0){
System.out.println("NO");
}else System.out.println("YES");
}else{
System.out.println(stl[tt]);
}
}
}
}
8. 表达式求值
原题链接
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
//以字符串形式输入表达式
String s = scan.next();
//map来添加运算符号进去,定义优先级
Map<Character,Integer> map = new HashMap<>();
map.put('+',1);
map.put('-',1);
map.put('*',2);
map.put('/',2);
Stack<Character> op = new Stack<>();//存运算符号
Stack<Integer> num = new Stack<>();//存数字
for(int i = 0 ; i < s.length(); i ++ ){
char c = s.charAt(i);
//判断c字符是不是数字
if(Character.isDigit(c)){
int x = 0,j = i;
//数字可能会是多位数,
while(j < s.length() && Character.isDigit(s.charAt(j))){
x = x * 10 + s.charAt(j) - '0';
j++;
}
num.push(x);//将数字x存入数字栈栈顶
i = j - 1;//重新赋值i
}else if(c == '('){
op.push(c); // 将左括号存入字符栈栈顶
}else if(c == ')'){
//如果栈顶不等于左括号,一直计算下去;
while(op.peek() != '('){
eval(op,num);
}
op.pop(); // 将左括号弹出栈顶
}else { //如果是正常字符
while(!op.empty() && op.peek() != '(' && map.get(op.peek()) >= map.get(c)){
eval(op,num);
}
op.push(c);
}
}
while(!op.empty()) eval(op,num);
System.out.println(num.peek());
}
public static void eval(Stack<Character> op,Stack<Integer> num){
int b = num.pop();
int a = num.pop();
char c = op.pop();
if(c == '+'){
num.push(a+b);
}else if(c == '-'){
num.push(a-b);
}else if(c == '*'){
num.push(a*b);
}else {
num.push(a/b);
}
}
}
4. 队列 tt = -1,hh = 0;
9. 模拟队列
原题链接
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int m = scan.nextInt();
//队列是在tt队尾插入元素,队头hh弹出元素
int[] dl = new int[100010];
int hh = 0;
int tt = -1;
while(m -- > 0){
String s = scan.next();
if(s.equals("push")){
int x = scan.nextInt();
dl[++tt] = x;
}else if(s.equals("pop")){
hh++;
}else if(s.equals("empty")){
if(hh <= tt) System.out.println("NO");
else System.out.println("YES");
}else {
System.out.println(dl[hh]);
}
}
}
}
5. 单调栈
常见模型:找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
10. 单调栈
力扣链接
原题链接
原题链接
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] nums = new int[n+2];
int[] st = new int[n+2];
int tt = 0;
for (int i = 0; i < n; i++) nums[i] = scanner.nextInt();
for (int i = 0; i < n; i++) {
while (tt != 0 && st[tt-1] >= nums[i]) {
tt--;
}
if (tt == 0) {
System.out.print(-1 + " ");
} else {
System.out.print(st[tt-1] + " ");
}
st[tt++] = nums[i];
}
}
}
6. 单调队列
11. 滑动窗口最大值
力扣链接
原题链接
原题链接
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] q = new int[nums.length];
int hh = 0, tt = -1;
int[] ans = new int[nums.length-k+1];
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (hh <= tt && q[hh] + k <= i) {
hh++;
}
while (hh <= tt && x >= nums[q[tt]]) {
tt--;
}
q[++tt] = i;
if (i+1 >= k) {
ans[i-k+1] = nums[q[hh]];
}
}
return ans;
}
}
7. KMP
12. KMP字符串
力扣链接
acwing链接
class Solution {
public int strStr(String haystack, String needle) {
int[] ne = new int[haystack.length()+2];
ne[0] = -1;
for (int i = 1,j = -1; i < needle.length(); i++) {
while (j != -1 && needle.charAt(j+1) != needle.charAt(i)) {
j = ne[j];
}
if (needle.charAt(j+1) == needle.charAt(i)) {
j++;
}
ne[i] = j;
}
int ans = 0;
for (int i = 0,j = -1; i < haystack.length(); i++) {
while (j != -1 && haystack.charAt(i) != needle.charAt(j+1)) {
j = ne[j];
}
if (haystack.charAt(i) == needle.charAt(j+1)) {
j++;
}
if (j == needle.length()-1) {
return i-needle.length()+1;
}
}
return -1;
}
}
8. Trie树
13. Trie字符串统计
力扣链接
acwing链接
class Trie {
public int N,idx;
public int[][] song;
public int[] cnt;
public char[] str;
public Trie() {
N = 100010;idx = 0;
song = new int[N][26];
cnt = new int[N];
str = new char[N];
}
public void insert(String word) {
char[] str = word.toCharArray();
int p = 0; //下标0表示头结点,根节点
for(int i = 0 ; i < str.length; i ++ ){
// 将字符串每个字符都转化成数字;0-25
int u = str[i] - 'a';
//如果这个的儿子分支没有字符,说明这条分支还没有这个字符插入过
//就新建一个然后赋值为然后把【idx】下标赋值上去,作为每个分支的专属坐标
if(song[p][u] == 0) song[p][u] = ++idx;
//然后将p往下前进一层
p = song[p][u];
}
//最后停在那一层的那个数字就做标记,说明这是一个字符串的结束。
cnt[p]++;
}
public boolean search(String word) {
char[] str = word.toCharArray();
int p = 0;//从根节点开始,下标是0表示根节点,头结点
for(int i = 0 ; i < str.length; i ++){
int u = str[i] - 'a'; // 将字符串每个字符都转化成数字0-25
//如果这个点上面没有标记,就说明没有存入过这个字符,所以返回0
if(song[p][u] == 0) return false;
//如果这个点上面能寻找到这个字符,就让他往下一层继续寻找;
p = song[p][u];
}
//最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。
return cnt[p] != 0;
}
public boolean startsWith(String prefix) {
char[] str = prefix.toCharArray();
int p = 0;//从根节点开始,下标是0表示根节点,头结点
for(int i = 0 ; i < str.length; i ++){
int u = str[i] - 'a'; // 将字符串每个字符都转化成数字0-25
//如果这个点上面没有标记,就说明没有存入过这个字符,所以返回0
if(song[p][u] == 0) return false;
//如果这个点上面能寻找到这个字符,就让他往下一层继续寻找;
if (i == str.length-1) {
return song[p][u] != 0;
}
p = song[p][u];
}
//最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。
return false;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
import java.util.Scanner;
public class Main{
static int N = 100010,idx = 0;
static int[][] song = new int[N][26];
static int[] cnt = new int[N];
static char[] str = new char[N];
public static void insert(char[] str){
int p = 0; //下标0表示头结点,根节点
for(int i = 0 ; i < str.length; i ++ ){
// 将字符串每个字符都转化成数字;0-25
int u = str[i] - 'a';
//如果这个的儿子分支没有字符,说明这条分支还没有这个字符插入过
//就新建一个然后赋值为然后把【idx】下标赋值上去,作为每个分支的专属坐标
if(song[p][u] == 0) song[p][u] = ++idx;
//然后将p往下前进一层
p = song[p][u];
}
//最后停在那一层的那个数字就做标记,说明这是一个字符串的结束。
cnt[p]++;
}
public static int query(char[] str){
int p = 0;//从根节点开始,下标是0表示根节点,头结点
for(int i = 0 ; i < str.length; i ++){
int u = str[i] - 'a'; // 将字符串每个字符都转化成数字0-25
//如果这个点上面没有标记,就说明没有存入过这个字符,所以返回0
if(song[p][u] == 0) return 0;
//如果这个点上面能寻找到这个字符,就让他往下一层继续寻找;
p = song[p][u];
}
//最后查找完之后输出最后一个做标记的点为下标的cnt数组的值。
return cnt[p];
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
String sss = scan.nextLine();
while(n -- > 0){
String s = scan.nextLine();
String[] st = s.split(" ");
String s1 = st[0];
String s2 = st[1];
if(s1.equals("I")){
insert(s2.toCharArray());
}else{
System.out.println(query(s2.toCharArray()));
}
}
}
}
14. 最大异或对
力扣链接
acwing链接
class Solution {
public static int N,idx;
public static int[][] song;
public static void add(int x){
int p = 0;//从头结点开始
for(int i = 30 ; i >= 0 ; i -- ){ //因为每一个数的二进制是有31位组成,所以需要从大开始遍历
int u = x >> i & 1;//每一个数的二进制31个二进制每一位看0还是1
if(song[p][u] == 0) song[p][u] = ++idx;//判断这一层是空的,就创建,然后赋值下标
p = song[p][u];//然后让往下前进一层
}
}
//查询
public static int query(int x){
int p = 0,res = 0;//从根节点0开始。res进就算异或后的最大值
for(int i = 30; i>= 0 ; i --){
int u = x >> i & 1;
if(song[p][1-u] != 0){ //如果该节点的u是0,则判断一下在这一层有没有跟他相反的0-1,1-0,如果相反对应位置有数
res += (1 << i);//res就将该二进制位对应异或之后的最优解1每一位顺次加起来。因为是异或相反数就是1,这是最优解
p = song[p][1-u];//然后往最优解那边前进一层。
}else{//否则就不是最优解的0匹配1,1匹配0,所以就异或之后的值是0
//res += (0 << i);因为是0所以可以省略,
p = song[p][u];//然后让他往不优解那边前进一层。
}
}
return res;//最后返回异或之后的最大值res
}
public int findMaximumXOR(int[] nums) {
N = 3100010;idx = 0;
song = new int[N][2];
int n = nums.length;
for(int i = 0 ; i < n ; i ++ ){
add(nums[i]);
}
int res = 0;
for(int i = 0 ; i < n ; i ++ ){
//因为输入的是字符串所以需要转成整形。然后每一次比较res的值谁大,然后将最大值重新赋值给res
res = Math.max(res,query(nums[i]));
}
return res;
}
}
import java.io.*;
public class Main{
static int N = 3100010,idx = 0;
static int[][] song = new int[N][2];
//插入
public static void add(int x){
int p = 0;//从头结点开始
for(int i = 30 ; i >= 0 ; i -- ){ //因为每一个数的二进制是有31位组成,所以需要从大开始遍历
int u = x >> i & 1;//每一个数的二进制31个二进制每一位看0还是1
if(song[p][u] == 0) song[p][u] = ++idx;//判断这一层是空的,就创建,然后赋值下标
p = song[p][u];//然后让往下前进一层
}
}
//查询
public static int query(int x){
int p = 0,res = 0;//从根节点0开始。res进就算异或后的最大值
for(int i = 30; i>= 0 ; i --){
int u = x >> i & 1;
if(song[p][1-u] != 0){ //如果该节点的u是0,则判断一下在这一层有没有跟他相反的0-1,1-0,如果相反对应位置有数
res += (1 << i);//res就将该二进制位对应异或之后的最优解1每一位顺次加起来。因为是异或相反数就是1,这是最优解
p = song[p][1-u];//然后往最优解那边前进一层。
}else{//否则就不是最优解的0匹配1,1匹配0,所以就异或之后的值是0
//res += (0 << i);因为是0所以可以省略,
p = song[p][u];//然后让他往不优解那边前进一层。
}
}
return res;//最后返回异或之后的最大值res
}
public static void main(String[] args)throws IOException{
BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter wt = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(re.readLine());
String[] s = re.readLine().split(" ");
for(int i = 0 ; i < n ; i ++ ){
add(Integer.parseInt(s[i]));
}
int res = 0;
for(int i = 0 ; i < n ; i ++ ){
//因为输入的是字符串所以需要转成整形。然后每一次比较res的值谁大,然后将最大值重新赋值给res
res = Math.max(res,query(Integer.parseInt(s[i])));
}
wt.write(res +" ");//最后输出res,因为快输出输出的是字符串,所以需要在后面加上“ ”;
wt.close();
}
}
9. 并查集 find merge
15. 合并集合
原题链接
原题链接
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] p = new int[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); // 全部有n个数
int m = scan.nextInt(); // 读入m个操作
//将n个数每个数各自都在一个集合里面。都指向自己,说明现在有多少个集合
for(int i = 1 ; i <= n ; i ++) p[i] = i;
while(m -- > 0){
String s = scan.next();
int a = scan.nextInt();
int b = scan.nextInt();
//合并集合
if(s.equals("M")) p[find(a)] = find(b); //将a集合的根节点即祖先指向b集合的祖先
else{ //是否同个集合
if(find(a) == find(b))System.out.println("Yes"); //如果两个集合的祖先相同说明两个集合在同个集合中。
else System.out.println("No"); //否则相反
}
}
}
//并查集的核心操作,寻找根节点祖先 + 路径压缩
public static int find(int x){
// 如果这个集合的父节点指向的不是自己,说明不是根节点,递归寻找,
//最后找到根节点之后,把路径上的所有集合都指向根节点、
if(p[x] != x) p[x] = find(p[x]);
return p[x]; // 最后返回根节点
}
}
16. 连通块中点的数量(每个集合有多少个元素)
原题链接
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] p = new int[N];
static int[] size = new int[N];//size用来存每个集合中数的个数
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
for(int i = 1 ; i <= n ;i ++){
p[i] = i;
size[i] = 1;// 一开始每个数是一个集合,各自都是个数为1;
}
while(m -- > 0){
String s = scan.next();
if(s.equals("C")){
int a = scan.nextInt();
int b = scan.nextInt();
if(find(a) == find(b)) continue; // 这里需要特判一下,如果两个数是同个集合中的数,就结束;
else{
size[find(b)] += size[find(a)]; // 只有两个数的根节点,也就是祖先的size值才是有用的,
//两个集合中的赋值给另一个祖先的,即赋值给另一个祖先的这个祖先就是合并之后的两个集合的祖先
// b的size[] + =a的size[] 因为b是合并之后的新祖先,所以要让b加上被合并的a
p[find(a)] = find(b); //合并操作,p[a]的祖先指向b,说明b是合并之后的祖先
}
}else if(s.equals("Q1")){
int a = scan.nextInt();
int b = scan.nextInt();
if(find(a) == find(b))System.out.println("Yes");
else System.out.println("No");
}else{
int a = scan.nextInt();
//只有根节点的size才是有用的,则通过find(a)找到他的根节点然后输出根节点的size;
System.out.println(size[find(a)]);
}
}
}
public static int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
}
17. 食物链
原题链接
法一: x,x+n,x+n+n merge(f[x+n],f[x])
思路:
- 因为有三种物种,A吃B,B吃C,C吃A
- 如果我们用一个数组存储,那么比如1吃2,那么我们让2的角标处的值标记成1,如果3吃2,那怎么标记?一个数组指定标记不过来。
- 那么我们想用三个数组存储,其实也存储不过来,因为角标就那么几个,
- 最好的方法就是,用x,x+n,x+n+n来表示
比如1吃2,那么就可能有三种情况,
A类中的1吃B类的2 : fa[1] = fa[2+n+n]
B类中的1吃C类的2 : fa[1+n] = fa[2]
C类中的1中A类的2 : fa[1+n+n] = fa[2+n];
这样的话,就会有3*n个角标,就可以充分表达
A中的1吃B中的2(B中的2用2+n表示)
这样的话就不会出现数字冲突
A吃B
则让f[A] = B
/*
*/
#include <bits/stdc++.h>
using namespace std;
int fa[200000];
int n,m,k,x,y,ans;
int get(int x)
{
if(x==fa[x])
return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
fa[get(x)]=get(y);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=3*n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&k,&x,&y);
if(x>n || y>n)
ans++;
else if(k==1)
{
if(get(x)==get(y+n) || get(x)==get(y+n+n)) //如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误.
ans++;
else
{
merge(x,y);
merge(x+n,y+n);
merge(x+n+n,y+n+n);
}
}
else
{
if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x
ans++;//都是假话
else
{
merge(x,y+n+n);//y的捕食域加入x
merge(x+n,y);//x的天敌域加入y
merge(x+n+n,y+n);//x的捕食域是y的同类域.
}
}
}
cout<<ans<<endl;
}
法二:将有关系的都存储在一个部落,用到根节点的距离表示关系
二刷总结
- X吃Y 让x的祖宗等于y的祖宗 或者 y的祖宗等于x的祖宗都可以
- find查找函数中,具有压缩路径的作用,所以在写的时候,先找到此根节点,然后依次压缩,如下代码
find中 d[x] += d[p[x]];
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
不可以如下代码
int find(int x)
{
if (p[x] != x)
{
d[x] += d[p[x]];
return p[x] = find(p[x]);
}
return p[x];
}
- 在查询合并过程中,比如查询x的父节点,应该用一个变量记录下来,不能多次find,不然找不到x的原来父节点了
- 初始化 p[i] = i; d[i] = 0;
- 合并的时候,画图即可明白彼此的距离
具体过程如下:
#include <iostream>
using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];
int find(int x)
{
if (p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) p[i] = i;
int res = 0;
while (m -- )
{
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if (x > n || y > n) res ++ ;
else
{
int px = find(x), py = find(y);
if (t == 1)
{
if (px == py && (d[x] - d[y]) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] - d[x];
}
}
else
{
if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
else if (px != py)
{
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n", res);
return 0;
}