LeetCode 주간 경기 202

오 랜 만 에 주간 경 기 를 치 르 게 되 었 는데,오늘 은 긴 장 된 시험 전 재 개(예비)학습 에서 시간 을 내 서 한 번 치 는 것 이 매우 자극적이다.
전체적으로 말 하면 이 문 제 는 그런대로 괜 찮 은 편 이 고 난이도 가 적당 하 다.
세 개의 홀수 가 연속 되 는 배열 이 존재 합 니 다.
제목 의 대 의 는 세 개의 연속 적 인 홀수 가 있 는 지 를 확인 하 는 배열 을 정 하 는 것 이다.
이것 은 출석 문제 라 고 할 수 있 습 니 다.기록 을 한 번 훑 어보 면 됩 니 다.

class Solution {
    public boolean threeConsecutiveOdds(int[] arr) {
		int flag = 0;
		int n = arr.length;
		for(int i = 0;i < n;i++) {
			if(arr[i] % 2 == 1) {
				flag++;
			}else {
				flag = 0;
			}
			if(flag == 3) {
				return true;
			}
		}
		return false;
    }
}

배열 의 모든 요 소 를 동일 하 게 하 는 최소 조작 수
제목 의 대 의 는 하나의 배열 을 정 하고 매번 한 쌍 의 요 소 를 선택 하여 그 중 하 나 를 추가 하고 다른 하 나 를 줄 일 수 있다 는 것 이다.몇 번 을 조작 한 후에 배열 의 요 소 는 모두 같 습 니까?
이 문제 도 어렵 지 않다.매번 하 나 를 더 하고 다른 하 나 를 줄 이 며 배열 의 총 화 는 변 하지 않 는 다 는 것 을 알 게 되 었 다.최종 결 과 는 틀림없이 평균치 일 것 이다.
배열 이 무 작위 로 주어진 다 면 모든 요소 가 평균 값 차이 까지 의 절대 치 를 한 번 훑 어보 고 마지막 에 더하기 와 나 누 기 2 가 답 이다.
하지만!!
이 문제 에서 배열 의 요 소 는 규칙 이 존재 한다.즉 a i=2 i−1(1≤i≤n)ai=2i-1\\(1≤i≤n)ai=2i-1(1≤i≤n)즉,이 서열 은 1,3,5,7.원소 개수 에 따라 짝 을 나 누 어 토론 할 수 있다.
홀수
a v g = a ⌊ n 2 ⌋ = n a n s = ∑ i = 1 ⌊ n 2 ⌋ ( a v g − a i )   = ∑ i = 1 ⌊ n 2 ⌋ ( n − 2 i + 1 ) avg = a_{\left \lfloor \frac{n} {2}\right \rfloor } = n\\ ans = \sum^ {\left \lfloor \frac{n} {2}\right \rfloor} _ {i = 1} (avg - a_i)\\ \ =\sum^ {\left \lfloor \frac{n} {2}\right \rfloor} _ {i = 1} (n - 2i+1) avg=a⌊2n​⌋​=nans=i=1∑⌊2n​⌋​(avg−ai​) =n-2i+1 은 등차수열 구 와 공식 을 이용 하여 다음 과 같이 다음 과 같이 다음 과 같이 다음 과 같이 다음 과 같이 다음 과 같이 다음 과 같이 다음 과 같이 정의 한다.a n s=(⌊n 2⌋+1)∗n 2⌊n n 2⌋ans=(\\\\\\\\lflor\\\\\frac{n}{2}\\\\\\\\\\\\\\\\\\\\lflor\\\\\\\\\frac{n}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\∗⌊2n⌋
짝수
a v g = a n 2 + a n 2 + 1 2 = n − 2 a n s = ∑ i = 1 n 2 ( a v g − a i )   = ∑ i = 1 n 2 ( n − 2 i − 1 ) avg = \frac{a_{\frac{n} {2}} + a_{\frac{n} {2} + 1}} {2} = n - 2\\ ans= \sum^ {\frac{n} {2}} _ {i = 1} (avg - a_i)\\ \ =\sum^ {\frac{n} {2} }_ {i = 1} (n - 2i-1) avg=2a2n​​+a2n​+1​​=n−2ans=i=1∑2n​​(avg−ai​) =i=1∑2n(n−2i−1)등차 수열 구 와 공식 을 이용 하여 a n s=n 2∗n 2 ans=\frac{n}{2}*\frac{n}{2}\\ans=2 n∗2n a n s=n 2 4 ans=\frac{n^2}{4}ans=4n2

public class Solution2 {
	int minOperations(int n) {
        if(n % 2 == 1) {
        	return (1 + n / 2) * (n / 2);
        }else {
        	return n * n / 4;
        }
    }
}

두 공 사이 의 자력
제목 의 대 의 는 n 개의 바구니 와 m 개의 작은 공(n>=m)을 정 하 는 것 이다.바구니 마다 1 차원 좌표 가 있 고 두 개의 작은 공의 자력 치 는|pi-pj|이 며 p 는 작은 공이 있 는 바구니 의 위치 이다.--최소 자력 치 는 최대 얼마 인가.
이 문 제 는 올 라 와 서 최소 치 를 구 하 는 것 이 가장 큰 것 을 보 았 는데,그 큰 확률 로 2 점 의 답 을 놓 칠 수 없 었 다.
우 리 는 이 최소 자력 값 을 직접 2 분 한 후에 매번 옮 겨 다 니 며 놓 을 수 있 는 지 를 검사 할 수 있다.
2 점 전에 모든 바구니 에 순 서 를 매 기 는 것 을 기억 하 세 요.
복잡 도:O(n l o g(m a x(p i)))O(nlog(max(pi))) O(nlog(max(pi​)))

class Solution {
   private boolean check(int k,int[] p,int m) {
		int n = p.length;
		int flag = p[0];
		m--;
		for(int i = 1;i < n;i++) {
			if(p[i] - flag >= k) {
				m--;
				flag = p[i];
			}
			if(m == 0) {
				return true;
			}
		}
		return false;
	}
	public int maxDistance(int[] position, int m) {
		Arrays.sort(position);
		int n = position.length;
		int l = 0,r = position[n - 1];
		while(l < r) {
			int mid = (l + r) / 2 + 1;
			if(check(mid,position,m)) {
				l = mid;
			}else {
				r = mid - 1;
			}
		}
		return l;
    }

}

귤 N 개 먹 은 최소 일수
제목 의 대 의 는 귤 n 개 를 정 하고 매일 세 가지 먹 는 방법 중 하 나 를 선택 할 수 있다 는 것 이다.

귤 한 개 먹 기

귤 의 수량 이 2 의 배수 라면 귤 의 절반 을 먹는다

귤 의 수량 이 3 의 배수 라면 귤 의 3 분 의 2 를 먹는다

귤 을 최소 며칠 만 에 다 먹 을 수 있 냐 고 물 어보 시 네요.
제목 을 번역 하면 얻 을 수 있 습 니 다.
세 가지 동작 중 하 나 를 선택 할 때마다 숫자 n 을 지정 합 니 다.

이 숫자 를 1 로 줄 였 다

이 숫자 가 2 의 배수 라면 2

로 나 누 어 라.

이 숫자 가 3 의 배수 라면 3

으로 나 누 어 라.
최소 몇 번 조작 하면 숫자 를 0 으로 줄 일 수 있 냐 고 물 었 다.
이렇게 보면 이것 은 수학 상의 문제 다.만약 에 이 숫자의 범위 가 비교적 작고 선형 시간 안에 해결 할 수 있다 면 우 리 는 동적 계획 으로 이 문 제 를 해결 할 수 있다.
그러나 문제 에서 이 숫자 는 규모 가 매우 커서 2*109 가 있 고 선형 시간 에 해결 할 수 없고 저장 할 수 없다.
그럼 검색 도 좋 은 방법 이 야.그러나 검색 의 복잡 도가 매우 높 기 때문에 우 리 는 그것 에 대해 일련의 최적화 가 필요 하 다.

우 리 는 숫자 를 가능 한 한 빨리 떨 어 뜨 려 야 하기 때문에 우 리 는 먼저 3 과 2 를 나 누 는 것 을 고려 하고 마지막 으로 1 을 줄 이 는 것 을 고려 하고 있다.

검색 과정 에 대해 가지치기 최 적 화 를 실시 하고 조작 수량 이 이미 알 고 있 는 최소 답안 보다 많다

앞의 두 부분의 최적화 알고리즘 만 으로 는 규정된 시간 내 에 임 무 를 완성 할 수 없 기 때문에 우 리 는 계속 최적화 해 야 한다.

기억 화 처 리 를 하 는데 재 귀 과정 에서 많은 숫자 가 자주 나타 나 는 것 을 감안 하여 기억 화 를 하면 중복 분해 횟수 를 줄 일 수 있다.맵 을 사용 하여 나타 난 모든 숫자 와 분 해 된 최소 절 차 를 기록 합 니 다.한 번 에 어떤 숫자 로 분 해 된 조작 수가 이전에 나 타 났 던 최소 조작 수 보다 적지 않다 면 이번 조작 은 반드시 답 에 기여 하지 않 고 바로 가 지 를 자 르 면 된다.그렇지 않 으 면 맵 을 업데이트 하고 계속 검색 합 니 다.

class Solution {
   static int ans = 1 << 30;
	static HashMap<Integer,Integer> map = new HashMap();
	private void dfs(int n,int k) {
		if(k >= ans) {
			return;
		}
		if(map.containsKey(n)) {
			if(map.get(n) <= k) {
				return;
			}
		}
		map.put(n, k);
		if(n == 0) {
			ans = k;
			return;
		}
		if(n % 3 == 0) {
			dfs(n / 3,k + 1);
		}
		if(n % 2 == 0) {
			dfs(n / 2,k + 1);
		}
		dfs(n - 1,k + 1);
	}
	public int minDays(int n) {
		map.clear();
        ans = 1 << 30;
		dfs(n,0);
		return ans;
    }
}