lintcode 계단훈련 제5관(9장)

10. 문자열의 다른 배열

제목은 문자열을 보여 줍니다. 모든 배열을 찾으십시오. 같은 문자열을 두 번 인쇄하지 않도록 주의하십시오.샘플은 "abb"를 제시하고 ["abb", "bab", "bba"]를 되돌려줍니다."aabb"를 주고 ["aabb", "abab", "baba", "bbaa", "abba", "baab"]로 돌아갑니다.

코드

public class Solution {
    public List stringPermutation2(String str) {
        List results = new ArrayList<>();
        if (str == null) {
            return results;
        }
        ArrayList list = new ArrayList<>();
        char[] s = str.toCharArray();
        Arrays.sort(s);
        boolean[] flag = new boolean[s.length];
        dfsHelper(s, flag, list, results);
        return results;
    }
    private void dfsHelper(char[] s,
                           boolean[] flag,
                           ArrayList list,
                           List results) {
        if (list.size() == s.length) {
            results.add(toStr(list));
        }
        for (int i = 0; i < s.length; i++) {
            if (flag[i]) {
                continue;
            }
            if (i != 0 && s[i] == s[i - 1] && !flag[i - 1]) {
                continue;
            }
            list.add(s[i]);
            flag[i] = true;
            dfsHelper(s, flag, list, results);
            flag[i] = false;
            list.remove(list.size() - 1);
        }
    }
    private String toStr(ArrayList list) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++) {
            sb.append(list.get(i));
        }
        return sb.toString();
    }
}

135, 디지털 조합

제목은 후보 숫자(C)와 목표 숫자(T)를 한 조로 제시하고 C의 모든 조합을 찾아 찾은 숫자가 T가 되도록 한다.C의 숫자는 무제한으로 선택될 수 있습니다.예를 들어 후보 수조[2,3,6,7]와 목표 숫자 7을 제시하고 구한 해답은 [7],[2,2,3] 주의사항의 모든 숫자(목표 숫자 포함)는 정수이다.원소조합(a1,a2,...,ak)은 반드시 비강차순(ie,a1≤a2≤...≤ak)이어야 한다.해집은 중복된 조합을 포함할 수 없다.예시 후보 수조[2,3,6,7]와 목표 숫자 7이 [[[7],[2,2,3]

로 되돌아오기

코드

public class Solution {
    public List<List> combinationSum(int[] candidates, int target) {
        List<List> result = new ArrayList<List>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        List list = new ArrayList<>();
        dfsHelper(candidates, 0, 0, target, list, result);
        return result;
    }
    private void dfsHelper(int[] candidates,
                           int pos,
                           int sum,
                           int target,
                           List list,
                           List<List> result) {
        if (sum == target) {
            result.add(new ArrayList(list));
        }
        for (int i = pos; i < candidates.length; i++) {
            if (i != pos && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] + sum > target) {
                break;
            }
            list.add(candidates[i]);
            dfsHelper(candidates, i, candidates[i] + sum, target, list, result);
            list.remove(list.size() - 1);
        }
    }
}

153, 디지털 조합 II

제목은 후보 숫자(C)와 목표 숫자(T)를 한 조로 제시하고 C의 모든 조합을 찾아내 조합 중의 숫자의 합을 T로 한다.C의 각 숫자는 각 조합에서 한 번만 사용할 수 있습니다.주의 사항의 모든 숫자(목표 숫자 포함)는 정수입니다.원소조합(a1,a2,...,ak)은 반드시 비강차순(ie,a1≤a2≤...≤ak)이어야 한다.해집은 중복된 조합을 포함할 수 없다.예를 들어 후보 숫자의 집합은 [10,1,6,7,2,1,5]와 목표 숫자 8이고 해집은 [[[1,7],[1,2,5],[2,6],[1,6]]

이다.

코드

public class Solution {
    public List<List> combinationSum2(int[] num, int target) {
        List<List> result = new ArrayList<List>();
        if (num == null || num.length == 0) {
            return result;
        }
        List list = new ArrayList<>();
        Arrays.sort(num);
        dfsHelper(num, 0, 0, target, list, result);
        return result;
    }
    private void dfsHelper(int[] num,
                           int pos,
                           int sum,
                           int target,
                           List list,
                           List<List> result) {
        if (sum == target) {
            result.add(new ArrayList(list));
        }
        for (int i = pos; i < num.length; i++) {
            if (i != pos && num[i] == num[i - 1]) {
                continue;
            }
            if (num[i] + sum > target) {
                break;
            }
            list.add(num[i]);
            dfsHelper(num, i + 1, num[i] + sum, target, list, result);
            list.remove(list.size() - 1);
        }
    }
}

136, 분할 회문열

제목에 문자열 s를 정하고 s를 일부 문자열로 나누어 모든 문자열이 회문열로 만든다.s의 모든 가능한 문자열 분할 방안을 되돌려줍니다.샘플은 s="aab", ["aa", "b"], ["a", "a", "b"]로 되돌아오기

코드

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> results = new ArrayList<List<String>>();
        if (s == null || s.length() == 0) {
            return results;
        }
        List<String> list = new ArrayList<String>();
        dfsHelper(s, list, results);
        return results;
    }
    private void dfsHelper(String s,
                           List<String> list,
                           List<List<String>> results) {
        if (s.length() == 0) {
            results.add(new ArrayList<String>(list));
        }
        for (int i = 0; i < s.length(); i++) {
            if (!isPalind(s, i)) {
                continue;
            }
            list.add(s.substring(0, i + 1));
            dfsHelper(s.substring(i + 1), list, results);
            list.remove(list.size() - 1);
        }
    }
    private boolean isPalind(String s, int i) {
        int start = 0;
        int end = i;
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}

108, 분할 회문열 II

제목에 문자열 s를 정하고 s를 일부 문자열로 나누어 모든 문자열이 회문으로 만든다.s가 요구에 부합되는 최소 분할 횟수를 되돌려줍니다.[다시 해야 함]

예를 들어 문자열s="aab"을 주고 1을 되돌려준다. 한 번의 분할을 통해 문자열s를 ["aa", "b"로 분할할 수 있기 때문이다

코드

public class Solution {
    public int minCut(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        boolean[][] isPalind = isPalindrome(s);
        int[] f = new int[s.length() + 1];
        f[0] = 0;
        for (int i = 1; i <= s.length(); i++) {
            f[i] = i;
            for (int j = 0; j < i; j++) {
                if (isPalind[j][i - 1]) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[s.length()] - 1;
    }
    private boolean[][] isPalindrome(String s) {
        int len = s.length();
        boolean[][] isPalind = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            isPalind[i][i] = true;
        }
        for (int i = 0; i < len - 1; i++) {
            isPalind[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
        }
        for (int length = 2; length < len; length++) {
            for (int start = 0; start + length < len; start++) {
                isPalind[start][start + length] = isPalind[start + 1][start + length - 1] && (s.charAt(start) == s.charAt(start + length));
            }
        }
        return isPalind;
    }
}

211. 문자열 바꾸기

제목에 두 개의 문자열을 지정하고 그 중 한 문자열이 다른 문자열로 바뀌었는지 여부를 판정하는 방법을 설계하십시오.바꾸는 것은 순서를 바꾸면 두 문자열을 같게 할 수 있다는 뜻이다.샘플 "abc"는 "cba"의 변환입니다."aabc"는 "abcc"의 교환이 아니다.

코드

public class Solution {
    public boolean stringPermutation(String A, String B) {
        if (A.length() != B.length()) {
            return false;
        }
        int[] flag = new int[1000];
        int len = A.length();
        for (int i = 0; i < len; i++) {
            flag[A.charAt(i)]++;
        }
        for (int i = 0; i < len; i++) {
            flag[B.charAt(i)]--;
        }
        for (int i = 0; i < len; i++) {
            if (flag[A.charAt(i)] != 0) {
                return false;
            }
        }
        return true;
    }
}

51. 이전 정렬

제목은 정수 그룹을 정해서 배열을 표시하고 그 이전의 배열을 찾아낸다.주의사항 배열에는 중복된 정수 예시를 포함할 수 있습니다 [1,3,2,3]. 그 위의 배열은 [1,2,3,3]이고 그 위의 배열은 [4,3,2,1]

입니다.

코드

public class Solution {
    public ArrayList previousPermuation(ArrayList nums) {
        int n = nums.size();
        int i = n - 1;
        while (i != 0 && nums.get(i) >= nums.get(i - 1)) {
            i--;
        }
        if (i == 0) {
            reverse(nums, 0, n - 1);
            return nums;
        }
        reverse(nums, i, n - 1);
        int j = i;
        for (; j < n - 1; j++) {
            if (nums.get(j) < nums.get(i - 1)) {
                break;
            }
        }
        swap(nums, i - 1, j);
        return nums;
    }
    private void swap(ArrayList nums, int i, int j) {
        int temp = nums.get(i);
        nums.set(i, nums.get(j));
        nums.set(j, temp);
    }
    private void reverse(ArrayList nums, int start, int end) {
        for (; start < end; start++, end--) {
            swap(nums, start, end);
        }
    }
}

52. 다음 줄

제목은 정수 그룹을 정하여 배열을 표시하고 그 다음의 배열을 찾아낸다.주의사항 배열에는 중복된 정수 예시가 포함될 수 있습니다 [1,3,2,3]. 그 다음 배열은 [1,3,3,2]입니다 [4,3,2,1]. 그 다음 배열은 [1,2,3,4]

입니다.

코드

public class Solution {
    public int[] nextPermutation(int[] nums) {
        if (nums == null) {
            return nums;
        }
        int n = nums.length;
        int i = n - 1;
        while (i != 0 && nums[i] <= nums[i - 1]) {
            i--;
        }
        if (i == 0) {
            reverse(nums, i, n - 1);
            return nums;
        }
        int j = n - 1;
        for (; j > i - 1; j--) {
            if (nums[j] > nums[i - 1]) {
                break;
            }
        }
        swap(nums, i - 1 , j);
        reverse(nums, i, n - 1);
        return nums;
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void reverse(int[] nums, int start, int end) {
        for (; start < end; start++, end--) {
            swap(nums, start, end);
        }
    }
}

190、다음 줄

제목은 약간의 정수의 배열을 정하고 정수 크기에 따라 사전의 순서를 작은 것부터 큰 것까지 정렬한 다음 배열을 제시한다.다음 배열이 없으면 사전의 순서가 가장 작은 서열을 출력합니다.예제 왼쪽은 원시 배열이고 오른쪽은 대응하는 다음 배열이다.1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

코드

public class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null) {
            return;
        }
        int n = nums.length;
        int i = n - 1;
        while (i != 0 && nums[i] <= nums[i - 1]) {
            i--;
        }
        if (i == 0) {
            reverse(nums, 0, n - 1);
            return;
        }
        int j = n - 1;
        for (; j > i - 1; j--) {
            if (nums[j] > nums[i - 1]) {
                break;
            }
        }
        swap(nums, i - 1, j);
        reverse(nums, i, n - 1);
        return;
    }
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private void reverse(int[] nums, int start, int end) {
        for(; start < end; start++, end--) {
            swap(nums, start, end);
        }
    }
}

197. 정렬 번호

제목은 중복된 숫자가 없는 배열을 제시하고 이 숫자의 모든 배열을 사전 순서에 따라 배열한 번호를 구한다.여기서 번호는 1부터 시작합니다.예를 들어 배열[1,2,4]은 첫 번째 배열이다.

코드

public class Solution {
    public long permutationIndex(int[] A) {
        int[] flag = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                if (A[i] > A[j]) {
                    flag[i]++;
                }
            }
        }
        long result = 0;
        for (int i = 0; i < A.length; i++) {
            result += flag[i] * Jec(A.length - i - 1);
        }
        return result + 1;
    }
    private long Jec(int x) {
        long ans = 1;
        while (x > 0) {
            ans *= (long) x;
            x--;
        }
        return ans;
    }
}

198, 정렬 번호 II

제목은 중복된 숫자를 포함할 수 있는 배열을 보여 줍니다. 이 숫자의 모든 배열을 사전 순서대로 정렬한 후에 그 안에 배열된 번호를 구하십시오.번호는 1부터 시작합니다.[다시 한 번 ~] 샘플은 [1,4,2,2]로 배열하고 그 번호는 3이다.

코드

public class Solution {
    public long permutationIndexII(int[] A) {
        Map map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            if (map.containsKey(A[i])) {
                map.put(A[i], map.get(A[i]) + 1);
            } else {
                map.put(A[i], 1);
            }
        }
        long result = 0;
        for (int i = 0; i < A.length; i++) {
            Map flag = new HashMap<>();
            for (int j = i + 1; j < A.length; j++) {
                if (A[i] > A[j] && !flag.containsKey(A[j])) {
                    flag.put(A[j], 1);
                    map.put(A[j], map.get(A[j]) - 1);
                    result += getNum(map);
                    map.put(A[j], map.get(A[j]) + 1);
                }
            }
            map.put(A[i], map.get(A[i]) - 1);
        }
        return result + 1;
    }
    private long getNum(Map map) {
        int sum = 0;
        long dup = 1;
        for (Integer v : map.values()) {
            if (v == 0) {
                continue;
            }
            sum += v;
            dup *= Jec(v);
        }
        if (sum == 0) {
            return sum;
        }
        return Jec(sum) / dup;
    }
    private long Jec(int x) {
        long ans = 1;
        while (x > 0) {
            ans *= (long) x;
            x--;
        }
        return ans;
    }
}

107 단어 구분

제목은 문자열 s와 사전을 보여 주며 문자열 s가 빈칸으로 나누어져 사전에 있는 단어로 나눌 수 있는지 판단합니다.[다시 한 번 필요해~] 예시 s = "lintcode"dict = ["lint", "code"] 반환true "lintcode"는 빈칸으로 나눌 수 있기 때문에"lint code"

코드

public class Solution {
    public boolean wordBreak(String s, Set dict) {
        if (s == null || s.length() == 0) {
            return true;
        } //?
        if (dict.isEmpty()) {
            return false;
        }
        int n = s.length();
        boolean[] flag = new boolean[n + 1];
        flag[n] = true;
        int maxLen = getMax(dict);
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j - i <= maxLen && j <= n; j++) {
                if (!flag[j]) {
                    continue;
                }
                String sub = s.substring(i, j);
                if (dict.contains(sub)) {
                    flag[i] = true;
                }
            }
        }
        return flag[0];
    }
    private int getMax(Set dict) {
        int maxLen = Integer.MIN_VALUE;
        for (String d : dict) {
            maxLen = Math.max(maxLen, d.length());
        }
        return maxLen;
    }
}

맥스렌 없으면 시간 초과~

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.