# lg-algorithm

**Repository Path**: sunli1103_admin/lg-algorithm

## Basic Information

- **Project Name**: lg-algorithm
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-10-19
- **Last Updated**: 2022-03-04

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

## 作业说明

#### 课程介绍

> **第十阶段 底层调优与算法深入**
>
> 模块一 数据结构、算法
>
> 本模块会讲解算法高级内容，例如高级数据结构、排序、递归与回溯、深度与广度优先搜索、动态规划、二分搜索与贪婪算法等。



#### 作业内容

> **作业一：数据结构与算法基础**
>
> 判断数组中所有的数字是否只出现一次。给定一个数组array，判断数组 array 中是否所有的数字都只 出现过一次。例如，arr = {1, 2, 3}，输出 YES。又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。
>
> **作业二：数据结构与算法高级**
>
> 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要 求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？




#### 软件版本

```
jdk-11.0.7
```



#### 相关代码


* 作业一

  判断数组中所有的数字是否只出现一次。给定一个数组array，判断数组 array 中是否所有的数字都只 出现过一次。例如，arr = {1, 2, 3}，输出 YES。又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。



```java
import java.util.HashSet;
import java.util.Set;

public class Homework1 {
    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
        }
        return false;
    }

    public static void main(String[] args) {

        int[] nums = {1, 2, 3, 1};
        if (containsDuplicate(nums)) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }
    }
}
```



* 作业二

  很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要 求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？



```java
public class Homework2 {

    public static int getBestGoldMining(int w, int n, int[] p, int[] g) {
        if (w == 0 || n == 0) {
            return 0;
        }
        if (w < p[n - 1]) {
            return getBestGoldMining(w, n - 1, p, g);
        }
        return Math.max(getBestGoldMining(w, n - 1, p, g), getBestGoldMining(w - p[n - 1], n - 1, p, g) + g[n - 1]);
    }

    public static int getBestGoldMiningV2(int w, int[] p, int[] g) {
        int[][] resultTable = new int[g.length + 1][w + 1];
        for (int i = 1; i <= g.length; i++) {
            for (int j = 1; j <= w; j++) {
                if (j < p[i - 1]) {
                    resultTable[i][j] = resultTable[i - 1][j];
                } else {
                    resultTable[i][j] = Math.max(resultTable[i - 1][j], resultTable[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        return resultTable[g.length][w];
    }

    public static int getBestGoldMiningV3(int w, int[] p, int[] g) {
        int[] results = new int[w + 1];
        for (int i = 1; i <= g.length; i++) {
            for (int j = w; j >= 1; j--) {
                if (j >= p[i - 1]) {
                    results[j] = Math.max(results[j], results[j - p[i - 1]] + g[i - 1]);
                }
            }
        }
        return results[w];
    }
    
    public static void main(String[] args) {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("最优收益：" + getBestGoldMining(w, g.length, p, g));
    }
}
```