leetcode 약탈 1, 2, 3 (dp + 재 귀)
코드 는 다음 과 같 습 니 다:
public int rob(int[] nums) {
if(nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
if(nums.length==2){
return Math.max(nums[0],nums[1]);
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = nums[1];
dp[1] = Math.max(dp[0],dp[1]);
dp[2] = dp[0]+nums[2];
dp[2] = Math.max(dp[2],dp[1]);
for(int i = 2;i<nums.length;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.length-1];
}
코드 공간 에 대한 복잡 도 를 계속 합 니 다. 우 리 는 dp [i - 2] 와 dp [i - 1] 이전의 데이터 만 사용 할 수 없 기 때문에 두 개의 임시 변수 로 저장 할 수 있 습 니 다. 최적화 후 코드 는 다음 과 같 습 니 다.
public int rob(int[] num) {
int prevMax = 0;
int currMax = 0;
for (int x : num) {
int temp = currMax;
currMax = Math.max(prevMax + x, currMax);
prevMax = temp;
}
return currMax;
}
leetcode 가 집 을 약탈 하 는 2 가지 의미: 1 을 바탕 으로 머리 와 꼬리 도 서로 인접 하지 못 한다. 사고: 최대 와 의 영향 은 두 가지 상황 으로 나 눌 것 이다. 1. 머리 를 강탈 하지만 꼬리 를 강탈 하지 않 으 면 0 - n - 1 2. 거 리 를 강탈 하지 않 지만 꼬리 를 강탈 하면 1 - n 이 2 자 에 게 최대 ans 를 유지 하면 된다.
코드 는 다음 과 같 습 니 다:
class Solution {
public int robs(int[] nums) {
if(nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
if(nums.length==2){
return Math.max(nums[0],nums[1]);
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = nums[1];
dp[1] = Math.max(dp[0],dp[1]);
dp[2] = dp[0]+nums[2];
dp[2] = Math.max(dp[2],dp[1]);
for(int i = 2;i<nums.length;i++){
dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[nums.length-1];
}
public int rob(int[] nums) {
if(nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
return Math.max(robs(Arrays.copyOfRange(nums,0,nums.length-1)),robs(Arrays.copyOfRange(nums,1,nums.length)));
}
}
leetcode 가 집 을 약탈 하 는 3 가지 의미: 이 진 트 리 유형의 집에 서 약탈 하 는 것 은 연결 되 어 있 는 점 을 만족 시 키 고 생각 을 빼 앗 을 수 없습니다. 모든 노드 를 재 귀적 으로 유지 하 는 두 가지 상황 1. 두 결점 참여 + 손자 결점 과 2. 머리 없 는 결점 참여 + 아들 결점 의 합
코드 는 다음 과 같 습 니 다:
class Solution {
public int rob(TreeNode root) {
if(root==null){
return 0;
}
int lval = rob(root.left);
int rval = rob(root.right);
int llval = 0;
int lrval = 0;
int rrval = 0;
int rlval = 0;
if(root.left!=null){
llval = rob(root.left.left);
lrval = rob(root.left.right);
}
if(root.right!=null){
rrval = rob(root.right.right);
rlval = rob(root.right.left);
}
return Math.max(lval+rval,llval+lrval+rrval+rlval+root.val);
}
}
계속 이 사고방식 에 따라 최적화 하 다
class Solution {
public int rob(TreeNode root){
int[] res = doRob(root);
return Math.max(res[0],res[1]);
}
public int[] doRob(TreeNode root){
int[] res = new int[2];
if(root==null){
return res;
}
int[] left = doRob(root.left);
int[] right = doRob(root.right);
res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
res[1] = root.val+left[0]+right[0];
return res;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.