1. 전체 배열 변형(귀속)

제목 설명
Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example,[1,1,2]have the following unique permutations:[1,1,2],[1,2,1], and[2,1,1].
생각

한 가지 조건이 더 생겼다. 바로 중복된 숫자가 나타나는 것이다.그러면 먼저 정렬한 다음에 해당하는 위치에 숫자를 놓을 때 사용했는지 아닌지를 판단할 수 있습니다. 즉, 앞의 숫자와 비교할 수 있습니다. 만약에 앞의 숫자가 그것과 같은 값이고 현재used가false를 표시한다면 이 숫자는 이미 이 위치에서 사용되었고 결과res에 계산되었음을 의미합니다.

코드

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList> permuteUnique(int[] num) {
        ArrayList> res=new ArrayList<>();
        int len=num.length;
        if(num==null||len==0){
            return res;
        }
        boolean [] used=new boolean[len];
        ArrayList list=new ArrayList<>();
        Arrays.sort(num);
        dfs(list,num,used,res);
        return res;
    }
    
    public void dfs(ArrayList list,int [] num,boolean [] used,ArrayList> res){
        if(list.size()==num.length){
            res.add(new ArrayList(list));
            return ;
        }
        for(int i=0;i0&&num[i]==num[i-1]&&!used[i-1]){// ， ，
                // list ， 。。。 ， 
                continue;
            }
            if(!used[i]){
                used[i]=true;
                list.add(num[i]);
                dfs(list,num,used,res);
                list.remove(list.size()-1);
                used[i]=false;
            }
        }
    }
}

욕심

제목 설명
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example:A =[2,3,1,1,4], returntrue. A =[3,2,1,0,4], returnfalse
생각

욕심의 문제는 한 걸음 한 걸음 현재 이 위치에서 도달할 수 있는 최대 거리를 새롭게 한다.이것이 바로 이 문제의 욕심이다. 욕심은 일반적으로 증명하기 어렵지만 논리적으로 간단하게 생각해 보면 갈 수 있는 거리가 클수록 좋고 종점에 도달할 수 있다. 게다가 최대 거리가 종점에 도달하지 못하면 다른 상황은 더욱 불가능하다.

코드

public class Solution {
    public boolean canJump(int[] A) {
        int maxlen=A[0];
        for(int i=1;i

3. 동적 기획 or 욕심

제목 설명
Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example:Given array A =[2,3,1,1,4] The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index
생각

dp 해법:

제목을 고찰하고 싶은 것은 욕심이다. 생각해 보니 생각이 좀 혼란스럽다.먼저 동적 기획의 해법을 봅시다.

우선, dp의 조건을 만족: 1.서브 문제의 최우선 해법도 전체 국면의 최우선 해법이고 최우선 서브 구조가 있다.2. 현재 상태는 이전 상태에만 의존하고 이전 상태에 어떻게 도달하는 경로와 무관하다.

코드

public class Solution {
    public int jump(int[] A) {
        int [] dp=new int[A.length];// 
        for(int i=0;i

생각 2

욕심 해법:

욕심은 대법이 좋지만 정말 이해하기 어렵다.먼저 세 가지 값을 설정해야 합니다. 현재 위치(한 구역입니다: i~furthest_pre에서 구역의 점에서 도달할 수 있는 최대 위치(furthest_cur, 현재 위치의 이전 위치(또는 구역)에서 도달할 수 있는 최대 위치(furthest_pre, 그리고 걷는 걸음 수입니다.

약간 멍할 수도 있다. furthest_cur 아직 step++가 없을 때 코드를 구체적으로 결합하면 도착할 수 있으나 아직 가지 않은 상태이다.

아직 혼란스러워요. 코드를 버리고 제목이 준 수조의 시작 위치에 서 있다고 상상해 보세요. 시작 위치부터 시작 위치까지 갈 수 있는 최대 거리(furthest_pre 사이에 구역이 구성되어 있습니다. 그리고 우리는 한 칸 한 칸 걷기 시작합니다. 한 번 걸을 때마다 현재 이 구역이 갈 수 있는 최대 위치(furthest_cur를 새로 고칩니다.만약 시작 위치에서 furthest_pre까지 갔다면 우리도 가장 큰 furthest_cur을 갱신했을 것이다. 만약furthest_cur이 결승점보다 크다면 축하한다!한 번만 더 뛰면 결승점에 도착하잖아!한 걸음 해도 돼요!그리고 결승점에 도달할 때까지 상술한 동작을 반복합니다.

만약에 한 걸음 최대 위치furthest_pre까지 갈 수 있다면 한 걸음 그 앞의 어느 위치까지 가서 다음 점프를 실행할 수 있을 것이다furthest_cur.

테스트 용례를 주면 종이에 그림을 그릴 수 있다.

4 1 6 9 7 4 5 0 6 8 1 2 3 5 8 0 2 1 2

코드

public class Solution {
    public int jump(int[] A) {
        int len=A.length;
        if(len==0||A==null){
            return 0;
        }
        int furthest_cur=0;
        int furthest_pre=0;
        int steps=0;
        for(int i=0;i=len){
                return steps;
            }
            if(i>furthest_pre){
                furthest_pre=furthest_cur;
                steps++;
            }
            furthest_cur=Math.max(furthest_cur,A[i]+i);
        }
        return steps;
    }
}