面试算法题

1：连续子序列最大乘积 <a href="https://blog.csdn.net/seagal890/article/details/91358875">https://blog.csdn.net/seagal890/article/details/91358875</a> 有可能前面负数乘以负数很大
<pre class="blockcode"><code class="language-java">package com.bean.algorithmbasic;

public class MaximumProductSubarray {

public static int maxProduct(int[] nums) {
 //如果数组为null或者数组长度为0，直接返回0.
 if (nums == null || nums.length == 0) {
 return 0;
 }

 //开始将A[0]分别设置为：最大值、最小值，和最终的返回结果。
 int max = nums[0], min = nums[0], result = nums[0];
 //从数组的第二个元素开始取值
 for (int i = 1; i < nums.length; i++) {
 int temp = max;
 //状态转换方程的定义和实现
 max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
 min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
 //始终用result存放最大值，以返回结果。
 if (max > result) {
 result = max;
 }
 }
 return result;
}

public static void main(String[] args) {
 // TODO Auto-generated method stub
 int[] arraydemo= {2,5,-1,2,-1};
 int RESULT=maxProduct(arraydemo);
 System.out.println("RESULT IS: "+RESULT);
}

}</code></pre>
2：快速排序选取topk：<a href="https://www.lmlphp.com/user/5986/article/item/340698/">https://www.lmlphp.com/user/5986/article/item/340698/</a> 二分思想，如果小的话直接返回，否则选择排序长度
3：Java 蒙特卡洛算法求圆周率近似值实例详解 <a href="https://www.jb51.net/article/123408.htm">https://www.jb51.net/article/123408.htm</a>
<pre class="blockcode"><code class="language-java">package com.xu.main;
import java.util.Scanner;
public class P9_1 {
static double MontePI(int n) {
 double PI;
 double x, y;
 int i, sum;
 sum = 0;
 for (i = 1; i < n; i++) {
x = Math.random();
y = Math.random();
if ((x * x + y * y) <= 1) {
sum++;
}
 }
 PI = 4.0 * sum / n;
 return PI;
}
public static void main(String[] args) {
 int n;
 double PI;
 System.out.println("蒙特卡洛概率算法计算圆周率:");
 Scanner input = new Scanner(System.in);
 System.out.println("输入点的数量：");
 n = input.nextInt();
 PI = MontePI(n);
 System.out.println("PI="+PI);
}
}</code></pre>
4：链表上的快速排序(first指向前一个元素，second指向后一个，second遇到小的，first往后走一个然后交换，最后要交换一下中轴和first)
<pre class="blockcode"><code class="language-java">public void quickSort(ListNode begin, ListNode end) {
 //判断为空，判断是不是只有一个节点
 if (begin == null || end == null || begin == end)
 return;
 //从第一个节点和第一个节点的后面一个几点
 ListNode first = begin;
 ListNode second = begin.next;

 int nMidValue = begin.val;
 //结束条件，second到最后了
 while (second != end.next && second != null) {
 if (second.val < nMidValue) {
 first = first.next;
 //判断一下，避免后面的数比第一个数小，不用换的局面
 if (first != second) {
 int temp = first.val;
 first.val = second.val;
 second.val = temp;
 }
 }
 second = second.next;
 }
 //判断，有些情况是不用换的，提升性能
 if (begin != first) {
 int temp = begin.val;
 begin.val = first.val;
 first.val = temp;
 }
 //前部分递归
 quickSort(begin, first);
 //后部分递归
 quickSort(first.next, end);
}</code></pre>
 
5：AVL树调整
6：编辑距离
<pre class="blockcode"><code class="language-java">package com.legend.code;

public class MinDistance {
public static int minDistance(String word1, String word2) {
 //dp[i][j]表示源串A位置i到目标串B位置j处最低需要操作的次数
 int[][] dp = new int[word1.length() + 1][word2.length() + 1];
 for(int i = 0; i< word1.length() + 1; i++){
 dp[i][0] = i;
 }
 for(int j = 0; j< word2.length() + 1; j++){
 dp[0][j] = j;
 }
 for(int i = 1; i< word1.length() + 1; i++){
 for(int j = 1; j< word2.length() + 1; j++){
 if(word1.charAt(i - 1) == word2.charAt(j - 1)){ // 第i个字符是字符串下标为i-1第哪个
 dp[i][j] = dp[i - 1][j - 1];
 }else{
 dp[i][j] = (Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1])) + 1;
 }
 }
 }
 return dp[word1.length()][word2.length()];
}
public static void main(String[] args)