资讯专栏INFORMATION COLUMN

484. Find Permutation

OBKoro1 / 3276人阅读

摘要:题目链接,用一个来指向现在到的数,每次碰到,就的数量,最后碰到把到放入结果,更新。还有一种写法是先赋值,之后检查,再。

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--;
        }
    }
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/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 评论0 收藏0
  • [LintCode] Permutation Index I & Permutation I

    摘要:我觉得虽然在里分类是,但其实是一道难题。思路如下搞一个哈希表,存储数组中每一位的后面小于它的数的个数。与上一题的不同之处时会有重复的数。当然,每个重复数的都要阶乘,例如有个,个,就是。是所有排列的次数和,返回下一次。 Permutation Index Problem Given a permutation which contains no repeated number, find...

    lucas 评论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 评论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 评论0 收藏0
  • 【LC总结】回溯 (Subsets I II/Permutation I II/Combinatio

    摘要:不同数包含重复数为的时候,表示在外层的循环正在被使用,所以当前循环遇到为一定要跳过。对当前循环要添加的数组,在添加当前元素后进行递归,递归之后要将当前元素的使用标记改为,表示已经使用和递归完毕,然后再将这个元素从的末位删除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

    tuomao 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<