484. Find Permutation

OBKoro1 發布于2019-08-14 17:28 / 3374人閱讀

摘要：題目鏈接，用一個來指向現在到的數，每次碰到，就的數量，最后碰到把到放入結果，更新。還有一種寫法是先賦值，之后檢查，再。

484. Find Permutation

題目鏈接：
https://leetcode.com/problems...

greedy，用一個point：number來指向現在到的數，每次碰到"D"，就count"D"的數量，最后碰到I把number + count到number放入結果，更新count = 0。

public class Solution {
    public int[] findPermutation(String s) {
        int n = s.length();
        // the value in result
        int number = 1;
        int count = 0;
        int[] result = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            if(i == n || s.charAt(i) == "I") {
                for(int j = i; j >= i - count; j--) result[j] = number++;
                count = 0;
            }
            else count++;
        }
        
        return result;
    }
}

還有一種寫法是先賦值，之后檢查"D"，再reverse。

public class Solution {
    public int[] findPermutation(String s) {
        int n = s.length();
        
        int[] result = new int[n + 1];
        // assign value
        for(int i = 0; i <= n; i++) result[i] = i + 1;
        // reverse for D
        for(int i = 0; i < n; i++) {
            if(s.charAt(i) == "D") {
                int j = i + 1;
                while(j < n && s.charAt(j) == "D") j++;
                reverse(result, i, j);
                i = j;
            }
        }
        return result;
    }
    
    private void reverse(int[] result, int i, int j) {
        while(i < j) {
            int temp = result[i];
            result[i] = result[j];
            result[j] = temp;
            i++; j--;
        }
    }
}

GPU云服務器云服務器 Permutation find _find find linux

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66664.html

Find and Replace Pattern

1. 題目 You have a list of words and a pattern, and you want to know which words in words matches the pattern. A word matches the pattern if there exists a permutation of letters p so that after replaci...

ityouknow 2019-08-23 17:11 評論0 收藏0
[LintCode] Permutation Index I & Permutation I

摘要：我覺得雖然在里分類是，但其實是一道難題。思路如下搞一個哈希表，存儲數組中每一位的后面小于它的數的個數。與上一題的不同之處時會有重復的數。當然，每個重復數的都要階乘，例如有個，個，就是。是所有排列的次數和，返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

lucas 2019-08-14 16:23 評論0 收藏0
[LintCode] Previous Permutation

Problem Given a list of integers, which denote a permutation. Find the previous permutation in ascending order. Notice The list may contains duplicate integers. Example For [1,3,2,3], the previous per...

Pines_Cheng 2019-08-14 15:44 評論0 收藏0
[LeetCode] 267. Palindrome Permutation II

Problem Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form. Example Given s = aabb, return [abba,baa...

huashiou 2019-08-16 12:40 評論0 收藏0
【LC總結】回溯 (Subsets I II/Permutation I II/Combinatio

摘要：不同數包含重復數為的時候，表示在外層的循環正在被使用，所以當前循環遇到為一定要跳過。對當前循環要添加的數組，在添加當前元素后進行遞歸，遞歸之后要將當前元素的使用標記改為，表示已經使用和遞歸完畢，然后再將這個元素從的末位刪除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

tuomao 2019-08-14 15:53 評論0 收藏0