热题系列9

剑指 Offer 39. 数组中出现次数超过一半的数字

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：0≤n≤50000，数组中元素的值0≤val≤10000
要求：空间复杂度O(1)，时间复杂度O(n)
输入描述：
保证数组输入非空，且保证有解

示例1
输入：[1,2,3,2,2,2,5,4,2]
返回值：2

示例2
输入：[3,3,3,3,2,2,2]
返回值：3

示例3
输入：[1]
返回值：1

题解一：1.用一个dict记录nums数组中每个数字出现的次数。2.返回dict中出现次数大于数组长度一半的数字。class Solution:def majorityElement(self, nums: List[int]) -> int:length = len(nums)numsdict = {}for num in nums:if num not in numsdict:numsdict[num]=1else:numsdict[num]=numsdict[num]+1for num in numsdict:if numsdict[num]>length/2:return num

题解二：因为寻找的数字出现次数大于数组的一半，因此该数位于排序后数组的中间位置

class Solution:def majorityElement(self, nums: List[int]) -> int:new = sorted(nums)length = len(nums)return new[length//2]

678. 有效的括号字符串

在这里插入图片描述
如果没有*：用一个变量，遇到左括号，自增1，遇到右括号，如果此时计数器已经为0了，直接返回false，否则自减1，一旦计数器出现了负数，立即返回false，最后还要看变量是否为0即可
难点是这里有*，它既可以作为(，又可以作为)。问题是它什么时候当做括号来用呢？举个极端例子：
)：此时作为(
)：此时当左括号，右括号，还是空，( 都是不对的
总之：只要在)的前面，就一定可以消除)
算法：
用两个stack，分别存放(和的位置
遍历字符串：
当遇到时，压入栈
当遇到(时，压入(栈
当遇到)时：
如果leftStack和starStack均为空，返回false
如果leftStack不为空，则pop出一个(来抵消当前)，否则从starStack中pop出一个来当做(来抵消)
遍历结束后，我们希望leftStack中没有多余的(；如果有，我们可以尝试用*来抵消它：
当star和left均不为空时，进行循环：
如果left的栈顶左括号的位置在star的栈顶星号的右边，那么就组成了 *( 模式，直接返回false
否则就说明星号可以抵消左括号，各自pop一个元素。
最终退出循环后我们看left中是否还有多余的左括号，没有就返回true，否则false

class Solution {
public:bool checkValidString(string s) {std::stack<int> left, star;for (int i = 0; i < s.size(); ++i) {if(s[i] == '*'){star.push(i);}else if(s[i] == '('){left.push(i);}else{if(left.empty() && star.empty()){return false;}if(!left.empty()){left.pop();}else{star.pop();}}}while (!left.empty() && !star.empty()){if(left.top() > star.top()){return false;}left.pop();star.pop();}return left.empty();}
};

正向把所有星号转成左括号，反向把所有星号转成右括号,统计左括号和右括号的数量，只要有一个小于0，说明不匹配，也就不是一个有效字符串

class Solution {
public:bool checkValidString(string s) {return helper(s, 0, 0);}bool helper(string s, int start, int cnt) {if (cnt < 0) return false;for (int i = start; i < s.size(); ++i) {if (s[i] == '(') {++cnt;} else if (s[i] == ')') {if (cnt <= 0) return false;--cnt;} else {return helper(s, i + 1, cnt) || helper(s, i + 1, cnt + 1) || helper(s, i + 1, cnt - 1);}}return cnt == 0;}
};

面试题 02.05. 链表求和

题目：给定两个用链表表示的整数，每一个节点包含一个数位。这些数式反向存放的，也就是个位排在链表首部，编写函数对这两个整数求和，并用链表形式返回结果。

示例：
输入：（7->1->6）和(5->9->2)
即617+295
输出：2->1->9 即912

struct ListNode
{int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};
class Solution
{
public:ListNode*  TwoList_Sum(ListNode* l1,ListNode* l2){ListNode* head=new ListNode(-1);ListNode* p=head;ListNode* p1=l1;ListNode* p2=l2;int sum=0;int flag=0;while(p1 || p2 || flag){sum=0;if(p1){sum+=p1->val;p1=p1->next;}if(p2){sum+=p2->val;p2=p2->next;}sum+=flag;ListNode* temp=new ListNode(sum % 10);p->next=temp;flag=sum / 10;p=p->next;}return head->next;}
};

71. 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格绝对路径（以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（…）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，‘//’）都被视为单个斜杠 ‘/’ 。对于此问题，任何其他格式的点（例如，‘…’）均被视为文件/目录名称。
请注意，返回的规范路径必须遵循下述格式：
始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的规范路径。

示例 1：
输入：path = “/home/”
输出：“/home”
解释：注意，最后一个目录名后面没有斜杠。

示例 2：
输入：path = “/…/”
输出：“/”
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：
输入：path = “/home//foo/”
输出：“/home/foo”
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：
输入：path = “/a/./b/…/…/c/”
输出：“/c”
提示：

1 <= path.length <= 3000
path 由英文字母，数字，‘.’，‘/’ 或 ‘_’ 组成。
path 是一个有效的 Unix 风格绝对路径。

解题思路
利用栈。如果是…且栈里有元素，则弹出栈顶。如果是其他的则压栈，Python可以直接利用split去除掉多余的/，所以不用考虑

class Solution:def simplifyPath(self, path: str) -> str:path = path.split('/')stack = []for item in path:if item == '':continueif item == '..':if len(stack) > 0:stack.pop()elif item != '.':stack.append(item)return "/"+'/'.join(stack)

679. 24 点游戏

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
示例 1:
输入: [4, 1, 8, 7]
输出: True
解释: (8-4) * (7-1) = 24

示例 2:
输入: [1, 2, 1, 2]
输出: False

注意:
除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

思路：回溯
抛开本题，先说一下，我们平时玩 24 点游戏一般顺序是：
选择两个数字，进行四项运算；
然后就计算结果与剩下两个数字中，再次选取两个数字，再进行四项运算，得到结果；
最终剩下两个数字，进行四项运算，看最终结果是否等于 24。
现在看本题，我们也是采用上面的形式进行枚举，去尝试所有可能的组合。
这里额外提及一下，在例题当中出现了括号’(’、’)’，这里括号有优先级。但是在这里，我们不做处理，因为在枚举的时候，是包含这种情况的。
还有个需要注意的地方。题目中说明除法运算是实数除法，并不是整数除法，那么这里会涉及到精度问题。这里默认只要最终结果误差小于 1e-6，那么认为相等。除数不能为 0，这里也同样默认绝对值小于 1e-6，则认为等于 0。
我们知道，四项运算中，加法、乘法是符合交换律的。那么这两项运算当中，两个数字前后位置不影响结果，可考虑跳过其中一种情况。

class Solution:def judgePoint24(self, nums: List[int]) -> bool:def helper(nums):if not nums:return Falseif len(nums) == 1:return abs(nums[0] - 24) < 0.000001for i in range(len(nums)):for j in range(len(nums)):# 不能选取同个位置的数字if i == j:continue# 标记是否最终结果等于 24status = Falsex = nums[i]y = nums[j]# 选取 i,j 对应位置的数字进行计算，其他数字放入数组后续计算new_nums = [nums[k] for k in range(len(nums)) if( k!=i and k!=j)]# 执行四项运算，加法乘法符合交换律，a + b = b + a, a*b=b*a，可跳过其中一项# 这里默认 i > j 部分跳过，or 短路语句# 加法，乘法if i < j:status = status or helper(new_nums + [x+y])status = status or helper(new_nums + [x*y])# 减法status = status or helper(new_nums + [x-y])# 除法if abs(y) > 0.000001:status = status or helper(new_nums + [x/y])if status:return Truereturn Falsereturn helper(nums)

44. 通配符匹配

给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够完全匹配输入字符串（而不是部分匹配）。

示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。

示例 2：
输入：s = “aa”, p = “”
输出：true
解释：'’ 可以匹配任意字符串。

示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

方法一：动态规划
解题步骤
初始化状态数组：创建一个二维布尔数组 ( dp ) ，其中 ( dp[i][j] ) 表示字符串 ( s ) 的前 ( i ) 个字符是否与模式 ( p ) 的前 ( j ) 个字符匹配。
处理边界条件：
( dp[0][0] = \text{True} )，两个空字符串是可以匹配的。
( dp[i][0] = \text{False} )，空模式不能匹配非空字符串。
( dp[0][j] )，只有当 ( p ) 的前 ( j ) 个字符全部为 ‘’ 时才为真。
填充状态数组：
如果 ( p[j-1] == ‘?’ ) 或 ( s[i-1] == p[j-1] )，则 ( dp[i][j] = dp[i-1][j-1] )。
如果 ( p[j-1] == ‘’ )，则 ( dp[i][j] = dp[i][j-1] )（不使用 '’) 或 ( dp[i-1][j] )（使用 ‘’）。
返回结果：( dp[len(s)][len§] )。

def isMatch(s: str, p: str) -> bool:m, n = len(s), len(p)dp = [[False] * (n + 1) for _ in range(m + 1)]dp[0][0] = Truefor j in range(1, n + 1):if p[j - 1] == '*':dp[0][j] = dp[0][j - 1]for i in range(1, m + 1):for j in range(1, n + 1):if p[j - 1] == '?' or s[i - 1] == p[j - 1]:dp[i][j] = dp[i - 1][j - 1]elif p[j - 1] == '*':dp[i][j] = dp[i][j - 1] or dp[i - 1][j]return dp[m][n]# 示例调用
print(isMatch("aa", "a"))  # 输出: False
print(isMatch("aa", "*"))  # 输出: True

法二：双指针
解题步骤
初始化指针：分别为字符串 ( s ) 和模式 ( p ) 设置两个指针 ( i ) 和 ( j )。
跟踪最后一个星号：使用变量记录最后匹配的 ‘’ 的位置和对应的 ( s ) 的指针位置。
匹配字符串与模式：
如果当前字符匹配或 ( p[j] == ‘?’ )，则 ( i ) 和 ( j ) 都加一。
如果 ( p[j] == ‘’ )，更新星号匹配的位置，将 ( j ) 增加一，并记录 ( i ) 的位置。
如果不匹配，检查是否存在之前匹配的 ‘'，如果有，回溯到最后一个 '’，增加对应的 ( s ) 的指针位置。
检查剩余模式字符：所有主要字符匹配后，确保模式剩余的都是 ‘*’。

def isMatch(s: str, p: str) -> bool:si, pi = 0, 0star_idx = -1match = 0while si < len(s):if pi < len(p) and (s[si] == p[pi] or p[pi] == '?'):si += 1pi += 1elif pi < len(p) and p[pi] == '*':star_idx = pimatch = sipi += 1elif star_idx != -1:pi = star_idx + 1match += 1si = matchelse:return Falsewhile pi < len(p) and p[pi] == '*':pi += 1return pi == len(p)# 示例调用
print(isMatch("aa", "a"))  # 输出: False
print(isMatch("aa", "*"))  # 输出: True

168. Excel表列名称

题目描述：
给定一个正整数，返回它在 Excel 表中相对应的列名称。
例如，

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

示例 1:

输入: 1
输出: “A”
示例 2:

输入: 28
输出: “AB”
示例 3:

输入: 701
输出: “ZY”

解题思路：
Excel序是这样的：A~Z, AA~ZZ, AAA~ZZZ, ……
本质上就是将一个10进制数转换为一个26进制的数
注意：由于下标从1开始而不是从0开始，因此要减一操作。

class Solution(object):def convertToTitle(self, n):""":type n: int:rtype: str"""res=''alp='ABCDEFGHIJKLMNOPQRSTUVWXYZ'while n>0:i=(n-1)%26res+=alp[i]n=(n-i)//26return res[::-1]

剑指 Offer 61. 扑克牌中的顺子

从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。2 ～ 10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
数组长度为 5
数组的数取值为 [0, 13] .

题目样例
示例
输入: [1,2,3,4,5]
输出: True

输入: [0,0,1,2,5]
输出: True

class Solution(object):def isStraight(self, nums):""":type nums: List[int]:rtype: bool"""joker = 0nums.sort()for i in range(4):if nums[i] == 0:joker += 1elif nums[i] == nums[i + 1]:return Falsereturn nums[4] - nums[joker] < 5

1047. 删除字符串中的所有相邻重复项

输入：“abbaca”
输出：“ca”
先删除bb,后剩aaca，再删除aa，剩ca为输出

class Solution(object):def removeDuplicates(self, s):""":type s: str:rtype: str"""stack = []# 以下注释的写法存在问题# 对第一个字符的处理问题，应该保证第一个元素一定进去stack# 以下注释的写法导致对空栈进行pop# for i in s:#     if stack and stack[-1] != i:#         stack.append(i)#     else:#         # stack需要pop#         stack.pop()for i in s:if stack and stack[-1] == i:stack.pop()else:# stack需要popstack.append(i)# return stack 不能直接return stack,输出应该是字符串# 拿字符串直接作为栈，省去了栈还要转为字符串的操作。# stack是列表实现的，可用join实现字符串否则应该先将stack中元素pop后再反转顺序输出return ''.join(stack)

673. 最长递增子序列的个数

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

class Solution:def lengthOfLIS(self, nums: List[int]) -> int:if len(nums) <= 1:return len(nums)dp = [1] * len(nums)result = 1for i in range(1, len(nums)):for j in range(0, i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)result = max(result, dp[i]) #取长的子序列return result

1444. 切披萨的方案数

253. 会议室 II

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回所需会议室的最小数量。

示例 1：
输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：
输入：intervals = [[7,10],[2,4]]
输出：1

提示：
1 <= intervals.length <= 104
0 <= starti < endi <= 106

import heapq # heapq库中的堆默认是最小堆(树中各个父节点的值总是小于或等于任何一个子节点的值)
def minMeetingRooms(intervals):intervals.sort() # 按开始时间排序(按各数组的第一个元素大小排序)heap = []  # 结束时间堆ans = 0for interval in intervals:left, right = interval # 如interval:[0,30]，则left:0;right:30while heap and heap[0] <= left: # heap[0]是堆中的最小值heapq.heappop(heap) # 弹出堆heap中最小值(删除并返回最小值，因为堆的特征是heap[0]永远是最小的元素，所以一般都是删除第一个元素)heapq.heappush(heap, right) # 把元素right加入堆heap中ans = max(ans, len(heap))return ans

443. 压缩字符串

压缩后的长度必须始终小于或等于原数组长度。
数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。
在完成原地修改输入数组后，返回数组的新长度。

进阶：
你能否仅使用O(1) 空间解决问题？

示例 1：
输入：
[“a”,“a”,“b”,“b”,“c”,“c”,“c”]
输出：
返回6，输入数组的前6个字符应该是：[“a”,“2”,“b”,“2”,“c”,“3”]
说明：
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。

示例 2：
输入：
[“a”]
输出：
返回1，输入数组的前1个字符应该是：[“a”]
说明：
没有任何字符串被替代。

示例 3：
输入：
[“a”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”]
输出：
返回4，输入数组的前4个字符应该是：[“a”,“b”,“1”,“2”]。

说明：
由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
注意每个数字在数组中都有它自己的位置。

解析：

1.首先构建一个字符串用于存放字符和其重复的次数
2.遍历字符串，碰到连续的字符计算其连续次数，如果连续相同字符的个数大于1则还需要把字符串的次数统计减进去
3.最后把构建好的char_str，list一下并顺序用char_str中的字符改变chars对应位置的字符并返回char_str的长度

class Solution:def compress(self, chars):""":type chars: List[str]:rtype: int"""strr = ""count = 1i = 1c_len = len(chars)if c_len == 1:return c_lenfor i in range(1,c_len):if chars[i-1] == chars[i]:count += 1else:if count >1:strr += chars[i-1] + str(count)else:strr += chars[i-1] count = 1    if count >1:strr += chars[i] + str(count)else:strr += chars[i]strr = list(strr)chars[::] = strr[::]return len(strr)