KWAN的解忧杂货铺

# 一. 初识算法

# 1.什么是算法？

定义:

在数学和计算机科学领域，算法是一系列有限的严谨指令，通常用于解决一类特定问题或执行计算

不正式的说，算法就是任何定义优良的计算过程：接收一些值作为输入，在有限的时间内，产生一些值作为输出。

# 2.什么是数据结构？

定义:

在计算机科学领域，数据结构是一种数据组织、管理和存储格式，通常被选择用来高效访问数据

数据结构是一种存储和组织数据的方式，旨在便于访问和修改

# 3.解题思路

  • 打印中间值,可以找出规律
  • 对于不懂的题解,可以打出中间的关键值,帮助自己理解

# 4.解题模板

if 有思路
    开写
else
    去看相关标签，确定具体解题方法
    if 有思路
        开写
    else
        看提示信息
        if 有思路
            开写
        else
            看答案
1
2
3
4
5
6
7
8
9
10
11
12

# 二.算法学习

# 1.学习路线

image-20230702120714077

image-20230915202343419

image-20230911014538257

# 2.链表

链表从后往前遍历有两种常用的方式：

  1. 反转链表再正向遍历

可以先将链表反转，然后正向遍历即可实现从后往前遍历。这种方法的时间复杂度为 O(N)，其中 N 为链表的长度。

CLASS LISTNODE:
    DEF __INIT__(SELF, VAL=0, NEXT=NONE):
        SELF.VAL = VAL
        SELF.NEXT = NEXT
DEF REVERSELIST(HEAD):
    PREV, CURR = NONE, HEAD
    WHILE CURR:
        NEXT_NODE = CURR.NEXT
        CURR.NEXT = PREV
        PREV = CURR
        CURR = NEXT_NODE
    RETURN PREV

DEF TRAVERSELIST(HEAD):
    NEW_HEAD = REVERSELIST(HEAD)
    WHILE NEW_HEAD:
        PRINT(NEW_HEAD.VAL)
        NEW_HEAD = NEW_HEAD.NEXT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  1. 递归遍历

可以使用递归的方式遍历链表，每次遍历到链表末尾时再开始输出节点的值。这种方法的时间复杂度也为 O(N)，其中 N 为链表的长度。

CLASS LISTNODE:
    DEF __INIT__(SELF, VAL=0, NEXT=NONE):
        SELF.VAL = VAL
        SELF.NEXT = NEXT

DEF TRAVERSELIST(HEAD):
    IF NOT HEAD:
        RETURN
    TRAVERSELIST(HEAD.NEXT)
    PRINT(HEAD.VAL)
1
2
3
4
5
6
7
8
9
10

需要注意的是，递归遍历链表时，如果链表过长，可能会导致递归层数过深，从而出现栈溢出的情况。因此，如果链表长度较大，建议使用反转链表再正向遍历的方法。

# 三.常见查找算法

查找算法是一种在数据集中寻找特定数据项的方法。通常，数据集是在计算机程序中存储的，例如数组、链表或散列表。在编写程序时，查找算法是非常重要的，它有助于快速找到所需的数据。在本文中，我们将介绍一些基本的查找算法及其特点。

# 1.线性查找

线性查找也称为顺序查找，是一种最简单的查找算法。在这种算法中，我们从数据集的开头开始，逐个比较每个数据项，以寻找要查找的数据。如果我们找到了目标数据，查找过程就结束了。如果我们到达数据集的末尾，仍然找不到目标数据，则可以认为它不存在于数据集中。

线性查找的时间复杂度是 O(n)，其中 n 是数据集的大小。因此，它在大型数据集中可能会很慢。然而，在小型数据集中，它仍然是一种非常有用的算法。

# 2.二分查找

二分查找也称为折半查找，是一种更快速的查找算法。但前提是，数据集必须已经排序。在二分查找中，我们取数据集的中间值，然后将目标与中间值进行比较。如果目标小于中间值，则在左侧子集中继续查找；如果目标大于中间值，则在右侧子集中继续查找。每次比较都会缩小要搜索的数据集的大小。

二分查找的时间复杂度是 O(log n)，其中 n 是数据集的大小。这种算法在大型数据集中非常有效，但在小型数据集中可能并不是最快的选择。

# 3.哈希表查找

哈希表查找也称为散列表查找，是另一种常见的查找算法。它利用哈希函数将数据项映射到散列表中的位置。在查找过程中，我们只需通过哈希函数计算目标数据的位置，然后检查该位置是否包含目标数据。

哈希表查找的时间复杂度是 O(1)。这使得它成为大型数据集中最快的查找算法之一。但是，哈希表查找的效率取决于哈希函数的质量。如果两个数据项映射到相同的位置，就会发生哈希冲突，这可能会导致性能下降。

# 4.小结

在编写程序时，我们需要选择适合数据集大小和其他要求的最佳查找算法。例如，如果数据集很小，则线性查找可能是最快的选择；如果数据集已经排序，则二分查找是非常有用的。然而，在大型数据集中，哈希表查找通常是最好的选择。了解不同类型的查找算法及其特点可以帮助我们在编写程序时做出明智的选择。

# 四.小细节

# 1.长度

  • 字符串的 length 是 length()
  • 数组的 length 是 length

# 2.pop 和 poll

  • pop 获取并删除栈顶部元素
  • poll 获取并删除队列头部元素

# 3.offer 和 push

  • offer 是队列的添加元素的方法
  • push 是栈的添加元素的方法

# 五.题目汇总

# 1.待处理的题目

贪心
动态规划
HTTPS://LEETCODE.CN/PROBLEMS/MAXIMUM-ALTERNATING-SUBSEQUENCE-SUM/DESCRIPTION/
1
2
3
4

# 六.如何判断奇偶

判断一个数是奇数还是偶数有许多方法，以下是一些常见的方法：

# 1.除法运算

  • 如果一个整数除以 2 的余数为 0，那么它是偶数；否则，它是奇数。
if num % 2 == 0:
    print("偶数")
else:
    print("奇数")
1
2
3
4

# 2.位运算

  • 利用位运算，通过检查最低位的值来判断奇偶性。例如，(num & 1) == 0 表示 num 是偶数。
  • & 是位与运算符，它对两个二进制数的每一位执行与操作。如果两个相应位都为 1，则结果为 1；否则，结果为 0。
  • (len & 1) 表示对整数 len 和二进制数 1 进行位与运算。这将返回一个新的整数，其二进制表示仅保留 len 最低位与 1 相对应的位。
  • == 0 检查上一步的结果是否等于 0。如果 (len & 1) 的结果为 0，则整数的最低位是 0；如果结果为 1，则最低位是 1。
  • (len & 1) == 0 表达式用于检查整数 len 的二进制表示的最低位是否为 0。如果条件成立（即整数的最低位是 0），则整数是偶数；如果条件不成立（即最低位是 1），则整数是奇数。
if (num & 1) == 0:
    print("偶数")
else:
    print("奇数")
1
2
3
4

# 3.字符串比较

  • 将整数转换为字符串，然后检查字符串的最后一位数字。
if str(num)[-1] in ['0', '2', '4', '6', '8']:
    print("偶数")
else:
    print("奇数")
1
2
3
4

# 4.列表判断

  • 利用一个包含偶数的列表，判断给定的数是否在列表中。
even_numbers = [0, 2, 4, 6, 8]
if num in even_numbers:
    print("偶数")
else:
    print("奇数")
1
2
3
4
5

# 5.数学性质

  • 利用数学性质，例如奇数和偶数之间的关系，判断给定的数。
if num // 2 * 2 == num:
    print("偶数")
else:
    print("奇数")
1
2
3
4

# 6.使用函数

  • 定义一个函数来判断奇偶性，使代码更模块化。
def is_even(n):
    return n % 2 == 0

if is_even(num):
    print("偶数")
else:
    print("奇数")
1
2
3
4
5
6
7

选择适合你代码场景的方法，这些方法在实际编程中都是可行的。

上次更新: 10/29/2024, 10:27:50 AM

← 03-如何科学上分 →