LeetCode题解

53 最大子序和

public class LeetCode53 {
    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        Solution53 s53 = new Solution53();
        System.out.println(s53.maxSubArray(nums));
    }
}

class Solution53 {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (currentSum > 0)
                currentSum += nums[i];
            else
                currentSum = nums[i];
            if (currentSum > maxSum)
                maxSum = currentSum;
        }
        return maxSum;
    }
}

62 不同路径

public class LeetCode62 {
    public static void main(String[] args) {
        Solution62 s62 = new Solution62();
        System.out.println(s62.uniquePaths(7, 3));
    }
}

class Solution62 {
    public int uniquePaths(int m, int n) {
        int[][] dpArr = new int[n][m];
        for (int i = 0; i < m; i++) {
            dpArr[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            dpArr[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dpArr[i][j] = dpArr[i - 1][j] + dpArr[i][j - 1];
            }
        }
        return dpArr[n - 1][m - 1];
    }
}

70 爬楼梯

public class LeetCode70 {
    public static void main(String[] args) {
        Solution70 s70 = new Solution70();
        System.out.println(s70.climbStairs(3));
    }
}

class Solution70 {
    public int climbStairs(int n) {
        int n1 = 2;  //n-1
        int n2 = 1;  //n-2
        int an = 0;  //n
        if (n == 1)
            return n2;
        else if (n == 2)
            return n1;
        else
            for (int i = 0; i < n - 2; i++) {
                an = n2 + n1;
                n2 = n1;
                n1 = an;
            }
        return an;
    }
}

121 买卖股票的最佳时机

public class LeetCode121 {
    public static void main(String[] args) {
        int[] prices = new int[]{7, 1, 5, 3, 6, 4};
        Solution121 s121 = new Solution121();
        System.out.println(s121.maxProfit(prices));
    }
}

class Solution121 {
    public int maxProfit(int[] prices) {
        if (prices.length == 0)
            return 0;
        int lowPrice = prices[0];
        int highProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < lowPrice)
                lowPrice = prices[i];
            else
                highProfit = Math.max(prices[i] - lowPrice, highProfit);
        }
        return highProfit;
    }
}

198 打家劫舍

public class LeetCode198 {
    public static void main(String[] args) {
        int[] nums = new int[]{2, 7, 9, 3, 1};
        Solution198 s198 = new Solution198();
        System.out.println(s198.rob(nums));
    }
}

class Solution198 {
    public int rob(int[] nums) {
        int[] array = new int[nums.length + 3];
        int max = 0;
        for (int i = 3; i < array.length; i++) {
            array[i] = nums[i - 3] + Math.max(array[i - 2], array[i - 3]);
            max = Math.max(max, array[i]);
        }
        return max;
    }
}

746 使用最小花费爬楼梯

public class LeetCode746 {
    public static void main(String[] args) {
        int[] cost = new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        Solution746 s746 = new Solution746();
        System.out.println(s746.minCostClimbingStairs(cost));
    }
}

class Solution746 {
    public int minCostClimbingStairs(int[] cost) {
        int[] array = new int[cost.length + 3];
        System.arraycopy(cost, 0, array, 2, cost.length);
        for (int i = 2; i < array.length; i++) {
            array[i] += Math.min(array[i - 1], array[i - 2]);
        }
        return array[array.length - 1];
    }
}

package peixun;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int xx = 250;
        int yy = 250;
        int zz = 2;
        long[][][] dpArr = new long[xx][yy][zz];
        for (int i = 0; i < xx; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) {   //头部

                    if ((i + 1) % 2 == 0) {
                        dpArr[i][j][0] = 1;
                    } else {
                        dpArr[i][j][1] = 1;
                    }

                } else if (i == j) {    //尾部

                    dpArr[i][j][0] = dpArr[i][j - 1][0];
                    dpArr[i][j][1] = dpArr[i][j - 1][1] + 1;

                } else {    //中间部分

                    dpArr[i][j][0] += dpArr[i][j - 1][0];
                    dpArr[i][j][1] += dpArr[i][j - 1][1];

                    //i=xj+y;
                    int x = (i + 1) / (j + 1);

                    for (int k = 1; k <= x; k++) {
                        int y = (i + 1) - k * (j + 1);  //余数
                        if (y == 0) {
                            if (k % 2 == 0) {
                                dpArr[i][j][0]++;
                            } else {
                                dpArr[i][j][1]++;
                            }
                        } else {
                            int tempI = y - 1;
                            int tempJ = j - 1;
                            if (tempJ > tempI) {
                                tempJ = tempI;
                            }
                            if (k % 2 == 0) {
                                dpArr[i][j][0] += dpArr[tempI][tempJ][0];
                            } else {
                                dpArr[i][j][1] += dpArr[tempI][tempJ][0];
                            }
                        }
                    }
                }
            }
        }
        for (int i = 0; i < xx; i++) {
            System.out.print((i + 1) + ":");
            for (int j = 0; j <= i; j++) {
                System.out.print(Arrays.toString(dpArr[i][j]));
            }
            System.out.println();
        }
    }
}

import java.io.*;
//import java.util.*;

////////
// You can add and modify values and implementations if needed.
// Professional 검정에서는 입출력 코드를 '문제의 조건에 맞게' 직접 작성하셔야 합니다.
// 입출력은 표준 입출력을 사용하여야 합니다.
// 단, 여러분의 PC에서 작업하실 때 필요한 System.setIn 구문은 아래 제시된 것을 이용하시면 됩니다.
// 입력은 BufferedReader, StringTokenizer 를 사용하는 것을 권장합니다. 
// 예) 한 줄에 있는 int형 정수 N 개를 입력받는 경우 (공백 구분)
//     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 최초 1회 설정
//     ...
//     StringTokenizer st = new StringTokenizer(br.readLine());
//     for(int i=0; i<N; i++) myvalue[i] = Integer.parseInt(st.nextToken());
////////

class Solution {
    public static void main(String args[]) throws Exception {
        
        // 아래의 메소드 호출은 앞으로 표준 입력(키보드) 대신 sample_input.txt 파일로부터
        // 읽어오겠다는 의미의 코드입니다. 여러분이 작성한 코드를 테스트 할 때, 편의를 위해서
        // sample_input.txt에 입력을 저장한 후, 이 코드를 프로그램의 처음 부분에 추가하면 
        // 이후 입력을 수행할 때 표준 입력 대신 파일로부터 입력을 받아올 수 있습니다.
        // 따라서 테스트를 수행할 때에는 아래 주석을 지우고 이 메소드를 사용하셔도 좋습니다.
        // 단, 채점을 위해 코드를 제출하실 때에는 반드시 이 메소드를 지우거나 주석처리 하셔야 합니다.
        //System.setIn(new FileInputStream("sample_input.txt"));

        //////// Your algorithm is implemented here. ////////

    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • LeetCode 题解
    按照 探索 中初级-中级-高级的顺序刷题，下面是目前完成的题解，未完成版，随时更新。 18/08/30更新 回溯算...
    whd_Alive阅读 410评论 0赞 2
  • Leetcode题解 - Easy - 4
    110- 平衡二叉树 问题 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一...
    aaanthony阅读 508评论 0赞 0
  • Leetcode题解 - Easy - 1
    先做Easy级别的题目吧~（由于刚开始刷还没规划好，这篇里面先夹杂了两道中等难度的题） 1-两数之和 要求 给定一...
    aaanthony阅读 730评论 0赞 0
  • leetcode 题解
    1. 关于旋转数组 旋转数组求最小值,最大值，以及任意值：https://leetcode.windliang.c...
    trcheng阅读 1,284评论 0赞 0
  • Leetcode题解 - Easy - 3
    67- 二进制求和 问题 给定两个二进制字符串，返回他们的和（用二进制表示）。 输入为非空字符串且只包含数字 1 ...
    aaanthony阅读 380评论 0赞 0