我家小花儿

这个屌丝很懒，什么也没留下！

热门标签

牛客刷题高频_给定一个长度为n的可能有重复值的数组,找出其中不去重

作者：我家小花儿 | 2024-03-23 12:38:22

踩

给定一个长度为n的可能有重复值的数组,找出其中不去重

1.列表反转
给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。

public ListNode ReverseList(ListNode head) {
        if (head == null ) return null ;
        ListNode pre = null ; 
        ListNode next = null ;
        while(head != null ) {
            next = head.next ;
            head.next = pre ;
            pre = head ;
            head = next ;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12

2.快速排序
给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

public class Solution {
    public int[] MySort (int[] arr) {
        quickSort(arr , 0 , arr.length-1);
        return arr;
    }
    public void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组，找到分割点
            int point = partition(list, left, right);
            // 递归调用，对左子数组进行快速排序
            quickSort(list, left, point - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, point + 1, right);
        }
    }
 
    /**
     * 分割数组，找到分割点
     */
public  int partition(int[] n, int l, int r) {
		// p为基数，即待排序数组的第一个数
		int p = n[l];
		int i = l;
		int j = r;
		while (i < j) {
			// 从右往左找第一个小于基数的数
			while (n[j] >= p && i < j) {
				j--;
			}
			// 从左往右找第一个大于基数的数
			while (n[i] <= p && i < j) {
				i++;
			}
			// 找到后交换两个数
			swap(n, i, j);
		}
		// 使划分好的数分布在基数两侧
		swap(n, l, i);
		return i;
	}

 
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
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

5.最小k个数
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> num = new ArrayList() ;
        if(k > input.length) return num ;
        for ( int i = 0 ; i < k ; i ++ ){
            for(int j = input.length -1 ; j > i ; j -- ){
                if ( input[j] < input[j-1]) {
                    int temp = input[j] ;
                    input[j] = input[j-1] ; 
                    input[j - 1 ] = temp ;
                }
            }
            num.add(input[i]);
        }
        return num ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

动态规划
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
输入：
[1,-2,3,10,-4,7,2,-5]
返回值：
18
说明：
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int res = array[0]; //记录当前所有子数组的和的最大值
        int max=array[0];   //包含array[i]的连续数组最大值
        for (int i = 1; i < array.length; i++) {
            max=Math.max(max+array[i], array[i]);
            res=Math.max(max, res);
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

使用动态规划

F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变

F（i）=max（F（i-1）+array[i] ， array[i]）

res：所有子数组的和的最大值

res=max（res，F（i））

如数组[6, -3, -2, 7, -15, 1, 2, 2]

初始状态：

F（0）=6

res=6
1
2
3

i=1：

F（1）=max（F（0）-3，-3）=max（6-3，3）=3

res=max（F（1），res）=max（3，6）=6
1
2
3

i=2：

F（2）=max（F（1）-2，-2）=max（3-2，-2）=1

res=max（F（2），res）=max（1，6）=6
1
2
3

i=3：

F（3）=max（F（2）+7，7）=max（1+7，7）=8

res=max（F（2），res）=max（8，6）=8
1
2
3

i=4：

F（4）=max（F（3）-15，-15）=max（8-15，-15）=-7

res=max（F（4），res）=max（-7，8）=8
1
2
3

以此类推

最终res的值为8
最长无重复子数组
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

public class Solution {
    public int maxLength (int[] arr) {
        // write code here
        int[] a = arr ;
        int n = a.length;
        if(n < 2) return n;
        int res = 0;
        HashMap<Integer,Integer> map= new HashMap<>();
        int i = 0, j = 0;
        while (j < n) {
            if (!map.containsKey(a[j])) {
                map.put(a[j], j);
            } else {
                // 1.冲突之后取前一个数字的下一个位置
                // 例[1,2,3,4,1,5,6,7,8,1]
                // 第一次冲突之后i=1，也就是左指针从数字2位置重新开始，右指针稳定输出
                // 原来是1234，冲突之后变为2341
                // 2.而且左指针必须向右移动，不能向左移动，故取max
                // 如[3,3,2,1,3,3,3,1]，就会有3331的情况
                // 理解为窗口
                i = Math.max(i, map.get(a[j])+1);
                map.put(a[j], j);
            }
            res = Math.max(res, j - i + 1);
            j++;
        }
        return res;
    }
}
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

求平方根（实现sqir函数）

    public int sqrt (int x) {
        // write code here
        if(x == 0) return 0 ;
        int left = 1 , right = x , mid ;
        while(left <= right){
        // 防止越界
            mid = left + (right - left) / 2 ;
            // x/mid>mid == x>mid*mid 防止越界
            if(x / mid == mid) return mid ;
            else if((x / mid) > mid) left = mid + 1 ;
            else right = mid - 1 ;
        }
        return right ;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

解法二：根据平方数的性质——连续n个奇数相加的结果一定是平方数。
如：9=1+3+5；
16=1+3+5+7；
所以，不断的进行奇数相加，并判断x大小即可。代码如下：=

    public int sqrt(int x) {
        int i = 1;
        int res = 0;
        while (x >= 0) {
            x -= i;
            res++;
            i += 2;
        }
        return res - 1;
    }
1
2
3
4
5
6
7
8
9
10

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。（不能重复）

public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>() ;
        if(num.length <= 2) return arr ;
        int n = num.length ;
        int left , right ;
        Arrays.sort(num) ;
        for(int i = 0 ; i < n - 2 ; i ++){
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            left =i+1 ; right = n - 1 ;
            while(left < right) {
                if(num[i] + num[left] + num[right] < 0) left ++ ;
                else if(num[i] + num[left] + num[right] > 0) right --;
                else {
                    ArrayList<Integer> ar = new ArrayList<Integer>() ;
                    ar.add(num[i]);ar.add(num[left]);ar.add(num[right]);
                    arr.add(ar) ;
                    left++;
                    right--;
                    while (left < right && num[left] == num[left - 1]) {
                        left++;
                    }
                    while (left < right && num[right] == num[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return arr ;
    }
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

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
数据范围：节点总数 0 \le n \le 50000≤n≤5000，每个节点的val满足 |val| <= 1000∣val∣<=1000
要求：时间复杂度 O(nlogn)O(nlogn)
输入：
[{1,2,3},{4,5,6,7}]
返回值：
{1,2,3,4,5,6,7}
采用分治

import java.util.*;
public class Solution {
    public ListNode mergeKLists(ArrayListlists) {
        // 采用分治进行合并链表
        return mergeList( lists , 0 , lists.size() - 1 );
    }
    // 分治进行链表两两合并
    public ListNode mergeList(ArrayListlists , int L ,int R){
         
        if(L == R){
            return lists.get(L);
        }
        if(L > R){
            return null;
        }
         
        int mid = L + ((R - L) >> 1);
        return merge( mergeList(lists,L,mid) , mergeList(lists,mid+1,R));
    }
     
    // 合并两个链表，对比合并
    public ListNode merge(ListNode l1 , ListNode l2){
        if(l1 == null || l2 == null){
            return l1 == null ? l2 : l1;
        }
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while( l1 != null && l2 != null){
            if(l1.val < l2.val){ 
            	cur.next = l1; 
            	l1 = l1.next;
            }
            else{ 
            	cur.next = l2;
             	l2 = l2.next; 
            } 
            cur = cur.next; 
        } 
        cur.next = (l1 == null ? l2 : l1); 
        return dummy.next; 
     } 
}
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

在这里插入图片描述

import java.util.*;
public class Solution {
    public long maxWater (int[] arr) {
if (arr == null || arr.length <= 2) {
        return 0;
    }
    int left = 0, right = arr.length - 1;
    long sum = 0;
    // 找出左右边界的最小值作为水位高度
    int mark = Math.min(arr[left], arr[right]);
    while (left < right) {
        // 如果左边较低，则左边界向右遍历， 否则右边界向左移动
        if (arr[left] < arr[right]) {
            left++;
            // 如果当前标尺小于水位，则水量累加
            if (arr[left] < mark) {
                sum += mark - arr[left];
            } else { // 否则，将此标尺和右边边界高度进行比较，找出剩下数组中的新水位
                mark = Math.min(arr[left], arr[right]);
            }
        } else {
            right--;
            // 同理，如果当前标尺小于水位，则水量累加
            if (arr[right] < mark) {
                sum += mark - arr[right];
            } else { // 否则，将此标尺和左边界的高度进行比较，找出剩余数组中的新水位
                mark = Math.min(arr[right], arr[left]);
            }
        }
    }
    return sum;
}}
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

**（重点）设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，并有如下两个功能

set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
提示:
1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过k时，移除最不经常使用的记录。
3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value
若opt=1，接下来两个整数key, value，表示set(key, value)
若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
对于每个opt=2，输出一个答案
4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹
要求：set和get操作复杂度均为 O(1)O(1)
示例
输入：
[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
返回值：
[1,-1]
说明：
[1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{“1”=1}
[1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{“1”=1,“2”=2}
[1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{“1”=1,“2”=2,“3”=2}
[2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{“2”=2,“3”=2,“1”=1}
[1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{“2”=2}，插入{“4”=4}，缓存是{“3”=2,“1”=1,“4”=4}
[2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]**

    private static HashMap<Integer, Integer> map = new HashMap();
    private static Queue<Integer> queue = new LinkedList<>();
 
    public static int[] LRU(int[][] operators, int k) {
        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        int i=0;
         
        // write code here
        for (int[] operator : operators) {
            if (operator.length == 2 && operator[0] == 2) {
                //get
                Integer integer = map.get(operator[1]);
                if (null != integer) {
                    //取到，更新key为最新
                    queue.remove(operator[1]);//删除队列中该key
                    queue.add(operator[1]);//放在队尾
                    res[i++]=integer;//存value
                } else {
                    res[i++]=-1;//没取到，存-1
                }
            } else if (operator.length == 3 && operator[0] == 1) {
                //set
                if (map.size() >= k) {
                    //超过大小，先移除最久未用
                    Integer remove = queue.remove();//删除队首
                    map.remove(remove);//从map中删除队首
                }
                    //set
                    map.put(operator[1], operator[2]);//再放入新键值对
                    //更新key为最新
                    queue.remove(operator[1]);//删除队列中该key
                    queue.add(operator[1]);//放在队尾
            } 
        }
        return res;
    }
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

NC102 给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

要求：时间复杂度 O(n)

注：本题保证二叉树中每个节点的val值均不相同。

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        //记录遍历到的每个节点的父节点。
    Map<Integer, Integer> parent = new HashMap<>();
    Queue<TreeNode> queue = new LinkedList<>();
    parent.put(root.val, Integer.MIN_VALUE);//根节点没有父节点，给他默认一个值
    queue.add(root);
    //直到两个节点都找到为止。
    while (!parent.containsKey(o1) || !parent.containsKey(o2)) {
        //队列是一边进一边出，这里poll方法是出队，
        TreeNode node = queue.poll();
        if (node.left != null) {
            //左子节点不为空，记录下他的父节点
            parent.put(node.left.val, node.val);
            //左子节点不为空，把它加入到队列中
            queue.add(node.left);
        }
        //右节点同上
        if (node.right != null) {
            parent.put(node.right.val, node.val);
            queue.add(node.right);
        }
    }
    Set<Integer> ancestors = new HashSet<>();
    //记录下o1和他的祖先节点，从o1节点开始一直到根节点。
    while (parent.containsKey(o1)) {
        ancestors.add(o1);
        o1 = parent.get(o1);
    }
    //查看o1和他的祖先节点是否包含o2节点，如果不包含再看是否包含o2的父节点……
    while (!ancestors.contains(o2))
        o2 = parent.get(o2);
    return o2;
    }
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

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

import java.util.*;
public class Solution {
    //为了让递归函数添加结果方便，定义到函数之外，这样无需带到递归函数的参数列表中
    ArrayList<String> list = new ArrayList<>();
    //同；但是其赋值依赖c，定义声明分开
    char[] c;
    public ArrayList<String> Permutation(String str) {
        c = str.toCharArray();
        //从第一层开始递归
        dfs(0);
        //将字符串数组ArrayList转化为String类型数组
//         return list.toArray(new String[list.size()]);
        return list ;
    }

    private void dfs(int x) {
        //当递归函数到达第三层，就返回，因为此时第二第三个位置已经发生了交换
        if (x == c.length - 1) {
            //将字符数组转换为字符串
            list.add(String.valueOf(c));
            return;
        }
        //为了防止同一层递归出现重复元素
        HashSet<Character> set = new HashSet<>();
        //这里就很巧妙了,第一层可以是a,b,c那么就有三种情况，这里i = x,正巧dfs(0)，正好i = 0开始
        // 当第二层只有两种情况，dfs(1）i = 1开始
        for (int i = x; i < c.length; i++){
            //发生剪枝，当包含这个元素的时候，直接跳过
            if (set.contains(c[i])){
                continue;
            }
            set.add(c[i]);
            //交换元素，这里很是巧妙，当在第二层dfs(1),x = 1,那么i = 1或者 2， 不是交换1和1，要就是交换1和2
            swap(i,x);
            //进入下一层递归
            dfs(x + 1);
            //返回时交换回来，这样保证到达第1层的时候，一直都是abc。这里捋顺一下，开始一直都是abc，那么第一位置总共就3个交换
            //分别是a与a交换，这个就相当于 x = 0, i = 0;
            //     a与b交换            x = 0, i = 1;
            //     a与c交换            x = 0, i = 2;
            //就相当于上图中开始的三条路径
            //第一个元素固定后，每个引出两条路径,
            //     b与b交换            x = 1, i = 1;
            //     b与c交换            x = 1, i = 2;
            //所以，结合上图，在每条路径上标注上i的值，就会非常容易好理解了
            swap(i,x);
        }
    }    
    private void swap(int i, int x) {
        char temp = c[i];
        c[i] = c[x];
        c[x] = temp;
    }
}
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

NC93 设计LRU缓存结构
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，并有如下两个功能

set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值

提示:
1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过k时，移除最不经常使用的记录。
3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value
若opt=1，接下来两个整数key, value，表示set(key, value)
若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
对于每个opt=2，输出一个答案
4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为 O(1)O(1)
示例1
输入：
[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

返回值：
[1,-1]

说明：
[1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{“1”=1}
[1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{“1”=1,“2”=2}
[1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{“1”=1,“2”=2,“3”=2}
[2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{“2”=2,“3”=2,“1”=1}
[1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{“2”=2}，插入{“4”=4}，缓存是{“3”=2,“1”=1,“4”=4}
[2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]
使用队列+哈希

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    HashMap<Integer,Integer> hash = new HashMap() ;
    Queue queue = new LinkedList() ;
    public int[] LRU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> arr = new ArrayList() ;
        int key = 0 , value = 0 ;
        for(int[] operator : operators){
            if(operator.length == 3) {
                key = operator[1] ;
                value = operator[2] ;
                set(key , value , k) ;
            }
            else if(operator.length == 2){
                key = operator[1] ;
                arr.add(get(key)) ;
            }
        }
        int[] res = new int[arr.size()] ;
        for(int i = 0 ; i < arr.size() ; i ++) res[i] = arr.get(i) ;
        return res ;
    }
    
    public void set(int key , int value , int k){
        if(hash.containsKey(key)){
            hash.put(key,value) ;
            queue.remove(key) ;
            queue.offer(key) ;
        }
        else{
            if(queue.size() >= k){
                Object rekey = queue.peek() ;
                hash.remove(rekey) ;
                queue.poll() ;
            }
            hash.put(key,value) ;
            queue.offer(key) ;
        }
    }
    
        public int get(int key){
        if(hash.containsKey(key)){
            queue.remove(key) ;
            queue.offer(key) ;
            return hash.get(key) ;
        }
        else{
            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
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/295212?site