162. 寻找峰值
2021.9.15 每日一题
题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
二分，怎么说呢，其实一下子还想不太通
首先要注意给定的条件 nums[-1] = nums[n] = -∞ 还有 nums[i] != nums[i + 1]
这样保证了这个数组肯定是有峰值的
如果nums[mid] < nums[mid + 1]，那么说明是一个上坡，这个上坡的峰值肯定值mid+1到right，所以left=mid+1；如果相反，那么说明是一个下坡，所以峰值可能在 left 到mid部分，所以right = mid；
而走到最后，可以保证这个点肯定不是在上坡，也不是在下坡；或者说是上坡和下坡的交汇点，所以是峰值
class Solution {
public int findPeakElement(int[] nums) {
int l = nums.length;
//二分查找
int left = 0;
int right = l -1;
while(left < right){
int mid = left + (right - left) / 2;
if(nums[mid] < nums[mid + 1]){
left = mid + 1;
}else
right = mid;
}
return left;
}
}
212. 单词搜索 II
题目描述
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例 1：
输入：board = [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words = [“oath”,“pea”,“eat”,“rain”]
输出：[“eat”,“oath”]
示例 2：
输入：board = [[“a”,“b”],[“c”,“d”]], words = [“abcb”]
输出：[]
提示：
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
首先将words中的单词构成一个字典树，然后回溯遍历board，如果能查到对应的单词，就加入set集合中（因为可能多个路径都有这个单词，所以要去重）
class Solution {
class Trie{
String s;
Trie[] child;
public Trie(){
child = new Trie[26];
}
public void insert(String word){
Trie node = this;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
//如果没有这个树，就建立
if(node.child[c - 'a'] == null){
node.child[c - 'a'] = new Trie();
}
node = node.child[c - 'a'];
}
node.s = word;
}
}
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
int m;
int n;
boolean[][] used;
//用set去重
Set<String> set = new HashSet<>();
char[][] board;
public List<String> findWords(char[][] board, String[] words) {
this.board = board;
m = board.length;
n = board[0].length;
used = new boolean[m][n];
int l = words.length;
//构建字典树
Trie trie = new Trie();
for(String s : words){
trie.insert(s);
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int id = board[i][j] - 'a';
//如果这个点存在在字典树中，就回溯
if(trie.child[id] != null){
used[i][j] = true;
dfs(i, j, trie.child[id]);
used[i][j] = false;
}
}
}
List<String> res = new ArrayList<>();
for(String s : set){
res.add(s);
}
return res;
}
public void dfs(int x, int y, Trie node){
//如果到达了一个word，就加入set中
if(node.s != null){
set.add(node.s);
}
for(int[] dir : dirs){
int nx = x + dir[0];
int ny = y + dir[1];
if(nx < 0 || ny < 0 || nx >= m || ny >= n || used[nx][ny])
continue;
int id = board[nx][ny] - 'a';
if(node.child[id] != null){
used[nx][ny] = true;
dfs(nx, ny, node.child[id]);
used[nx][ny] = false;
}
}
}
}
36. 有效的数独
2021.9.17 每日一题
题目描述
请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
示例 1：
输入：board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
示例 2：
输入：board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-sudoku
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
之前看的别人的写的，现在还能想起来
就是创建三个二维数组分别表示行列和九宫格，然后遍历到一个数就存储到对应的位置，如果有相同的，就返回false
class Solution {
public boolean isValidSudoku(char[][] board) {
//先创建三个二维数组，分别对应行、列、宫
//然后遍历数独，如果存在相应的元素
int[][] row = new int[9][10];
int[][] col = new int[9][10];
int[][] box = new int[9][10];
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
//遍历数独
char num = board[i][j];
if(num != '.'){
int n = (int)(num - '0');
int b = i / 3 * 3 + j / 3;
if(row[i][n] == 1 || col[j][n] == 1 || box[b][n] == 1)
return false;
else{
row[i][n] += 1;
col[j][n] += 1;
box[b][n] += 1;
}
}
}
}
return true;
}
}
三叶姐的位运算：
class Solution {
public boolean isValidSudoku(char[][] board) {
int[] row = new int[10], col = new int[10], area = new int[10];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.') continue;
int u = c - '0';
int idx = i / 3 * 3 + j / 3;
if ((((row[i] >> u) & 1) == 1) || (((col[j] >> u) & 1) == 1) || (((area[idx] >> u) & 1) == 1)) return false;
row[i] |= (1 << u);
col[j] |= (1 << u);
area[idx] |= (1 << u);
}
}
return true;
}
}
作者：AC_OIer
链接：https://leetcode-cn.com/problems/valid-sudoku/solution/gong-shui-san-xie-yi-ti-san-jie-ha-xi-bi-ssxp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。