剑指offer三五题-0

题目描述

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

题解

遍历链表,将每次遍历的值压栈,然后依次出栈到ArrayList

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while(listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }

        ArrayList<Integer> list = new ArrayList<>();
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }

        return list;
    }
}

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

题解

从(0,0)开始遍历,用布尔二维数组标记已访问的格子,递归计算上下左右相邻的格子的数位和,直到所有格子都被访问过。

public class Solution {
    public int movingCount(int threshold, int rows, int cols)
    {
        if(rows<=0||cols<=0){
            return 0;
        }

        boolean[][] isVisited = new boolean[rows][cols];
        int count = movingCountCore(threshold, rows, cols, 0, 0, isVisited);
        return count;
    }

    private int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[][] isVisited){
        if(row < 0||col<0||row>=rows||col>=cols||cal(row)+cal(col)>threshold||isVisited[row][col])
            return 0;

        isVisited[row][col]=true;
        return 1+movingCountCore(threshold, rows, cols, row-1, col, isVisited)
            +movingCountCore(threshold, rows, cols, row+1, col, isVisited)
            +movingCountCore(threshold, rows, cols, row-1, col, isVisited)
            +movingCountCore(threshold, rows, cols, row, col+1, isVisited)
            +movingCountCore(threshold, rows, cols, row, col-1, isVisited);
    }

    private int cal(int num){
        int sum = 0;
        while(num>0){
            sum += num%10;
            num /=10;
        }
        return sum;
    }
}

题目描述

给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1,m<=n),每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

题解

算术平均数大于几何平均数,令乘积为$f(n) = x^\frac{n}{x}$,求导得极大值点为$x = e$,又$x$只能取整数,即$$f(2) = 2^\frac{n}{2},f(3) = 3^\frac{n}{3}$$,当$n>3$时,$f(3)>f(2)$,故,$x$取3,但绳子的份数$\frac{n}{x}$需取整数,故分段讨论。

对$\frac{n}{x}$向下取最大整数,绳子剩下的部分则为0,1,2,当得0时,直接返回$3^\frac{n}{3}$,当得1时,返回$3^{\frac{n}{3}-1}* 4$,当得2时,返回$3^\frac{n}{3} * 2$。

public class Solution {
    public int cutRope(int target) {
        if(target <= 0)
            return 0;
        if(target == 1 || target == 2)
            return 1;
        if(target == 3)
            return 2;

        int m = target%3;
        switch(m){
            case 0:
                return (int)Math.pow(3, target / 3);
            case 1:
                return (int)Math.pow(3, target / 3 - 1) * 4;
            case 2:
                return (int)Math.pow(3, target /3) * 2;
        }
        return 0;
    }
}

题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

题解

从数组的左下方值开始比较,若该值大于目标,则向上一格,再比较,若该值小于目标,则向右一格,再比较,直到找着目标,并返回true。若数组为空,则返回false。

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null){
            return false;
        }
        int rows = array.length;
        int cols = array[0].length;
        if(rows <= 0 || cols <=0){
            return false;
        }
        int row = rows - 1;
        int col = 0;
        while(row >=0 && col <cols){
            if(array[row][col]>target){
                row--;
            }
            else if(array[row][col]<target){
                col++;
            }
            else
                return true;
        }
        return false;
    }
}

题目描述

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

题解

方法一:

构造一个新的字符串,遍历旧字符串,遇到非空格的字符,则将其添加到新字符串的尾部,遇到空格字符则将「%20」添加到新字符串的尾部。

方法二:

直接用replace方法将空格替换为「%20」。

import java.util.*;

public class Solution {
    public String replaceSpace(StringBuffer str) {
        //return str.toString().replace(" ", "%20");
        StringBuilder so = new StringBuilder();
        for(int i = 0; i < str.length(); i++){
            if(str.charAt(i) != ' '){
                so.append(str.charAt(i));
            }
            else{
                so.append("%20");
            }
        }
        return so.toString();
    }
}

   转载规则


《剑指offer三五题-0》 帅张 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录