Fork me on GitHub

Java数据结构和算法-单调栈学习记录

单调栈

单调栈本质上也是栈，栈(stack)是很经典的一种数据结构，具有先进先出的逻辑特点。单调栈是栈的一种应用，主要特点就是栈中存放的数据要么递增要么递减。主要分为单调递增栈和单调递减栈两种

  • 单调递增栈就是从栈底到栈顶是从大到小
  • 单调递减栈就是从栈底到栈顶是从小到大

单调栈主要解决一种名为Next Greater Element的典型问题，在LeetCode中有一类题目就属于这种

496. 下一个更大元素 I : 入门题目，单调栈的基础应用

739. 每日温度 ：经典入门

503. 下一个更大元素 II ：单调栈问题升级为环形问题

84. 柱状图中最大的矩形 ：难度增加

85. 最大矩形 ：题意不好理解，难度较大

239. 滑动窗口最大值 ： 单调队列的应用解法，需要理解

参考链接

展开全文 >>

Java数据结构和算法-栈实现表达式求值

栈

一种先进先出的数据结构，是一种线性表，与之相对应的是队列

栈：后进先出（LIFO-last in first out）:最后插入的元素最先出来。

队列：先进先出（FIFO-first in first out）:最先插入的元素最先出来。

使用栈完成表达式求值的思路

  1. 通过一个index的值(索引)，来遍历我们的表达式
  2. 如果是一个数字，则直接入数栈
  3. 如果是一个符号，则进一步判断
    1. 如果符号栈为空，则直接入栈
    2. 如果符号栈不为空，则进行比较：如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数字，从符号栈中pop出一个符号吗，进行运算，将得到的结果入数栈，然后当前的操作符入符号栈；如果当前操作符的优先级大于栈中的操作符，就直接入符号栈
  4. 当表达式扫描完毕后，就顺序的从数栈和符号栈中pop出相应的数和符号，并运算，将结果压入数栈
  5. 最后数栈中只有一个数字，就是表达式的结果
more >>

展开全文 >>

Java数据结构和算法-单向环形链表

单向环形链表

  • Josephu（约瑟夫、约瑟夫环）问题为

　　 设编号为1,2,3,……n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

  • 提示

　　 用一个不带头节点的环形链表来处理 Josephu 问题：先构成一个有n个节点的单循环链表，然后由k节点起从1开始计数，记到m时，对应节点从链表中删除，然后再从被删除节点又从1开始计数，直到最后一个节点从链表中删除算法结束。

单向环形链表

more >>

展开全文 >>

Java数据结构和算法-插入排序算法

算法思想

​ 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

代码实现

  • 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
    • 从第一个元素开始，该元素可以认为已经被排序；
    • 取出下一个元素，在已经排序的元素序列中从后向前扫描；
    • 如果该元素（已排序）大于新元素，将该元素移到下一位置；
    • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
    • 将新元素插入到该位置后；
    • 重复步骤2~5。
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
package com.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author Taoweidong
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {10, 2, 3, 56, 24, 12, 9, 85, 533, 62};
        System.out.println(JSON.toJSONString(arr));
        insertionSort(arr);
        System.out.println(JSON.toJSONString(arr));
    }

    /**
     * 插入排序
     * @param arr 待排序数组
     */
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            //待插入的数据
            int currentValue = arr[i + 1];
            //当前位置往前都为已经排好序的数据
            int index = i;
            while (index >= 0 && arr[index] > currentValue) {
                //如果当前位置的值小于待插入的数据，则将该位置的数据往后挪一位
                //当前位置的下一个位置为占位的数据
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = currentValue;
        }

    }
}

参考

展开全文 >>

Java数据结构和算法-选择排序算法

算法思想

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

  • 初始状态：无序区为R[1..n]，有序区为空；
  • 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  • n-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
package com.sort;

import com.alibaba.fastjson.JSON;

/**
 * 选择排序
 * 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，
 * 然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
 * 以此类推，直到所有元素均排序完毕
 * 算法分析：最佳情况：T(n) = O(n2)  最差情况：T(n) = O(n2)  平均情况：T(n) = O(n2)
 *
 * @author Taoweidong
 */
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {10, 2, 3, 56, 24, 12, 9, 85, 533, 62};
        System.out.println(JSON.toJSONString(arr));
        selectionSort(arr);
        System.out.println(JSON.toJSONString(arr));
    }

    /**
     * 选择排序
     *
     * @param array 待排序的数组
     */
    public static void selectionSort(int[] array) {
        if (array.length == 0) {
            return;
        }
        for (int i = 0; i < array.length; i++) {

            //i:当前的i就是已经排序的的后一个位置，这个位置的数据也属于没有排序的元素，所以也参与下面找最小值索引的方法


            //遍历剩余没有排序的元素，找到最小值的索引
            int minIndex = i;
            for (int j = i; j < array.length; j++) {
                //找到最小值
                if (array[j] < array[minIndex]) {
                    //保存最小值的索引
                    minIndex = j;
                }
            }

            //将当前的开始位置i和最小值索引minIndex的值交换，这样当前位置i中存放的就是当前剩余待排序数字中的最小值
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }
}

参考

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

心之所向，梦之所在.
一个努力学习的程序猿！

涉及技术：
JavaWeb后端技术开发
SpringCloud微服务
开源爱好者、CI集成


联系QQ:546642132