609.在系统中查找重复文件

题目描述

给定一个目录信息列表，包括目录路径，以及该目录中的所有包含内容的文件，您需要找到文件系统中的所有重复文件组的路径。一组重复的文件至少包括二个具有完全相同内容的文件。
输入列表中的单个目录信息字符串的格式如下：
“root/d1/d2/…/dm f1.txt(f1_content) f2.txt(f2_content) … fn.txt(fn_content)”
这意味着有 n 个文件（f1.txt, f2.txt … fn.txt 的内容分别是 f1_content, f2_content … fn_content）在目录 root/d1/d2/…/dm 下。注意：n>=1 且 m>=0。如果 m=0，则表示该目录是根目录。
该输出是重复文件路径组的列表。对于每个组，它包含具有相同内容的文件的所有文件路径。文件路径是具有下列格式的字符串：
“directory_path/file_name.txt”

示例 1：
输入：
[“root/a 1.txt(abcd) 2.txt(efgh)”, “root/c 3.txt(abcd)”, “root/c/d 4.txt(efgh)”, “root 4.txt(efgh)”]
输出：
[[“root/a/2.txt”,”root/c/d/4.txt”,”root/4.txt”],[“root/a/1.txt”,”root/c/3.txt”]]

题目链接

思路

1.哈希表
首先我们通过字符串操作获取目录路径、文件名和文件内容。我们使用哈希映射（HashMap）来寻找重复文件，哈希映射中的键（key）是文件内容，值（value）是存储路径和文件名的列表。
我们遍历每一个文件，并把它加入哈希映射中。在这之后，我们遍历哈希映射，如果一个键对应的值列表的长度大于 1，说明我们找到了重复文件，可以把这个列表加入到答案中。

43.字符串相乘

题目描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”

题目链接

思路

1.将num1、num2两个字符串转为整数相乘，然后将结果转为字符串返回
2.使用python内置函数eval()执行num1 * num2表达式，将eval函数返回结果转为字符串返回
3.做加法（详细思路见leetcode题解）
4.做乘法（详细思路见leetcode题解）

22.括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
有效括号组合需满足：左括号必须以正确的顺序闭合。

题目链接

思路

1.暴力法
可以生成所有 2^2n 个 ‘(‘ 和 ‘)’ 字符构成的序列，然后我们检查每一个是否有效即可。
2.回溯法
方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 ‘(‘ or ‘)’，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果左括号数量不大于 n，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
3.按括号序列的长度递归

itertools.product()

使用product()前需要导入itertools库
用法1：

print(list(itertools.product(‘a', repeat=4)))   # 等价于 print(list(itertools.product('a', 'a', 'a', 'a')))

a = ['a', 'b', 'c']
print(list(itertools.product(a, repeat=2)))  # s等价于 print(list(itertools.product(a, a)))

用法2：

print(list(itertools.product(a, b)))  # 等价于 print(list((x, y) for x in a for y in b))

17.电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

题目链接

思路

1.遍历并组合每一个数字对应的字母列表 –> letterCombinations()
点击这里查看完整解题思路！！！
2.使用内置库 –> letterCombinations1()
3.回溯 –> letterCombinations2()
回溯法和使用内置库思路见leetcode题解

5.最长回文串

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

题目链接

思路

1.暴力解法
2.动态规划
3.中心扩展算法
4.Manacher 算法
注：算法详情请参考leetcode题解

几种方法的总结！！！强烈推荐！！！

657.机器人能够返回原点

题目描述

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

题目链接

思路

起始时机器人的坐标为 (0,0)，在遍历完所有指令并对机器人进行移动之后，判断机器人的坐标是否为 (0,0) 即可。

具体来说，我们用两个变量 x 和 y 来表示机器人当前所在的坐标为 (x,y)，起始时 x=0，y=0。接下来我们遍历指令并更新机器人的坐标：
如果指令是 U，则令 y=y−1
如果指令是 D，则令 y=y+1
如果指令是 L，则令 x=x−1
如果指令是 R，则令 x=x+1
最后判断 (x,y) 是否为 (0,0) 即可。

557.反转字符串中的单词3

题目描述

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例：
输入：”Let’s take LeetCode contest”
输出：”s’teL ekat edoCteeL tsetnoc”

题目链接

思路

1.将字符串按照空格划分开得到字符串中的每一个单词,然后将每个单词反转
，在将反转后的所有单词用空格拼接起来
2.使用额外空间
开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
3.原地解法
此题也可以直接在原字符串上进行操作，避免额外的空间开销。当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符……如此反复，就可以在原空间上翻转单词。
需要注意的是，原地解法在某些语言（比如 Java，JavaScript，python）中不适用，因为在这些语言中 String 类型是一个不可变的类型。
在python中可以先将字符串转为列表然后进行算法设计。

更多思路参考“一行流”，简直牛逼！！！

551.学生出勤记录1

题目描述

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
‘A’：Absent，缺勤
‘L’：Late，迟到
‘P’：Present，到场
如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
按 总出勤 计，学生缺勤（’A’）严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（’L’）记录。
如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。

示例 1：
输入：s = “PPALLP”
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。

题目链接

思路

1.一次遍历
可奖励的出勤记录要求缺勤次数少于 2 和连续迟到次数少于 3。判断出勤记录是否可奖励，只需要遍历出勤记录，判断这两个条件是否同时满足即可。
遍历过程中，记录缺勤次数和连续迟到次数，根据遍历到的字符更新缺勤次数和连续迟到次数：
如果遇到 ‘A’，即缺勤，则将缺勤次数加 1，否则缺勤次数不变；
如果遇到 ‘L’，即迟到，则将连续迟到次数加 1，否则将连续迟到次数清零。
如果在更新缺勤次数和连续迟到次数之后，出现缺勤次数大于或等于 2 或者连续迟到次数大于或等于 3，则该出勤记录不满足可奖励的要求，返回 false。如果遍历结束时未出现出勤记录不满足可奖励的要求的情况，则返回 true。

541.反转字符串2

题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：
输入：s = “abcdefg”, k = 2
输出：”bacdfeg”

题目链接

思路

反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串