泡LeetCode的日子-入门级Test

按照朋友的话来说, 入门级的难度会写for循环/ifelse判断即可.

0x20 题目

0x21 第一题

题目

题目的意思大概是: 给定一个长度为26的字符串buttons, 和一个匹配字符串word, 在长度为26的字符串buttons中搜索匹配字符串word的每个字符的间距, 一开始从buttons的第一个字符开始.

思路

比较暴力地搜索button中的所有在word当中的字符, 并且加一个oldIdx来保留上一个字符所在的位置, 用当前字符的idx索引减去上一字符的索引oldIdx得到当前字符与上一字符的距离. 以此类推.

题解

package com.killshadow.exam.primary;

public class PrimaryFirst {
    public static void main(String[] args) {
        String buttons = "zyxwvutsrqponmlkjihgfedcba";
        String word = "xyz";
        System.out.println(new PrimaryFirst().testButtons(buttons, word));
    }

    /**
     * Calculate test Button length
     * @param buttons total button
     * @param word need to be match words
     * @return the length between words
     */
    public int testButtons(String buttons, String word) {
        char[] wordCh = word.toCharArray();
        char[] buttonCh = buttons.toCharArray();
        int ans = 0;
        int oldIdx = 0;
        for (int i = 0; i < wordCh.length; i++) {
            int idx = 0;
            while (true) {
                if (wordCh[i] == buttonCh[idx]) {
                    ans += Math.abs(idx - oldIdx);
                    oldIdx = idx;
                    break;
                } else {
                    idx++;
                    idx %= 26;
                }
            }
        }
        return ans;
    }
}

0x22 第二题

题目

题意大概是: 给定一个MxN的二维数组matrixA, 计算该二维数组matrixA中所有元素左上角的元素和(包括该元素的值), 并存为当前元素的值.

示例

思路

此题利用了动态规划的思路, 如果用暴力地话会超时. 设当前元素为, 则左边元素和上边元素的值分别为: 用当前元素的左边的值+当前元素上边的值-当前元素左上角的值等于当前元素的值, 如下:

思路

题解

package com.killshadow.exam.primary;

import java.util.Arrays;

public class PrimarySecond {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {3, 7, 1}, {2, 4, 0}, {9, 4, 2}
        };
        int[][] ans = new PrimarySecond().calculate(matrix);
        for (int i = 0; i < matrix[0].length; i++) {
            System.out.println(Arrays.toString(ans[i]));
        }
    }

    /**
     * Calculate new matrix by matrixA
     * @param matrixA input matrix which need to be calculated
     * @return new matrix which has been calculate
     */
    public int[][] calculate(int[][] matrixA) {
        int colLen = matrixA[0].length;
        int rowLen = matrixA.length;
        int[][] ans = new int[rowLen][colLen];
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                ans[i][j]+=matrixA[i][j];
                if (i != 0) {
                    ans[i][j] += ans[i - 1][j];
                }
                if (j != 0) {
                    ans[i][j] += ans[i][j - 1];
                }
                if (i != 0 && j != 0) {
                    ans[i][j] += - ans[i - 1][j - 1];
                }
            }
        }
        return ans;
    }
}