Ruizhi Ma's Blog

Problem 53

Maximum Subarray

问题描述 https://leetcode.com/problems/maximum-subarray/ 解决思路动态规划问题初挖，所谓动态规划，就是把一个大问题，分为无数个小问题，而且这些个小问题，可能还包含在其他小问题之内。代码 class Solution { public int maxSubArray(int[] nums) { int n = nu...

Posted by Ruizhi Ma on July 26, 2019

Problem 50

Pow(x, n)

问题描述 https://leetcode.com/problems/powx-n/ 解决思路采用了二分的思路。举例而言，2^8变成4^4，变成16^2变成256. 问题解惑为什么负数这样处理？因为负数最小值-2^32无法由正数最大值2^32-1直接表示，所以先把负数加1，取反，再在最后幂运算结束之后，乘以一个底数，再取倒数。代码 class Solution { ...

Posted by Ruizhi Ma on July 25, 2019

Problem 49

Group Anagrams

问题描述 https://leetcode.com/problems/group-anagrams/ 解决思路先将数组中的每一个字符串元素进行排序，以辨别字符串是否相等。再以HashMap存排好序的字符串（作为key），和原始字符串（作为value）。代码 class Solution { public List<List<String>> group...

Posted by Ruizhi Ma on July 25, 2019

Problem 48

Rotate Image

问题描述 https://leetcode.com/problems/rotate-image/ 解决思路遇到这种旋转题目，可以考虑用对折的方法。举例而言： [1,2,3] [4,5,6] [7,8,9] 沿着1,5,9这一斜对角对折，变成了： [1,4,7] [2,5,8] [3,6,9] 再沿着中间列4,5,6对折，变成了： [7,4,1] [8,5,2] [9,6,3] 即为结...

Posted by Ruizhi Ma on July 24, 2019

Problem 47

Permutation II

问题描述 https://leetcode.com/problems/permutations-ii/ 解决思路大体思路和46题一样，只不过需要增加一个boolean数组来判断当前元素是否被用过了。((i > 0 && nums[i] == nums[i - 1])，这一句是在判重类型的题经常会用的模板。代码 class Solution { publi...

Posted by Ruizhi Ma on July 24, 2019

Problem 46

Permutations

问题描述 https://leetcode.com/problems/permutations/ 解决思路递归回溯。研究了好久，对递归有了进一步认识。问题解惑为什么是res.add(new ArrayList<>(list))而不是res.add(list)？第一，因为从参数列表传过来的list只是List类的list，是抽象的，所以这个地方需要申明他是Arra...

Posted by Ruizhi Ma on July 23, 2019

Problem 43

Multiply Strings

问题描述 https://leetcode.com/problems/multiply-strings/ 解决思路每一位相乘，和做正常乘法过程类似。代码 class Solution { public String multiply(String num1, String num2) { if(num1 == null || num2 == null) ret...

Posted by Ruizhi Ma on July 23, 2019

Problem 40

Combination Sum II

问题描述 https://leetcode.com/problems/combination-sum-ii/ 问题解惑这题还要回头理解，这次先放过去了，大体和39题差不多，还有一些细节处理。代码 class Solution { public List<List<Integer>> combinationSum2(int[] candidates, i...

Posted by Ruizhi Ma on July 22, 2019

Problem 39

Combination Sum

问题描述 https://leetcode.com/problems/combination-sum/ 解决思路直接看篮子王的视频吧，这里不太好解释，看代码应该也能看个大概懂。问题解惑有很多问题，递归如何调用，回溯怎么回溯，一层层回溯的过程。都通过debug理解了，没办法一句句说清楚，这题要多回头看看。代码 class Solution { public List<...