数组元素重排问题求助：需满足每个元素首位数字与前一元素末位数字匹配

Hey there! No worries at all—this is a great problem to start with when diving into algorithms, and I’ll break it down in simple terms so you can follow along.

The Problem Breakdown #

You need to rearrange an array of numbers such that each number's first digit matches the previous number's last digit. If possible, output 1; if not, output 0.

The Key Insight: Model It as a Graph Problem #

This problem is actually a classic Euler Path problem in graph theory. Here's how to map it:

• Treat each single digit (0-9) as a node in a graph.
• Treat each number in the array as a directed edge from its first digit (start node) to its last digit (end node).

For example:

• The number 67 becomes an edge from node 6 to node 7.
• The number 96 becomes an edge from node 9 to node 6.

Now, the problem reduces to: does there exist a path that uses every edge exactly once? That's exactly what an Euler Path is!

Euler Path Conditions #

An Euler Path exists if one of the following is true:

1. All nodes have equal in-degree and out-degree: This means we can start at any node and form a cycle (Euler Circuit) that uses all edges.
2. Exactly one node has an out-degree 1 greater than its in-degree (start node), and exactly one node has an in-degree 1 greater than its out-degree (end node): All other nodes have equal in-degree and out-degree.

If neither condition is met, no valid rearrangement exists.

Step-by-Step Implementation #

Let's turn this logic into code (using Python, since it's beginner-friendly):

1. Track In-Degree and Out-Degree

First, we'll count how many times each digit is a start (out-degree) or end (in-degree) of an edge.

2. Validate the Euler Path Conditions

We check if the in-degree/out-degree counts match one of the valid scenarios.

Here's the code:

def can_rearrange(arr):
    # Initialize in-degree and out-degree arrays for digits 0-9
    in_degree = [0] * 10
    out_degree = [0] * 10
    
    for num in arr:
        # Convert number to string to easily grab first and last digits
        num_str = str(num)
        start_digit = int(num_str[0])
        end_digit = int(num_str[-1])
        
        out_degree[start_digit] += 1
        in_degree[end_digit] += 1
    
    count_positive_diff = 0  # Nodes where out-degree - in-degree = 1
    count_negative_diff = 0  # Nodes where in-degree - out-degree = 1
    is_valid = True
    
    for digit in range(10):
        degree_diff = out_degree[digit] - in_degree[digit]
        
        if degree_diff == 1:
            count_positive_diff += 1
        elif degree_diff == -1:
            count_negative_diff += 1
        elif degree_diff != 0:
            # Any difference other than -1, 0, or 1 makes it impossible
            is_valid = False
            break
    
    # Check if we meet one of the Euler Path conditions
    if not is_valid:
        return 0
    return 1 if (count_positive_diff == 0 and count_negative_diff == 0) or (count_positive_diff == 1 and count_negative_diff == 1) else 0

# Test your examples
print(can_rearrange([67, 96]))  # Output: 1 (valid rearrangement exists)
print(can_rearrange([12, 34]))  # Output: 0 (no valid rearrangement)

Let's Walk Through Your Examples #

1. Example 1: [67, 96]

   • 67 → start=6, end=7 → out_degree[6] +=1, in_degree[7] +=1
   • 96 → start=9, end=6 → out_degree[9] +=1, in_degree[6] +=1
   • Degree differences: 6 (0), 7 (-1), 9 (1), others (0)
   • This matches condition 2 (one positive, one negative difference) → output 1

2. Example 2: [12, 34]

   • 12 → start=1, end=2 → out_degree[1] +=1, in_degree[2] +=1
   • 34 → start=3, end=4 → out_degree[3] +=1, in_degree[4] +=1
   • Degree differences: 1 (1), 2 (-1), 3 (1),4 (-1), others (0)
   • We have two positive and two negative differences → doesn't meet any condition → output 0

Tips for Beginners #

• If you're new to graph terms like in-degree/out-degree, think of them as:
  • Out-degree: How many times a digit is the start of a number.
  • In-degree: How many times a digit is the end of a number.
• Start by manually calculating these values for small arrays to get comfortable with the logic.

内容的提问来源于stack exchange，提问作者Karan Kundra