热题100_20230503
22、括号生成
题目说明
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
解题思路1
直接每一个位置都放'('或者')'，共有2的2n次方种组合。再设置一个isLegal函数判定最终生成的字符串是否合法，合法则加入最终结果。此法可以通过限定第一个和最后一个位置必须放置'('和')'进行剪枝
解题思路2
设定left数量和right数量分别记录左右括号。在left数量小于n时，是可以一直放置'('的，但是当right >= left时是不能放置')'的，因此在回溯的过程中可以设定一个分支用于下一个位置加左括号或者右括号，在相当于在过程中就判定是否合法了（合法必须满足以上两个要求）
if (open < n) {
chs[index] = '(';
backTracking2(index + 1, chs, open + 1, close, n);
}
if (close < open) {
chs[index] = ')';
backTracking2(index + 1, chs, open, close + 1, n);
}
79、单词搜索
题目说明
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
解题思路
和字符串匹配是一样的道理，只不过多了方向，每次的展开最多会有四个方向，但只要后续有一条路径是可以的当前就可以返回，所以本题的回溯函数设定为Boolean，我们需要函数的返回值来向上传递。因为有四个方向但只要有一个符合就行，所以四个方向之间的关系是“或”，用一个tag来记录并且返回。
在过程中判定可以有效剪枝，当当前位置和对应的字符串的位置不匹配时直接返回false即可，无需凑齐等长之后再用equals()去判定
因为使用过的字符串不能够再次使用，所以我们需要额外设定一个和board同等大小的二维数组used来记录字符的使用状态。
33、搜索旋转排序数组
题目说明
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
解题思路1：
首先要找出旋转的位置，从前往后遍历即可，当nums[i] < nums[i - 1]时说明在此处发生了转折，然后拿头部元素进行比较，如果大于target则从trun处开始向后搜索，否则从当前位置开始搜索。
解题思路2：二分查找：
把nums切成两半，总会有一边是有序的，所以仍然可以使用二分查找的方法。如果左边有序，就判定target是不是在左边的区间里[l, mid]，如果在的话则控制在左边查找，否则在右边查找；反之如果是右边有序就拿右边去判定
// 部分判定代码
if (nums[0] <= nums[mid]) { // 左边有序
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else { // 右边有序
if (nums[mid] < target && target <= nums[nums.length - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}