class Solution {
    public int minPathSum(int[][] grid) {
        int height = grid.length;
        int width = grid[0].length;
        // 从终点往起点走
        for (int i = height - 1; i >= 0; i--) {
            for (int j = width - 1; j >= 0; j--) {
                if (i == height - 1 && j != width - 1) {
                    grid[i][j] += grid[i][j + 1];
                } else if (i != height - 1 && j == width - 1) {
                    grid[i][j] += grid[i + 1][j];
                } else if (i != height - 1 && j != width - 1) {
                    grid[i][j] += Math.min(grid[i + 1][j], grid[i][j + 1]);
                }
            }
        }
        return grid[0][0];
    }
}

public class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int columns = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (i == 0 && j != 0) {
                    grid[i][j] += grid[i][j - 1];
                } else if (j == 0 && i != 0) {
                    grid[i][j] += grid[i - 1][j];
                } else if (i != 0) {
                    grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
                }
            }
        }
        return grid[rows - 1][columns - 1];
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int columns = grid[0].length;
        int[] dp = new int[columns];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < rows; i++) {
            dp[0] = dp[0] + grid[i][0];
            for (int j = 1; j < columns; j++) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
            }
        }
        return dp[columns - 1];
    }
}

@HotSpotIntrinsicCandidate
protected native Object clone() throws CloneNotSupportedException;

public class Video {
    private String name;
    private Date gmtCreated;

    public Video(String name, Date gmtCreated) {
        this.name = name;
        this.gmtCreated = gmtCreated;
    }

    public Video() {
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Date getGmtCreated() {
        return gmtCreated;
    }

    public void setGmtCreated(Date gmtCreated) {
        this.gmtCreated = gmtCreated;
    }

    @Override
    protected Video clone() throws CloneNotSupportedException {
        return (Video)super.clone();
    }

    @Override
    public String toString() {
        return "Video{" +
                "name='" + name + '\'' +
                ", gmtCreated=" + gmtCreated +
                '}';
    }
}

public static void main(String[] args) throws CloneNotSupportedException {
    Video video = new Video();
    video.setName("视频一号");
    video.setGmtCreated(new Date());
    System.out.println(video);
    System.out.println(video.hashCode());
    System.out.println(video.getGmtCreated().hashCode());
    System.out.println("=============克隆后================");
    Video clone = (Video) video.clone();
    System.out.println(clone);
    System.out.println(clone.hashCode());
    System.out.println(clone.getGmtCreated().hashCode());
    System.out.println();
}

/**
 * A class implements the <code>Cloneable</code> interface to
 * indicate to the {@link java.lang.Object#clone()} method that it
 * is legal for that method to make a
 * field-for-field copy of instances of that class.
 * <p>
 * Invoking Object's clone method on an instance that does not implement the
 * <code>Cloneable</code> interface results in the exception
 * <code>CloneNotSupportedException</code> being thrown.
 * <p>
 * By convention, classes that implement this interface should override
 * {@code Object.clone} (which is protected) with a public method.
 * See {@link java.lang.Object#clone()} for details on overriding this
 * method.
 * <p>
 * Note that this interface does <i>not</i> contain the {@code clone} method.
 * Therefore, it is not possible to clone an object merely by virtue of the
 * fact that it implements this interface.  Even if the clone method is invoked
 * reflectively, there is no guarantee that it will succeed.
 *
 * @author  unascribed
 * @see     java.lang.CloneNotSupportedException
 * @see     java.lang.Object#clone()
 * @since   1.0
 */
public interface Cloneable {
}

@Override
protected Object clone() throws CloneNotSupportedException {
    Object obj = super.clone();
    Video v = (Video) obj;
    v.setGmtCreated((Date) v.getGmtCreated().clone());
    return obj;
}

public interface Copyable {
    Object copy();
}

@Data
@NoArgsConstructor
@ToString
@AllArgsConstructor
public class Car {
    private CarBody carBody;
    private Engine engine;
    private Lamp lamp;
    private Window window;
    public boolean isWhole(){
        if(carBody!=null&&engine!=null&&lamp!=null&&window!=null){
            return true;
        }
        return false;
    }
}

public interface Component {
}

public interface CarBody extends Component {
    void printName();
}

public interface Engine extends Component {
    void printName();
}

public interface Window extends Component {
    void printName();
}

public class GoodCarBody implements CarBody{
    @Override
    public void printName() {
        System.out.println("好的车身");
    }
}

public class BadCarBody implements CarBody{
    @Override
    public void printName() {
        System.out.println("差的车身");
    }
}

public class GoodEngine implements Engine{
    @Override
    public void printName() {
        System.out.println("好的发动机");
    }
}

public class BadEngine implements Engine{
    @Override
    public void printName() {
        System.out.println("差的发动机");
    }
}

public class GoodWindow implements Window{
    @Override
    public void printName() {
        System.out.println("好的车窗");
    }
}

public class BadWindow implements Window{
    @Override
    public void printName() {
        System.out.println("差的车窗");
    }
}

public interface CarBuilder {
    void addCarBody(CarBody carBody);
    void addWindow(Window window);
    void addLamp(Lamp lamp);
    void addEngine(Engine engine);
    Car getCar();
}

public class DaZhongCarBulder implements CarBuilder {
    private Car car;
    public DaZhongCarBulder(){
        car = new Car();
    }
    @Override
    public void addCarBody(CarBody carBody) {
        if(carBody==null){
            car.setCarBody(new GoodCarBody());
            return;
        }
        car.setCarBody(carBody);
    }

    @Override
    public void addWindow(Window window) {
        if(window==null){
            car.setWindow(new GoodWindow());
            return;
        }
        car.setWindow(window);
    }

    @Override
    public void addLamp(Lamp lamp) {
        if(lamp==null){
            car.setLamp(new GoodLamp());
            return;
        }
        car.setLamp(lamp);
    }

    @Override
    public void addEngine(Engine engine) {
        if(engine==null){
            car.setEngine(new GoodEngine());
            return;
        }
        car.setEngine(engine);
    }

    @Override
    public Car getCar() {
        if(!car.isWhole()){
            throw new IllegalArgumentException("零件不齐，车不能出厂");
        }
        return car;
    }
}

public class Director {
    public static Car getCar(CarBuilder carBuilder){
        carBuilder.addWindow(null);
        carBuilder.addCarBody(null);
        carBuilder.addLamp(new BadLamp());
        carBuilder.addEngine(null);
        return carBuilder.getCar();
    }
}

public interface ComponentFactory {
    CarBody getCarBody();
    Engine getEngine();
    Window getWindow();
    Lamp getLamp();
}

public class BadFactory implements ComponentFactory{
    @Override
    public CarBody getCarBody() {
        return new BadCarBody();
    }

    @Override
    public Engine getEngine() {
        return new BadEngine();
    }

    @Override
    public Window getWindow() {
        return new BadWindow();
    }

    @Override
    public Lamp getLamp() {
        return new BadLamp();
    }
}

public class GoodFactory implements ComponentFactory{

    @Override
    public CarBody getCarBody() {
        return new GoodCarBody();
    }

    @Override
    public Engine getEngine() {
        return new GoodEngine();
    }

    @Override
    public Window getWindow() {
        return new GoodWindow();
    }

    @Override
    public Lamp getLamp() {
        return new GoodLamp();
    }
}

public interface CarBuilder {
    CarBuilder addCarBody(CarBody carBody);
    CarBuilder addWindow(Window window);
    CarBuilder addLamp(Lamp lamp);
    CarBuilder addEngine(Engine engine);
    Car getCar();
}

public class DaZhongCarBulder implements CarBuilder {
    private Car car;
    public DaZhongCarBulder(){
        car = new Car();
    }
    @Override
    public CarBuilder addCarBody(CarBody carBody) {
        car.setCarBody(carBody);
        return this;
    }

    @Override
    public CarBuilder addWindow(Window window) {
        car.setWindow(window);
        return this;
    }

    @Override
    public CarBuilder addLamp(Lamp lamp) {
        car.setLamp(lamp);
        return this;
    }

    @Override
    public CarBuilder addEngine(Engine engine) {
        car.setEngine(engine);
        return this;
    }

    @Override
    public Car getCar() {
        if(!car.isWhole()){
            throw new IllegalArgumentException("零件不齐，车不能出厂");
        }
        return car;
    }
}

public class Customer {
    public static void main(String[] args) {
        DaZhongCarBulder daZhongCarBulder = new DaZhongCarBulder();
        ComponentFactory goodFactory = new GoodFactory();
        ComponentFactory badFactory = new BadFactory();
        // 这就是链式编程
        Car car = daZhongCarBulder
                .addCarBody(goodFactory.getCarBody())
                .addEngine(badFactory.getEngine())
                .addLamp(goodFactory.getLamp())
                .addWindow(goodFactory.getWindow())
                .getCar();
        System.out.println(car);
    }
}

public interface Food {
}

public interface Drink extends Food{
    void drink();
}

public interface Chip extends Food{
    void eatChip();
}

public interface Chicken extends Food{
    void eatChicken();
}

public class OrleansFriedChicken implements Chicken{
    @Override
    public void eatChicken() {
        System.out.println("奥尔良炸鸡");
    }
}

public class CuminFriedChicken implements Chicken{
    @Override
    public void eatChicken() {
        System.out.println("孜然炸鸡");
    }
}

public class Cola implements Drink{
    @Override
    public void drink() {
        System.out.println("可口可乐");
    }
}

public class BigChip implements Chip{

    @Override
    public void eatChip() {
        System.out.println("大份薯条");
    }
}

public class BaiShi implements Drink {
    @Override
    public void drink() {
        System.out.println("百事可乐");
    }
}

@Data
@ToString
public class Order {
    private List<Food> foods;
    public Order(){
        foods = new ArrayList<>();
    }
    public void addFood(Food food){
        foods.add(food);
    }
}

public class OrderApplication implements Builder{
    private Order order;
    public OrderApplication(){
        order = new Order();
    }
    @Override
    public Builder addFood(Food food) {
        order.addFood(food);
        return this;
    }

    @Override
    public Order getOrder() {
        if(order.getFoods().size()==0){
            throw new IllegalArgumentException("您未点单！");
        }
        return order;
    }
}

public static void main(String[] args) {
    OrderApplication orderApplication = new OrderApplication();
    Order order = orderApplication
            .addFood(new BigChip())
            .addFood(new OrleansFriedChicken())
            .addFood(new Cola())
            .getOrder();
    System.out.println(order);
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        for (int k : nums1) {
            list.add(k);
        }
        for (int j : nums2) {
            list.add(j);
        }
        Collections.sort(list);
        int size = list.size();
        if(size%2==0){
            return (list.get(size/2)+list.get(size/2-1))/2.0;
        }else {
            return list.get(size/2);
        }
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 总长度
        int wholeSize = nums1.length + nums2.length;
        // 去中间值
        int mid = wholeSize / 2;
        // 新建中间值+1长度的数组
        int[] temp = new int[mid + 1];
        int index1 = 0;
        int index2 = 0;
        for (int i = 0; i < temp.length; i++) {
            if (index1 == nums1.length) {
	            // num1已经放完了，直接放num2的值即可
                temp[i] = nums2[index2++];
            } else if (index2 == nums2.length) {
    	        // num1已经放完了，直接放num2的值即可
                temp[i] = nums1[index1++];
            } else if (nums1[index1] <= nums2[index2]) {
	            // num1相对比较小，所以放num1的值
                temp[i] = nums1[index1++];
            } else {
	            // num2相对比较小，所以放num2的值
                temp[i] = nums2[index2++];
            }
        }
        // 如果总长度是偶数，则返回最后两个数的和的平均数
        // 如果总长度是奇数，则直接返回最后一个数即可
        return wholeSize % 2 == 0 ? (temp[mid] + temp[mid - 1]) / 2.0 : temp[mid];
    }
}