Hexo

Posted 2022-08-15Updated 2022-08-15LeetCode / Easy2 minutes read (About 342 words)

Question

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.

X can be placed before L (50) and C (100) to make 40 and 90.

C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Solution

倒叙遍历，记录几个mark以标注是否出现对应的字母。

初始res为0，根据字符加减数值。
如果出现则将mark设置为真。
如果mark为真，且上一个字符出现对应需要减去的罗马字符，则改加为减。

最后返回res值。

Code

class Solution {
    public int romanToInt(String s) {
        int res = 0;
        boolean markX = false, markC = false, markM = false;
        
        for(int i = s.length()-1; i >= 0; i--){
            char c = s.charAt(i);
            if(c == 'I'){
                if(markX) res -= 1;
                else res += 1;
            }
            else if(c == 'V'){
                markX = true;
                res += 5;
            }
            else if(c == 'X'){
                markX = true;
                if(markC) res -= 10;
                else res += 10;
            }
            else if(c == 'L'){
                markC = true;
                res += 50;
            }
            else if(c == 'C'){
                markC = true;
                if(markM) res -= 100;
                else res += 100;
            }
            else if(c == 'D'){
                markM = true;
                res += 500;
            }
            else if(c == 'M'){
                markM = true;
                res += 1000;
            }
        }
        return res;
    }
}

Posted 2022-08-08Updated 2022-08-08LeetCode / Medium / 复习3 minutes read (About 474 words)

823. Binary Trees With Factors

Question

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node’s value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10<sup>9</sup><span> </span>+ 7.

Solution

根据题意，二叉树的根是两个子节点的乘积，因此一个根节点可组成的二叉树总数，相当于其左子节点可组成的二叉树总数，乘以其右子节点可组成的二叉树总数。

因此我们可以先将数组arr排序，用dp[]数组记录以从小到大的数字作为根节点可组成的最大二叉树总数。

由于每个根节点至少可以和自身组成一个节点，因此将dp[]数组初始化为1。

动态规划

从小到大遍历dp[]数组。
在遍历时，从遍历数值i的左侧选取当前位置的子节点。（根据题意子节点一定小于根节点）
当当前位置arr[i]可以整除arr[left]时，则有可能存在另一个子节点。此时根据哈希表中获得对应的另一个子节点right。如果right存在，则dp[i]更新为dp[i]+dp[left]*dp[right]的值。

最后将dp[]数组中记录的所有数字加和并返回。

Code

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final int MOD = (int) Math.pow(10, 9) + 7;
        Arrays.sort(arr);   //from minium to maxium
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++){
            map.put(arr[i], i);
        }
        
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);
        
        for(int i = 0; i < arr.length; i++){
            for(int left = 0; left < i; left++){
                if(arr[i] % arr[left] == 0){   //make sure divisible
                    int k = arr[i] / arr[left];
                    if(map.containsKey(k)){
                        int right = map.get(k);
                        dp[i] = (dp[i] + dp[left] * dp[right]) % MOD; 
                    }
                }
            }
        }
        
        int res = 0;
        
        for(long num : dp){
            res += num;
            res %= MOD;
        }
        
        return (int) res;
    }
}

Posted 2022-08-06Updated 2022-08-06LeetCode / Hard2 minutes read (About 291 words)

1220. Count Vowels Permutation

Question

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')

Each vowel 'a' may only be followed by an 'e'.

Each vowel 'e' may only be followed by an 'a' or an 'i'.

Each vowel 'i' may not be followed by another 'i'.

Each vowel 'o' may only be followed by an 'i' or a 'u'.

Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Solution

DFS搜索，记忆化剪枝。
每次根据上一个字母last来从哈希表里选择下一个可选字母进行遍历，并计算总的可组成数sum。

Code

class Solution {
    final int MOD = (int) Math.pow(10, 9) + 7;
    int[][] memo;
    HashMap<Character, Character[]> map;
    public int countVowelPermutation(int n) {
        if(n == 1) return 5;
        map = new HashMap<>();
        memo = new int[26][n+1];
        Character[] vowels = {'a', 'e', 'i', 'o', 'u'}, 
        a = {'e'}, e = {'a','i'}, i = {'a','e','o','u'}, o = {'i', 'u'}, u = {'a'};
        map.put('a', a);
        map.put('e', e);
        map.put('i', i);
        map.put('o', o);
        map.put('u', u);
        
        int ans = 0;
        
        for(char vowel : vowels){
            ans += count(vowel, n-1);
            ans %= MOD;
        }
        return ans;
    }
    
    private int count(char last, int n){
        if(memo[last-'a'][n] != 0) return memo[last-'a'][n];
        if(n == 1){
            memo[last-'a'][n] = map.get(last).length;
            return memo[last-'a'][n];
        }
        
        int sum = 0;
        for(char next : map.get(last)){
            sum += count(next, n-1);
            sum %= MOD;
        }
        memo[last-'a'][n] = sum;
        return sum;
    }
}

Posted 2022-08-05Updated 2022-08-05LeetCode / Medium2 minutes read (About 296 words)

377. Combination Sum IV

Question

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Solution

记忆化搜索，memo[]数组用来记录达到某个总和时的可行方案数量。
辅助方法count记录累计的总和memo[total]。

递归DFS，记忆化剪枝，如果memo[]数组不为空，则直接返回记忆内容。
当total等于target时，该组合成立，返回1。

遍历nums[]数组中的每个元素，并将总组合数相加记录到memo[total]中。
最后返回总组合数memo[total]。

*非常奇怪的是，当我使用int[]数组进行记忆化搜索时部分case会超时，推测是因为我判断int[]数组是否被记录是通过是否等于0而非是否为空导致的。

Code

class Solution {
    int[] numbers;
    Integer[] memo;
    public int combinationSum4(int[] nums, int target) {
        numbers = nums;
        memo = new Integer[target+1];
        return count(0, target);
    }
    
    private int count(int total, int target){
        if(memo[total] != null) return memo[total];
        if(total == target) return 1;
    
        int sum = 0;
        for(int i = 0; i < numbers.length; i++){
            if(total + numbers[i] <= target) sum += count(total + numbers[i], target);
        }
        memo[total] = sum;
        
        return memo[total];
    }
}

Posted 2022-08-04Updated 2022-08-05Drawing/Modelling / Blender2 minutes read (About 307 words)

使用Blender生成Avatar并添加动作

拍摄并处理照片

拍摄正面照片，手脚需要分开，背景可以用PS修改为白色，方便软件后期处理。

使用PIFuHD生成模型文件

PIFuHD Demo - Colaboratory (google.com)

通过这个库来处理照片文件。
处理完毕后得到OBJ文件和PNG文件。

使用Blender为模型添加材质

打开Blender，将OBJ文件导入。
选择UV Editing，在UV界面加载之前处理过的PNG文件，

首先将OBJ文件的正面向前。然后选择UV-Project from View。
此时会将模型上的控制点映射到UV窗口中。然后通过Scale，Move等工具将正面贴图与控制点相匹配。
如果出现双面人脸，可以通过调整部分控制点使材质隐藏。

再Material Properties一栏中的base color选择Image Texture。载入人物正面图片即可。

导出为FBX文件。

使用Mixamo为模型添加动作

将文件上传到Mixamo，选择不同动作，即可为自己的模型添加各种动作。

Question

Solution

Code

Question

Solution

动态规划

Code

Question

Solution

Code

Question

Solution

Code

拍摄并处理照片

使用PIFuHD生成模型文件

使用Blender为模型添加材质

使用Mixamo为模型添加动作

Recents

Archives

Links