组合?"/>
面试题:“中国浙江杭州”这样的一串字符串有多少个不重复的排序组合?
“中国浙江杭州”这样的一串字符串有多少个不重复的排序组合?要求:长度不变,不能重复。
1) java实现:
import java.util.ArrayList;
import java.util.List;public class StringCombination {public static void main(String[] args) {String input = "中国浙江杭州";int length = 6;List<String> combinations = generateCombinations(input, length);System.out.println("满足条件的组合数量:" + combinations.size());System.out.println("满足条件的组合:");for (String combination : combinations) {System.out.println(combination);}}private static List<String> generateCombinations(String input, int length) {List<String> combinations = new ArrayList<>();generateCombinationsHelper(input, length, "", combinations);return combinations;}private static void generateCombinationsHelper(String input, int length, String currentCombination, List<String> combinations) {if (currentCombination.length() == length) {combinations.add(currentCombination);return;}for (int i = 0; i < input.length(); i++) {char c = input.charAt(i);if (!currentCombination.contains(String.valueOf(c))) {generateCombinationsHelper(input, length, currentCombination + c, combinations);}}}
}
2)C#实现:
csharp
using System;
using System.Collections.Generic;namespace StringCombination
{class Program{static void Main(string[] args){string input = "中国浙江杭州";int length = 6;List<string> combinations = GenerateCombinations(input, length);Console.WriteLine("满足条件的组合数量:" + combinations.Count);Console.WriteLine("满足条件的组合:");foreach (string combination in combinations){Console.WriteLine(combination);}}private static List<string> GenerateCombinations(string input, int length){List<string> combinations = new List<string>();GenerateCombinationsHelper(input, length, "", combinations);return combinations;}private static void GenerateCombinationsHelper(string input, int length, string currentCombination, List<string> combinations){if (currentCombination.Length == length){combinations.Add(currentCombination);return;}for (int i = 0; i < input.Length; i++){char c = input[i];if (!currentCombination.Contains(c.ToString())){GenerateCombinationsHelper(input, length, currentCombination + c, combinations);}}}}
}
3) python实现:
def generate_combinations(input_string, length):combinations = []generate_combinations_helper(input_string, length, "", combinations)return combinationsdef generate_combinations_helper(input_string, length, current_combination, combinations):if len(current_combination) == length:combinations.append(current_combination)returnfor i in range(len(input_string)):char = input_string[i]if char not in current_combination:generate_combinations_helper(input_string, length, current_combination + char, combinations)input_string = "上海金燕航空"
length = 6combinations = generate_combinations(input_string, length)
print("满足条件的组合数量:", len(combinations))
print("满足条件的组合:")
for combination in combinations:print(combination)
4) object-c实现:
objective-c
#import <Foundation/Foundation.h>void generateCombinationsHelper(NSString *input, int length, NSString *currentCombination, NSMutableArray *combinations) {if (currentCombination.length == length) {[combinations addObject:currentCombination];return;}for (int i = 0; i < input.length; i++) {unichar c = [input characterAtIndex:i];NSString *charString = [NSString stringWithCharacters:&c length:1];if (![currentCombination containsString:charString]) {generateCombinationsHelper(input, length, [currentCombination stringByAppendingString:charString], combinations);}}
}NSArray *generateCombinations(NSString *input, int length) {NSMutableArray *combinations = [NSMutableArray array];generateCombinationsHelper(input, length, @"", combinations);return combinations;
}int main(int argc, const char * argv[]) {@autoreleasepool {NSString *input = @"上海金燕航空";int length = 6;NSArray *combinations = generateCombinations(input, length);NSLog(@"满足条件的组合数量:%lu", (unsigned long)combinations.count);NSLog(@"满足条件的组合:");for (NSString *combination in combinations) {NSLog(@"%@", combination);}}return 0;
}
5) C++实现:
#include <iostream>
#include <vector>
using namespace std;void generateCombinationsHelper(string input, int length, string currentCombination, vector<string>& combinations) {if (currentCombination.length() == length) {combinations.push_back(currentCombination);return;}for (int i = 0; i < input.length(); i++) {char c = input[i];if (currentCombination.find(c) == string::npos) {generateCombinationsHelper(input, length, currentCombination + c, combinations);}}
}vector<string> generateCombinations(string input, int length) {vector<string> combinations;generateCombinationsHelper(input, length, "", combinations);return combinations;
}int main() {string input = "上海金燕航空";int length = 6;vector<string> combinations = generateCombinations(input, length);cout << "满足条件的组合数量:" << combinations.size() << endl;cout << "满足条件的组合:" << endl;for (string combination : combinations) {cout << combination << endl;}return 0;
}
6) c实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>void generateCombinationsHelper(char* input, int length, char* currentCombination, char** combinations, int* count) {if (strlen(currentCombination) == length) {combinations[*count] = malloc((length + 1) * sizeof(char));strcpy(combinations[*count], currentCombination);(*count)++;return;}for (int i = 0; i < strlen(input); i++) {char c = input[i];if (strchr(currentCombination, c) == NULL) {char* newCombination = malloc((strlen(currentCombination) + 2) * sizeof(char));strcpy(newCombination, currentCombination);newCombination[strlen(newCombination)] = c;newCombination[strlen(newCombination) + 1] = '\0';generateCombinationsHelper(input, length, newCombination, combinations, count);free(newCombination);}}
}char** generateCombinations(char* input, int length, int* count) {char** combinations = malloc(10000 * sizeof(char*));*count = 0;generateCombinationsHelper(input, length, "", combinations, count);return combinations;
}int main() {char* input = "上海金燕航空";int length = 6;int count;char** combinations = generateCombinations(input, length, &count);printf("满足条件的组合数量:%d\n", count);printf("满足条件的组合:\n");for (int i = 0; i < count; i++) {printf("%s\n", combinations[i]);free(combinations[i]);}free(combinations);return 0;
}
更多推荐
面试题:“中国浙江杭州”这样的一串字符串有多少个不重复的排序组合?
发布评论