买卖股票的最佳时机

买卖股票的最佳时机 ||
题目分析：动态规划问题
初始问题：第0天的时候利润为多少，第0天的利润 由前一天的操作决定，第0天不持有股票，因此利润为0 ，无法卖出股票，可以使用 Integer.MINVALUE 表示。
状态： 第i天持有股票的利润，第i天不持有股票的利润
选择：买入，卖出，无操作
状态转换：第i天如果持有股票，那么可能是i-1天本身就持有，也可能是i天买入了股票。第i天不持有股票，那么可能是第i-1天持有，然后i天卖出，或者是第i-1天本身不持有，第i 天也没进行操作。
子问题：i天应该做出什么样的选择，会带来的收益更大

 //买卖股票的最佳时机
    public int maxProfit(int[] prices) {
        //第i天不持有股票
        int d_i_0 = 0;
        //第i天持有股票 初始化为0
        int d_i_1 = Integer.MIN_VALUE;
        for(int i=0;i<prices.length;i++){
            int temp = d_i_0;
            d_i_0 = Math.max(d_i_0,d_i_1+prices[i]);
            d_i_1 = Math.max(temp-prices[i],d_i_1);
        }
        return d_i_0;
    }

递归实现冒泡排序

这还真是第一次看到这种题冒泡排序还行，递归实现嘶~

public void sortArray(int [] array,int m,int n){
        if(m>0){
            if(array[n]<array[n-1]){
                swap(array,n);
            }
            if(n>=m){
//然后在重新排列前m-1个元素
               sortArray(array,m-1,1);
            }else{
//这样就将最大的数字交换到最后一个位置了
                sortArray(array,m,n+1);
            }
        }
    }

    //交换位置
    void swap(int []arr,int n){
        int temp = arr[n];
        arr[n] = arr[n-1];
        arr[n-1] = temp;
    }

手撕快排

//快排
    public void QuickSort(int [] arr,int low,int height) {
        if(low>height) {
            return;
        }
        int piv = QuickSortFunction(arr, low, height);
        QuickSort(arr,piv+1, height);
        QuickSort(arr, low, piv-1);
    }
    //快排调用函数
    private int QuickSortFunction(int [] arr,int left,int right) {
        int cur = arr[left];
        while (left<right) {
            while(left<right && cur<=arr[right]) right--;
            arr[left] = arr[right];
            while(left<right && cur>=arr[left]) left++;
            arr[right] = arr[left];
        }
        arr[left] = cur;
        return left;
    }
    }

使用基本的数据结构实现一个hash 表

前缀树

写一段代码，实现三个进程，第一个线程打印1，2，3，4 第二个线程打印5，6，7，8 第三个线程打印9，10，11，12.然后第一个线程在去打印13，14，15，16 一直这样打印下去。

手写观察者模式

最长公共子序列

题目链接
视频讲解

 public int longestCommonSubsequence(String text1, String text2) {
          int n = text1.length();
          int m = text2.length();
          int [][] dp = new int[n+1][m+1];
          for(int i=1;i<=n;i++) {
              char x = text1.charAt(i-1);
              for(int j=1;j<=m;j++) {
                  char y = text2.charAt(j-1);
                  if(x==y) {
                      dp[i][j] = dp[i-1][j-1]+1;
                  }else {
                      dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                  }
              }
          }
          return dp[n][m];
     }

二叉排序树，给你一个target值，问是否存在两个数的和刚好等于target(需要自己写树节点以及构建树，跑测试样例)

0<=price<=9999 ,将price 转化为汉字，例如输入 12345 转化为一万两千三百四十五元

手写一个死锁

class Source1{}
class Source2{}
public class DeadLock {
    //创建两个资源
    private static volatile Source1 reSource1 = new Source1();
    private static volatile Source2 reSource2 = new Source2();
    public static void main(String[] args) {
        new Thread(()->{
            synchronized (reSource1) {
                System.out.println(Thread.currentThread().getName()+"get");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread().getName()+"wait");
                synchronized (reSource2) {
                    System.out.println(Thread.currentThread().getName()+"over");
                }
            }
        }).start();
        //线程二
        new Thread(()->{
            synchronized (reSource2) {
                System.out.println(Thread.currentThread().getName()+"get");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread().getName()+"wait");
                synchronized (reSource1) {
                    System.out.println(Thread.currentThread().getName()+"over");
                }
            }
        }).start();
    }
}