Java函数实现常见算法题：斐波那契数列、字符串最长公共子串等
Java作为一种广泛使用的编程语言，其功能丰富，能够实现各种各样的算法题目。本文将介绍常见的算法题：斐波那契数列、字符串最长公共子串等，并给出Java函数实现。
1、斐波那契数列
斐波那契数列是指：1、1、2、3、5、8、13、21、34、……，即数列中某一项的值等于其前两项之和。要求实现一个函数，输入n，返回斐波那契数列第n项的值。
Java函数实现：
public static int fibonacci(int n) {
if(n == 0) {
return 0;
} else if(n == 1) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
2、字符串最长公共子串
给定两个字符串S1和S2，求这两个字符串的最长公共子串。例如，对于字符串“abcde”和“acde”，它们的最长公共子串是“cde”。要求实现一个函数，输入两个字符串，返回它们的最长公共子串。
Java函数实现：
public static String longestCommonSubstring(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int maxLen = 0;// 最长的子串长度
int endIndex = 0; // 最长子串在s1中的末尾位置
int[][] dp = new int[m+1][n+1]; // 初始化二维数组
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1.charAt(i-1) == s2.charAt(j-1)) { // 如果二者字符相等
dp[i][j] = dp[i-1][j-1] + 1; // 则当前公共子串长度等于之前一个的长度加上1
if (dp[i][j] > maxLen) { // 更新最长子串数据
maxLen = dp[i][j];
endIndex = i;
}
} else {
dp[i][j] = 0; // 如果二者字符不等，则当前长度为0
}
}
}
return s1.substring(endIndex-maxLen, endIndex); // 返回最长子串
}
3、二叉树的最近公共祖先
给定一棵二叉树以及两个节点p和q，求它们的最近公共祖先节点。要求实现一个函数，输入两个节点p和q，返回它们的最近公共祖先节点。
Java函数实现：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q); // 遍历左子树，查找p和q的最近公共祖先
TreeNode right = lowestCommonAncestor(root.right, p, q); // 遍历右子树，查找p和q的最近公共祖先
if (left != null && right != null) { // 如果左子树和右子树均可以找到，说明当前节点就是最近公共祖先
return root;
} else if (left != null) { // 如果只在左子树找到p或q，则继续向上查找
return left;
} else { // 如果只在右子树找到p或q，则继续向上查找
return right;
}
}
以上就是本文介绍的三个算法题：斐波那契数列、字符串最长公共子串、二叉树的最近公共祖先，并给出了Java函数实现。这些算法题可以帮助我们提高编程能力，并拓宽我们的专业知识。