思路分析：
这道题属于贪心算法，但本质仍然是动态规划。对于这样一个棋盘，到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到，要么是前一列(i,j-1)向右移动一列得到
这个计算过程中有三个特殊情况
情况1：如果是起点，那么直接忽略即可
情况2：如果处在第一行，那么由于是第一行，所以从起点走，它只可能是向右不断走得到的
情况3：如果处在第一列，那么由于是第一列，所以从起点走，它只可能是向下不断走的到的
其余情况均是即可向右走，也可以向下走
代码：
import java.util.*; public class Bonus { public int getMost(int[][] board) { // write code here int row = board.length; int col = board[0].length; // gifts[i][j]表示从起点到i,j这一点中某条路径代表的礼物价值值总和 int[][] gifts = new int[row][col]; gifts[0][0] = board[0][0]; for (int i = 1; i < row; ++i) { gifts[i][0] = gifts[i - 1][0] + board[i][0]; } for (int j = 1; j < col; ++j) { gifts[0][j] = gifts[0][j - 1] + board[0][j]; } for (int i = 1; i < row; ++i) { for (int j = 1; j < col; ++j) { // 对于这样一个棋盘，到达(i,j)这一点要么是上一行(i-1,j)向下移动一行得到，要么是前一列(i,j-1)向右移动一列得到 gifts[i][j] = Math.max(gifts[i - 1][j], gifts[i][j - 1]) + board[i][j]; // board[i][j]代表此点上的礼物价值 // gifts[i][j]代表从起点到i,j这一点所经过路径代表的礼物价值总和 } } return gifts[row - 1][col - 1]; } }
最长不含重复字符的子字符串
step 1：dp[i]dp[i]dp[i]表示以下标i结尾的字符串最长不含重复子串的长度，用哈希表记录是否重复出现字符，并记录其下标位置。
step 2：遍历字符串，哈希表中没有出现过的就不是重复，因此考虑dp[i]=dp[i−1]+1，即在前一个字符的基础上加上它。
step 3：哈希表中出现过的，这是重复的字符，考虑i−map[s[i]]，但是为了防止中间出现其他重复的字符，还是应该考虑它的前一个字符的基础，因此实际转移方程为dp[i]=min(dp[i−1]+1,i−map[s[i−1]])——map[s[i - 1]]
step 4：遍历过程中遇到的字符都要加入哈希表，同时维护最大的长度。
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ public int lengthOfLongestSubstring (String str) { // write code here int[] dp= new int[str.length()]; char[] s = str.toCharArray(); dp[0] = 1; // dp[i]代表以s[i]结尾的的字符串的最长子字符串的长度 Map<Character, Integer> map = new HashMap<>(); map.put(str.charAt(0), 0); int res = 1, len = 0; // 当字符串只有一个字符，程序不会执行for循环，此时要进行特判 for (int i = 1; i < str.length(); ++i) { if (!map.containsKey(str.charAt(i))) { dp[i] = dp[i - 1] + 1; } else { dp[i] = Math.min(dp[i - 1] + 1, i - map.get(str.charAt(i))); // dp[i] = i - map.get(str.charAt(i)); } map.put(str.charAt(i), i); res = Math.max(dp[i], res); } return res; } }
合唱团
import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = null; while((str = bf.readLine()) != null) { int n = Integer.parseInt(str); String num = bf.readLine(); String[] nums = num.split(" "); int[] a = new int[nums.length]; for (int i = 0; i < nums.length; ++i) { a[i] = Integer.parseInt(nums[i]); } String str2 = bf.readLine(); String[] strs2 = str2.split(" "); int k = Integer.parseInt(strs2[0]); int d = Integer.parseInt(strs2[1]); long[][] maxVal = new long[n + 1][k + 1]; long[][] minVal = new long[n + 1][k + 1]; // maxVal[i][j]代表当最后一个是第i个同学，共选了j个同学所得到了最大能力值 // 初始化 for (int i = 1; i <= n; ++i) { maxVal[i][1] = minVal[i][1] = a[i - 1]; } long ret = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { // 约束条件 for (int m = i - 1; m >= Math.max(i - d, 1); --m) { maxVal[i][j] = Math.max(maxVal[i][j], Math.max(maxVal[m][j - 1] * a[i - 1], minVal[m][j - 1] * a[i - 1])); minVal[i][j] = Math.min(minVal[i][j], Math.min(minVal[m][j - 1] * a[i - 1], maxVal[m][j - 1] * a[i - 1])); } } ret = Math.max(ret, maxVal[i][k]); } System.out.println(ret); } } }
三、数组篇
顺时针打印矩阵
解题思路
1、声明四个变量，分别为左界限 L，右界限 R，上界限 T，下界限 B。
2、先从左往右遍历，然后从上到下，从右往左，最后从下往上。循环这个操作，每次从左往右遍历完，T += 1，说明最上面这一行已经遍历过了，上界限 T 应该往下移了；从上往下遍历完， R -= 1，说明最右边这一列已经遍历过了，右界限 R 应该往左移了；其他遍历操作也是如此。当四个界限中，T 和 B，或者 L 和 R 碰撞在一起，说明遍历完成，退出循环。
3、值得注意的是，需要考虑非方阵的情况，比如矩阵 A[3][4]，因为行数比列数少，T 和 B 碰撞时 L 和 R 仍未碰撞，若此时还在循环体内，会继续执行遍历操作。所以在循环体内，需要时刻监控界限碰撞的情况。
import java.util.ArrayList; public class Solution { public ArrayList<Integer> printMatrix(int [][] matrix) { int t = 0; int b = matrix.length - 1, row = matrix.length; int l = 0; int r = matrix[0].length - 1, col = matrix[0].length; ArrayList<Integer> list = new ArrayList<>(); while (t <= b && l <= r) { // 从左到右, 需要注意我们的边界都是动态变化的 for (int i = l; i <= r; ++i) { list.add(matrix[t][i]); } ++t; // 第一行遍历完了，上边界要发生变化 if (t > b || l > r) break; // 从上到下 for (int j = t; j <= b; ++j) { list.add(matrix[j][r]); } --r; if (t > b || l > r) break; // 从右到左 for (int i = r; i >= l; --i) { list.add(matrix[b][i]); } --b; if (t > b || l > r) break; // 从下到上 for (int j = b; j >= t; --j) { list.add(matrix[j][l]); } ++l; } return list; } }
