LeetCode 제1 97 회 주간 경기 문제 풀이
글 목록
제목
정수 배열 nums 를 드 리 겠 습 니 다.만약 에 한 조 의 숫자 (i, j) 가 nums [i] = = nums [j] 와 i j 를 만족 시 키 면 이것 은 좋 은 숫자 라 고 볼 수 있다.숫자 쌍 의 숫자 를 되돌리다.
예제 1 입력: nums = [1, 2, 3, 1, 1, 3] 출력: 4 해석: 4 조 의 좋 은 숫자 쌍 이 있 는데 각각 (0, 3), (0, 4), (3, 4), (2, 5) 이 고 아래 표 지 는 0 부터 시작한다.
예제 2 입력: nums = [1, 1, 1] 출력: 6 해석: 배열 의 모든 숫자 가 좋 은 숫자 입 니 다.
예제 3 입력: nums = [1, 2, 3] 출력: 0
제시 하 다.
분석 하 다
제목 에 따라 계산 을 해 보 겠 습 니 다.
전체 시간 복잡 도 는 각각 i 와 뒤의 j 를 O (n ^ 2) 로 옮 겨 다 니 는 것 이다.
참조 코드
class Solution {
public
int numIdenticalPairs(vectorint& nums) {
int ans=0;
for(int i=0;inums.size()-1;i++)
for(int j=i+1;jnums.size();j++)
if(nums[i]==nums[j])ans++;
return ans;
}
};
b. 1 만 포함 하 는 하위 문자열 수
b. 제목
바 이 너 리 문자열 s ('0' 과 '1' 로 만 구 성 된 문자열) 를 드 립 니 다. 모든 문자 가 1 인 하위 문자열 의 수 를 되 돌려 줍 니 다. 답 이 많 을 수 있 으 니 10 ^ 9 + 7 을 되 돌려 주 십시오.
예제 1 입력: s = 011011 출력: 9 설명: 모두 9 개의 문자열 이 '1' 로 만 구성 되 어 있 습 니 다. 1 - 5 회 11 - 3 회 111 - 1 회
예제 2 입력: s = 101 출력: 2 해석: 하위 문자열 1 은 s 에서 모두 2 회 나타 납 니 다.
예제 3 입력: s = 111111 출력: 21 설명: 모든 하위 문자열 은 '1' 로 만 구성 되 어 있 습 니 다.
예제 4 입력: s = 000 출력: 0
제시 하 다.
b. 분석
11011 을 살 펴 보 겠 습 니 다. 이 꼬치 는 3 + 3 개 연속 1 꼬치 인 데 왜 제 가 3 + 3 으로 계산 하 죠? 저 는 1 연속 1 꼬치 로 계산 하 는 거 니까 요.
다음 문 제 는 3 과 6 을 어떻게 계산 하 느 냐 하 는 것 입 니 다.
그러면 전체적인 시간 복잡 도 는 전체 문자열 을 옮 겨 다 니 는 O (n) 입 니 다.
b. 참조 코드
class Solution {
public
int ans=0;
const int mod = 1e9+7;
int numSub(string s) {
int cnt=0; 1+2+...+n
for(int i=0;is.size();i++)
{
if(s[i]=='1'){ 1
cnt=(cnt+1)%mod;
ans=(ans+cnt)%mod;
}
else cnt=0; 0
}
return ans;
}
};
c. 확률 이 가장 높 은 경로
c. 제목
n 개의 노드 (아래 표 시 는 0 부터) 로 구 성 된 무 방향 가중 도 를 드 립 니 다. 이 그림 은 설명 변 의 목록 으로 구성 되 어 있 습 니 다. 그 중에서 edges [i] = [a, b] 는 연결 노드 a 와 b 의 무 방향 도 를 나타 내 고 이 변 을 옮 겨 다 니 며 성공 할 확률 은 succProb [i] 입 니 다.. 두 노드 를 각각 기점 start 와 종점 end 로 지정 합 니 다. 출발점 에서 종점 까지 성공 확률 이 가장 높 은 경 로 를 찾 아 성공 확률 을 되 돌려 주 십시오. start 에서 end 까지 의 경로 가 존재 하지 않 는 다 면 0 으로 돌아 가 십시오. 답 과 표준 답안 의 오차 가 1e - 5 를 초과 하지 않 으 면 정 답 으로 간 주 됩 니 다.
예시 1 [외부 체인 이미지 저장 실패, 원본 사이트 에 도 난 방지 체인 메커니즘 이 있 을 수 있 습 니 다. 그림 을 저장 하여 직접 업로드 하 는 것 을 권장 합 니 다 (img - PCOBzdHw - 1594541358065) (httpsassets. leetcode - cn. caliyun - lc - uploads 202007121558 ex1. png)] 입력: n = 3, edges = [0, 1], [1, 2], [0, 2], succProb = [0.5, 0.5, 0.2], start = 0, end = 2 출력: 0.25000 해석: 출발점 에서 종점 까지 두 가지 경로 가 있 는데 그 중 하 나 는 성공 확률 이 0.2 이 고 다른 하 나 는 0.5 = 0.25 이다.
예시 2 [외부 체인 이미지 저장 실패, 원본 사이트 에 도 난 방지 체인 메커니즘 이 있 을 수 있 습 니 다. 그림 을 저장 하여 직접 업로드 하 는 것 을 권장 합 니 다 (img - SRjf5pZZ - 1594541358067) (httpsassets. leetcode - cn. caliyun - lc - uploads 202007121558 ex2. png)] 입력: n = 3, edges = [0, 1], [1, 2], [0, 2], succProb = [0.5, 0.5, 0.3], start = 0, end = 2 출력: 0.30000
예시 3 [외부 체인 이미지 저장 실패, 원본 사이트 에 도 난 방지 체인 메커니즘 이 있 을 수 있 습 니 다. 그림 을 저장 하여 직접 업로드 하 는 것 을 권장 합 니 다 (img - mTeHREQc - 1594541358069) (httpsassets. leetcode - cn. caliyun - lc - uploads 202007121558 ex3. png)] 입력: n = 3, edges = [0, 1], succProb = [0.5], start = 0, end = 2 출력: 0.00000 설명: 노드 0 과 노드 2 사이 에 경로 가 존재 하지 않 습 니 다.
제시 하 다.
어떤 조건 에서 가장 좋 은 경 로 를 구 하 는 것 처럼 보 입 니 다.
클래스 최 단 템 플 릿 문제 인 만큼 dijkstra 가 정확 하지 않 은 지 생각해 보 겠 습 니 다.
그럼 바로 템 플 릿 으로 하 겠 습 니 다. 상세 하 게 보면 코드 가 선명 하고 전체적인 시간 복잡 도 는 nlogn 입 니 다.
c. 참조 코드
class Solution {
public
vectorint e,ne,h;
vectordouble w;
int n,m;
int idx=0;
double maxProbability(int N, vectorvectorint& edges, vectordouble& succProb, int start, int end) {
m=2edges.size();
n=N;
e.resize(m+5,0);
w.resize(m+5,0.0);
ne.resize(m+5,0);
h.resize(n+5,-1);
for(int i=0;iedges.size();i++)
{
add(edges[i][0],edges[i][1],succProb[i]);
add(edges[i][1],edges[i][0],succProb[i]);
}
return dijkstra(start,end);
}
void add(int a,int b,double W)
{
e[idx]=b;
w[idx]=W;
ne[idx]=h[a];
h[a]=idx++;
}
double dijkstra(int begin,int end) dijk
{
vectordouble dis(n,0); 0 dis
vectorint vis(n,false);
dis[begin]=1; 1
priority_queuepairdouble,int,vectorpairdouble,int,lesspairdouble,int heap;
heap.push({1,begin});
while(heap.size())
{
int node=heap.top().second;
heap.pop();
if(vis[node])continue;
for(int i=h[node];~i;i=ne[i]){
int now_node=e[i];double W=w[i];
if(dis[now_node]dis[node]W)
{
dis[now_node]=dis[node]W;
heap.push({dis[now_node],now_node});
}
}
vis[node]=true;
}
return dis[end];
}
};
d. 서비스 센터 의 최 적 위치
제목
한 택배 회 사 는 신도 시 에 새로운 서비스 센터 를 만 들 기 를 희망 합 니 다. 회 사 는 이 도시 의 모든 고객 이 2 차원 지도 에 있 는 좌 표를 통계 하고 이 를 근거 로 새로운 서비스 센터 의 주 소 를 선택 할 수 있 기 를 바 랍 니 다. 서비스 센터 에서 모든 고객 의 유클리드 거리 까지 의 총 계 를 최소 화 합 니 다. 배열 positions 를 드 리 겠 습 니 다. 그 중에서 positions [i] = [xi, yi]i 번 째 고객 이 2 차원 지도 에 있 는 위 치 를 나타 내 고 모든 고객 의 유클리드 거리의 최소 총화 로 돌아 갑 니 다. 다시 말 하면 서비스 센터 에 주 소 를 선택 하 십시오. 이 위치의 좌표 [xcentre, ycentre] 는 아래 의 공식 을 최소 값 으로 해 야 합 니 다. [외부 체인 이미지 저장 실패, 소스 스테이션 에 도 난 방지 체인 체제 가 있 을 수 있 습 니 다. 그림 을 저장 해서 직접 업로드 하 는 것 을 권장 합 니 다.(img - Bz47Nzx 9 - 1594541358071) (httpsassets. leetcode - cn. caliyun - lc - uploads 20200712 q4 edited. jpg)] 실제 값 오차 와 10 ^ - 5 이내 의 답 은 정 답 으로 간주 된다.
예시 1 [외부 체인 이미지 저장 실패, 원본 사이트 에 도 난 방지 체인 메커니즘 이 있 을 수 있 습 니 다. 그림 을 저장 해서 직접 업로드 하 는 것 을 권장 합 니 다 (img - 00oCloz4 - 1594541358073) (httpsassets. leetcode - cn. caliyun - lc - uploads 20200712 q4 e1. jpg)] 입력: positions = [0, 1], [1, 0], [1, 2], [2, 1] 출력: 4.00000 설명: 그림 에서 보 듯 이 [xcentre, ycentre] = [1, 1]새로운 중심 위치 로 서 모든 고객 의 거 리 는 1 이 고 모든 거리의 합 은 4 이 며 이것 도 찾 을 수 있 는 최소 치 이다.
예시 2 [외부 체인 이미지 저장 실패, 원본 사이트 에 도 난 방지 체인 메커니즘 이 있 을 수 있 습 니 다. 그림 을 저장 해서 직접 업로드 하 는 것 을 권장 합 니 다 (img - G7ZsuyP7 - 1594541358075) (httpsassets. leetcode - cn. caliyun - lc - uploads 20200712 q4 e3. jpg)] 입력: positions = [1, 1], [3, 3] 지 는 것: 2.82843 해석: 유클리드 거리 가능 한 최소 합 계 는 sqrt (2) + sqrt (2) = 2.82843
예제 3 입력: positions = [1, 1] 출력: 0.00000
예시 4 입력: positions = [1, 1], [0, 0], [2, 0] 출력: 2.73205 설명: 언뜻 보기 에는 중심 을 [1, 0] 으로 정 하고 최소 총 화 를 기대 할 수 있 지만, 주소 가 [1, 0] 거리 총 화 를 3 으로 선택 하면 [1.0, 0.5773502711] 거리 총 화 는 2.730205 의 정밀도 문제 로 변 할 수 있 습 니 다!
예제 5 입력: positions = [0, 1], [3, 2], [4, 5], [7, 6], [8, 9], [11, 1], [2, 12] 출력: 32.94036 해석: [4.3460852395, 4.9813795505] 을 새로운 중심 으로 하 는 위치 로 사용 할 수 있 습 니 다.
제시 하 다.
d. 분석
기 하 문 제 는 어 려 운 거 죠. 알고리즘 을 모 르 면 안 나 오 니까 저도 분석 을 안 해 요. 어떻게 생각해 야 돼 요. 배 워 야 알 아 요. 제 글 을 안 봐 요. 논문 을 찾 아 봐 야 겠 어 요. hh.
여기 간단 한 알고리즘 3 점 찾기 를 소개 합 니 다.
이것 은 오 씨 거리 에 이런 규칙 이 있 기 때문이다. 우 리 는 먼저 공식 을 본다. ans = sum (sqrt (x - xi)² + (y-yi)² )) 만약 에 우리 가 x 를 고정 시 켰 다 면 ans 의 최소 치 는 y 와 관련 된 2 차 함수 의 최소 치 이 고 2 차 함수 의 최소 치 는 3 분 법 으로 최 치 를 찾 을 수 있 습 니 다.
그러면 똑 같은 이치 로 x 에 대응 하 는 y 가 모두 알 고 있다 면 모든 xj 에 게 yj 는 고정 적 이다. 그러면 y 는 x 에 관 한 함수 getY (x) 로 쓸 수 있다. 그러면 이것 도 2 차 함수 의 가장 값 이 있 는 문제 이기 때문에 3 분 할 수 있다.
그래서 총 3 점, 3 점.
총 시간 복잡 도 는 O (nlogmlogm) m 가 정밀도 입 니 다.
d. 참조 코드
class Solution {
public
double getMinDistSum(vectorvectorint& p) {
int n=p.size();
auto getSum = [&n,&p](double x,double y){ （x，y）
double sum=0;
for(int i=0;in;i++)
sum+=sqrt((x-p[i][0])(x-p[i][0])+(y-p[i][1])(y-p[i][1]));
return sum;
};
auto getY = [&getSum](double x){ x y
double l=0,r=100;
for(int i=0;i100;i++)
{
double m1=(l+r)2,m2=(m1+r)2;
if(getSum(x,m1)getSum(x,m2))r=m2;
else l=m1;
}
return getSum(x,l);
};
double l=0,r=100;
for(int i=0;i100;i++) x
{
double m1=(l+r)2,m2=(m1+r)2;
if(getY(m1)getY(m2))r=m2; x
else l=m1;
}
return getY(l);
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
