Huawei machine test: number of continuous licensing

【 Programming topics |200 branch 】 Number of consecutive cards 【2022 Q1,Q2 Examination questions 】

Title Description

• Give a deck of cards in your hand , Figures from the 0-9, Yes r( Red ),,g( green ）,b( Blue ),y( yellow ) Four colors , The rule of playing cards is that each card played must be followed by the same number or color , Otherwise, you cannot select .
• How should players choose to maximize the number of draws , And output the maximum number .

Input description

• first line The number of cards n (1<=n<=9)
• The second line The color of the card （r,g,b,y Four colors indicate )

Output description

• Output the maximum number of cards

Example

Input

1 4 3 4 5
r y b b r

Output

3

explain

If you hit （1, r）-> (5, r), Then you can print two .

If you hit （4,y) -> (4, b) -> (3, b), Then you can make three .

Thought analysis

This problem can also be considered BFS, The same number or the same color are stored in a continuous relationship .

Enter the queue from the first , Count the maximum number of times corresponding to each , Finally, update the maximum value .

You can use two dimensions when saving continuous relationships list

Indexed by serial number , Judge whether the elements are the same or the colors are the same, and add the corresponding list.

And then there's the regular BFS Join the team for processing .

Reference code

import java.util.*;
import java.util.Scanner;

public class lianXuChupaiNum {
    
    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
        String[] str1 = in.nextLine().split(" ");
        String[] str2 = in.nextLine().split(" ");
        String[][] arr = new String[str1.length][2];
        for (int i = 0; i < str1.length; i++) {
    
            arr[i][0] = str1[i];
            arr[i][1] = str2[i];
        }
        //  Store equality 
        List<List<Integer>> list = new ArrayList<>(arr.length);
        for (int i = 0; i < arr.length; i++) {
      //  initialization 
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < arr.length; i++) {
    
            for (int j = 0; j < arr.length; j++) {
    
                if (i != j) {
    
                    if (arr[i][0].equals(arr[j][0]) || arr[i][1].equals(arr[j][1])) {
    
                        list.get(i).add(j);
                    }
                }
            }
        }
        // BFS
        Queue<Integer> queue = new ArrayDeque<>();
        Queue<Integer> visited = new ArrayDeque<>();  //  Used to judge whether you have visited 
        int[] res = new int[arr.length];
        Arrays.fill(res, 1);
        queue.add(0);
        visited.add(0);
        while (!queue.isEmpty()) {
    
            int poll = queue.poll();
            for (int node : list.get(poll)) {
    
                if (!visited.contains(node)) {
    
                    visited.add(node);
                    res[node] = res[poll] + 1;
                    queue.add(node);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
    
            ans = Math.max(ans, res[i]);
        }
        System.out.println(ans);
    }
}

Welcome to comment and leave your own more concise method .