文章目录
第一题: 剑指 Offer 13. 机器人的运动范围
LeetCode: 剑指 Offer 13. 机器人的运动范围
描述:
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
解题思路:
代码实现:
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] tmp = new boolean[m][n];
return dfs(0,0,m,n,k,tmp);
}
public int dfs(int i, int j, int m, int n, int k, boolean[][] tmp) {
if(i >= m || j >=n || tmp[i][j] || (i%10 + i/10 + j%10 + j/10)>k) {
return 0;
}
tmp[i][j] = true;
return 1 + dfs(i+1,j,m,n,k,tmp) + dfs(i,j+1,m,n,k,tmp);
}
}
第二题: 剑指 Offer 14- I. 剪绳子
LeetCode: 剑指 Offer 14- I. 剪绳子
描述:
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
解题思路:
代码实现:
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n+1];
if(n == 2) return 1;
if(n == 3) return 2;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
for(int i = 4; i <= n; i++) {
for(int j = 1; j <= i / 2; j++) {
dp[i] = Math.max(dp[i], dp[j] * dp[i-j]);
}
}
return dp[n];
}
}
第三题: 剑指 Offer 14- II. 剪绳子 II
LeetCode: 剑指 Offer 14- II. 剪绳子 II
描述:
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
解题思路:
代码实现:
class Solution {
public int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
long ans = 1;
// 只要n>4就拆分
while (n > 4) {
ans *= 3;
ans = ans % 1000000007;
n -= 3;
}
// 拆分到 n <= 4的时候, 直接成.
return (int)(ans * n % 1000000007);
}
}
第四题: 剑指 Offer 16. 数值的整数次方
LeetCode: 剑指 Offer 16. 数值的整数次方
描述:
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。不得使用库函数，同时不需要考虑大数问题。
解题思路:
代码实现:
class Solution {
public double myPow(double x, int n) {
long N = n;
return N > 0 ? myPow2(x,n) : 1/myPow2(x,-n);
}
public double myPow2(double x, int n) {
if(n == 0){
return 1;
}
double y = myPow2(x,n / 2);
return n % 2 == 0 ? y * y : y * y * x;
}
}
第五题: 剑指 Offer 20. 表示数值的字符串
LeetCode: 剑指 Offer 20. 表示数值的字符串
描述:
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
- 若干空格
- 一个 小数 或者 整数
- （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
- 若干空格
小数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（‘+’ 或 ‘-’）
- 下述格式之一：
- 至少一位数字，后面跟着一个点 ‘.’
- 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
- 一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（‘+’ 或 ‘-’）
- 至少一位数字
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
解题思路:
代码实现:
class Solution {
public boolean isNumber(String s) {
s = s.trim();
if(s.length() == 0) return false;
StringBuilder sb = new StringBuilder();
boolean flg = true;
for(int i = 0; i < s.length();i++){
if(s.charAt(i) != 'e' && s.charAt(i) != 'E'){
sb.append(s.charAt(i));
}else{
if(!flg) return false;
flg = false;
if(isdecimal(sb)){
sb = new StringBuilder();
continue;
}else{
return false;
}
}
}
if(!flg && isInteger(sb)){
return true;
}
if(flg && (sb.length()==0 || isdecimal(sb)) || isInteger(sb)){
return true;
}else{
return false;
}
}
public boolean isdecimal(StringBuilder s) {
if(s.length() == 0) return false;
int i = 0;
if(s.charAt(0) == '+' || s.charAt(0) == '-'){
i++;
}
boolean flg = true;
boolean tmp = true;
while(i < s.length()) {
if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
tmp = false;
i++;
}else if(flg && s.charAt(i) == '.') {
flg = false;
i++;
}else{
return false;
}
}
if(tmp){
return false;
}
return true;
}
public boolean isInteger(StringBuilder s) {
if(s.length() == 0) return false;
int i = 0;
if(s.charAt(0) == '+' || s.charAt(0) == '-'){
i++;
}
if(s.length() == i) return false;
while(i < s.length()) {
if(!Character.isDigit(s.charAt(i))){
return false;
}
i++;
}
return true;
}
}
第六题: 剑指 Offer 29. 顺时针打印矩阵
LeetCode: 剑指 Offer 29. 顺时针打印矩阵
描述:
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
解题思路:
代码实现:
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[]{};
int high = 0;
int low = matrix.length-1;
int left = 0;
int right = matrix[0].length-1;
int[] ans = new int[matrix.length * matrix[0].length];
int index = 0;
while(left <= right && high <= low) {
for(int i = left; i <= right; i++) {
ans[index++] = matrix[high][i];
}
for(int i = high+1; i <= low; i++) {
ans[index++] = matrix[i][right];
}
if(left < right && high < low){
for(int i = right - 1; i >= left; i--) {
ans[index++] = matrix[low][i];
}
for(int i = low - 1; i > high ; i--) {
ans[index++] = matrix[i][left];
}
}
left++;
right--;
high++;
low--;
}
return ans;
}
}