刷题练习2021-12-15
数组拷贝：
int scores[] = new int[] { 57, 81, 68, 75, 91, 66, 75, 84 };
// 复制原数组的前5个元素到newScores数组中
int newScores[] = Arrays.copyOfRange(scores, 0, 5);
System.out.println(Arrays.toString(newScores));
数据结构：剑指 Offer 05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
限制：0 <= s 的长度 <= 10000
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(int i=0;i<s.length();i++) {
if(s.charAt(i)==' ') {
sb.append("%20");
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
System.out.println(new Solution().replaceSpace(s));
}
}
动态规划：剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：0 <= num < 231
递归：
class Solution {
public int translateNum(int num) {
return translateNum(String.valueOf(num));
}
public int translateNum(String s) {
if(s.length()<=1) return 1;
if(s.charAt(0)=='0') return translateNum(s.substring(1));
if(s.charAt(0)<'2'||(s.charAt(0)=='2'&&s.charAt(1)<='5')) return translateNum(s.substring(2))+translateNum(s.substring(1));
else return translateNum(s.substring(1));
}
}
包括路径的递归：
package cn.orzlinux.nettysource;
import java.util.*;
class Solution {
List<String> result = new LinkedList<>();
StringBuilder sb = new StringBuilder();
public List<String> translateNum(int num) {
translateNum(String.valueOf(num));
return result;
}
public void translateNum(String s) {
if(s.length()==0) {
result.add(sb.toString());
}
else if(s.length()==1||s.charAt(0)=='0') {
sb.append((char)(s.charAt(0)+'a'-'0'));
translateNum(s.substring(1));
sb.delete(sb.length()-1,sb.length());
}
else if(s.charAt(0)<'2'||(s.charAt(0)=='2'&&s.charAt(1)<='5')) {
sb.append((char)(Integer.parseInt(s.substring(0,2))+'a'));
translateNum(s.substring(2));
sb.delete(sb.length()-1,sb.length());
sb.append((char)(s.charAt(0)+'a'-'0'));
translateNum(s.substring(1));
sb.delete(sb.length()-1,sb.length());
}
else {
sb.append((char)(s.charAt(0)+'a'-'0'));
translateNum(s.substring(1));
sb.delete(sb.length()-1,sb.length());
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
System.out.println(new Solution().translateNum(num));
}
}
动态规划：
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length()+2];
dp[0] = dp[1] = 1;
for(int i=1;i<s.length();i++) {
if(s.charAt(i-1)=='0') {
dp[i+1]+=dp[i];
}
else if(s.charAt(i-1)<'2'||(s.charAt(i-1)=='2'&&s.charAt(i)<='5')) {
dp[i+1] = dp[i]+dp[i-1];
} else {
dp[i+1]+=dp[i];
}
}
return dp[s.length()];
}
}
搜索与回溯：
1. 剑指 Offer 12. 矩阵中的路径
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
解答：
class Solution {
public boolean exist(char[][] board, String word) {
boolean[][] visited = new boolean[board.length][board[0].length];
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[0].length;j++) {
if(exist0(board,visited,word,i,j)) {
return true;
}
}
}
return false;
}
private boolean exist0(char[][] board, boolean[][] visited,String word,int i,int j) {
if(word.length()==0) return true;
if(i<0||j<0||i>=board.length||j>=board[0].length||visited[i][j]||board[i][j]!=word.charAt(0)) return false;
visited[i][j] = true;
boolean result = exist0(board,visited,word.substring(1),i+1,j)||
exist0(board,visited,word.substring(1),i-1,j)||
exist0(board,visited,word.substring(1),i,j+1)||
exist0(board,visited,word.substring(1),i,j-1);
visited[i][j] = false;
return result;
}
}
2 剑指 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：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：1
提示：
1 <= n,m <= 100
0 <= k <= 20
解答：
class Solution {
private int count = 0;
public int movingCount(int m, int n, int k) {
movingCount0(m,n,k,new boolean[m][n],0,0);
return count;
}
private void movingCount0(int m,int n,int k,boolean[][] visited,int i,int j) {
if(i<0||j<0||i>=m||j>=n||visited[i][j]) return;
visited[i][j] = true;
if(sumOfEveryPos(i)+sumOfEveryPos(j)>k) return;
count+=1;
movingCount0(m,n,k,visited,i+1,j);
movingCount0(m,n,k,visited,i,j+1);
movingCount0(m,n,k,visited,i-1,j);
movingCount0(m,n,k,visited,i,j-1);
}
private int sumOfEveryPos(int n) {
int result = 0;
int tmp;
while(n!=0) {
tmp = n%10;
result+=tmp;
n = n/10;
}
return result;
}
}
分治：重建二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// Output: [3,9,20,null,null,15,7]
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree0(preorder,inorder,0,preorder.length-1,0,preorder.length-1);
}
private TreeNode buildTree0(int[] preorder,int[] inorder,int start,int end,int left,int right) {
if(start>end) return null;
if(start==end) return new TreeNode(inorder[start]);
int i;
for(i=start;i<=end;i++) {
if(inorder[i]==preorder[left]) break;
}
TreeNode node = new TreeNode(inorder[i]);
node.left = buildTree0(preorder,inorder,start,i-1,left+1,left+i-start);
node.right = buildTree0(preorder,inorder,i+1,end,left+i-start+1,right);
return node;
}
}