算法与数据结构全阶班-左程云版(二)基础阶段之1.复杂度、对数器、二分法和异或运算(下)

简介: 本文主要介绍了数据结构与算法的基本概念,包括算法评价指标、复杂度、对数器、二分法和异或运算。

4)局部最小值问题

一个无序数组,任意两个相邻元素都不相等,找到一个局部最小值。

package complexity01;
/**
 * @author Corley
 * @date 2021/10/4 9:45
 * @description LeetCodeAlgorithmZuo-complexity01
 */
public class BinarySearchLocalMin {
    public static int getLessIndex(int[] arr) {
        if (null == arr || 0 == arr.length) {
            return -1;
        }
        if (1 == arr.length || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1, right = arr.length - 2;
        int mid;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (arr[mid - 1] < arr[mid]) {
                right = mid - 1;
            } else if (arr[mid + 1] < arr[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
    public static void main(String[] args) {
        System.out.println(getLessIndex(new int[]{0, 2, 5, 5, 6, 7, 7, 7, 9, 12}));
        System.out.println(getLessIndex(new int[]{8, 2, 5, 7, 6, 4, 7, 2, 3, 4}));
        System.out.println(getLessIndex(new int[]{7, 2, 8, 5, 6, 9, 7, 3, 9, 0}));
    }
}

5.异或运算

认识异或运算

异或运算:相同为0,不同为1

同或运算:相同以1,不同为0

能长时间记住的概率接近0%

所以,异或运算就记成无进位相加!

2345_image_file_copy_98.jpg

异或运算的性质

1)0^N==N

N^N == 0

2)异或运算满足交换律和结合率

2345_image_file_copy_99.jpg

上面的两个性质用无进位相加来理解就非常的容易

如何不用额外变量交换两个数

2345_image_file_copy_100.jpg

可以进行这种操作的前提是变量属于不同的对象,即指向不同的内存,否则对象的数值会被置为0,但是允许两个对象的值相等。

一个数组中有一个数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这一个数。

2345_image_file_copy_101.jpg

代码:

public static void getOneOddTimes(int[] arr) {
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    System.out.println(eor);
}

怎么把一个int类型的数,提取出最右侧的1

方法:N & ((~N) + 1)

2345_image_file_copy_102.jpg

一个数组中有两个数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两个数。

2345_image_file_copy_103.jpg

如下:

/*
一个数组中有两个数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两个数。
 */
public static void getTwoOddTimes(int[] arr) {
    int eor1 = 0;
    for (int j : arr) {
        eor1 ^= j;
    }
    // 提取最右边的1
    int rightOne = eor1 & (~eor1 + 1);
    int eor2 = 0;
    for (int j : arr) {
        if ((j & rightOne) != 0) {
            eor2 ^= j;
        }
    }
    int num1 = eor2, num2 = eor1 ^ eor2;
    System.out.println(num1 + " " + num2);
}
public static void main(String[] args) {
    int[] arr = {1, 2, 2, 4, 6, 6, 6, 6, 6, 4, 4, 4, 7, 7, 6, 7, 8, 8};
    getTwoOddTimes(arr);
}

给定一个数,计算这个数的二进制形式中1的个数。

public static int bit1Count(int num) {
    int count = 0;
    int rightOne;
    while (num != 0) {
        rightOne = num & (~num + 1);
        count++;
        num ^= rightOne;
    }
    return count;
}
public static void main(String[] args) {
    // int[] arr = {1, 2, 2, 4, 6, 6, 6, 6, 6, 4, 4, 4, 7, 7, 6, 7, 8, 8};
    // getTwoOddTimes(arr);
    System.out.println(Integer.toBinaryString(12345));
    System.out.println(bit1Count(12345));
}

总结

左神极力推荐的对数器是检验算法实现正确性的有力工具,可以覆盖几乎所有情况的测试用例,无死角实现对算法的验证。同时异或也是可以在算法实现中加快运算效率的技巧。

相关文章
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
66 1
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
77 0
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
185 10
 算法系列之数据结构-二叉树
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
155 3
 算法系列之数据结构-Huffman树
|
6月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
187 22
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
194 30
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
219 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
49 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
8月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
332 77

热门文章

最新文章