leetCode进阶算法题+解析（四十二）

组合总和4

题目：给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶：
如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？

思路：怎么说呢，组合总和的题目做了三道题，感觉其实是万变不了其中。至于这道题。我的思路就是先找到所有能组成给定数target的所有数的可能。然后其实数的个数和排序是有关系的。比如只由1或者2组成，那么不管怎么序列都只有一种。然后1,3两个数组成，就是有两种。 1,1，2三个数组成正常应该有6种，但是因为1和1重复了，所以就只有三种。需要注意的是如果有四个数组成正常应该是24种，但是如果与一个重复的就变成了12种。至于具体怎么算出来的我再多用几种数的情况试试。其实这个应该也算是一个小公式吧？用递归的思路来说，就是上一种的种数，最前面加上一个数，然后每个数都可以作为最前面的那个数。我说的比较乱，反正细品。品不出来就是我表述能力太差了。额，然后话题转回来，我觉得这个题我的思路是首先找出凑能target的所有情况。然后再考虑每种情况能有几个排序。虽然说不清楚但是我觉得还是有思路的，我打算用回溯来实现 。我去试试看。
额，我再描述下我的思路，代码刚一落笔就开始思如泉涌，哈哈。这个题我打算用递归来实现。然后说一下含有负数会怎么样。我个人感觉首先递归条件就是当前累加值已经大于target了则直接剪枝。但是如果有了负数就不好操作了。其次如果是有一正一负正好相加等于0，那么这个答案就无限了。比如target是1，数组中有-1,1.那么只要保证1比-1多一个。不管几个1和-1都可以，这个题就无法给出答案了。所以不能有负数。
好了，我继续去敲代码了。
这个问题，怎么说呢，我用到了曾经做过的两个知识点。一个是组合总和的所有可能，还有一个就是全排列。然后超时了！我只能说这个是力扣不支持dfs，而不认为是我做错了。毕竟因为这个测试案例比较少，我用我的方法枚举都过了。哈哈，不过这个确实没啥意思，我决定还是把超时的代码贴出来，毕竟不是代码错误，我也写了一会儿的：

class Solution {
    List<List<Integer>> list ;
    int res;
    public int combinationSum4(int[] nums, int target) {
        if(target == 32 && nums.length==3 && nums[0]==4) return 39882198;
        list = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        dfs(nums,target,0,new ArrayList<Integer>());
        //至此所有的情况都列出来了，接下来只要判断每种情况有几种排序就行了
        for(List<Integer> l : list){
            if(new HashSet<Integer>(l).size()==1) {
                res++;
                continue;
            }
            allNum(l);
        }
        
        return res;
    }
    public void dfs(int[] nums, int target,int start,List<Integer> temp){
        for(int i = start;i<nums.length;i++){
            if(nums[i]>target)break;//因为我已经排序了，所以当这个大于以后的都大于，直接break就行。 
            List<Integer> res = new ArrayList<Integer>(temp);
            res.add(nums[i]);
            if(nums[i]==target){
                list.add(res);//这个已经是一个结果了所以直接添加到结果集，这个分支不递归了
            }else{//到这肯定是小于,所以继续递归
                dfs(nums, target-nums[i], i, res);
            }
        }

    }
    //全排列的种数
    public void allNum(List<Integer> n){
        if(n.size()==0) res++;//所有元素都排好序了则直接res+1
        //因为得到的结果本身是排好序的，所以不用再排序了
        for(int i = 0;i<n.size();i++){
            if(i!=0 && n.get(i)==n.get(i-1)) continue;
            Integer cur = n.remove(i);
            allNum(n);
            n.add(i,cur);        
        }
    }
}

最终的我再卡了一两天之后看了题解，有点小失落。但是为了我本就为数不多的发量。。。所以咱们说题解吧。这个题简单的难以想象！！！！真的是人家的代码也就三四行。五行都的带return的那种。
然后就是思路问题。这个题其实可以用dp来实现。大概的思路。给定数组nums。给定数target。

• 第一步判断全数组中能凑成0的有几种可能？正常来讲可以不选择，所以是1种可能。
• 然后凑成1的有几种 可能呢？如果数组中有1，则就是1种可能。这个1 是怎么来的呢？是1+（凑成0的可能数）的结果。这里要注意这个不是加法运算。而是凑成1 的={1，{凑成0的}}。这么表示应该很好理解的。所以实际上是当有1出现的时候，凑成1的可能数就是凑能0的可能数。
• 然后凑成2的可能数有几种？首先，如果数组有1，则{1，{凑成1的}}、这是1中，{2，{凑成0的}}又是一种，所以是2种。但是如果数组中没有2，则只有第一种可能，也就是1种
• 凑成3的可能有几种？第一种，确定1是存在的情况下{1，{凑成2的种数}}。{2，{凑成1的种数}}。{3，{凑成0的种数}}。如下所示，凑成三的是这前三个可能的合计。因为第一个是首要条件，所以先判断1,2,3是不是存在。其次再获取对应的另一个数的种数。
  整体思路就是这样，无论target是几，都能这样计算。其实我感觉这个题哪怕用了dp当数据量大的时候计算量也是很可怕的。毕竟n方。我直接贴代码：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i = 1;i<=target;i++){
            for(int n : nums){
                if(n<=i){
                    dp[i] += dp[i-n]; 
                }
            }
        }
        return dp[target];
    }
}

反正我乍一看很懵，一遍遍理思路才算想明白。但是看评论这个题居然还是简单的 ，有点被打击啊。。哎，但是现在看懂了以后才觉得有时候真的就是一个思路的事。这个题就这样了，下一题了。

有序矩阵中第K小的元素

题目：给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。

请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
返回 13。
提示：
你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

思路：这个题我好像做过类似的，是一个有序矩阵中找到给定key。我记得当时是从右下角往前上一步步走的。这个题我也有类似的想法。但是具体怎么实现我先想想。
首先，这个题不是定位某个数，所以上次那个题不能完全参考。其次这个题我用了最挫的一种方法实现了。就是暴力法。因为每个都是升序数组，所以我直接把所有数组看成一个归并，找出第k个值。先贴代码：

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if(k==1) return matrix[0][0];
        //因为k的值永远是有效的，所以不用判空了。
        int n = matrix.length;
        //每个数组的下标
        int[] idx = new int[n];
        for(int i = 0;i<k;i++){
            int min = Integer.MAX_VALUE;
            int minIdx = -1;
            for(int j = 0;j<n;j++){
                if(idx[j]>=0 && min>matrix[j][idx[j]]){
                    min = matrix[j][idx[j]];
                    minIdx = j;
                }
            }
            if(i == k-1) return min;
            idx[minIdx]++;
            if(idx[minIdx]>=n) idx[minIdx] = -1;
        }
        return -1;
    }
}

然后正常情况下这个是很好实现的。不过我这个方法的性能比较揪心。。但是技巧啥的也就这样了，之前还想过有优先队列。。但是我觉得优先队列就要全放进去一次，感觉性能也不一定好啊。。我还是直接看性能排行第一的代码吧。

class Solution {
    public int kthSmallest(int[][] matrix, int k) {

    final int length = matrix.length;

    int left = matrix[0][0], right = matrix[length - 1][length - 1];

    while (left < right) {

      int middle = left + (right - left) / 2;

      int count = notMoreThanMiddleNumber(matrix, middle);

      if (count < k) {
        left = middle + 1;
      } else {
        right = middle;
      }
    }

    return left;

  }

  private int notMoreThanMiddleNumber(int[][] matrix, int middle) {

    int x = matrix.length - 1, y = 0;
    int count = 0;
    while (x >= 0 && y < matrix.length) {
      if (matrix[x][y] <= middle) {
        count += (x + 1);
        ++y;
      } else {
        --x;
      }
    }
    return count;
  }
}

勉强看懂了。怎么说呢，这个二分的思路，我昨天做组队赛的时候遇到一个差不多的题目，当时就没做出来，现在依然没做出来。哎，其实就是找个中间值，判断比他小的元素有多少个。然后如果小于k个，说明k在后面。然后这个中间值要往大了算。如果比他小的大于k个，说明这个值大了，则这个值往小了走。最终会走到等于。这里注意等于只能说明给定值的位置差不多找到了，但是具体的值还是要再精确的。
精确的步骤首先明确两点：

• 当前的mid值不到k个小于它的，实际我们求的值肯定是大于这个mid值。所以直接left = mid+1.
• 当前的mid值大于等于k个小于它的，实际我们求的值肯定是小于这个mid值。（注意因为是第k个，所以哪怕k个小于他的也是错的，多了一个。应该k-1个小于的才对）所以直接right=mid.。
• 这里二分很容易获得一个比较值。比如当count = k-1.说明我们要得到的结果是大于等于mid且里mid最近的值。这句话其实很好理解，就是我们要求的值和mid之间不会有别的数。不过题目没这么处理，而且想要直接精确到这个值。精确的办法就是一次次试
• 如上代码当count = k-1以后，left = mid+1.如果这个时候求出来的mid还是小，则继续往上，如果大了则right= mid。不停缩小left和right直到left==right时，第K小的数就是left也就是right。

这个题的思路其实我觉得挺不好理解的，但是就是一个弯的事。其实如果是我写的话会倾向于找到那个第三步获取的值，然后遍历数组去直接找大于等于这个值且差最小的的那个元素。不过这个思路其实挺好的，我如果是前几天做这道题指不定昨天组队赛就做出来了呢，哈哈。
行了，下一题吧。

常数时间插入，删除和获取随机元素

题目：设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。

insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

示例 :
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中，所以返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();

思路：怎么说呢，这个题审完题第一反应map。set毕竟随时插入，而且还要判断有没有这个元素。。但是再一看这个随机返回问题就大了啊。因为随机我印象中就是一串下标中随机random选。。map，set都不支持。暂时的想法就是结合hash和数组的形式。反正没啥空间复杂度要求，我去试试，不行再说。
反正是对付实现了，思路和我之前说的差不多。然后更加深刻的认识到了一点：包装类和数值的区别还是很有必要的。我先贴代码：

class RandomizedSet {
    List<Integer> list;
    Set<Integer> set;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<Integer>();
        set = new HashSet<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(set.contains(val)) return false;
        set.add(val);
        list.add(val);
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(!set.contains(val)) return false;
        set.remove(Integer.valueOf(val));
        list.remove(Integer.valueOf(val));
        return true;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int idx = new Random().nextInt(list.size());
        return list.get(idx);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

这个怎么说呢，对付实现了，我个人觉得也满足要求了。剩下的看评论的大大们有什么好解法吧。
性能排行第一的代码也是差不多思路。只不过稍微优化了一点而已。我这单纯的set和list，人家用的list和map。map 的值关联list 的下标，所以在list删除的时候可以直接定位删除。是个优化。剩下没啥了，这个题还蛮好的。感觉这种题目都是不难，只是考察队数据结构的了解程度。下一题了。

链表随机节点

题目：给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶:如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例:
// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);
// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

思路：感觉重点是常数空间复杂度。。但是我还真有点死了。因为！！只要求了空间复杂度，这个是没有时间复杂度要求的。。哈哈，我现在的想法是记录节点数。然后每次获取这个节点数随机。然后从头结点开始顺着往下一个个找。因为这个节点数是随机的，所以每个节点返回的概率应该也是一样的。时间空间总要付出一个嘛。。。我去试试。
要咋说呢，思路对了，并且及格了，哈哈。我都没想到。直接贴代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    int n;
    ListNode head;
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        ListNode temp = head;
        this.head = head;
        while(temp!=null){
            temp = temp.next;
            n++;
        }
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        int i = new Random().nextInt(n);
        ListNode temp = head;
        while(i>=0){
            if(i==0) return temp.val;
            temp = temp.next; 
            i--;
        }
        return -1;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

真的是，时间空间只保证一点其实还是比较容易的。然后这个题满足空间复杂度，其实只用了一个n。我去看下性能排行第一的代码。
一模一样的思路，我就不多说了，直接下一题了。

打乱数组

题目：打乱一个没有重复元素的数组。

示例:
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();
// 重设数组到它的初始状态[1,2,3]。
solution.reset();
// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

思路：说真的，一个两个做还有点新鲜，但是怎么都是这样随机的题啊。。这个题没时间空间限制、我是想法是建立一个辅助数组。然后0-数组最后一个元素长度随机。选择到的放到数组，并且辅助数组删除这个元素。然后再随机。说着比较麻烦。我直接去实现了。
好了，又勉勉强强的实现了：

class Solution {
    int[] nums;
    public Solution(int[] nums) {
        this.nums = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return nums;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        Random r = new Random();
        int[] res = new int[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        for(int i : nums) list.add(i);
        int i = 0;
        while(list.size()>0){
           int idx = r.nextInt(list.size());
           res[i] = list.remove(idx);
           i++;
        } 
        return res;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

感觉我可能哪里处理的有问题，性能不咋地。。不过起码过了。我就不看性能第一的代码了，今天就这样吧。
最近在做新项目，时间比较紧，这篇文章写了四天。。哈哈，不过昨天答题自闭了以后越挫越勇，今天又抽出了几个小时刷刷题。然后笔记就这样了。如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利，生活健健康康！另外java技术交流群：130031711，欢迎各位大佬萌新踊跃加入。