1.二叉树节点类
核心是递归,左右交叉的典型代码
public static TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode right = invertTree(root.right);
TreeNode left = invertTree(root.left);
root.left = right;
root.right = left;
return root;
}
2.字符串回文类型
核心是整体思想,将回文作为一个整体字符看待,下个字符相同时,右边扩张,字符不同时,两边扩张
public static String longestPalindrome(String s){
if(s == null || s.length() == 0){
return "";
}
//保存起始位置
char[] str = s.toCharArray();
int maxLong = 0,bengin=0,last=0;
for(int i=0;i<s.length();i++){
//end代表重复字符串的最后一位
int first = i;
int end = i;
//如果f(i) 的值与f(i+1)相等 代表中间部分重复的字符是同一个字符串
while (end<s.length()-1 && str[first] == str[end+1]){
end++;
}
//中间字符串向左右两边扩展,两边堆成
while (first>0&&end<s.length()-1 && str[end+1] == str[first-1]){
first--;
end++;
}
//将end减去i就是回文的起始与结束位置
if(end-first>maxLong){
maxLong = end-first;
bengin = first;
last = end;
}
}
return s.substring(bengin,last+1);
}
3.动态规划的核心是动态转移方程(下一个f(i+1)依赖于f(i))
最大乘积子数组
public static int maxProduct(int[] nums) {
int length = nums.length;
int[] maxs = new int[length];
int[] mins = new int[length];
maxs[0] = mins[0] = nums[0];
int maxResult = maxs[0];
for (int i = 1; i < length; i++) {
maxs[i] = Math.max(maxs[i - 1] * nums[i], Math.max(mins[i - 1] * nums[i], nums[i]));
mins[i] = Math.min(mins[i - 1] * nums[i], Math.min(maxs[i - 1] * nums[i], nums[i]));
maxResult = Math.max(maxResult, maxs[i]);
}
return maxResult;
}