LeetCode Weekly Contest 147

悠悠 2023-06-01 05:48 13阅读 0赞

### 1137. N-th Tribonacci Number ###

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given `n`, return the value of Tn.

Example 1:

Input: n = 4
    Output: 4
    Explanation:
    T_3 = 0 + 1 + 1 = 2
    T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
    Output: 1389537

Constraints:

*  `0 <= n <= 37`
 *  The answer is guaranteed to fit within a 32-bit integer, ie. `answer <= 2^31 - 1`.

题目大意：和斐波那契数列差不多，简单。

思路：暴力模拟。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

class Solution {
        public int tribonacci(int n) {
            if( n == 0 || n == 1 ) return n;
            if( n == 2 ) return 1;
            int sum = 0, three = 1, two = 1, one = 0;
            for(int i=3; i<=n; i++) {
                sum = three + two + one;
                one = two;
                two = three;
                three = sum;
            }
            return sum;
        }
    }

### 1138. Alphabet Board Path ###

On an alphabet board, we start at position `(0, 0)`, corresponding to character `board[0][0]`.

Here, `board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]`.

We may make the following moves:

*  `'U'` moves our position up one row, if the square exists;
 *  `'D'` moves our position down one row, if the square exists;
 *  `'L'` moves our position left one column, if the square exists;
 *  `'R'` moves our position right one column, if the square exists;
 *  `'!'` adds the character `board[r][c]` at our current position `(r, c)` to the answer.

Return a sequence of moves that makes our answer equal to `target` in the minimum number of moves.  You may return any path that does so.

Example 1:

Input: target = "leet"
    Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
    Output: "RR!DDRR!UUL!R!"

Constraints:

*  `1 <= target.length <= 100`
 *  `target` consists only of English lowercase letters.

题目大意：给你一个字母地图board，你最开始是在‘a’的位置，给你一个字符串，让你依次走过每个字母的位置，然后打印路径（随便一个路径就好）。

思路：暴力模拟，但是z有坑，z只能由u下去。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

class Solution {
        private static int m = 5;
    
        public String alphabetBoardPath(String target) {
            StringBuilder res = new StringBuilder();
            char[] chars = target.toCharArray();
            int len = target.length();
            char last = 'a';
            for(int i=0; i<len; i++) {
                char ch = chars[i];
                if( ch == 'z' && ch == last ) {
                    res.append("!");
                    continue;
                }
                if( chars[i] == 'z' ) ch = 'u';
                int x = 0, y = 0;
                if( ch > last ) {
                    int ch_o = ch - 'a';
                    int last_o = last - 'a';
                    x = ch_o/m - last_o/m;
                    y = Math.abs(ch_o%m - last_o%m);
                    for(int k=0; k<x; k++) {
                        res.append("D");
                        last = (char) (last + m);
                    }
                } else if( ch < last ) {
                    int ch_o = ch - 'a';
                    int last_o = last - 'a';
                    x = last_o/m - ch_o/m;
                    y = Math.abs(last_o%m - ch_o%m);
                    for(int k=0; k<x; k++) {
                        res.append("U");
                        last = (char) (last - m);
                    }
                }
                if( ch > last ) {
                    for(int k=0; k<y; k++) res.append("R");
                } else if( ch < last ) {
                    for(int k=0; k<y; k++) res.append("L");
                }
                if( chars[i] == 'z' ) res.append("D");
                res.append("!");
                last = chars[i];
            }
            return res.toString();
        }
    }

转载于:https://www.cnblogs.com/Asimple/p/11258560.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/68d735c8f77d457fb91878e8002853dc.png