目录

题目

思路

Code

题目

在一个创意设计工坊中，设计师 希望用不同的大写字母瓷砖拼出独特图案，给定一个只包含大写英文字母的图案字符串 L，要求你给出对 L重新排列的所有不相同的图案，但是有以下约束条件：

相同的字母不能相邻

输入描述
输入一个长度不超过 12 的字符串 L，确保都是大写的

输出描述
输出满足约束条件的L重新排列的所有不相同的排列数

用例1
输入
"AAB"
输出
1
说明
只有ABA满足条件

用例2
输入
""
输出
1
说明
空字符串也是符合没有相邻的要求
 

思路

长度上限只有 12， 无所谓速度快慢了，“字符计数 + 回溯”。

核心想法：

• 先统计每个字母还剩多少个可用
• 每次递归放下一个字符时：
  • 只能放“剩余数量大于 0”的字符
  • 不能和上一个放入的字符相同
• 当已经放满 n 个字符时，说明找到一种合法排列，答案加一

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.TreeMap;

public class Main {
    static Map<Character, Integer> counter = new TreeMap<>();
    static char[] letters;
    static int totalLen;
    static long answer = 0;

    static void dfs(char lastChar, int usedLen) {
        // 已经放满全部字符，说明找到一种合法排列。
        if (usedLen == totalLen) {
            answer++;
            return;
        }

        // 枚举每一种还剩余的字符。
        for (char ch : letters) {
            int remain = counter.get(ch);

            // 当前字符已经用完，跳过。
            if (remain == 0) {
                continue;
            }

            // 不能与上一个放入的字符相同。
            if (ch == lastChar) {
                continue;
            }

            // 选择当前字符，递归处理下一位。
            counter.put(ch, remain - 1);
            dfs(ch, usedLen + 1);

            // 回溯，恢复现场。
            counter.put(ch, remain);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;

        // 读取全部输入，兼容末尾换行。
        while ((line = br.readLine()) != null) {
            sb.append(line);
        }

        String s = sb.toString().trim();

        // 输入固定为带双引号的字符串，这里取出双引号内部内容。
        // 例如 "AAB" -> AAB，"" -> 空字符串。
        if (s.length() >= 2 && s.charAt(0) == '"' && s.charAt(s.length() - 1) == '"') {
            s = s.substring(1, s.length() - 1);
        }

        // 空字符串只有一种合法排列。
        if (s.isEmpty()) {
            System.out.print(1);
            return;
        }

        totalLen = s.length();

        // 统计每个字符的剩余数量。
        for (char ch : s.toCharArray()) {
            counter.put(ch, counter.getOrDefault(ch, 0) + 1);
        }

        // TreeMap 天然有序，这里取出有序字符集合。
        letters = new char[counter.size()];
        int idx = 0;
        for (char ch : counter.keySet()) {
            letters[idx++] = ch;
        }

        dfs('\0', 0);
        System.out.print(answer);
    }
}

Go

package main

import (
	"fmt"
	"io"
	"os"
	"sort"
	"strings"
)

var (
	counter  map[byte]int
	letters  []byte
	totalLen int
	answer   int
)

func dfs(lastChar byte, usedLen int) {
	// 已经放满全部字符，说明找到一种合法排列。
	if usedLen == totalLen {
		answer++
		return
	}

	// 枚举还剩余的字符。
	for _, ch := range letters {
		if counter[ch] == 0 {
			continue
		}

		// 相同字符不能相邻。
		if ch == lastChar {
			continue
		}

		// 选择当前字符。
		counter[ch]--
		dfs(ch, usedLen+1)

		// 回溯恢复。
		counter[ch]++
	}
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	s := strings.TrimSpace(string(data))

	// 输入固定为带双引号的字符串，这里取出双引号内部内容。
	if len(s) >= 2 && s[0] == '"' && s[len(s)-1] == '"' {
		s = s[1 : len(s)-1]
	}

	// 空字符串只有一种排列。
	if s == "" {
		fmt.Print(1)
		return
	}

	counter = make(map[byte]int)
	for i := 0; i < len(s); i++ {
		counter[s[i]]++
	}

	// 保存所有不同字符，并排序保证遍历稳定。
	letters = make([]byte, 0, len(counter))
	for ch := range counter {
		letters = append(letters, ch)
	}
	sort.Slice(letters, func(i, j int) bool {
		return letters[i] < letters[j]
	})

	totalLen = len(s)
	dfs(0, 0)
	fmt.Print(answer)
}

C

#include <stdio.h>
#include <string.h>
#include <ctype.h>

char letters[26];
int counts[26];
int letterCount = 0;
int totalLen = 0;
long long answer = 0;

void dfs(char lastChar, int usedLen) {
    // 已经放满全部字符，说明得到一种合法排列。
    if (usedLen == totalLen) {
        answer++;
        return;
    }

    // 枚举所有仍可使用的字符。
    for (int i = 0; i < letterCount; i++) {
        char ch = letters[i];
        int idx = ch - 'A';

        // 当前字符没有剩余了，跳过。
        if (counts[idx] == 0) {
            continue;
        }

        // 相同字母不能相邻。
        if (ch == lastChar) {
            continue;
        }

        // 选择当前字符。
        counts[idx]--;
        dfs(ch, usedLen + 1);

        // 回溯，恢复剩余数量。
        counts[idx]++;
    }
}

int main() {
    char raw[1000];
    int len = 0;
    int ch;

    // 读取全部输入。
    while ((ch = getchar()) != EOF) {
        raw[len++] = (char)ch;
    }
    raw[len] = '\0';

    // 去掉首尾空白字符。
    int left = 0, right = len - 1;
    while (left <= right && isspace((unsigned char)raw[left])) left++;
    while (right >= left && isspace((unsigned char)raw[right])) right--;

    char s[1000];
    int p = 0;
    for (int i = left; i <= right; i++) {
        s[p++] = raw[i];
    }
    s[p] = '\0';

    // 输入固定为带双引号的字符串，这里取出双引号内部内容。
    if ((int)strlen(s) >= 2 && s[0] == '"' && s[strlen(s) - 1] == '"') {
        int n = (int)strlen(s);
        memmove(s, s + 1, n - 2);
        s[n - 2] = '\0';
    }

    // 空字符串只有一种合法排列。
    if (strlen(s) == 0) {
        printf("1");
        return 0;
    }

    totalLen = (int)strlen(s);

    // 统计每个字符出现次数。
    for (int i = 0; s[i] != '\0'; i++) {
        counts[s[i] - 'A']++;
    }

    // 提取所有出现过的不同字符。
    for (int i = 0; i < 26; i++) {
        if (counts[i] > 0) {
            letters[letterCount++] = (char)('A' + i);
        }
    }

    dfs('\0', 0);
    printf("%lld", answer);
    return 0;
}

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。