- 序言
- 10- I. 斐波那契数列
- 个人思路（suc）
- 个人解法
- 官方解法（滚动数组）
- 10- II. 青蛙跳台阶问题
- 个人思路
- 个人解法（suc）（滑动数组）
- 官方解法
- 63. 股票的最大利润
- 个人思路（遍历）
- 个人解法
- 官方解法
- 个人的dp解法
- 第三题 42. 连续子数组的最大和
- 个人思路
- 个人解法
- 官方解法
- 第四题 47. 礼物的最大价值
- 个人思路
- 个人解法（dp）（suc）
- 官方解法
- 第五题 46. 把数字翻译成字符串
- 个人思路
- 个人解法（HashSet)
- 官方解法
- 第六题 48. **最长不含重复字符的子字符串**
- 个人思路
- 个人解法
- 官方解法
其实就是状态转移公式
直接带入就可以
class Solution {
public int fib(int n) {
List list = new ArrayList<>();
list.add(0);
list.add(1);
for (int i = 2; i <= n; i++) {
list.add((list.get(i-1) + list.get(i-2))% 1000000007);
}
return (list.get(n));
}
}
官方解法（滚动数组）
class Solution {
public int fib(int n) {
int a = 0,b=1, sum;
for(int i=0; i
sum = ( a + b )% 1000000007;;
a = b;
b = sum;
}
return a;
}
}
10- II. 青蛙跳台阶问题
个人思路
个人解法（suc）（滑动数组）
class Solution {
public int numWays(int n) {
int sum = 0, pre = 1, cur = 1;
for (int i = 0; i < n; i++) {
sum = (pre + cur)%1000000007;
pre = cur;
cur = sum;
}
return pre;
}
}
官方解法
63. 股票的最大利润
个人思路（遍历）
遍历所有，寻找最大值；
简单直接，但是计算复杂度很高
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int max = 0;
for (int i = 0; i < len; i++) {
int cur_P = prices[i];
for (int j = i+1; j < len; j++) {
if(prices[j]>cur_P && (prices[j] - cur_P)>max){
max = prices[j] - cur_P;
}
}
}
return max;
}
}
官方解法
class Solution {
public int maxProfit(int[] prices) {
int cost = Integer.MAX_VALUE, profit = 0;
for(int price : prices) {
cost = Math.min(cost, price);
profit = Math.max(profit, price - cost);
}
return profit;
}
}
个人解法
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
dp[0] = nums[0];
for (int i = 1; i < len; i++) {
dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
}
Arrays.sort(dp);
return (dp[len-1]);
}
}
官方解法
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}
个人解法（dp）（suc）
class Solution {
public int maxValue(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if(i==0&&j==0){
dp[0][0] = grid[0][0];
}else if(i==0){
dp[i][j] = dp[i][j-1]+grid[i][j];
}else if(j==0){
dp[i][j] = dp[i-1][j]+grid[i][j];
}else{
dp[i][j] = Math.max(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j]);
}
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
官方解法
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 && j == 0) continue;
if(i == 0) grid[i][j] += grid[i][j - 1] ;
else if(j == 0) grid[i][j] += grid[i - 1][j];
else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
}
}
return grid[m - 1][n - 1];
}
}
/** 作者：jyd
第五题 46. 把数字翻译成字符串
个人思路
个人解法（HashSet)
官方解法
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length()+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.length(); i ++){
String temp = s.substring(i-2, i);
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
dp[i] = dp[i-1] + dp[i-2];
else
dp[i] = dp[i-1];
}
return dp[s.length()];
}
}
/**作者：jyd
第六题 48. 最长不含重复字符的子字符串
个人思路
个人解法
class Solution {
public int lengthOfLongestSubstring(String s) {
int len =s.length();
int[] dp = new int[len];
int max = 0;
if(len==0){
return 0;
}
for (int i = 0; i < len; i++) {
int cur = 0;
Set set = new LinkedHashSet<>();
for (int j = i; j < len; j++) {
if (!set.add(s.substring(j,j+1))){
break;
}
cur++;
}
set.clear();
dp[i] = cur;
}
Arrays.sort(dp);
return dp[len-1];
}
}
官方解法
class Solution {
public int lengthOfLongestSubstring(String s) {
Map dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
dic.put(s.charAt(j), j); // 更新哈希表
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
作者：jyd
