首页 > 代码库 > 一道OJ编程题总结

一道OJ编程题总结

2024-09-11 12:56:12   219人阅读

技术分享

用暴力递归的话，以图中的测试用例为例，先让A号选择0号活，在让2-n 号员工选择1-5号活          有res1种

                                                        让A号选择1号活，在让2-n 号员工选择0, 2-5号活       有res2种

　　　　　　　　　　　　　　　　　　　　让A号选择2号活，在让2-n 号员工选择0-1,3-5号活     有res3种

                                                                        。。。

                                                        让A号选择5号活，在让2-n 号员工选择0-4号活            有res5种

res = res1 + res2 + ... + res5

因为前1名员工选择了0活，为了让0不出现在候选列表中，需要将其对应的flag置为true， 表示其已被选择。

这种思路和在数组中找到出现次数大于一半的数中，一次删去2个数 的原理相同，也是通过改变其flag，并不是真的删去该数。

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.TreeSet;

public class test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int num = Integer.parseInt(in.nextLine());
		List<Integer>[] list = new ArrayList[num];
		for(int i = 0; i < num; i++){
			list[i] = new ArrayList<>();
		}
		for(int i = 0; i < num; i++){
			String str = in.nextLine();
			for(int j = 0; j < str.length(); j++)
				list[i].add(str.charAt(j) - ‘0‘);
		}
		
		boolean[] flag = new boolean[6];
		process(list, 0, flag);
		
		System.out.println(res);
		
	}
	
	public static int res = 0; 
	
	public static void process(List<Integer>[] array, int index, boolean[] flag){
		
		if(index == array.length) return;
		List<Integer> list = array[index];
		for(int i = 0; i < list.size() ; i++){
			if(!flag[list.get(i)]){
				flag[list.get(i)] = true;
				if(index == array.length - 1)
					res++;
				process(array, index+1, flag);
				flag[array[index].get(i)] = false;
			}
			
			
		}
	}

}

　　

一道OJ编程题总结


联系
我们