算法记

我不是女神ヾ 2022-12-03 02:21 94阅读 0赞

1、去重算法

价格策略重复KEY生成算法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70][]

2、对象比较算法

3、分组算法

业务主子维度，时常批量处理，分组归类业务处理。此时利用groupingBy分组后循环处理业务。

Map<Integer,List<JSONObject>> priceMap= priceObjs.stream().collect(Collectors.groupingBy(priceObj->priceObj.getInteger("groupId")));

4、时间重叠算法

业务场景如下：

2020-08-01 ~ 2020-08-30

2020-08-15 ~ 2020-09-15

2020-09-01 ~ 2020-09-30

以上时间段校验时间重叠。

/***
     * 时间范围重叠校验工具
     * @author gsj
     */
    public class PriceDateRangeUtil {
    
        public static void checkOverlap(List<DateLongTimeDTO> list) throws ServiceException {
            list.stream().sorted(Comparator.comparing(DateLongTimeDTO::getCommodityMinNum))
                    .reduce((a, b) -> {
                        if (a.getCommodityMaxNum() >= b.getCommodityMinNum()) {
    
                            throw new ServiceException("pricing.e5000");
    
                        }
                        return b;
                    });
        }
    }

public class DateLongTimeDTO {
        @NotBlank(message = "最小数量不可为空")
        private Long commodityMinNum;
    
        @NotBlank(message = "最大数量不可为空")
        private Long commodityMaxNum;
    
        public Long getCommodityMinNum() {
            return commodityMinNum;
        }
    
        public void setCommodityMinNum(Long commodityMinNum) {
            this.commodityMinNum = commodityMinNum;
        }
    
        public Long getCommodityMaxNum() {
            return commodityMaxNum;
        }
    
        public void setCommodityMaxNum(Long commodityMaxNum) {
            this.commodityMaxNum = commodityMaxNum;
        }
    }

5、提取对象ID列（JDK8 Lambad实现）

List<Long> productIds = products.stream().map(Product::getId).collect(Collectors.toList());

![20200903093353141.png][]

6、数据库笛卡尔积算法能力

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 1][]

7、二分搜索（Arrays源码）

// Like public version, but without range checks.
        private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
                                         Object key) {
            int low = fromIndex;
            int high = toIndex - 1;
    
            while (low <= high) {
                int mid = (low + high) >>> 1;
                @SuppressWarnings("rawtypes")
                Comparable midVal = (Comparable)a[mid];
                @SuppressWarnings("unchecked")
                int cmp = midVal.compareTo(key);
    
                if (cmp < 0)
                    low = mid + 1;
                else if (cmp > 0)
                    high = mid - 1;
                else
                    return mid; // key found
            }
            return -(low + 1);  // key not found.
        }

常见算法：

> 算法：
> 
> 二分搜索 Binary Search
> 
> 分治 Divide Conquer
> 
> 宽度优先搜索 Breadth First Search
> 
> 深度优先搜索 Depth First Search
> 
> 回溯法 Backtracking
> 
> 双指针 Two Pointers
> 
> 动态规划 Dynamic Programming
> 
> 扫描线 Scan-line algorithm
> 
> 快排 Quick Sort
> 
> 数据结构部分：
> 
>     栈 Stack
>     队列 Queue
>     链表 Linked List 
>     数组 Array 
>     哈希表 Hash Table
>     二叉树 Binary Tree  
>     堆 Heap
>     并查集 Union Find
>     字典树 Trie
> 
>

单链表

**　　**一种重要的数据结构，HashMap等集合的底层结构都是链表结构。链表以结点作为存储单元，这些存储单元可以是不连续的。每个结点由两部分组成：存储的数值+前序结点和后序结点的指针。即有前序结点的指针又有后序结点的指针的链表称为双向链表，只包含后续指针的链表为单链表，本文总结的均为单链表的操作。

单链表常见操作的实现，包括链表结点添加、删除；链表正向遍历和反向遍历、链表排序、判断链表是否有环、是否相交、获取某一结点等。

/**
     * 单链表数据结构
     */
    class ListNode{
        int v;
        ListNode next;
    
        ListNode(int x) {
            v = x;
            next = null;
        }
    
        public int getV() {
            return v;
        }
    
        public void setV(int v) {
            this.v = v;
        }
    
        public ListNode getNext() {
            return next;
        }
    
        public void setNext(ListNode next) {
            this.next = next;
        }
    }

初始化一个单链表：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 2][]

为单链表末端插入新结点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 3][]

单链表反转思路

# 新建链表，头节点插入法 #

新建一个头结点，遍历原链表，把每个节点用头结点插入到新建链表中。最后，新建的链表就是反转后的链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70]: /images/20221123/afbaba80956f447db24375234f221afc.png
[20200903093353141.png]: /images/20221123/87fc080f560c4280868564ea5b9fb495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 1]: /images/20221123/54bee25a8676427e9b6618ec4c4f54f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 2]: /images/20221123/482aabafca9a45f8b938a93d77d13dcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 3]: /images/20221123/2c9d3f84f5354c4fbf249fe0aa6ec299.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 4]: /images/20221123/e642a1ea10ee45dba8e8c66e09929a93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbXBsZW11cnJpbmE_size_16_color_FFFFFF_t_70 5]: /images/20221123/4905844e504f49f3bdd7349b47cfbec2.png