leetcode 31 차 더 블 주 경기 와 홀수 인 하위 배열 수

3687 단어 동적 계획leetcode알고리즘데이터 구조
홀수 의 하위 배열 수 와 정수 배열 arr 를 드 립 니 다.홀수 인 하위 그룹 수 를 되 돌려 주 십시오.답 이 많 을 수 있 으 니 결 과 를 10 ^ 9 + 7 에 나머지 를 취하 고 돌아 오 세 요.문제 풀이: 먼저 한 가지 알 겠 습 니 다. 홀수 + 짝수 = 홀수 + 홀수 = = = 홀수 그러면 문 제 는 동적 계획 문제 로 바 뀔 수 있 습 니 다. 우 리 는 배열 의 모든 수 를 옮 겨 다 닐 수 있 습 니 다. 만약 에 현재 홀수 라면 우 리 는 몇 개의 짝수 가 있 는 접두사 와 앞 에 짝수 라면 그 전에 몇 개의 홀수 접두사 가 있 는 지 찾 아야 합 니 다.그 이 유 는 이전에 몇 가지 홀수 배열 의 조합 이 있 었 는데 새로운 홀수 가 생 겼 을 때 이전의 모든 조합 과 홀수 의 하위 배열 을 구성 할 수 있 었 기 때문이다.
public class numOfSubarrays {

    public static int numOfSubarrays(int[] arr){
       int ans=0;
       //           
       int odd=0;
       //           
       int even=1;
       int sum=0;
       for (int num:arr){
           sum=(sum+num)%2;
           if ((sum&1)==1){
               ans+=even;
               odd++;
           }else {
               ans+=odd;
               even++;
           }
        ans%=1000000007;
       }
       return ans;
    }
}
49 Days of Ruby: Day 33 - 루비 보석 만들기
백준 11048번: 이동하기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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