最长回文子串
leetcode005 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2： 输入: “cbbd” 输出: “bb”
public String longestPalindrome(String s) {int start = 0, end = 0;//如果我们已经知道 \textrm{“bab”}“bab” 是回文，//那么很明显，\textrm{“ababa”}“ababa” 一定是回文，//因为它的左首字母和右尾字母是相同的for (int i = 0; i < s.length(); i++) {int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i + 1);int len = Math.max(len1, len2);if (len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substring(start, end + 1);}private int expandAroundCenter(String s, int left, int right) {int L = left, R = right;while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {L--;R++;}return R - L - 1;}
最大子序和
Leetcode053> 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
不同路径
Leetcode062 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？
public int uniquePaths(int m, int n) {
int[][] dq=new int[m][n];
for (int i=0;i<n;i++){
dq[0][i]=1;
}
for (int i=0;i<m;i++){
dq[i][0]=1;
}
for (int i=1;i<m;i++){
for (int j=1;j<n;j++){
dq[i][j]= dq[i-1][j]+dq[i][j-1];
}
}
return dq[m-1][n-1];
}
不同路径 II
Leetcode063 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid[0][0] == 1) {
return 0;
} else {
obstacleGrid[0][0] = 1;
}
for (int i = 1; i < obstacleGrid.length; i++) {
obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
}
for (int i = 1; i < obstacleGrid[0].length; i++) {
obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
}
for (int i = 1; i < obstacleGrid.length; i++) {
for (int j = 1; j < obstacleGrid[0].length; j++) {
obstacleGrid[i][j]= (obstacleGrid[i][j]==1)?0:obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
}
}
return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
}
最小路径和
Leetcode064 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
public int minPathSum(int[][] grid) {
for (int i = 1; i < grid[0].length; i++) {
grid[0][i] = grid[0][i - 1] + grid[0][i];
}
for (int i = 1; i < grid.length; i++) {
grid[i][0] = grid[i][0] + grid[i - 1][0];
}
for (int i = 1; i < grid.length; i++) {
for (int j = 1; j < grid[0].length; j++) {
grid[i][j] = (grid[i-1][j]>grid[i][j-1]) ? (grid[i][j-1]+grid[i][j]):(grid[i-1][j]+grid[i][j]);
}
}
return grid[grid.length - 1][grid[0].length - 1];
}
爬楼梯
Leetcode070 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
public static int climbStairs(int n) {
int memo[] = new int[n+1];
climb_Stairs(n,memo);
return memo[n];
}
public static int climb_Stairs(int i, int memo[]) {
if(i==1){
memo[1]=1;
}
if(i==2){
memo[2]=2;
}
if(memo[i]>0){
return memo[i];
}
return memo[i]=climb_Stairs(i-1,memo)+climb_Stairs(i-2,memo);
}
解码方法
Leetcode091 一条包含字母 A-Z 的消息通过以下方式进行了编码： ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。
public int numDecoding(String s) {
int[] temp = new int[s.length()];
if (s == null || s.length() == 0) {
return 0;
}
if (s.length() == 1) {
return 1;
}
temp[0] = 1;
String substring = s.substring(0, 2);
Integer integer = Integer.valueOf(substring);
temp[1] = ((integer > 9 && integer < 27) ? 2 : 1);
initArr(temp,s);
return temp[temp.length-1];
}
public void initArr(int[] ints, String s) {
for (int i = 2; i < s.length(); i++) {
String substring = s.substring(i - 1, i+1);
Integer integer = Integer.valueOf(substring);
ints[i] = ((integer > 9 && integer < 27) ? ints[i - 1] + 1 : ints[i - 1]);
}
}
不同的二叉搜索树 II
Leetcode095 给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。
public List<TreeNode> generateTrees(int n) {
if (n == 0) {
return new LinkedList<TreeNode>();
}
return generateTrees(1, n);
}
public List<TreeNode> generateTrees(int start, int end) {
List<TreeNode> allTrees = new LinkedList<TreeNode>();
if (start > end) {
allTrees.add(null);
return allTrees;
}
// 枚举可行根节点
for (int i = start; i <= end; i++) {
// 获得所有可行的左子树集合
List<TreeNode> leftTrees = generateTrees(start, i - 1);
// 获得所有可行的右子树集合
List<TreeNode> rightTrees = generateTrees(i + 1, end);
// 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode currTree = new TreeNode(i,"");
currTree.leftChild = left;
currTree.rightChild = right;
allTrees.add(currTree);
}
}
}
return allTrees;
}
不同的二叉搜索树
Leetcode095 给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
public int numTrees(int n) {
if(n==0){
return 0;
}
List list = generateTrees(1, n);
return list.size();
}
private List<TreeNode> generateTrees(int start, int end){
List<TreeNode> allTrees = new LinkedList<TreeNode>();
if(start>end){
allTrees.add(null);
return allTrees;
}
for (int i = start; i <= end; i++) {
// 获得所有可行的左子树集合
List<TreeNode> leftTrees = generateTrees(start, i - 1);
// 获得所有可行的右子树集合
List<TreeNode> rightTrees = generateTrees(i + 1, end);
// 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for (TreeNode left : leftTrees) {
for (TreeNode right : rightTrees) {
TreeNode currTree = new TreeNode(i,"");
currTree.leftChild = left;
currTree.rightChild = right;
allTrees.add(currTree);
}
}
}
return allTrees;
}
三角形最小路径和
Leetcode120 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。 例如，给定三角形： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle.size()==1){
return triangle.get(0).get(0);
}
int minValue=0;
for (int i = 0; i < triangle.size(); i++) {
for (int j = 0; j < triangle.get(i).size(); j++) {
if(i==0){
continue;
}else {
int value=0;
if(j==0){
value=triangle.get(i-1).get(0)+triangle.get(i).get(j);
}else if(j==triangle.get(i).size()-1){
value=triangle.get(i-1).get(j-1)+triangle.get(i).get(j);
}else {
value=Math.min(triangle.get(i-1).get(j-1),triangle.get(i-1).get(j))+triangle.get(i).get(j);
}
if((i==triangle.size()-1) && j==0){
minValue=value;
}
if(i==triangle.size()-1){
minValue=Math.min(minValue,value);
}
triangle.get(i).set(j,value);
}
}
}
return minValue;
}
买卖股票的最佳时机
leetcode121 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。 注意：你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
public int maxProfit(int[] prices) {
if(prices == null || prices.length==0){
return 0;
}
int buyValue = prices[0];
int sellValue = 0;
int monkey=0;
for (int i = 1; i < prices.length; i++) {
if(prices[i]<buyValue){
buyValue=prices[i];
sellValue=0;
}
sellValue=Math.max(sellValue,prices[i]);
if(sellValue-buyValue>0){
monkey=Math.max(sellValue-buyValue,monkey);
}
}
return monkey;
}
单词拆分
leetcode139 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明： 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1： 输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
乘积最大子数组
leetcode152 给你一个整数数组
nums，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 输入: [2,3,-2,4] 输出:6解释: 子数组 [2,3] 有最大乘积 6。
public int maxProduct(int[] nums) {
int length = nums.length;
int[] maxF = new int[length];
int[] minF = new int[length];
System.arraycopy(nums, 0, maxF, 0, length);
System.arraycopy(nums, 0, minF, 0, length);
for (int i = 1; i < length; ++i) {
maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
}
int ans = maxF[0];
for (int i = 1; i < length; ++i) {
ans = Math.max(ans, maxF[i]);
}
return ans;
}
打家劫舍
leetcode198 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警.
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
public int rob(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
if(nums.length==2){
return Math.max(nums[0],nums[1]);
}
nums[2]=nums[0]+nums[2];
for (int i = 3; i < nums.length; i++) {
nums[i]= Math.max(nums[i-2],nums[i-3])+nums[i];
}
return Math.max(nums[nums.length-1],nums[nums.length-2]);
}
打家劫舍 II
leetcode213 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
public int rob(int[] nums) {
if(nums.length == 0) {
return 0;
}
if(nums.length == 1) {
return nums[0];
}
return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)),
myRob(Arrays.copyOfRange(nums, 1, nums.length)));
}
private int myRob(int[] nums) {
int pre = 0, cur = 0, tmp;
for(int num : nums) {
tmp = cur;
cur = Math.max(pre + num, cur);
pre = tmp;
}
return cur;
}
最大正方形
leetcode221 在一个由
'0'和'1'组成的二维矩阵内，找到只包含'1'的最大正方形，并返回其面积。 输入：matrix = [[“1”,”0”,”1”,”0”,”0”],
["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"]]输出：4
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
int row = matrix.length;
if (row == 0) {
return 0;
}
int column = matrix[0].length;
int[][] dp = new int[row][column];
for (int i = 1; i <= row; i++){
for (int j = 1; j <= column; j++){
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
maxSide = Math.max(dp[i][j], maxSide);
}
}
}
return maxSide*maxSide;
}
丑数 II
leetcode264 编写一个程序，找出第
n个丑数。丑数就是质因数只包含
2, 3, 5的正整数。**输入: n = 10
输出: 12
解释:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12是前 10 个丑数。
public class S264丑数II {
public static Ugly u = new Ugly();
public static void main(String[] args) {
}
public int nthUglyNumber(int n) {
return u.nums[n - 1];
}
}
class Ugly {
public int[] nums = new int[1690];
Ugly() {
HashSet<Long> seen = new HashSet();
PriorityQueue<Long> heap = new PriorityQueue<Long>();
seen.add(1L);
heap.add(1L);
long currUgly, newUgly;
int[] primes = new int[]{2, 3, 5};
for(int i = 0; i < 1690; ++i) {
currUgly = heap.poll();
nums[i] = (int)currUgly;
for(int j : primes) {
newUgly = currUgly * j;
if (!seen.contains(newUgly)) {
seen.add(newUgly);
heap.add(newUgly);
}
}
}
}
}
完全平方数
leetcode279 给定正整数 n，找到若干个完全平方数（比如
1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。**输入: n =
12输出: 3
解释:
12 = 4 + 4 + 4.
public int numSquares(int n) {
int dp[] = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
// bottom case
dp[0] = 0;
// pre-calculate the square numbers.
int max_square_index = (int) Math.sqrt(n) + 1;
int square_nums[] = new int[max_square_index];
for (int i = 1; i < max_square_index; ++i) {
square_nums[i] = i * i;
}
for (int i = 1; i <= n; ++i) {
for (int s = 1; s < max_square_index; ++s) {
if (i < square_nums[s]){
break;
}
dp[i] = Math.min(dp[i], dp[i - square_nums[s]] + 1);
}
}
return dp[n];
}
最长上升子序列
leetcode300 给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
public int lengthOfLIS(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
if(nums.length==1){
return 1;
}
int[] dp = new int[nums.length];
dp[0]= 1;
dp[1]= nums[0]<nums[1]?2:1;
int maxValue=dp[1];
for (int i = 2; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
maxValue=Math.max(maxValue,dp[i]);
}else {
dp[i]=Math.max(dp[i],1);
}
}
}
return maxValue;
}
若有收获，就点个赞吧
0 人点赞
