posted in leetcode  数组 

问题

数组 \(A\) 是 \([0, 1, ..., N - 1]\) 的一种排列,\(N\) 是数组 \(A\) 的长度。全局倒置指的是 \(i,j\) 满足 \(0 <= i < j < N\) 并且 \([i] > A[j]\) ,局部倒置指的是 \(i\) 满足 \(0 <= i < N\) 并且 \(A[i] > A[i+1]\) 。

当数组 \(A\) 中全局倒置的数量等于局部倒置的数量时,返回 \(true\) 。

示例 1:

输入: \(A = [1,0,2]\)
输出: \(true\)
解释: 有 1 个全局倒置,和 1 个局部倒置。

示例 2:

输入: \(A = [1,2,0]\)
输出: false
解释: 有 2 个全局倒置,和 1 个局部倒置。

注意:

  • \(A\) 是 \([0, 1, ..., A.length - 1]\) 的一种排列
  • \(A\) 的长度在 \([1, 5000]\)之间
  • 这个问题的时间限制已经减少了。

解法

一开始想法比较简单,既然是求逆序对的数量,那么双层for循环一个\(O(n^2)\)的解法就完了。但是第三项注意事项中说了时间限制已经减少,所以毫无意外的超时了。
此时考虑逆序对的性质,全局倒置一定是局部倒置。
对一个\([0,1,...,A.length - 1]\)的排序数组而言,索引\(i\),如果满足\(abs(A[i]-i) <=1\),那么,说明\(i\)只是左移或者右移了一位(或者没变),全局倒置与局部倒置至少同时加一(或者保持不变),仍然满足条件;如果\(abs(A[i] - i) >= 2\),那么,说明\(A[i]\)至少左移或者右移了两位,意味着右边至少有两个比自己小的数(或者左边必然有来2个比自己大且不相邻的数,其中至少一个不相邻)局部(必然<)全局所以造成一定不等,此时不满足条件,直接返回false。

代码

java

class Solution {
    public boolean isIdealPermutation(int[] A) {
        if (A.length <3) {
            return true;
        }
        for (int i = 0; i < A.length; i++) {
            if (Math.abs(A[i] - i) >= 2) {
                return false;
            }
        }
        return true;
    }
}
posted in leetcode  数组  双指针 

问题

给定两个数组,编写一个函数来计算它们的交集。
示例 1:

输入: nums1 = \([1,2,2,1]\), nums2 = \([2,2]\)
输出: \([2,2]\)

示例 2:

输入: nums1 = \([4,9,5]\), nums2 = \([9,4,9,8,4]\)
输出: [4,9]

说明:

  • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢?你将如何优化你的算法?
  • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
  • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

解法

问题比较简单。可以遍历两个数组,获得数字出现的频次,然后对比两个频次即可。或者可以直接排序两个数组,然后使用两个指针分别遍历数组即可。

解法

频次法

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        //这里使用hashmap,因为数字是不定长的。
        Map<Integer, Integer> map1 = new HashMap<>(nums1.length);
        for (Integer i: nums1) {
            Integer count = map1.get(i);
            if (count == null) {
                map1.put(i, 1);
            } else {
                map1.put(i, count+1);
            }
        }
        Map<Integer, Integer> map2 = new HashMap<>(nums2.length);
        for (Integer i: nums2) {
            Integer count = map2.get(i);
            if (count == null) {
                map2.put(i, 1);
            } else {
                map2.put(i, count+1);
            }
        }
        Iterator iter = map1.entrySet().iterator(); 
        List<Integer> result = new LinkedList();
        //遍历两个频次map即可,这里使用小的那个map遍历。可以减少查询次数
        while(iter.hasNext()) {
            Map.Entry<Integer, Integer> entry = (Map.Entry) iter.next(); 
            Integer key = entry.getKey(); 
            Integer val1 = entry.getValue(); 
            Integer val2 = map2.get(key);
            if(val2 != null) {
                int count = Math.min(val1, val2);
                while (count-- > 0) {
                    result.add(key);
                }
            }
        }
        
        //最终生成结果,因为没有用从List到int[]的方便转换方法。
        int[] res = new int[result.size()];
        for(int m=0;m<res.length;m++)
        {
            res[m]=result.get(m);
        }
        return res;
    }
}

排序遍历法

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        List<Integer> result = new LinkedList();
        
        //排序两个数组
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //遍历两个数组
        for (int i = 0,j=0; i<nums1.length && j<nums2.length;) {
            //相等则加入result
            if (nums1[i] == nums2[j]) {
                result.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]){
                // 这里注意只有其中一个往前推进。
                i++;
            } else {
                j++;
            }
        }
        
        int[] res = new int[result.size()];
        for(int m=0;m<res.length;m++)
        {
            res[m]=result.get(m);
        }
        return res;
    }
}
posted in leetcode  数组 

问题

给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

示例 1:

输入:\(["bella","label","roller"]\)
输出:\(["e","l","l"]\)

示例 2:

输入:\(["cool","lock","cook"]\)
输出:\(["c","o"]\)

提示:

  1. \(1 <= A.length <= 100\)
  2. \(1 <= A[i].length <= 100\)
  3. \(A[i][j]\) 是小写字母

解法

首先需要将每一个字符串进行字母的数量统计。然后遍历数量数组,获取每个字符的最小出现次数,即为答案。
数量统计有多种做法,二维数组、hashmap。此题中使用了二维数组。

代码

java

class Solution {
    public List<String> commonChars(String[] A) {
        //生成一个二维数组用于保存词频
        int[][] array = new int[A.length][26];
        //词频统计
        for (int i = 0; i < A.length; i++) {
            String s = A[i];
            for (char c : s.toCharArray()) {
                array[i][c - 97]++;
            }
        }
        List<String> result = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if(array[0][i]==0) {
                continue;
            }
            //得到第一组词频
            int count = array[0][i];
            for (int j = 1; j < A.length; j++) {
                if (array[j][i] == 0){
                    count = 0;
                    break;
                }
                count = Math.min(count, array[j][i]);
            }
            //如果词频大于0,那么加入结果中
            if (count > 0) {
                char c = (char) (97 + i);
                String s = Character.toString(c);
                while (count-- >0) {
                    result.add(s);
                }
            }
        }
        return result;
    }
}
posted in leetcode  数组 

问题

给定一个二进制数组, 计算其中最大连续1的个数。

示例 1:

输入: \([1,1,0,1,1,1]\)
输出: \(3\)
解释: 开头的两位和最后的三位都是连续\(1\),所以最大连续\(1\)的个数是 \(3\).

注意:

  • 输入的数组只包含 0 和1。
  • 输入数组的长度是正整数,且不超过 10,000。

解法

此题比较简单,一次遍历即可完成。直接上代码。

代码

java

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int result = 0;
        int curr = 0;
        for(int i: nums) {
            if (i == 0) {
                curr = 0;
            } else{
                curr++;
                result = Math.max(result, curr);
            }
        }
        return result;
    }
}
posted in 二叉树  leetcode  数组 

问题

最大树定义:一个树,其中每个节点的值都大于其子树中的任何其他值。

给出最大树的根节点 \(root\)。

就像之前的问题那样,给定的树是从表 \(A(root = Construct(A))\)递归地使用下述 \(Construct(A)\) 例程构造的:

  • 如果 \(A\) 为空,返回 \(null\)
  • 否则,令 \(A[i]\) 作为 \(A\) 的最大元素。创建一个值为 \(A[i]\) 的根节点 \(root\)
  • \(root\) 的左子树将被构建为 \(Construct([A[0], A[1], ..., A[i-1]])\)
  • \(root\) 的右子树将被构建为 \(Construct([A[i+1], A[i+2], ..., A[A.length - 1]])\)
  • 返回 \(root\)
    请注意,我们没有直接给定 \(A\),只有一个根节点 \(root = Construct(A)\).

假设 \(B\) 是 \(A\) 的副本,并附加值 \(val\)。保证 \(B\) 中的值是不同的。

返回 \(Construct(B)\)。

示例 1:

输入: \(root = [4,1,3,null,null,2], val = 5\)
输出: \([5,4,null,1,3,null,null,2]\)
解释: \(A = [1,4,2,3], B = [1,4,2,3,5]\)

示例 2:

输入:\(root = [5,2,4,null,1], val = 3\)
输出:\([5,2,4,null,1,null,3]\)
解释:\(A = [2,1,5,4], B = [2,1,5,4,3]\)

示例 3:

输入:\(root = [5,2,3,null,1], val = 4\)
输出:\([5,2,4,null,1,3]\)
解释:\(A = [2,1,5,3], B = [2,1,5,3,4]\)

解法

这道题本身不难,难得是理解题意,一开始我还在想示例2中的3放在5前面似乎也并无不可。后来才发现,其实\(val\)是追加在\(A\)末尾的,而不是随便放在哪个位置的。既然这样,考虑一下\(val\)与\(root\)的大小关系,一共有三种情况:

  1. \(root\)为空,此时直接生成一个TreeNode(val)返回即可
  2. \(root.val < val\),此时说明,\(val\)已经找到了应该在的位置,那么生成一个TreeNode(val), 并且将左儿子设置成\(root\)(因为\(root\)对应的数组元素必然在\(val\)的左边。)
  3. \(root.val > val\),此时说明,\(val\)仍然没有找到所在位置,但是因为\(val\)在最右,那么递归到\(root.right\)中去处理。

递归完成后返回root即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        // 情况1
        if (root == null) {
            return new TreeNode(val);
        }
        // 情况2
        if (root.val < val) {
            TreeNode node = new TreeNode(val);
            node.left = root;
            return node;
        }
        // 情况3
        root.right = insertIntoMaxTree(root.right,val); 
        //最终递归返回
        return root;
    }
}
posted in 二叉树  数组  leetcode 

问题

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

  1. 二叉树的根是数组中的最大元素。
  2. 左子树是通过数组中最大值左边部分构造出的最大二叉树。
  3. 右子树是通过数组中最大值右边部分构造出的最大二叉树。
  4. 通过给定的数组构建最大二叉树,并且输出这个树的根节点。

Example 1:

输入: \([3,2,1,6,0,5]\)
输入: 返回下面这棵树的根节点:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

注意:

  • 给定的数组的大小在 [1, 1000] 之间。

解法

通过定义,我们发现,可以通过遍历获取到此次遍历的根结点,然后再次分别遍历根节点左边的子数组获取此次遍历的根节点的左儿子,遍历根节点右边的子数组获取根节点的右儿子。需要注意的点是儿子是否存在有两种情况,需要在遍历子数组的时候处理好。
整体没有太大难度,边界条件处理好即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return treefy(nums, 0, nums.length-1);
    }
    private TreeNode treefy(int[] nums, int start, int end){
        //当start==end时,表示为叶节点了,可以生成叶节点跳出了
        if(start == end) {
            return new TreeNode(nums[start]);
        }
        //当start>end时,表示叶节点为空,返回null
        if (start>end) {
            return null;
        }
        //遍历start与end之间的元素,找到最大值,生成节点。
        int maxIndex = start;
        for(int i = start; i <= end; i++) {
            if (nums[i] > nums[maxIndex]) {
                maxIndex = i;
            }
        }
        //找到最大值后,递归调用左儿子与右儿子
        TreeNode node = new TreeNode(nums[maxIndex]);
        node.left = treefy(nums, start, maxIndex - 1);
        node.right = treefy(nums,maxIndex + 1, end);
        return node;
    }
}