[Golang] LeetCode - 검지 Offer - 면접 문제 60 - n 주사위 포인트

10730 단어 LeetCode 개인 문제 풀이알고리즘동적 계획leetcodego.데이터 구조
제목.
n 개의 주사 위 를 바닥 에 던 지고 모든 주사 위 는 위 를 향 한 포인트 의 합 은 s 이다.n 을 입력 하면 s 의 모든 가능 한 값 이 나타 날 확률 을 출력 합 니 다.너 는 부동 소수점 배열 로 답 을 되 돌려 야 한다. 그 중에서 i 번 째 요 소 는 n 개의 주사위 가 던 질 수 있 는 포인트 집합 에서 i 번 째 작은 확률 을 대표 한다.
예시 1: 입력: 1 출력: [0.16667, 0.16667, 0.16667, 0.16667, 0.16667, 0.16667, 0.16667, 0.16667]
예시 2: 입력: 2 출력: [0.02778, 0.05556, 0.08333, 0.11111, 0.13889, 0.16667, 0.13889, 0.11111, 0.08333, 0.05556, 0.02778]
제한:
1 <= n <= 11
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof
문제 풀이 의 사고 방향.
문제 풀이 방향 은 LeetCode 작성 자 huwt 에서 참조 합 니 다. 여 기 를 클릭 하여 문제 풀이 원문 을 방문 하 십시오.
  • 분석 문제
  • 주사위 하나 에 6 개의 면 이 있 고 6 가지 결과 (n = 1)
  • n 개의 주사 위 는 6n - 1 가지 포인트 와 결과 가 있 고 포인트 와 크기 범 위 는 n ~ 6n - 1 (n > = 2)
    • 이다.
  • 문제 의 결 과 는 모든 주사위 포인트 와 나타 난 횟수 를 계산 한 다음 에 총 가능 수
    • 로 나 누 는 것 이다.
  • 전체적인 가능성 은 쉽게 구 할 수 있 고 6 ^ n (6 의 n 차방)
    • 이다.
  • 문 제 는 모든 포인트 와 나타 난 횟수
    • 를 푸 는 것 이 관건 이다.
  • 동적 기획 문제 풀이
  • 동태 계획 을 사용 하여 문 제 를 해결 하 는 것 은 보통 세 단계 로 나 뉜 다.
  • 상태 표시
  • 상태 전이 방정식 찾기
  • 경계 처리


    • 점진 적 분석
    1. 상태 표시
  • 문제 의 상 태 를 분석 할 때 전 체 를 분석 하지 말고 마지막 단계 만 분석 하면 된다!
  • 동태 계획 문 제 는 모두 여러 단계 로 나 뉘 기 때문에 각 단계 의 상 태 는 똑 같 고 우리 의 최종 답 은 마지막 단계 에 있다.

  • 마지막 단 계 는 무엇 일 까요?
  • 문 제 를 통 해 우 리 는 모두 n 개의 주사 위 를 던 진 다 는 것 을 알 았 다. 그 마지막 단 계 는 분명 하 다.
  • n 개의 주사 위 를 던 진 후 각 포인트 가 나타 나 는 횟수 (앞의 n 개의 주사위 포인트 와).


    • 여기 포 인 트 는 n 번 째 주사위 의 포인트 가 아니 라 n 번 째 주사위 의 포 인 트 를 말 합 니 다. 다음은 같 습 니 다.
  • 마지막 단 계 를 찾 아 상 태 를 어떻게 표시 하 는 지 찾 아 냈 다.
  • 먼저 변수 t = n 으로 주사 위 를 몇 개 던 져 야 하 는 지 를 표시 하고 주사 위 를 한 개 씩 던 질 때마다 t - 1.
  • 맵 을 정의 합 니 다
  • 이 주사 위 를 던 진 후 나타 날 수 있 는 포인트 와 맵 의 키 로 표시 합 니 다.
  • map 의 value 는 이 단계 의 각 포인트 가 나타 난 횟수 를 나타 낸다.


    • 그래서 상 태 는 다음 과 같다. map [int] int 는 n 개의 주사 위 를 던 진 후 포인트 키 의 출현 횟수 value 를 나타 낸다.
    2. 상태 전이 방정식 찾기
  • 즉, 각 단계 간 의 전환 관 계 를 찾 는 것 이다. 마찬가지 로 마지막 단계 만 분석 하면 된다.
  • 마지막 단계 t = 0 즉 n 개의 주사 위 를 던 진 후의 이 단계
  • 주사위 하나만 보면 포인트 가 1, 2, 3,... 6 일 수 있 습 니 다.
  • 따라서 n 개의 주사 위 를 던 진 후 포인트 와 나타 나 는 횟수 는 n - 1 개의 주사 위 를 던 진 후 해당 포인트 + n 번 째 주사위 에 나타 나 는 6 개의 포인트 (1 ~ 6) 와 나타 나 는 횟수 의 합 
    •  	t := n
    m := map[int]int{
     0:1}
    for t > 0 {
     
        m1 := map[int]int{
     }
        for i := 1; i <= 6; i++ {
     
            for k, v := range m {
     
                m1[k + i] += v
            }
        }
        m = m1
        t--
    }

    t 는 단계, k + i 는 n 개의 주사 위 를 던 진 후의 포인트 와 i 는 n 번 째 주사 위 를 던 지면 나타 나 는 6 개의 포 인 트 를 나타 낸다.
    3. 경계 처리
  • 이곳 의 경계 처 리 는 매우 간단 하 다. 우리 가 직접 알 수 있 는 상 태 를 초기 화하 면 된다.
  • 우리 가 직접 알 수 있 는 상태 가 무엇 인지, 바로 첫 번 째 단계 의 상태 이다.
  • 주사위 1 개 를 던 진 후 가능 한 포 인 트 는 각각 1, 2, 3,... 6 이 고 포인트 당 1
    • 입 니 다.
     	m1 := map[int]int{
     }
 	for i := 1; i <= 6; i++ {
     
 	    for k, v := range m {
     
 	        m1[k + i] += v
 	    }
 	}
 	m = m1

    코드
    – 실행 시간: 0 ms -- 메모리 소모: 2.1 MB
    func twoSum(n int) []float64 {
     
 	//    
    t := n
    //            1
    m := map[int]int{
     0:1}
    for t > 0 {
     
     	//   n        
        m1 := map[int]int{
     }
        //    
        for i := 1; i <= 6; i++ {
     
            for k, v := range m {
     
             	//k + i       n         
             	// += v n-1          +  n            (1~6)         
                m1[k + i] += v
            }
        }
        //    n-1              
        m = m1
        t--
    }
    //     
    sum := 0
    for _, v := range m {
     
        sum += v
    }
    //sum := math.Pow(6.0,float64(n))
    //          
    ret := make([]float64, n * 6 - n + 1)
    for k, v := range m {
     
     	//        k - n
        ret[k - n] = float64(v)/float64(sum)
    }
    return ret
}
    ☀[CSS3] 섀도우 박스-shadow
    CSS3 마우스 위로 버튼 띄우기 상자 보이기 효과

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage