第一题: 剑指 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。请问该机器人能够到达多少个格子？

解题思路:

1. 这里使用回溯的解法
2. 从0,0 开始,利用回溯的方法, 从左和右出发, 计算满足的个数
3. 如果下标超出预期 返回0
4. 如果走过的路线, 返回0, 这里需要使用一个boolean数组来进行标记
5. 要满足题目, 行坐标和列坐标的位数之和不能大于k, 例如, 当前坐标为(i , j ), 满足要求 i%10 + i/10 + j%10 + j/10<=k

代码实现:

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。

解题思路:

1. 这里使用动态规划的解法.
2. 初始的时候, 例如 长度为2的时候, 减了之后只能为 1 * 1 = 1, 长度为3的时候, 只能为 1 * 2 = 2.
3. 状态 F(i) : 当前绳长最大可以减成的乘积
4. 状态转移方程: F(i) = Math.max(F(i),F(j-i)*F(j))
5. 初始状态: F(1) = 1, F(2) = 2 , F(3) = 3;
6. 返回结果: F(n)

代码实现:

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。

解题思路:

相比于上一题, 这一题没办法使用动态规划, 因为当你有一个需要取模, 另一个不需要的时候, 会无法比较

1. 这里, 首先把初始的时候解决, 例如n是2和n是3的情况
2. 所以这里尽可能的让n多分出3出来.特殊的4的情况, 4分不分都应有, 因为4=2*2最大.
3. 一直让n进行分解3, 直到n<=4的时候, 此时n为4,3,2中任何一个的时候,都说不用再拆分的了

代码实现:

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）。不得使用库函数，同时不需要考虑大数问题。

解题思路:

这里使用分治的方法,

1. 例如这里的求 x的n次, 如果这里的n是16
   相当于: x -> x^2 -> x^4 -> x^8 -> x^16 这里进行了4次计算得到了
2. 如果这里的n是17
   相当于: x -> x^2 -> x^4 -> x^8 -> x^17 这里也进行了4次计算. 不一样的是 x^8 ->x^17是进行了 平方之后还成了一个x
3. 所以使用递归的方式去进行求得 y = x^(n/2)
4. 如果为偶数, 直接让 x^n = y^2
5. 如果为奇数, 直接让 x^n = y^2 * x

代码实现:

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. 表示数值的字符串

描述:

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

1. 若干空格
2. 一个 小数 或者 整数
3. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
4. 若干空格

小数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（‘+’ 或 ‘-’）
2. 下述格式之一：
   • 至少一位数字，后面跟着一个点 ‘.’
   • 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
   • 一个点 ‘.’ ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

1. （可选）一个符号字符（‘+’ 或 ‘-’）
2. 至少一位数字

部分数值列举如下：

• ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

• ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

解题思路:

1. 首先对字符串进行前后空格去除.
2. 如果去除之后长度为0直接返回false
3. 这里开始根据当前是否存在e进行判断.
   • 如果当前有 e 或 E , 对前部分进行判断, 判断是否为整数或者小数, 对后部分进行判断, 是否为整数
   • 如果当前没有 e 或 E, 对整个部分进行判断, 是否为小数或者整数
   • 如果有多个 e 或 E, 直接返回false
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. 顺时针打印矩阵

描述:
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

解题思路:

1. 首先设定几个点, 从左到右,设置 left ~ right, 从上到下 设置 high ~ low
2. 遍历, 按照顺时间的顺序加入到结果数组中/
   

代码实现:

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;}}