leetcode刷题

219. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值至多为 k。

示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

哈希表存储，更新位置，内存消耗会有点大。

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if(nums.length==0||k==0){
            return false;
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.get(nums[i])==null){
                map.put(nums[i],i);
            }
            else{
                int abs=i-map.get(nums[i]);
                map.put(nums[i],i);
                if(abs<=k){
                    return true;
                }
            }
        }
        return false;
    }
}

599. 两个列表的最小索引总和

假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个，则输出所有答案并且不考虑顺序。你可以假设总是存在一个答案。

示例 1:
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。
示例 2:
输入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

两个列表的长度范围都在 [1, 1000]内。
两个列表中的字符串的长度将在[1，30]的范围内。
下标从0开始，到列表的长度减1。
两个列表都没有重复的元素。

用一个哈希表实现，构建一个哈希表里面存入数组长度较短的那个数组，然后长数组只需要比较里面是否含有这个值，有的话就取出索引与本身索引相加，与最大值比较，决定是否加入到答案中。
代码也可以吧for循环放入到函数中，可以缩减一下代码量。

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        HashMap<String,Integer> map=new HashMap<>();
        if(list1.length==0||list2.length==0){
            return new String[]{};
        }
        int min=Integer.MAX_VALUE;
        List<String> res=new LinkedList<>();
        if(list1.length<list2.length){
            for (int i = 0; i <list1.length ; i++) {
                map.put(list1[i],i);
            }
            for (int i = 0; i <list2.length ; i++) {
                if(map.containsKey(list2[i])){
                    int s=map.get(list2[i]);
                    if(s+i<=min){
                        min=s+i;
                        res.add(list2[i]);
                    }
                }
            }
        }
        else{
            for (int i = 0; i <list2.length ; i++) {
                map.put(list2[i],i);
            }
            for (int i = 0; i <list1.length ; i++) {
                if(map.containsKey(list1[i])){
                    int s=map.get(list1[i]);
                    if(s+i<=min){
                        min=s+i;
                        res.add(list1[i]);
                    }
                }
            }
        }
        return res.toArray(String[]::new);
    }
}

315. 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:
输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

与求逆序对数量类似，不同的是需要求出每一位的逆序对，但是由于数组改变之后位置不确定，因此需要多定义一个索引数组定位用

class Solution {
    List<Integer> list=new ArrayList<>();
    int[] index;
    int[] count;
    public List<Integer> countSmaller(int[] nums) {
        if(nums.length==0){
            return list;
        }
        index=new int[nums.length];
        count=new int[nums.length];
        int[] tmp=new int[nums.length];
        for (int i = 0; i <nums.length ; i++) {
            index[i]=i;//索引数组
        }
        //归并排序
        merger(nums,0,nums.length-1,tmp);
        for(int i=0;i<count.length;i++){
            list.add(i,count[i]);
        }
        return list;
    }
    public void merger(int[] nums,int start,int end,int[] tmp){
        if(start>=end){
            return;
        }
        int mid=(start+end)>>1;
        merger(nums,start,mid,tmp);
        merger(nums,mid+1,end,tmp);
        int i=start;
        int j=mid+1;
        int h=start;
        while (i<=mid&&j<=end) {
            if(nums[index[i]]<=nums[index[j]]){
                tmp[h++]=index[j++];
            }
            else{
                count[index[i]]+=end-j+1;
                tmp[h++]=index[i++];
            }
        }
        while(i<=mid){
            tmp[h++]=index[i++];
        }
        while(j<=end){
            tmp[h++]=index[j++];
        }
        for(int k=start;k<=end;k++){
            index[k]=tmp[k];
        }
    }
}

350. 两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

哈希表存储。

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length==0||nums2.length==0)
            return new int[0];
        Map<Integer,Integer> map=new HashMap<>();
        List<Integer> result=new ArrayList<>();
        int[] tmp;
        if(nums1.length>nums2.length){
            tmp=nums2;
            nums2=nums1;
            nums1=tmp;
        }
        for (int i:nums1
        ) {
            if(map.containsKey(i)){
                map.put(i,map.get(i)+1);
            }
            else{
                map.put(i,1);
            }
        }
        for(int i:nums2){
            if(map.containsKey(i)){
                map.put(i,map.get(i)-1);
                result.add(i);
                if(map.get(i)==0){
                    map.remove(i);
                }
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：  
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

动态规划

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==0){
            return 0;
        }
        int y=triangle.size();
        int[][] tmp=new int[y][y];
        tmp[0][0]=triangle.get(0).get(0);
        for (int i = 1; i <y ; i++) {
            tmp[i][0]=tmp[i-1][0]+triangle.get(i).get(0);
            for(int j=1;j<i;j++){
                tmp[i][j]=Math.min(tmp[i-1][j-1],tmp[i-1][j])+triangle.get(i).get(j);
            }
            tmp[i][i]=tmp[i-1][i-1]+triangle.get(i).get(i);
        }
        int min=tmp[y-1][0];
        for(int j=1;j<y;j++){
            min=Math.min(min,tmp[y-1][j]);
        }
        return min;
    }

}

785. 判断二分图

给定一个无向图graph，当这个图为二分图时返回true。
如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。
graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。


示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释: 
无向图如下:
0----1
|    |
|    |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。

示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释: 
无向图如下:
0----1
| \  |
|  \ |
3----2
我们不能将节点分割成两个独立的子集。


graph 的长度范围为 [1, 100]。
graph[i] 中的元素的范围为 [0, graph.length - 1]。
graph[i] 不会包含 i 或者有重复的值。
图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

无向图，染色，直到遇到已经染过色并且不同于染色规则时，返回false

class Solution {
    private static final int UNCOLORED = 0;
    private static final int RED = 1;
    private static final int GREEN = 2;
    private int[] color;
    private boolean valid;

    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        valid = true;
        color = new int[n];
        Arrays.fill(color, UNCOLORED);
        for (int i = 0; i < n && valid; ++i) {
            if (color[i] == UNCOLORED) {
                dfs(i, RED, graph);
                if(!valid){
                    return valid;
                }
            }
        }
        return valid;
    }

    public void dfs(int node, int c, int[][] graph) {
        color[node] = c;
        int cNei = c == RED ? GREEN : RED;
        for (int neighbor : graph[node]) {
            if (color[neighbor] == UNCOLORED) {
                dfs(neighbor, cNei, graph);
                if (!valid) {
                    return;
                }
            } else if (color[neighbor] != cNei) {
                valid = false;
                return;
            }
        }
    }
}

97. 交错字符串

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:

回溯法，加上数组动态规划

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        return getResult(s1,s2,s3,0,0,0,new Boolean[s1.length()+1][s2.length()+1]);
    }

    private boolean getResult(String s1, String s2, String s3, int i, int j, int k,Boolean[][] booleans) {
        if(booleans[i][j]!=null){
            return booleans[i][j];
        }
        if(i==s1.length()&&j==s2.length()&&k==s3.length())
            return true;
        if(k>=s3.length()){
            return booleans[i][j]=false;
        }
        if(i<s1.length()){
            if(s1.charAt(i)==s3.charAt(k)&&getResult(s1,s2,s3,i+1,j,k+1,booleans)){
                return true;
            }
        }
        if(j<s2.length()){
            if(s2.charAt(j)==s3.charAt(k)&&getResult(s1,s2,s3,i,j+1,k+1,booleans)){
                return true;
            }
        }
        return booleans[i][j]=false;
    }
}

95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例：

输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n==0)
            return new LinkedList<TreeNode>();
        return getResult(1,n);

    }

    private List<TreeNode> getResult(int i, int n) {
        List<TreeNode> result=new LinkedList<>();
        while(i>n){
            result.add(null);
            return result;
        }
        for (int j = i; j <=n; j++) {
            List<TreeNode> leftTree=getResult(i,j-1);
            List<TreeNode> rightTree=getResult(j+1,n);
            for(TreeNode left:leftTree){
                for (TreeNode right:rightTree){
                    TreeNode tmp=new TreeNode(j);
                    tmp.left=left;
                    tmp.right=right;
                    result.add(tmp);
                }
            }
        }
        return result;
    }
}

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

基于快速排序衍生出来的快速选择，此外还可以通过最大堆来解决top-k问题

class Solution {
    Random random=new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums,nums.length-k,0,nums.length-1);
    }

    private int quickSelect(int[] nums, int k,int left,int right) {
        int q=randomSelect(nums,left,right);
        if(q==k)
            return nums[q];
        else
            return q<k?quickSelect(nums,k,q+1,right):quickSelect(nums,k,left,q-1);
    }

    private int randomSelect(int[] nums, int left, int right) {
        int r=random.nextInt(right-left+1)+1;
        swap(nums,r,right);
        return partition(nums,left,right);
    }

    private int partition(int[] nums, int left, int right) {
        int x=nums[right];
        int i=left;
        for (int j = left; j <right ; j++) {
            if(nums[j]<=x)
                swap(nums,i++,j);
        }
        swap(nums,i+1,right);
        return i+1;
    }

    private void swap(int[] nums, int r, int right) {
        int tmp=nums[right];
        nums[right]=nums[r];
        nums[r]=tmp;
    }
}