4月算法刷题总结_suc算法

4.22 动态规划三题

509. 斐波那契数

斐波那契数（通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

我的解法（基于ArrayList的解法）（通过）

class Solution {
    public int fib(int n) {

        if(n<2){
            return n;
        }
        int mid = 0;
        List<Integer> list = new ArrayList<Integer>();
        list.add(0);
        list.add(1);
        // System.out.println(list);
        for (int i = 2; i <= n; i++) {
            mid = list.get(i-2)+ list.get(i-1);
            list.add(mid);
        }
        return mid;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

推荐解法（基于动态规划的解法）

class Solution {
    public int fib(int n) {
        int pre = 0; int cur = 0; int last = 1;
        for (int i = 0; i < n; i++) {
            pre = cur;
            cur = last;
            last = pre +last;
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11

题解

动态规划：
首先，动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。

既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出**正确的「状态转移方程」**才能正确地穷举。

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

• 穷举：

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

1
2
3
4
5

这是一个重叠子问题。

PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

转换方法—带备忘录的递归解法
这也是我一开始使用的方法。

int fib(int N) {
    if (N < 1) return 0;
    // 备忘录全初始化为 0
    vector<int> memo(N + 1, 0);
    // 进行带备忘录的递归
    return helper(memo, N);
}
 
int helper(vector<int>& memo, int n) {
    // base case 
    if (n == 1 || n == 2) return 1;
    // 已经计算过
    if (memo[n] != 0) return memo[n];
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这是自顶向下

啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫「自顶向下」。

啥叫「自底向上」？反过来，我们直接从最底下，最简单，问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)，这就是动态规划的思路，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

int fib(int N) {
    vector<int> dp(N + 1, 0);
    // base case
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[N];
}
1
2
3
4
5
6
7
8

引用

1. 《动态规划套路详解》 labuladong

1137. 第 N 个泰波那契数

我的解法（基于动态规划的解法）（通过）

class Solution {
    public int tribonacci(int n) {
        if(n<2){
            return n;
        }
        if(n==2){
            return 1;
        }
        
        int prep=0, pre=0,cur=1,last=1;

        for(int i = 1;i<n;i++){
            prep = pre;
            pre = cur;
            cur = last;
            last = prep+pre+cur;
        }
        return cur;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

322. 零钱兑换

个人解法(动态规划)（未通过）

错误，需要更正
这种思路是错误的，并非每次选择最大的就是最优解，感谢大佬

public class leetcode {

    @Test
    public void coinChange() {
        int[] coins = {1,2,5,3};
        int amount = 11;

        Arrays.sort(coins);

        /*
        状态转移公式：  gap = amount- MaxGap;
                       gap = gap - MaxGap;
                   
        * */
        int gap=0;
        int mid=0;
        int len = coins.length;
        ArrayList<Integer> list = new ArrayList<Integer>();
        int getMaxGap = getMaxGap(gap, mid, len, amount,coins);
        while(gap != 0 ){
            list.add(getMaxGap);
            gap = amount - getMaxGap;
            getMaxGap = getMaxGap(getMaxGap, mid, len, gap,coins);
            
        }
        System.out.println(list.size());
    }
    

    public int getMaxGap(int gap, int mid, int len, int amount, int[] coins){
        int maxgap = 0;
        for (int i = 0; i < len; i++) {
            mid = gap;
            gap = amount - coins[i];
            if(gap >= 0 && gap<mid){
                maxgap = gap;
            }
        }
        return  maxgap;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

题解

每次都选择最少的选择；
所以就需要对过去的路径做出选择
即为

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路：dp[i]表示兑换面额i所需要的最少硬币，因为硬币无限，所以可以自底向上计算dp[i]，对于dp[0~i]的每个状态，循环coins数组，寻找可以兑换的组合，用i面额减去当前硬币价值，dp[i-coin]在加上一个硬币数就是dp[i],最后取最小值就是答案，状态转移方程就是dp[i] = Math.min(dp[i], dp[i - coin] + 1);

转自：leetcode chen-wei-f

首先，这个问题是动态规划问题，因为它具有「最优子结构」的。要符合「最优子结构」，子问题间必须互相独立。啥叫相互独立？你肯定不想看数学证明，我用一个直观的例子来讲解。

比如说，假设你考试，每门科目的成绩都是互相独立的。你的原问题是考出最高的总成绩，那么你的子问题就是要把语文考到最高，数学考到最高…… 为了每门课考到最高，你要把每门课相应的选择题分数拿到最高，填空题分数拿到最高…… 当然，最终就是你每门课都是满分，这就是最高的总成绩。

得到了正确的结果：最高的总成绩就是总分。因为这个过程符合最优子结构，“每门科目考到最高”这些子问题是互相独立，互不干扰的。

但是，如果加一个条件：你的语文成绩和数学成绩会互相制约，数学分数高，语文分数就会降低，反之亦然。这样的话，显然你能考到的最高总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为子问题并不独立，语文数学成绩无法同时最优，所以最优子结构被破坏。

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即**「目标金额」**，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量

# 伪码框架
def coinChange(coins: List[int], amount: int):

    # 定义：要凑出金额 n，至少要 dp(n) 个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # 题目要求的最终结果是 dp(amount)
    return dp(amount)

1
2
3
4
5
6
7
8
9
10
11
12
13

更正后我的解法

知识点

排序后打印

   Arrays.sort(coins);
    String c = Arrays.toString(coins);
    System.out.println(c);
1
2
3

引用

1. 《动态规划套路详解》 labuladong

2.《零钱兑换》潇晨

4.24 动态规划一题 + 腾讯笔试总结

晚上8点的腾讯笔试，一共4个算法题，难度中等；前两道简单题，后两道中等题；
总结一下就是在做大厂笔试前需要去做一下真题，和平时的leetcode还是有着一定不同，输出是对的，但是不符合厂子的要求

70.爬楼梯

个人解法 （通过）

• 这是一道简单题，利用动态规划的核心观念，dp（n）前的每一步都是一个子问题；
• 我们可以得到这样一个状态转移公式

dp(n) = dP(n-1) + dp(n-2);
1

• 需要注意的是，由于爬楼梯是从0开始，所以 dp（0） = 1，
  dp(1) = 1, 走到最后的n，所以int[n+1];

class Solution {
    public int climbStairs(int n) {
        //
        //dp(n) = dp(n-2) + dp(n-1);
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

推荐解法 动态规划（滑动数组）

它意味着爬到第 xx 级台阶的方案数是爬到第 x - 1级台阶的方案数和爬到第 x - 2 级台阶的方案数的和。很好理解，因为每次只能爬 11 级或 2 级，所以 f(x)只能从 f(x - 1)和 f(x - 2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。
以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0) = 1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1) = 1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 f(2) = 2，f(3) = 3，f(4) = 5，……，我们把这些情况都枚举出来，发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n)O(n) 的实现，但是由于这里的 f(x) 只和 f(x - 1)与 f(x - 2) 有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

4.25 动态规划三题

53. 最大子数组和

个人解法（通过）

我想的是找到每一个f(i)对应的真实值，即如果f（n）+ f（i-1）>f(n)就留下，

class Solution {
    public int maxSubArray(int[] nums) {

        int len = nums.length;
        int cur = 0;
        int pre = 0;
        for (int i = 0; i < len; i++) {
            cur = nums[i];
     		if(cur+pre>cur){
                nums[i] = cur  + pre;
                cur = nums[i];
            }
            pre = cur;
        }
        Arrays.sort(nums);
        return nums[len-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题解

其实就是寻找状态转移公式

f（i） = max{f(i-1) + nums[i], nums[i]}
1

官方答案

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
}

1
2
3
4
5
6
7
8
9
10
11

217. 存在重复元素

个人解法（通过）

三分钟搞定的小问题
直接上代码

class Solution {
    public boolean containsDuplicate(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if(nums[i] == nums[j]){
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

推荐解法 （哈希表）

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11

利用Set集合不能有重复特性；
Set set = new HashSet(）；

350. 两个数组的交集 II （等下搞）

个人解法

    @Test
    public void intersect1() {
        int[] nums2 = {3,1,2};
        int[] nums1 = {1,1};
        int len1 = nums1.length;
        int len2 = nums2.length;
        List<Integer> list1 = new ArrayList<Integer>(0);
        List<Integer> list2 = new ArrayList<Integer>(0);
        List<Integer> result = new ArrayList<Integer>(0);
        if(len1 > len2){
            list1 = getlist(len2,nums2,list1);
            list2 = getlist(len1, nums1, list2);
            result = cur(len1, len2, list1,list2,result);
        }else{
            list2 = getlist(len2,nums2,list1);
            list1 = getlist(len1, nums1, list2);
            result = cur(len2, len1, list2,list1,result);
        }
        int[] s = getarray(result);
        System.out.println(result);
    }

    private int[] getarray(List<Integer> result) {
        int[] s = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            s[i] = result.get(i);
        }
        return s;
    }

    private List<Integer> cur(int len1, int len2, List<Integer> list1, List<Integer> list2, List<Integer> result) {
        for (int i = 0; i < len1; i++) {
            for (int j = 0; j < len2; j++) {
                if(list2.get(i) == list1.get(j)){
                    result.add(list1.get(j));
                    list1.set(j, -1);
                    list2.set(i, -2);
                }
            }
        }
        return result;
    }

    private List<Integer> getlist(int len2, int[] nums2, List<Integer> list1) {
        for (int i = 0; i < len2; i++) {
            list1.add(nums2[i]);
        }
        return list1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

正确解法 （HashMap）

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4.29 动态规划4题+数据结构3题

746. 使用最小花费爬楼梯

个人解法（dp）（suc）

所谓dp就是分解为子问题，并且子问题可以递归为 总问题的解
一定要有一个状态转移公式

dp(n) = min(dp(n-1) + cost(n-1), dp(n-2) + cost(n-2))
1

给出结果

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        //dp(n) = min(dp(n-1) + cost(n-1), dp(n-2) + cost(n-2))
        //每次选择较小的
        int len = cost.length;
        int[] dp = new int[len+1];
        dp[0] = 0; dp[1] = 0;
        for(int i=2;i<=len;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2]);
        }

        return dp[len];

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

198. 打家劫舍

个人解法（dp）（suc）

   /* 给定状态转移公式
   dp(n) = dp(n-3) + cost[3],dp(n-2) + cost[2]
   遍历所有，求最大的dp
   */
1
2
3
4

class Solution {
    public int rob(int[] nums) {
        
        int len = nums.length;
        int[] dp = new int[len];
        int max = dp[0];
        if(len==1){
            return  nums[0] ;
        }
        if(len==2){
            return Math.max(nums[1], nums[0] );
        }
        if(len==3){
            return Math.max(nums[1], nums[0] + nums[2]);
        }
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[2]+nums[0];

        for (int n = 3; n < len; n++) {
            dp[n] = Math.max(dp[n-3] + nums[n],dp[n-2] + nums[n]);
        }

        for (int i = 0; i < len; i++) {
            if (dp[i] > max){
                max = dp[i];
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

官方解法

   /* 给定状态转移公式
   dp(n) = dp(n-3) + cost[3],dp(n-2) + cost[2]
   遍历所有，求最大的dp
这里的不太一样
dp公式对比一下。
   dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);

它的有意思的选择当前，头还是不投，不偷就是上一个状态的钱
而我认为，当钱的就一定得偷，所以上一个状态就不能偷，这里就得考虑上上个时刻和上上上个时刻的比较，这也是一种思想。
   */
1
2
3
4
5
6
7
8
9
10

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

213. 打家劫舍 II

个人解法（dp）（suc）

       /*
       dp(n) = dp(n-3) + cost[3],dp(n-2)+ dp(n-2) + cost[2]
       遍历所有
       */

      /*
       dp(n) = dp(n-3) + cost[3],dp(n-2)+ dp(n-2) + cost[2]
       遍历所有
       个人思路：
       如果变成一个回环，说明，最后和最前相接触，其实dp公式是适用的
       如何解决这个问题，比如，让数组变成（1,n）和（0，n-1),选取最大的即可
       */
1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        String d;
        int[] dp1 = new int[len];
        int[] dp2 = new int[len];
        int max = dp1[0];
        int[] list1  = new int[len-1];
        int[] list2  = new int[len-1];
        if(len<=3){
            if(len==1){
                max = (nums[0]);
            }
            if(len==2){
                max = ( Math.max(nums[1], nums[0] ));
            }
            if(len==3){
                max = Math.max(Math.max(nums[1], nums[0]), nums[2]);
            }
        }else {
            //从0开始
            for (int i = 0; i < len-1; i++) {
                list1[i] = nums[i];
            }
            //从1开始
            for (int i = 0; i < len-1; i++) {
                list2[i] = nums[i+1];
            }

            dp1[0] = nums[0];
            dp1[1] = nums[1];
            dp1[2] = nums[2]+nums[0];
            dp2[0] = nums[1];
            dp2[1] = nums[2];
            dp2[2] = nums[3]+nums[1];

            for (int n = 3; n < len-1; n++) {
                dp1[n] = Math.max(dp1[n-3] + list1[n],dp1[n-2] + list1[n]);
            }
            for (int n = 3; n < len-1; n++) {
                dp2[n] = Math.max(dp2[n-3] + list2[n],dp2[n-2] + list2[n]);
            }
            // d= Arrays.toString(dp1);
            // System.out.println("list1" + d);
            // d = Arrays.toString(dp2);
            // System.out.println("list2" + d);

            for (int i = 0; i < len-1; i++) {
                if (dp1[i] > max){
                    max = dp1[i];
                }
            }

            for (int i = 0; i < len-1; i++) {
                if (dp2[i] > max){
                    max = dp2[i];
                }
            }
            // System.out.println("max" + "=" + max);
            // d = Arrays.toString(dp1);
            // System.out.println(d);
        }

    return max;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

官方解法

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        } else if (length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
    }

    public int robRange(int[] nums, int start, int end) {
        int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

740. 删除并获得点数（一个超长的答案）

个人解答（dp）（suc）

附上自己2h的失败

class Solution {
     public int deleteAndEarn(int[] nums) {
        /*        选择，删除，获得
        首先排序，获得每个值对应的实际value，在对这个数组进行选，类似于
        爬楼梯了*/
        int len  = nums.length;
        Arrays.sort(nums);
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < len; i++) {
            if(map.get(nums[i]) == null ){
                map.put(nums[i],nums[i]);
            }else{
                map.put(nums[i],map.get(nums[i])+nums[i]);
            }
        }
        //获取到了所有的key值，并且，都是排序好的
        Set<Integer> set = map.keySet();
        List<Integer> list = new ArrayList<Integer>();
        for(Integer s:set){
            list.add(s);
        }
		/*
		一个小时的失败后，重新读题，发现这样缺少了很多中间数，
		当然是选择填满了，用0就可以;
		*/
        int minl = list.get(0);
        int maxl = list.get(list.size()-1);
        for (int i = 0; i < list.size(); i++) {
            if(list.get(i) < minl){
                minl = list.get(i);
            }
            if(list.get(i) > maxl){
                maxl = list.get(i);
            }
        }
        System.out.println(minl+ " " + maxl);

        list.clear();
        for (int i = minl; i <= maxl; i++) {
            if(map.get(i)==null){
                map.put(i,0);
            }
            list.add(i);
        }
 

/*
       map.getOrDefault("key", "defaultValue");
       爬楼梯的思想,其实一个半小时前我已经写好了总体框架，嗯，
       就是这个，其实所谓的获得点数就是一个爬楼梯的算法，可以说是打家劫舍的升级版，都是在选择找到最优，只要选对状态转移公式即可
       当然，再结合官方可能有更好的认识.
       */
        int[] dp = new int[list.size()];
        int max = dp[0];

        if(list.size()<=3){
            //3个以内直接判断
            if(list.size()==1){
                max = map.get(list.get(0));
            }
            if(list.size()==2){
                max = Math.max(map.get(list.get(0)), map.get(list.get(1)));
            }
            if(list.size()==3){
                max = (map.get(list.get(0))+ map.get(list.get(2)));
                max = Math.max(max, map.get(list.get(1)));
            }
        }else{
            dp[0] = map.get(list.get(0));
            dp[1] = map.get(list.get(1));
            dp[2] = map.get(list.get(2))+dp[0];
            for (int n = 3; n < list.size(); n++) {
                dp[n] = Math.max(dp[n-2]+map.get(list.get(n)), dp[n-3] + map.get(list.get(n)));
            }
        }


        for(int i=0;i<list.size();i++){
            if(dp[i] > max){
                max = dp[i];
            }
        }
 
        return max;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

推荐解法

class Solution {
    public int deleteAndEarn(int[] nums) {
        int maxVal = 0;
        for (int val : nums) {
            maxVal = Math.max(maxVal, val);
        }
        int[] sum = new int[maxVal + 1];
        for (int val : nums) {
            sum[val] += val;
        }
        return rob(sum);
    }

    public int rob(int[] nums) {
        int size = nums.length;
        int first = nums[0], second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

387. 字符串中的第一个唯一字符

个人解法（map+set） (suc)

class Solution {
    public int firstUniqChar(String s) {
        //寻找不重复的字母，可以考虑下Set和Map
        Set<Character> set = new HashSet<>();
        Map<Character, Integer> map = new LinkedHashMap<>();

        for (int i = 0; i < s.length(); i++) {

            if(set.add(s.charAt(i))){
                map.put(s.charAt(i),i);
            }else{
                map.put(s.charAt(i),-1);
            }

        }
        System.out.println(map);
        Set<Character> s1 = map.keySet();
        for (char s2:s1){
            if(map.get(s2)!=-1){
                System.out.println(map.get(s2));
                return map.get(s2);        
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

总结

• import java.util.HashMap;不能有序遍历。
• import java.util.LinkedHashMap;可以有序遍历。
  底层实现是双向链表，所以可以实现
  
  
  
  

官方解法一（hashmap）

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

官方解法二（Queue）

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> position = new HashMap<Character, Integer>();
        Queue<Pair> queue = new LinkedList<Pair>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (!position.containsKey(ch)) {
                position.put(ch, i);
                queue.offer(new Pair(ch, i));
            } else {
                position.put(ch, -1);
                while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                    queue.poll();
                }
            }
        }
        return queue.isEmpty() ? -1 : queue.poll().pos;
    }

    class Pair {
        char ch;
        int pos;

        Pair(char ch, int pos) {
            this.ch = ch;
            this.pos = pos;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

242. 有效的字母异位词

个人解法（HashMap）（suc）

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if(map.get(s.charAt(i)) == null){
                map.put(s.charAt(i),1);
            }else {
                map.put( s.charAt(i), map.get(s.charAt(i))+1);
            }
        }
        // System.out.println(map);
        for (int i = 0; i < t.length(); i++) {
            if(map.get(t.charAt(i))==null){
                return false;
            }else {
                map.put(t.charAt(i),map.get(t.charAt(i)) -1);
            }
        }
        for(Integer mm: map.values()){
            if (mm!=0){
                return false;
            }
        }
        return true;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

推荐解法

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

4.30 动态规划2+数据结构5

55. 跳跃游戏

个人解法（贪心）（suc）

/*
对于动态规划，从这个跳跃游戏中发现最优的逻辑，是有一个决策的过程，状态转移公式
而对于这个跳跃游戏，显然，最优逻辑不容易发现，不如直接用当前的状态能得到的最远位置作为
反馈，遍历位置，当当前能到达的位置x中的跳跃值>=目标值，说明已经到达了最优解
但是我认为，这样寻找路径的情况并非最优的，应该是一个局部最优
*/
1
2
3
4
5
6

class Solution {
    public boolean canJump(int[] nums) {

        int len = nums.length;
        //如果输入是null或者是小于等于0；肯定不行

        if(len==1&nums[0]>= 0){
            return true;
        }
        int max = 0;//当前可走最远的地方
        int[] list = new int[len-1];
        //update the list as the 局部最优表
        for (int i = 0; i < len-1; i++) {
            list[i] = nums[i]+i;
            if(list[i]>max){
                max = list[i];
            }
            if ((list[i]>=len-1)) {
                return true;
            }
            //需要增加一个逻辑：只有当前的max>i,才能继续走下去
            if(max <= i){
                break;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

谈谈贪心算法和动态规划的区别

/*
贪心算法，又名贪婪法，是寻找最优解问题的常用方法，
这种方法模式一般将求解过程分成若干个步骤，
但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），
并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字，贪心，
贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，
看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。}
贪婪法的基本步骤：
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来。
*/

/*
对于动态规划，从这个跳跃游戏中发现最优的逻辑，是有一个决策的过程，状态转移公式
而对于这个跳跃游戏，显然，最优逻辑不容易发现，不如直接用当前的状态能得到的最远位置作为
反馈，遍历位置，当当前能到达的位置x中的跳跃值>=目标值，说明已经到达了最优解
但是我认为，这样寻找路径的情况并非最优的，应该是一个局部最优
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

官方解法

public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

一种很有意思的解法（跳坑的思想）

思想：只要一段路程没有0，那么我们能到达任意的位置，我们把0相信成一个坑，如我我们遍历遇到了0，那么我们回头遍历之前的距离，看是否能过越过整个坑。

// 转自于leetcode的橙留香_
class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length == 1) {
            return true;
        }
        for(int i = 0;i < nums.length - 1;i ++) {
            if(nums[i] == 0) {
                boolean isOk = false;
                for(int j = i - 1;j >= 0;j --) {
                    if(j + nums[j] > i) {
                        isOk = true;
                        break;
                    }
                }
                if(!isOk) {
                    return false;
                }
            }
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

45. 跳跃游戏 II

个人解法（广度优先遍历）（mid-suc）

我想用广度优先遍历的思想，暂时在递归上卡住了，没有把递归写出来，需要一点时间修改

    /*
     * Java中集合list的add方法添加的是地址（引用）不是值
     * 所以new ArrayList<Integer>(integerList2）来new一个，重新传入，这个就是在堆中创建
     * 了新的空间存放
     * */
1
2
3
4
5

      @org.junit.Test
    public void jump() {
        int[] nums = {2,3,1,1,4};
        int len = nums.length;
        //如果输入是null或者是小于等于0；肯定不行
        if(len==1&nums[0]>= 0){
            System.out.println(true);
        }

        int[] list = new int[len-1];
        //update the list as the 位置可达表
        for (int i = 0; i < len-1; i++) {
            list[i] = nums[i] + i;
        }
        int y = 0; //当前目标位置
        List<List<Integer>> integerList = new ArrayList<>();
        List<Integer> integerList1 = new LinkedList<>();
        int step = 0;
        //获取integerList1，将integerList1放入integerList中
        System.out.println("第1th");
        integerList1 = getintegerList(len,integerList1,list,y);
        integerList.add(new ArrayList<>(integerList1));
        step++;
//        获取第一次，将集合存放到大集合里，递归
        System.out.println("第1th");
        step = dp1(integerList,list,y,step,len);
//        获取第三次，将集合存放到大集合里，递归
        System.out.println("第2th");
        step = dp2(integerList,list,y,step,len);
        System.out.println(step);
    }
    private int dp2(
            List<List<Integer>> integerList,

            int[] list, int y, int step, int len) {
        String s = Arrays.toString(list);
        System.out.println("list" + " = " + s);
        List<Integer> integerList2 = new ArrayList<>();
        for (int a = 0; a < integerList.size(); a++) {
            List<Integer> integerList1 = integerList.get(a);
            //遍历integerList1中所有的可能；
            for (int i = 0; i < (integerList1.size()); i++) {
                y = integerList1.get(i); //当前目标位置
                if(y==0){
                    return step;
                }
                System.out.println("y" + " = " + y);
                for (int j = 0; j < y; j++) {
                    if ((list[j] >= y)) {
                        integerList2.add(j);
                    }
                }
                //integerList2中所有的可能就是下一次的起点；
                integerList.add(new ArrayList<Integer>(integerList2));
                System.out.println(integerList2);
                integerList2.clear();
            }
        }
        step++;
        return step;
    }


    private int dp1(List<List<Integer>> integerList,
                   int[] list, int y, int step, int len) {

        String s = Arrays.toString(list);
        System.out.println("list" + " = " + s);
        List<Integer> integerList2 = new ArrayList<>();

        //遍历integerList中所有的可能；
        for (int a = 0; a < integerList.size(); a++) {
            List<Integer> integerList1 = integerList.get(a);
            //遍历integerList1中所有的可能；
            for (int i = 0; i < (integerList1.size()); i++) {
                y = integerList1.get(i); //当前目标位置
                if(y==0){
                    return step;
                }
                System.out.println("y" + " = " + y);
                for (int j = 0; j < y; j++) {
                    if ((list[j] >= y)) {
                        integerList2.add(j);
                    }
                }
                //integerList2中所有的可能就是下一次的起点；
                integerList.add(new ArrayList<Integer>(integerList2));
                System.out.println(integerList2);
                integerList2.clear();
            }
        }
        step++;
//        dp1();
        return step;
    }


    public List<Integer> getintegerList(int len, List<Integer> integerList,
                                        int[] list, int y) {
        y = len-1;
        for (int i = 0; i < y; i++) {
            if ((list[i] >= y)) {
                integerList.add(i);
            }
        }
        System.out.println(integerList);
        return integerList;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

整整三个多小时的努力，成功了，我真是天才，还是努力的天才
1

    @org.junit.Test
    public void jump() {
        int[] nums = {2,3,0,1,4};
        int len = nums.length;
        //如果输入是null或者是小于等于0；肯定不行
        if(len==1&nums[0]>= 0){
            System.out.println(true);
        }

        int[] list = new int[len-1];
        //update the list as the 位置可达表
        for (int i = 0; i < len-1; i++) {
            list[i] = nums[i] + i;
        }
        int y = 0; //当前目标位置
        List<List<Integer>> integerList = new ArrayList<>();
        List<Integer> integerList1 = new LinkedList<>();
        int step = 0;
        //获取integerList1，将integerList1放入integerList中
        System.out.println("第1th");
        integerList1 = getintegerList(len,integerList1,list,y);
        integerList.add(new ArrayList<>(integerList1));
        step++;
//   将集合存放到大集合里，递归
        System.out.println("第1th");
        step = dp(integerList,list,y,step,len);

        System.out.println("result"+step);
    }

    private int dp(List<List<Integer>> integerList,
                   int[] list, int y, int step, int len) {

        String s = Arrays.toString(list);
        System.out.println("list" + " = " + s);
        List<Integer> integerList2 = new ArrayList<>();
        step++;
        //遍历integerList中所有的可能；
        for (int a = 0; a < integerList.size(); a++) {
            List<Integer> integerList1 = integerList.get(a);
            //遍历integerList1中所有的可能；
            for (int i = 0; i < (integerList1.size()); i++) {
                y = integerList1.get(i); //当前目标位置
                if(y==0){
                    return step;
                }
                System.out.println("y" + " = " + y);
                for (int j = 0; j < y; j++) {
                    if ((list[j] >= y)) {
                        integerList2.add(j);
                    }
                }
                //integerList2中所有的可能就是下一次的起点；
                integerList.add(new ArrayList<Integer>(integerList2));
                System.out.println(integerList2);
                integerList2.clear();
            }
        }

        dp(integerList,list,y,step,len);
        return step;
    }

    /*
     * Java中集合list的add方法添加的是地址（引用）不是值
     * 所以new ArrayList<Integer>(integerList2）来new一个，重新传入，这个就是在堆中创建
     * 了新的空间存放
     * */
    public List<Integer> getintegerList(int len, List<Integer> integerList,
                                        int[] list, int y) {
        y = len-1;
        for (int i = 0; i < y; i++) {
            if ((list[i] >= y)) {
                integerList.add(i);
            }
        }
        System.out.println(integerList);
        return integerList;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

6个小时后（suc）

/*暂时没有好的思路，直接由上一个题升级下，BFS算了
* 其实就是对于目标点y找上一个可达点x，即x+nums[x] >=y
* 将x点存入
* 以此类推，可以找到多种组合
* 类似于二叉树的层次遍历;
* 寻找的方式就是通过nums[i] = y,get所有的i，让y=i得到下一批
* 就是递归了，直到找到i=0返回；
* */
1
2
3
4
5
6
7
8

• 这个算法是可以执行了，但是运算量太大了，计算复杂度爆掉
• 简单的是完全可的，也没有想到需要花了整整一天时间
• 算是锻炼了递归和BFS
• 对于多一点的运算，十分钟以上，广度优先不适合
  
  我在idea上跑了，结果如果，13是对的。
  但是需要4分钟大概，
  

class Solution {
    public int jump(int[] nums) {
        int len = nums.length;
        //如果输入是null或者是小于等于0；肯定不行
        if(nums[0]==0){
            return 0;
        }
        if(len==1){
            return 0;
        }
        if(nums[0]>=len-1){
            return 1;
        }


        int[] list = new int[len-1];
        //update the list as the 位置可达表
        for (int i = 0; i < len-1; i++) {
            list[i] = nums[i] + i;
        }
        int y = 0; //当前目标位置
        List<List<Integer>> integerList = new ArrayList<>();
        List<Integer> integerList1 = new LinkedList<>();
        int step = 0;
        //获取integerList1，将integerList1放入integerList中
        System.out.println("第1th");
        integerList1 = getintegerList(len,integerList1,list,y);
        step++;
        integerList.add(new ArrayList<>(integerList1));
        //将集合存放到大集合里，递归
        System.out.println("第2th");
        return dp(integerList,list,y,step,len);

        
    }

    private int dp(List<List<Integer>> integerList,
                   int[] list, int y, int step, int len) {

        String s = Arrays.toString(list);
        List<Integer> integerList2 = new ArrayList<>();
        List<List<Integer>> NextIntegerList = new ArrayList<>();
        step++;
        //遍历integerList中所有的可能；
        for (int a = 0; a < integerList.size(); a++) {
            List<Integer> integerList1 = integerList.get(a);
            //遍历integerList1中所有的可能；
  
            for (int i = 0; i < (integerList1.size()); i++) {
                y = integerList1.get(i); //当前目标位置 第二th 为5但是他所在的list[4]

                for (int j = 0; j < y; j++) {
                    if ((list[j] >= y)) {
                        integerList2.add(j);
                        if(j==0){
                            return step;
                        }
                    }
                }
                //integerList2中所有的可能就是下一次的起点；
                NextIntegerList.add(new ArrayList<Integer>(integerList2));
                System.out.println("integerList2"+integerList2);
                integerList2.clear();
            }
        }
        integerList.clear();
        integerList.addAll(NextIntegerList);
        return dp(integerList,list,y,step,len);


    }

    /*
     * Java中集合list的add方法添加的是地址（引用）不是值
     * 所以new ArrayList<Integer>(integerList2）来new一个，重新传入，这个就是在堆中创建
     * 了新的空间存放
     * */
    public List<Integer> getintegerList(int len, List<Integer> integerList,
                                        int[] list, int y) {
        y = len-1;
        for (int i = 0; i < len-1; i++) {
            if ((list[i] >= y)) { //那个可以到达nums最后，也就是第[5]的位置
                integerList.add(i);
            }
        }
        return integerList;
    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

建议算法（反向-贪心）

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

建议算法二（正向-贪心）

class Solution {
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0; 
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

141. 环形链表

个人解法（Set）（Map）

3分钟的题，没啥难度，map和set都可以，题意还给了poi根本不需要

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {

    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        Set<ListNode> set = new LinkedHashSet<>();
        while(head.next != null){
            head = head.next;
            if(set.add(head)==false){
                return true;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

另一种解法（快慢指针）

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

83. 删除排序链表中的重复元素

个人解法（suc）（链表）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode cur = head;
        while (head.next != null) {
            if(head.val == head.next.val){
                head.next = head.next.next;
            }else{
                head = head.next;
            }
        }

        return cur;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

232. 用栈实现队列

个人解法（suc）

原谅我，忘记栈是什么结构？
随便搞了个LinkedList上了，结果可行

class MyQueue {

    List<Integer> list1 = new LinkedList<>();
    List<Integer> list2 = new LinkedList<>();

    public  int[] MyQueue() {
        int[] list = new int[list1.size()];
        for (int i = 0; i < list1.size(); i++) {
            list[i] = list1.get(i);
        }
        return list;
    }
    
    public void push(int x) {
        list1.add(x);
    }

    public int pop() {
        int[] list = MyQueue();
        list2.clear();
        for (int i = 1; i < list1.size(); i++) {
            list2.add(list1.get(i));
        }
        list1.clear();
        list1.addAll(list2);
        return list[0];
    }

    public int peek() {
        int[] list = MyQueue();
        return list[0];
    }

    public boolean empty() {
        int[] list = MyQueue();
        if (list.length==0){
            return true;
        }else {
            return false;
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

Java Stack 类

栈是Vector的一个子类，它实现了一个标准的后进先出的栈。

堆栈只定义了默认构造函数，用来创建一个空栈。 堆栈除了包括由Vector定义的所有方法，也定义了自己的一些方法。

//给一个实例
public void test(int x) {
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();
        s1.push(x);
        s2.push(x);
        int p1 = s1.peek();
        int p2 = s2.peek();
        System.out.println(p1==p2);
        System.out.println(s1.peek() == s2.peek());
}
1
2
3
4
5
6
7
8
9
10
11

官方答案

private Stack<Integer> s1 = new Stack<>();
private Stack<Integer> s2 = new Stack<>();

// Push element x to the back of queue.
public void push(int x) {
    if (s1.empty())
        front = x;
    s1.push(x);
}


// Removes the element from in front of queue.
public void pop() {
    if (s2.isEmpty()) {
        while (!s1.isEmpty())
            s2.push(s1.pop());
    }
    s2.pop();    
}
// Return whether the queue is empty.
public boolean empty() {
    return s1.isEmpty() && s2.isEmpty();
}

// Get the front element.
public int peek() {
    if (!s2.isEmpty()) {
        return s2.peek();
    }
    return front;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

206. 反转链表

个人解法

可以用冒泡来反转
比如pre、cur、last三个指针
也有其他方式

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        int len = 0;
        if(head==null){
            return null;
        }
        ListNode cur = head;
        ListNode cur1 = head;
        List<Integer> list = new LinkedList<>();
        while(head!=null){
            list.add(head.val);
            head = head.next;
            len++;
        }
 
        System.out.println(list);
        while(cur1!=null){
            cur1.val = list.get(len-1);
            cur1 = cur1.next;
            len--;
        }

        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

官方题解

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

值得一看的递归解法

class Solution {
	public ListNode reverseList(ListNode head) {
		//递归终止条件是当前为空，或者下一个节点为空
		if(head==null || head.next==null) {
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);
		//这里请配合动画演示理解
		//如果链表是 1->2->3->4->5，那么此时的cur就是5
		//而head是4，head的下一个是5，下下一个是空
		//所以head.next.next 就是5->4
		head.next.next = head;
		//防止链表循环，需要将head.next设置为空
		head.next = null;
		//每层递归函数都返回cur，也就是最后一个节点
		return cur;
	}
}

// 作者：wang_ni_ma
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

四月结束了，总结+反馈，重新制定plan