leetcode 퀴즈 요약(지속 업데이트)

1. 귀속과 교체에 관하여
귀속 성능은 낮지만 코드는 직관적이어서 교체 후 서브 구조로 바뀌어 변하지 않는다
두 갈래 나무의 교체 실현?
2. 동적 기획
최대치 최소치와 같은 최치 문제는 일반적으로 동적 기획 방법을 통해 판단할 수 있고 일부 존재성 문제도 동적 기획 방법으로 계산할 수 있다
https://leetcode.com/problems/word-break/
3. 초기화 숫자가 최대일 경우 INTMAX, 하지만 기억해라, INTMAX+1 후 마이너스!!
https://leetcode.com/submissions/detail/188276800/
4. 오류 발생:
for(;;)에서 만약 두 분호 간의 판단 조건이 여러 개가 있다면 논리 연산 기호 & & & & |와 연결하고 쉼표를 사용하지 마십시오!
https://leetcode.com/submissions/detail/188428764/
5. 시간 초과 정보
일부 실행 가능한 모든 문제를 인쇄하려면 먼저 DP로 실행 가능한지 판단하고 실행 가능한지 DFS로 인쇄해야 한다. 그렇지 않으면 시간이 초과될 수 있다.
https://leetcode.com/problems/word-break-ii/discuss/44185/Getting-rid-of-TLE
6. 빠른 정렬 정보
만약 pivot가 첫 번째 숫자라면, 왜 먼저 뒤에서 앞으로 작은 것을 찾아야 합니까?왜냐하면 이런 상황이 나타날 수 있기 때문이다. 예를 들면,
1,4,2,3
먼저 갔다가 큰 것을 찾으면 마지막에 되돌아오는 pivot는 4와 1로 교환됩니다. 빠른 정렬은 되돌아오는 pivot에 대해 pivot의 왼쪽 수가 없거나 없거나 pivot보다 작거나 오른쪽 수가 없거나 없거나 pivot보다 큽니다.
왜 꼭 오른쪽부터 시작해야 하는지 구체적으로 알 수 있어요.
이게 틀리기 쉬웠으면 좋겠어요. 제가 오래 기억할 수 있었으면 좋겠어요...
7. c++ string에 관하여.substr()

string substr (size_t pos = 0, size_t len = npos) const;

만약pos의 값과 문자열의 길이가 같으면 빈 문자열을 되돌려줍니다
만약pos의 값이 문자열의 길이보다 크다면, 이상을 던집니다
8. 문자열과 숫자의 상호 전환에 대해
커다란 구덩이가 하나 있는데, 문자열이 너무 길면 숫자로 직접 바꿀 수 없다는 것이다...예를 들어 길이가 1000인 문자열을 어떻게 숫자로 바꿉니까?
9. 길이가 같은 두 문자열의 비교
두 개의 길이가 같은 문자열을 직접 비교할 수 있는데 이것은 c++의 언어 특성이다. 예를 들어'abb'< abc'(사전 순서에 따라)
10.leetcode236 공공조상, 이 문제의 사고방식은 본 노드에서 찾지 못하면 두 아들을 찾고 두 아들의 결과를 통해 판단하는 것이다...
11. 체인 시계 반전
12. 체인 테이블의 정렬, 단방향 체인 테이블은 병합 정렬, 양방향 체인 테이블은 빠른 정렬
13. 두 갈래 나무: 마지막 층 노드에 하위 노드가 없는 것을 제외하고 다른 노드는 모두 두 개의 하위 노드가 있다.완전 두 갈래 나무: 깊이가 K이고 n개의 노드가 있는 두 갈래 나무는 각 노드마다 두어의 깊이가 K인 두 갈래 나무 중 번호가 1~n인 노드가 일일이 대응할 때만 완전 두 갈래 나무라고 부른다.
나무의 층차순으로 완전한 두 갈래 나무인지 아닌지 판단할 수 있다.
14. 빠른 속도 지침의 문제
처음 만났을 때, 만남점에서 링 입구까지의 반시계 바늘 길이는 R1이고, 무환 부분의 길이는 L이다
2(L+R1) = L + nC, C는 도넛 둘레
즉 L = nC-R1, 즉 바늘을 하나 더 찾아 입구에 놓고 느린 바늘은 느린 바늘이 만나는 곳에 놓으면 그 다음에 반드시 입구에서 만난다.
이 문제는 만날 수 있을지 없을지를 먼저 판단해야 하기 때문에 몇 번 더 보는 것을 권장한다.
15 시계 방향으로 수조를 인쇄하면 이 문제는 틀리기 쉽다. 가로로 수조를 한 번 인쇄한 다음에 뒤에서 앞으로 다시 수조를 한 번 인쇄하거나 세로로 수조를 한 번 인쇄한 다음에 세로로 아래에서 위로 수조를 한 번 인쇄하는 경우가 있기 때문이다.
16 정규 표현식, 이 문제는 내가 가장 틀리기 쉬운 문제이다. 왜냐하면 빈 문자열도 일치할 수 있기 때문이다.
https://leetcode.com/problems/regular-expression-matching/
17 0-1 가방은 역순: 상태 이동 방정식은 다음과 같이 간단하기 때문이다.

dp[i][j] = max(dp[i-1][j-weight[i]]+value[i], dp[i-1][j])

완전 가방은 순서입니다. 상태 이동 방정식은 다음과 같습니다.

dp[i][j] = max{ dp[i-1][j-k*weight[i]]+k*value[i]}, 0 <= k*weight[i] <= j

이 상태 전환 방정식은 다음과 같이 변환할 수 있습니다.

dp[i][j] = max(dp[i][j-weight[i]]+value[i], dp[i-1][j])

18 unsigned int의 반대:
sum = INT_MAX, -SUM = INT_MAX + 2 의 32 차
19 빈 나무는 두 갈래 평형 나무입니다.
20 동전 문제, 자연수 분해 문제:
동전 문제: 인터넷의 각 회사에서 자주 문제를 낸다. 현재 1원, 2원, 5원짜리 지폐가 여러 장 있는데 현재 20원이 필요하다고 가정하면 거스름돈을 줄 수 있는 방안이 얼마나 되는지 완전한 배낭 문제로 볼 수 있다. 즉, 배낭의 용량은 20이고 물품의 부피는 각각 1, 2, 5이다.
자연수 분해 문제: 하나의 수 m를 정하고 m을 서로 다른 자연수로 분해하는 형식은 몇 가지 방안이 있습니까? 이것이 바로 전형적인 01가방 문제입니다. 가방의 용량은 m이고 물품의 수량은 k입니다. 이 안의 k는 은밀한 조건입니다. 구할 수 있습니다. m는 최대 1+2+...+k이기 때문에 m에 따라 물품 수량의 상한선을 구할 수 있습니다.
01 가방의 상태 이동 공식:

dp[i][j] = dp[i-1][j], j < nums[i];
dp[i][j] = dp[i-1][j](  ) + dp[i-1][j-nums[i]]( )

전체 가방의 상태 이동 공식:

dp[i][j] = dp[i-1][j], nums[i] > j;
dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]+dp[i-1][j-2*nums[i]]+....+dp[i-1][j-k*nums[i]],
                                                            (nums[i] <= j < (k+1)*nums[i])

그 중에서nums[i]>=j의 추이 공식은

dp[i][j] = dp[i-1][j], j < nums[i] 
dp[i][j] = dp[i-1][j] + dp[i][j-nums[i]], j >= nums[i]

21대수 곱하기 문제, 마지막 자리의 진위를 주의하세요.
22. 동적 기획 중의 바둑 문제는 일반적으로 dp[i]로 하여금 선수필승을 표시하게 한다. 그러면 dp[i]=!dp[i-1] || !dp[i-2] || .. dp[i-k].... 즉

dp[i] = !(dp[i-1] && dp[i-2] && .... && dp[i-j])