算法那些事儿

什么是计算机算法？

算法是计算机可以用来解决特定问题的指令列表。算法用于计算的所有领域，它们旨在以有效的方式解决问题。

算法的设计取决于它需要解决的问题的复杂性。对于简单的问题，蛮力可能是可行的。然而，对于更复杂的问题，需要更复杂的算法。

计算机算法无处不在

算法是我们所有数字生活的支柱。它们帮助我们更快、更有效地做出决策。

日常生活中用到的算法例子，比如谷歌搜索引擎、亚马逊推荐系统、Netflix电影推荐系统，算法无处不在！

高效算法和大 O(n)：

优化过程还取决于算法的类型和复杂性。在某些情况下，优化算法可能需要几天或几周的时间，而在其他情况下，可能只需要几小时或几分钟。

当涉及到 Big O(n) 时，时间和空间变量是最重要的。算法是软件工程和计算资源的重要组成部分。对其性能至关重要的组件之一是大 O(n) 符号。此短语中的字母 O(n) 限定了特定算法正在执行多少操作，其中较小的数字意味着更快的执行时间。还取决于我们谈论的 (n) 数量。Big O 专注于最坏的情况。

一项操作的突出之处在于它找到所需结果的效率。操作的大小是它对空间的依赖性以检索所需的结果。

您的操作输入越多，它就会变得越慢。有几种不同的常见类型的“大 O”符号表示输入如何影响操作的效率。其中包括 O(n)、O(1)，这是最有效的算法，以及 O(log n) 等等……

[图片上传失败...(image-8e00a4-1667142054392)]

算法如何工作？

算法用于对列表指令进行排序并找到给定问题的最佳可能解决方案或最优解决方案。排序算法是数据处理中最常用的算法。它们通过保持排序来帮助组织数据点，以便可以轻松访问。

排序算法的不同方法的列表是不完整的，没有提到线性排序，它不是真正的算法，而是一种可以与任何其他排序方法一起使用的技术。

可分为简单和复杂：

• 简单的排序算法称为“冒泡排序”和“插入排序”。
• 复杂的排序算法包括“快速排序”、“合并排序”和“堆排序”。

算法的复杂性

该算法可以通过两种方式来衡量：

算法的时间复杂度

时间复杂度是算法运行时间的上限。它用函数、渐近符号和常数值表示。这可以写成方程、图形或表格的形式，以显示函数对自变量的依赖性。O(n) 的时间复杂度意味着该算法将在与 n 个相关的一系列逻辑步骤中完成。

算法的空间复杂度

空间复杂度是执行算法需要多少空间的量度。算法的空间复杂度可以通过多种方式测量，包括：迭代次数、每次操作处理的位数或每次迭代处理的字数。O(n) 算法在输入大小上是线性的。这意味着它需要与输入大小相关的时间，直到某个最大工作量。

解决问题的多种技术？

解决问题的方法有很多种，可以使用不同的标准进行分类。

最常见的类型是：

1. 分而治之：是解决问题的聪明方法。首先，将问题细分为更小的子问题，解决那些更小的问题，并将所有解决方案组合成问题的最终解决方案。
2. 蛮力：尝试所有可能的解决方案，直到找到满意的解决方案。
3. 随机化：在计算过程中使用随机数来找到问题的解决方案。
4. 贪婪：在较小的零件上寻找有效的解决方案，然后将此最佳解决方案扩展到其余零件
5. 递归：用于通过解决更小、更简单的变化来解决问题的更大和更困难的版本。
6. 回溯：是一种计算机编程技术，将问题划分为子问题，然后将每个问题带到一个尝试的解决方案。如果没有达到所需的解决方案，它将通过找到一条在问题中向前移动的路径来向后工作。
7. 动态规划：专注于解决一系列简单问题中的复杂问题，这些问题只解决一次，而不是为每个问题重新计算。在至少计算一次之后，您需要将其存储在某个地方以便在必要时重新调用它
8. 指针遍历或寻路：在搜索图或网络时，使用经过验证的搜索算法很重要。指针遍历是一种搜索算法，可用于查找从图的一个节点到另一个节点的最短路径。例如，如果我们想使用指针遍历找到从节点 1 到节点 2 的最短路径，那么我们将首先寻找节点 1 的最近邻居，然后，如果没有，则寻找节点父节点的最近邻居
9. 哈希表：哈希表算法用于多种用途，例如碰撞检测和寻路。碰撞检测是当您要确保两个对象不相互交叉时，而寻路是计算两个或多个点之间的最短距离的过程。

我们遇到了问题

如何用简单的英语解决它？

首先要做的是阅读问题并确保您了解说明要求您做什么。

接下来，确定问题中给定的所有变量的可能值，并尝试为每个变量提出一个逻辑解决方案。

最后，试着写出一个算法，从文字而不是代码开始，写出每个程序员都知道的被称为“伪代码”的东西

什么是伪代码？

当我们考虑编程时，经常会看到伪代码。它是程序员用来设计算法或另一个系统功能的语言的描述性词。

这种编程语言可以使用普通语言的结构约定，但它是为人类阅读而不是机器阅读而设计的。

算法示例

这是一个例子，说明我们在面对问题时如何思考以及如何解决问题。

当然这只是我的观点，但我希望你能从中得到一些东西。我会从leetcode得到这个问题

这个关于字谜的问题，字谜是通过重新排列另一个单词的字母而创建的单词。新单词将始终具有原始单词的所有原始字母，但顺序不同。

示例 1

输入： strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

输出： [[“bat”]，[“nat”，“tan”]，[“ate”，“eat”，“tea”]]

您已阅读说明、查看示例并在 Google 上进行了研究。所有这些都应该让您提前为所请求的内容和代码行中包含的内容做好准备。

当然，您仍在尝试弄清楚如何将其放在代码中，但是现在您对解决方案有了一定的了解，您可以着手处理它。

我的想法逐步过程如下：

1. 我可以从输入数据中得到每个单词的一个实例。

2. 这个实例应该让它成为默认实例，并且它应该被排序。

3. 同样，此默认实例将是收集其他实例的键值。

4. 该集合是一个数组，其中的这些值来自已排序的键值。

5. 如果我找不到多个实例，那么我将返回我得到的任何实例。

现在让我们通过想象我们编写了几行代码来进一步分解它。但是这段代码将是一个伪代码。

所以我们需要一种可以存储键值对的表。键将是单词的默认排序实例，值将是同一单词的相同字符内的多个实例值的数组。如果我们找不到相同单词的任何其他实例，那么我们将其单独放入数组中。

所以，

遍历输入数组

对每个字符串进行排序，使其成为我们上面讨论的默认键

键是否存在于哈希表中，然后将未排序的版本放入它的值中

如果没有，则在循环中使用当前值创建一个数组

Javascript中的源代码：

function groupAnagrams(strs) {
//creating the Hash Table
const hashTable = {}
  for (let i = 0; i < strs.length; i++){ //Loop through the input list

  // Creating the default key by sorting out the value from each string

  // To use the Sort method in JS, you need to use it on an array.

  // By using the Split() method, you create an array from this current value that you standing on.

  // By using the join() method, you recreate the string from the group of characters you created with the split() method above.

    const defKey = strs[i].split('').sort().join('')

    if (hashTable[defKey]){ 
  //Checking if the hash table has this value if yes, push the current value which is in that case going to be  different instance from the sorted default instance.

    hashTable[defKey].push(strs[i])

    } else {

    // if not just initialize it with an array

    hashTable[defKey] = [strs[i]]

    }

  }
//Another great method in JS to help you flat all arrays created in the values of hash Table into one array
return Object.values(hashTable)
};

Python中的源代码：

def groupAnagrams(strs):
  hashTable = {}
  for s in strs:
    defKey = ''.join(sorted(s))
    if defKey in hashTable:
      hashTable[defKey].append(s)
    else:
      hashTable[defKey] = [s]
  return hashTable.values()