이 글에서는 주로 Java에서 집합의 모든 하위 집합을 가져오는 방법을 소개합니다. 참고할만한 가치가 아주 좋습니다.
면접에 필기시험 문제가 있습니다.
세트를 입력하세요. 이 세트의 모든 하위 세트를 출력합니다. 예를 들어 1, 2, 4를 입력합니다. 출력 결과는 다음과 같습니다.
[1] [2] [4] [1, 2] [1, 4] [2, 4] [1, 2, 4]
알아야 할 사항: 빈 집합은 모든 집합의 부분 집합입니다. 비어 있지 않은 고유 부분 집합은 부분 집합과 빈 집합을 포함하지 않습니다.
해결책 아이디어:
이 문제는 다음을 사용하여 계산할 수 있습니다. "비트별 대응 방법"
예를 들어 A={a,b,c}로 설정하면 모든 요소에 대해 각 하위 집합에 해당 요소가 존재하거나 존재하지 않습니다. 하위 집합에 매핑:
(a,b,c) (1,1,1)->(a,b,c) (1,1,0)->(a,b) (1,0,1)->(a,c) (1,0,0)->(a) (0,1,1)->(b,c) (0,1,0)->(b) (0,0,1)->(c) (0,0,0)->@(@表示空集)
위 규칙을 따르면 컴퓨터의 데이터 저장 방식과 유사하므로 정수를 집합...000 ~ 111...111(예라는 의미)에 매핑할 수 있습니다. 는 아니오를 의미하며 그 반대도 마찬가지입니다. 정수를 점진적으로 증가시키면 모든 숫자를 순회할 수 있습니다. 즉, 집합의 해당 하위 집합을 얻을 수 있습니다.
주요 테스트는 변위 조작 및 논리적 사고 능력입니다. 구체적인 코드는 다음과 같습니다(이 기계로 인증되었으며 절대적으로 신뢰할 수 있음):
import java.util.ArrayList; import java.util.Scanner; import org.apache.commons.collections.CollectionUtils; /** * 输入一个集合,输出这个集合的所有子集 * @author liangyongxing * @time 2017-02-06 */ public class SubListExport { public static void main(String[] args) { ArrayList<Integer> list = new ArrayList<Integer>(); System.out.println("请输入一串整数并在输入时用英文逗号隔开:"); String inputString = new Scanner(System.in).next().toString(); if (inputString != null && !inputString.isEmpty()) { String[] strArray = inputString.split(","); for (String str : strArray) { list.add(Integer.parseInt(str)); } ArrayList<ArrayList<Integer>> allsubsets = getSubsets(list); for(ArrayList<Integer> subList : allsubsets) { System.out.println(subList); } } } public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> subList) { ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>(); int max = 1 << subList.size(); for(int loop = 0; loop < max; loop++) { int index = 0; int temp = loop; ArrayList<Integer> currentCharList = new ArrayList<Integer>(); while(temp > 0) { if((temp & 1) > 0) { currentCharList.add(subList.get(index)); } temp>>=1; index++; }42 allsubsets.add(currentCharList);44 } return allsubsets; } }
참고: 2017-02-08 10:01:32 위 코드에는 특정 허점이 있습니다. 즉, 입력에 숫자가 반복되면 결과에 하위 집합이 반복 출력되어 질문의 요구 사항을 충족하지 않습니다. 중복 제거를 수행할 때 HashSet을 추가해야 하며, 구체적인 수정 내용은 아래 그림과 같습니다.
1 . 허용된 반환 값을 기본 함수가
을 인쇄하는 HashSet 유형으로 수정합니다. 패키지 목록을 수정해야 하며 목록을 set로 변경
수정이 완료되었으며, 테스트 실행 결과는 다음과 같습니다. 🎜>
얻을 수 있는 코드를 분석하면 시간복잡도는 O(n*log2n)
위 내용은 Java는 컬렉션의 모든 하위 집합에 대한 세부 정보를 얻습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!