13 机器人的运动范围
题目描述
地上有一个 m 行和 n 列的方格。
一个机器人从坐标 0,0 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子？
样例1
输入：k=7, m=4, n=5
输出：20
样例2
输入：k=18, m=40, n=40
输出：1484
解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
注意:
0<=m<=50
0<=n<=50
0<=k<=100
解法
从坐标(0, 0) 开始移动，当它准备进入坐标(i, j)，判断是否能进入，如果能，再判断它能否进入 4 个相邻的格子 (i-1, j), (i+1, j), (i, j-1), (i, j+1)。
class Solution {
/**
* 计算能到达的格子数
*
* @param threshold 限定的数字
* @param rows 行数
* @param cols 列数
* @return 能到达的格子数
*/
public int movingCount(int threshold, int rows, int cols) {
boolean[][] visited = new boolean[rows][cols];
return getCount(threshold, rows, cols, 0, 0, visited);
}
private int getCount(int threshold, int rows, int cols, int i, int j, boolean[][] visited) {
if (check(threshold, rows, cols, i, j, visited)) {
visited[i][j] = true;
return 1 + getCount(threshold, rows, cols, i + 1, j, visited)
+ getCount(threshold, rows, cols, i - 1, j, visited)
+ getCount(threshold, rows, cols, i, j + 1, visited)
+ getCount(threshold, rows, cols, i, j - 1, visited);
}
return 0;
}
private boolean check(int threshold, int rows, int cols, int i, int j, boolean[][] visited) {
return i >= 0 && i < rows && j >= 0 && j < cols
&& !visited[i][j] && (getDigitSum(i) + getDigitSum(j) <= threshold);
}
private int getDigitSum(int val) {
int sum = 0;
while (val > 0) {
sum += (val % 10);
val /= 10;
}
return sum;
}
}
14 剪绳子
来源：AcWing
题目描述
给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，n>1 并且 m≥1）。
每段的绳子的长度记为 k[0]、k[1]、……、k[m]。k[0]k[1] … k[m]可能的最大乘积是多少？
例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。
样例
输入：8
输出：18
解法
解法一：动态规划法
时间复杂度O(n²)，空间复杂度O(n)。
f(n) = max{f(n), f(i) * f(n - i)}, i = 1,2..n-1
长度为 2，只可能剪成长度为 1 的两段，因此 f(2)=1
长度为 3，剪成长度分别为 1 和 2 的两段，乘积比较大，因此 f(3) = 2
长度为 n，在剪第一刀的时候，有 n-1 种可能的选择，剪出来的绳子又可以继续剪，可以看出，原问题可以划分为子问题，子问题又有重复子问题。
class Solution {
/**
* 剪绳子求最大乘积
*
* @param length 绳子长度
* @return 乘积最大值
*/
public int maxProductAfterCutting(int length) {
if (length < 4) {
return length - 1;
}
int[] res = new int[length + 1];
res[1] = 1;
res[2] = 2;
res[3] = 3;
for (int i = 4; i <= length; ++i) {
for (int j = 1; j < i / 2 + 1; ++j) {
res[i] = Math.max(res[i], res[j] * res[i - j]);
}
}
return res[length];
}
}
贪心算法
时间复杂度O(1)，空间复杂度O(1)。
贪心策略：
当 n>=5 时，尽可能多地剪长度为 3 的绳子
当剩下的绳子长度为 4 时，就把绳子剪成两段长度为 2 的绳子。
证明：
当 n>=5 时，可以证明 2(n-2)>n，并且 3(n-3)>n。也就是说，当绳子剩下长度大于或者等于 5 的时候，可以把它剪成长度为 3 或者 2 的绳子段。
当 n>=5 时，3(n-3)>=2(n-2)，因此，应该尽可能多地剪长度为 3 的绳子段。
当 n=4 时，剪成两根长度为 2 的绳子，其实没必要剪，只是题目的要求是至少要剪一刀。
class Solution {
/**
* 剪绳子求最大乘积
*
* @param length 绳子长度
* @return 乘积最大值
*/
public int maxProductAfterCutting(int length) {
if (length < 4) {
return length - 1;
}
int timesOf3 = length / 3;
if (length % 3 == 1) {
--timesOf3;
}
int timesOf2 = (length - timesOf3 * 3) >> 1;
return (int) (Math.pow(2, timesOf2) * Math.pow(3, timesOf3));
}
}
15 二进制中1的个数
来源：AcWing
题目描述
输入一个 32 位整数，输出该数二进制表示中 1 的个数。
注意：
- 负数在计算机中用其绝对值的补码来表示。
样例1
输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。
样例2
输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
一共有31个1。
解法
解法一
利用整数 1，依次左移每次与 n 进行与运算，若结果不为0，说明这一位上数字为 1，++cnt。
此解法 i 需要左移 32 次。
不要用 n 去右移并与 1 进行与运算，因为 n 可能为负数，右移时会陷入死循环。
class Solution {
/**
* 求二进制中1的个数
*
* @param n 整数
* @return 该整数的二进制中1的个数
*/
public int NumberOf1(int n) {
int i = 1;
int cnt = 0;
while (i != 0) {
if ((n & i) != 0) {
++cnt;
}
i <<= 1;
}
return cnt;
}
}
解法二（推荐）
运算 (n - 1) & n，直至 n 为 0。运算的次数即为 n 的二进制中 1 的个数。
因为 n-1 会将 n 的最右边一位 1 改为 0，如果右边还有 0，则所有 0 都会变成 1。结果与 n 进行与运算，会去除掉最右边的一个 1。
举个栗子：
若 n = 1100，
n - 1 = 1011
n & (n - 1) = 1000
即：把最右边的 1 变成了 0。
把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于把整数的二进制表示中最右边的 1 变成 0。很多二进制的问题都可以用这种思路解决。
class Solution {
/**
* 求二进制中1的个数
*
* @param n 整数
* @return 该整数的二进制中1的个数
*/
public int NumberOf1(int n) {
int cnt = 0;
while (n != 0) {
++cnt;
n &= (n - 1);
}
return cnt;
}
}
解法三
利用 Java API。
class Solution {
/**
* 求二进制中1的个数
*
* @param n 整数
* @return 该整数的二进制中1的个数
*/
public int NumberOf1(int n) {
return Integer.bitCount(n);
}
}
16 数值的整数次方
来源：AcWing
题目描述
实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。
不得使用库函数，同时不需要考虑大数问题。
注意：
- 不会出现底数和指数同为 0 的情况。
样例1
输入：10 ，2
输出：100
样例2
输入：10 ，-2
输出：0.01
解法
注意判断值数是否小于 0。另外 0 的 0 次方没有意义，也需要考虑一下，看具体题目要求。
解法一
时间复杂度 O(N)。
class Solution {
/**
* 计算数值的整数次方
*
* @param base 底数
* @param exponent 指数
* @return 数值的整数次方
*/
public double Power(double base, int exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
double res = 1;
for (int i = 0; i < Math.abs(exponent); ++i) {
res *= base;
}
return exponent > 0 ? res : 1 / res;
}
}
解法二
递归求解，每次 exponent 缩小一半，时间复杂度为 O(log N)。
class Solution {
/**
* 计算数值的整数次方
*
* @param base 底数
* @param exponent 指数
* @return 数值的整数次方
*/
public double Power(double base, int exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
double res = Power(base, Math.abs(exponent) >> 1);
res *= res;
if ((exponent & 1) == 1) {
res *= base;
}
return exponent > 0 ? res : 1 / res;
}
}
17 打印从1到最大的n位数
来源：无
题目描述
输入数字 n，按顺序打印出从 1 最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。
解法
此题需要注意 n 位数构成的数字可能超出最大的 int 或者 long long 能表示的范围。因此，采用字符数组来存储数字。
解法一
对字符数组表示的数进行递增操作；
输出数字（0开头的需要把0去除）。
class Solution {
/**
* 打印从1到最大的n位数
*
* @param n n位数
*/
public void print1ToMaxOfNDigits(int n) {
if (n < 1) {
return;
}
char[] chars = new char[n];
Arrays.fill(chars, '0');
while (increment(chars)) {
printNumber(chars);
}
}
/**
* 打印字符数组表示的数字（需要省略前n个0）
*
* @param chars 字符数组
*/
private void printNumber(char[] chars) {
int i = 0, n = chars.length;
for (; i < n; ++i) {
if (chars[i] != '0') {
break;
}
}
StringBuilder sb = new StringBuilder();
for (; i < n; ++i) {
sb.append(chars[i]);
}
System.out.println(sb.toString());
}
private boolean increment(char[] chars) {
int n = chars.length;
int carry = 1;
for (int i = n - 1; i >= 0; --i) {
int sum = chars[i] - '0' + carry;
if (sum > 9) {
if (i == 0) {
return false;
}
chars[i] = '0';
} else {
++chars[i];
break;
}
}
return true;
}
}
解法二
利用递归全排列，设置每一位，设置完之后，打印出来。
class Solution {
/**
* 打印从1到最大的n位数
*
* @param n n位数
*/
public void print1ToMaxOfNDigits(int n) {
if (n < 1) {
return;
}
char[] chars = new char[n];
print1ToMaxOfNDigits(chars, n, 0);
}
private void print1ToMaxOfNDigits(char[] chars, int n, int i) {
if (i == n) {
printNumber(chars);
return;
}
// 每一位分别设置从0到9
for (int j = 0; j < 10; ++j) {
chars[i] = (char) (j + '0');
print1ToMaxOfNDigits(chars, n, i + 1);
}
}
/**
* 打印字符数组表示的数字（需要省略前n个0）
*
* @param chars 字符数组
*/
private void printNumber(char[] chars) {
int i = 0, n = chars.length;
for (; i < n; ++i) {
if (chars[i] != '0') {
break;
}
}
StringBuilder sb = new StringBuilder();
for (; i < n; ++i) {
sb.append(chars[i]);
}
System.out.println(sb.toString());
}
}
18.1 在O(1)时间删除链表节点
来源：AcWing
题目描述
给定单向链表的一个节点指针，定义一个函数在 O(1) 时间删除该节点。
假设链表一定存在，并且该节点一定不是尾节点。
样例
输入：链表 1->4->6->8
删掉节点：第2个节点即6（头节点为第0个节点）
输出：新链表 1->4->8
解法
判断要删除的节点是否是尾节点：
若是，那么需要遍历链表，找到节点的前一个节点，让前一个节点指向
null，时间复杂度为O(n)；若不是，把下一个节点的值赋给该节点，该节点指向下下个节点，时间复杂度为
O(1)。
题目中说明了节点不是尾节点，那么符合第二种情况。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 删除链表的节点
*
* @param node 要删除的节点
*/
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
18.2 删除链表中重复的节点
来源：AcWing
题目描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。
样例1
输入：1->2->3->3->4->4->5
输出：1->2->5```
样例2
输入：1->1->1->2->3
输出：2->3
### 解法
#### 解法一：递归
```java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 删除链表重复的节点
*
* @param head 链表头节点
* @return 删除重复节点后的链表
*/
public ListNode deleteDuplication(ListNode head) {
if (head == null || head.next == null) {
return head;
}
if (head.next.val == head.val) {
if (head.next.next == null) {
return null;
}
if (head.next.next.val == head.val) {
return deleteDuplication(head.next);
}
return deleteDuplication(head.next.next);
}
head.next = deleteDuplication(head.next);
return head;
}
}
解法二：非递归
pre 始终指向下一个不重复的节点。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 删除链表重复的节点
*
* @param head 链表头节点
* @return 删除重复节点后的链表
*/
public ListNode deleteDuplication(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null, cur = head;
while (cur != null) {
if (cur.next != null && cur.next.val == cur.val) {
int val = cur.val;
while (cur.next != null && cur.next.val == val) {
cur = cur.next;
}
if (pre == null) {
head = cur.next;
} else {
pre.next = cur.next;
}
} else {
pre = cur;
}
cur = cur.next;
}
return head;
}
}
19 正则表达式匹配
来源：AcWing
题目描述
请实现一个函数用来匹配包括 '.' 和 '*' 的正则表达式。
模式中的字符 '.' 表示任意一个字符，而 '*' 表示它前面的字符可以出现任意次（含 0 次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串 "aaa" 与模式 "a.a" 和 "ab*ac*a" 匹配，但是与 "aa.a" 和 "ab*a" 均不匹配。
样例
输入：
s="aa"
p="a*"
输出:true
解法
判断模式中第二个字符是否是 *：
若是，看如果模式串第一个字符与字符串第一个字符是否匹配：
若不匹配，在模式串上向右移动两个字符
j+2，相当于 a* 被忽略。若匹配，字符串后移
i+1。此时模式串可以移动两个字符j+2，也可以不移动j。若不是，看当前字符与模式串的当前字符是否匹配，即
str[i] == pattern[j] || pattern[j] == '.'：若匹配，则字符串与模式串都向右移动一位，
i+1，j+1。若不匹配，返回 false。
class Solution {
/**
* 判断字符串是否与模式串匹配
*
* @param s 字符串
* @param p 模式串
* @return 是否匹配
*/
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
char[] str = s.toCharArray();
char[] pattern = p.toCharArray();
return match(str, 0, str.length, pattern, 0, pattern.length);
}
private boolean match(char[] str, int i, int len1, char[] pattern, int j, int len2) {
if (i == len1 && j == len2) {
return true;
}
// pattern已经走到最后，而str还有未匹配的
// str走到最后，而pattern还没走完，此时是允许的
if (j == len2) {
return false;
}
if (j + 1 < len2 && pattern[j + 1] == '*') {
if (i < len1 && (str[i] == pattern[j] || pattern[j] == '.')) {
return match(str, i, len1, pattern, j + 2, len2)
|| match(str, i + 1, len1, pattern, j, len2)
|| match(str, i + 1, len1, pattern, j + 2, len2);
}
return match(str, i, len1, pattern, j + 2, len2);
}
if (i < len1 && (str[i] == pattern[j] || pattern[j] == '.')) {
return match(str, i + 1, len1, pattern, j + 1, len2);
}
return false;
}
}
20 表示数值的字符串
来源：AcWing
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
注意:
小数可以没有整数部分，例如.123等于0.123；
小数点后面可以没有数字，例如233.等于233.0；
小数点前面和后面可以有数字，例如233.666;
当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；
当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4;
样例：
输入: "0"
输出: true
解法
利用正则表达式匹配即可。
[] ： 字符集合
() ： 分组
? ： 重复 0 ~ 1
+ ： 重复 1 ~ n
* ： 重复 0 ~ n
. ： 任意字符
\. ： 转义后的 .
\d ： 数字
public class Solution {
/**
* 判断是否是数字
* @param str
* @return
*/
public boolean isNumeric(char[] str) {
return str != null
&& str.length != 0
&& new String(str).matches("[+-]?\d*(\.\d+)?([eE][+-]?\d+)?");
}
}
21 调整数组顺序使奇数位于偶数前面
来源：AcWing
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解法
解法一
计算出奇数的个数，就很容易写出来了。
import java.util.Arrays;
public class Solution {
/**
* 调整数组元素顺序，使得奇数元素位于偶数元素前面，且保证奇数和奇数，偶数和偶数之间的相对位置不变。
* @param array 数组
*/
public void reOrderArray(int [] array) {
if (array == null || array.length < 2) {
return;
}
int numsOfOdd = 0;
for (int val : array) {
if (val % 2 == 1) {
++numsOfOdd;
}
}
int[] bak = Arrays.copyOf(array, array.length);
int i = 0, j = numsOfOdd;
for (int val : bak) {
if (val % 2 == 1) {
array[i++] = val;
} else {
array[j++] = val;
}
}
}
}
解法二
import java.util.Arrays;
public class Solution {
public void reOrderArray(int [] array) {
if (array == null || array.length < 2) {
return;
}
Integer[] bak = new Integer[array.length];
Arrays.setAll(bak, i -> array[i]);
Arrays.sort(bak, (x, y) -> (y & 1) - (x & 1));
Arrays.setAll(array, i -> bak[i]);
}
}
扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有
推荐阅读
