动态规划
单词拆分
给定字符串 s 和单词字典 dict,确定 s 是否可以分成一个或多个以空格分隔的子串,并且这些子串都在字典中存在。
public boolean wordBreak(String s, Set<String> dict) {
// write your code here
int maxLength = getMaxLength(dict);
// 长度为n的单词 有n + 1个切割点 比如: _l_i_n_t_
boolean[] canBreak = new boolean[s.length() + 1];
// 当s长度为0时
canBreak[0] = true;
for(int i = 1; i < canBreak.length; i++){
for(int j = 1; j <= maxLength && j <= i; j++){
//i - j 表示从 i 点开始往前j个点的位置
String str = s.substring(i - j,i);
//如果此str在词典中 并且 str之前的 字符串可以拆分
if(dict.contains(str) && canBreak[i - j]){
canBreak[i] = true;
break;
}
}
}
return canBreak[canBreak.length - 1];
}
private int getMaxLength(Set<String> dict){
int max = 0;
for(String s : dict){
max = Math.max(max,s.length());
}
return max;
}
爬楼梯
假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?
public int climbStairs(int n) {
if (n == 0) return 0;
int[] array = new int[n + 1];
array[0] = 1;
if (array.length > 1) {
array[1] = 1;
}
for(int i = 2; i < array.length; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n];
}
打劫房屋
假设你是一个专业的窃贼,准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是:相邻的房子装着相互联系的防盗系统,且 当相邻的两个房子同一天被打劫时,该系统会自动报警。给定一个非负整数列表,表示每个房子中存放的钱, 算一算,如果今晚去打劫,在不触动报警装置的情况下, 你最多可以得到多少钱 。
public long houseRobber(int[] A) {
if (A.length == 0) return 0;
long[] res = new long[A.length + 1];
res[0] = 0;
res[1] = A[0];
for (int i = 2; i < res.length; i++) {
res[i] = Math.max(res[i - 2] + A[i - 1], res[i - 1]);
}
return res[A.length];
}
编辑距离
给出两个单词word1和word2,计算出将word1 转换为word2的最少操作次数。你总共三种操作方法:插入一个字符、删除一个字符、替换一个字符。
public int minDistance(String word1, String word2) {
// write your code here
int n = word1.length();
int m = word2.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i < n + 1; i++){
dp[i][0] = i;
}
for (int j = 0; j < m + 1; j++){
dp[0][j] = j;
}
for (int i = 1; i< n + 1; i++){
for (int j = 1; j < m + 1; j++){
if (word1.charAt(i - 1) == word2.charAt(j - 1)){
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
}
}
}
return dp[n][m];
}
乘积最大子序列
public int maxProduct(List<Integer> nums) {
// 分别记录正数最大值和负数最小值
int[] max = new int[nums.size()];
int[] min = new int[nums.size()];
min[0] = max[0] = nums.get(0);
int result = nums.get(0);
for (int i = 1; i < nums.size(); i++) {
min[i] = max[i] = nums.get(i);
if (nums.get(i) > 0) {
max[i] = Math.max(max[i], max[i - 1] * nums.get(i));
min[i] = Math.min(min[i], min[i - 1] * nums.get(i));
} else if (nums.get(i) < 0) {
max[i] = Math.max(max[i], min[i - 1] * nums.get(i));
min[i] = Math.min(min[i], max[i - 1] * nums.get(i));
}
result = Math.max(result, max[i]);
}
return result;
}
矩阵
螺旋矩阵
给定一个包含 m x n 个要素的矩阵,(m 行, n 列),按照螺旋顺序,返回该矩阵中的所有要素。
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if(matrix == null || matrix.length == 0) {
return rst;
}
int rows = matrix.length;
int cols = matrix[0].length;
int count = 0;
while(count * 2 < rows && count * 2 < cols){
for (int i = count; i < cols - count; i++) {
rst.add(matrix[count][i]);
}
for (int i = count + 1; i < rows - count; i++) {
rst.add(matrix[i][cols - count - 1]);
}
if (rows - 2 * count == 1 || cols - 2 * count == 1) { // 如果只剩1行或1列
break;
}
for (int i = cols - count - 2; i >= count; i--) {
rst.add(matrix[rows - count - 1][i]);
}
for (int i = rows - count - 2; i >= count + 1; i--) {
rst.add(matrix[i][count]);
}
count++;
}
return rst;
}