牛客网算法——名企高频面试题143题（1）

题目描述

字符串旋转:

给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（都不为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。

例如：如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同返回true。

package 牛客面试必会100题;

import org.junit.Test;

/**
 * @Classname 旋转字符串
 * @Description TODO  字符串旋转:
 * 给定两字符串A和B，如果能将A从中间某个位置分割为左右两部分字符串（都不为空串），并将左边的字符串移动到右边字符串后面组成新的字符串可以变为字符串B时返回true。
 * 例如：如果A=‘youzan’，B=‘zanyou’，A按‘you’‘zan’切割换位后得到‘zanyou’和B相同返回true。
 * @Date 2020/12/7 10:11
 * @Created by xjl
 */
public class 旋转字符串 {
    /**
     * @description TODO 利用的subString的函数来实现
     * @param: A
     * @param: B
     * @date: 2020/12/7 10:13
     * @return: boolean
     * @author: xjl
     */
    public boolean solve(String A, String B) {
        return B.equals(A.substring((A.length()) / 2) + A.substring(0, A.length() / 2));
    }

    @Test
    public void test() {
        boolean solve = solve("youzan", "zanyou");
        System.out.println(solve);
    }
}

 题目描述

给定一个整型矩阵matrix，请按照顺时针转圈的方式打印它。

第一：主要是考虑到 vis[][] 表示是否已访问过了：

boolean[][] vis = new boolean[row][cloum];

第二设置开始的位置

int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};

第三设置初始的位置

int x = 0;
int y = 0;

第四是判断时候是应该专向了，

if (nx >= 0 && nx < row && ny >= 0 && ny < cloum && !vis[nx][ny]) 

package 牛客面试必会100题;

import org.junit.Test;

import java.util.ArrayList;

/**
 * @Classname 转圈打印矩阵
 * @Description TODO 这个和螺旋矩阵是一样的思想
 * @Date 2020/12/7 13:37
 * @Created by xjl
 */
public class 转圈打印矩阵 {

    public int[] printMatrix(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) return null;
        int n = matrix[0].length;
        boolean[][] vis = new boolean[m][n];
        //表示方向 已经是设计好的
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        //表示的是起始位置
        int x = 0;
        int y = 0;
        //表示转向的标志
        int d = 0;
        //存放结果
        ArrayList list = new ArrayList();
        while (list.size() < m * n) {
            list.add(matrix[x][y]);
            vis[x][y] = true;
            int nx = x + dx[d];
            int ny = y + dy[d];
            //表示的是可以开始方向
            if (nx < m && nx >= 0 && ny < n && ny >= 0 && !vis[nx][ny]) {
                x = nx;
                y = ny;
            } else {
                d = (d + 1) % 4;
                nx = x + dx[d];
                ny = y + dy[d];
                x = nx;
                y = ny;
            }
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

    @Test
    public void test() {
        int[] arr = printMatrix(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}});
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

class Solution {
    public int translateNum(int num) {
            return slove(String.valueOf(num).toCharArray(),0);
    }
    private int slove(char[] CharArray, int start) {
        //终端条件
        if (start >= CharArray.length) {
            return 1;
        }
        //考虑一个数字翻译为一种的是时候
        int res1 = slove(CharArray, start + 1);
        //两个翻译到一起的时候
        int res2 = 0;
        if ((start < CharArray.length - 1) && ((CharArray[start] - '0') * 10 + (CharArray[start + 1] - '0')>9&&(CharArray[start] - '0') * 10 + (CharArray[start + 1] - '0') < 26)) {
            res2 = slove(CharArray, start + 2);
        }
        return res1 + res2;
    }
}

/**
     * @description TODO 采用的是的dfs的算法实现
     * @param: num
     * @date: 2020/12/7 15:08
     * @return: int
     * @author: xjl
     */
    public int translateNum2(int num) {
        //将字符串转化为数字
        String str = String.valueOf(num);
        //dfs遍历字符串求解
        return dfs(str, 0);
    }

    //表示从index位置开始有好多种翻译方法
    public int dfs(String str, int index) {
        //如果当前的下标大于等于字符串的长度 - 1，则说明当前位置是由上一次跳到此处的，则直接返回1
        if (index >= str.length() - 1)
            return 1;
        //先求解每一次都翻译一个字符的方法数
        int res = dfs(str, index + 1);
        //以当前字符的下标为开始，截取两位，判断这位组成的数字是否在10~25之间
        //如果在这一次就可以直接翻译两个字符，然后从两个字符后面的位置开始翻译
        String temp = str.substring(index, index + 2);
        if (temp.compareTo("10") >= 0 && temp.compareTo("25")  9 && currentNum < 26) {
                if (i - 2 < 0) {
                    dp[i]++;
                } else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[len - 1];
    }

    public int translateNum(int num) {
        String s = String.valueOf(num);
        int len = s.length();
        if (len < 2) {
            return len;
        }
        char[] charArray = s.toCharArray();
        int[] dp = new int[len];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 1; i < len; i++) {
            dp[i + 1] = dp[i];
            int currentNum = 10 * (charArray[i - 1] - '0') + (charArray[i] - '0');
            if (currentNum > 9 && currentNum < 26) {
                dp[i + 1] = dp[i] + dp[i - 1];
            }
        }
        return dp[len];
    }

 题目描述

有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字，返回有多少种可能的译码结果

import java.util.*;


public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        return slove(nums.toCharArray(), 0);
    }
    private int slove(char[] CharArray, int start) {
        //终端条件
        if (start >= CharArray.length) {
            return 1;
        }
         if (CharArray[start]=='0'){
            return 0;
        }
        //考虑一个数字翻译为一种的是时候
        int res1 = slove(CharArray, start + 1);
        //两个翻译到一起的时候
        int res2 = 0;
        if ((start < CharArray.length - 1) && ((CharArray[start] - '0') * 10 + (CharArray[start + 1] - '0') > 9 && (CharArray[start] - '0') * 10 + (CharArray[start + 1] - '0') 1, 'b->2', ... , 'z->26'。
 * 现在给一串数字，返回有多少种可能的译码结果
 * @Date 2020/12/7 14:15
 * @Created by xjl
 */
public class 数字翻译的的方式 {

    public int solve(String nums) {
        return back(nums.toCharArray(), 0);
    }

    // 递归函数  将大问题化解为小问题
    public int back(char[] nums, int start) {
        //当start走到终点时，证明已经解码完毕，直接返回1
        if (start == nums.length) {
            return 1;
        }
        //当字符为0的时候，0没对应的解码，所以直接返回0 (此路解码废掉)
        if (nums[start] == '0')
            return 0;
        //每次解码一个字符
        int res1 = back(nums, start + 1);
        int res2 = 0;
        //如果当前字符等于1 或者当前字符加上下一个字符合起来小于等于26 则可以一次解码两个字符
        if ((start < nums.length - 1) && (nums[start] == '1' || (nums[start] == '2' && nums[start + 1]