算法--2023.1.26

1.力扣338--比特位计数

class Solution {
    public int[] countBits(int n) {
        //关键在于找到递推公式
        int[] res = new int[n+1]; 
        for(int i = 1;i<=n;i++){
            res[i] = res[i>>1] + (i&1);
        }
        return res;
    }
}

2.力扣347--前k个高频元素

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        //hashmap记录每个元素出现的次数
        for(int i = 0;i<n;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        //这里新建一个数组，通过计数排序找到前k多的次数最少是多少次--i
        int[] cnt = new int[n+1];
        for(int key : map.keySet()){
            cnt[map.get(key)]++;
        }
        int t = 0,i = n;
        for(;i>=0&&t<k;i--){
            while(cnt[i]!=0){
                cnt[i]--;
                t++;
            }
        }
        int[] res = new int[k];
        int tt = 0; 
        //然后在遍历一次hashmap，其中出现次数比i大的都是我们的结果
        for(int key : map.keySet()){
            if(map.get(key)>i){
                res[tt++] = key;
            }
        }
        return res;
    }
}

3.acwing4--多重背包问题1

import java.util.Scanner;

public class acwing4 {
//01背包问题和完全背包问题可以优化位一维dp，01背包问题从后往前，完全背包问题从前往后，多重背包问题，因为每个物品种类数量有具体限制，所以必须用二维dp，在最后一层选取物品的数量
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), capicity = in.nextInt();
        int[] nums1 = new int[n+1], nums2 = new int[n+1], nums3 = new int[n+1];
        for(int i = 1;i<=n;i++){
            nums1[i] = in.nextInt();
            nums2[i] = in.nextInt();
            nums3[i] = in.nextInt();
        }
        int[][] dp = new int[n+1][capicity+1];
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=capicity;j++){
                for(int k = 0;k<=nums3[i]&&nums1[i]*k<=j;k++){
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-nums1[i]*k] + nums2[i]*k);
                }
            }
        }
        System.out.println(dp[n-1][capicity]);
    }
}