LeetCode79.单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] 给定 word = "ABCCED", 返回 true 给定 word = "SEE", 返回 true 给定 word = "ABCB", 返回 false
提示：
board 和 word 中只包含大写和小写英文字母。 1 <= board.length <= 200 1 <= board[i].length <= 200 1 <= word.length <= 10^3
分析
经典迷宫搜索题，这里我用dfs实现，对于迷宫搜索题需要注意以下几点：
- 定义四个方向数组，用来坐标模拟行走
- 走过的坐标需要临时标记(回溯)，回来的时候在清除标记
- 注意起始和结尾情况，尽量避免使用String频繁创建新的对象
而本题在搜索途中判断当前字符没有被使用且和目标位置字符相等即可模拟遍历。有一个注意的是一旦找到答案则不需要再进行搜索(需要停止)。
具体代码为：
int x[]= {-1,0,1,0}; int y[]= {0,-1,0,1}; boolean isvalue=false; boolean jud[][]; public boolean exist(char[][] board, String word) { jud=new boolean[board.length][board[0].length]; if(word.length()>board.length*board[0].length)return false; char words[]=word.toCharArray(); for(int i=0;i<board.length;i++) { for(int j=0;j<board[i].length;j++) { jud[i][j]=true; if(words[0]==board[i][j]) dfs(board, 1, words, i, j); jud[i][j]=false; if(isvalue)return true; } } return false; } private void dfs(char[][] board,int index, char words[],int x1,int y1) { // TODO Auto-generated method stub if(isvalue)return; if(index==words.length) { isvalue=true; } else { for(int i=0;i<4;i++) { int xnew=x1+x[i],ynew=y1+y[i]; if(xnew>=0&&xnew<board.length&&ynew>=0&&ynew<board[0].length) { if(!jud[xnew][ynew]&&words[index]==board[xnew][ynew]) { jud[xnew][ynew]=true; dfs(board, index+1, words, xnew, ynew); jud[xnew][ynew]=false; } } } } }
效率有待优化。
LeetCode80. 删除排序数组中的重复项 II
给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下：
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
示例 1：
输入：nums = [1,1,1,2,2,3] 输出：5, nums = [1,1,2,2,3] 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3] 输出：7, nums = [0,0,1,1,2,3,3] 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104 -104 <= nums[i] <= 104 nums 按递增顺序排列
分析：
刷这题前回顾26题 删除排序数组中的重复项
而这一题同样也是要用双指针原地修改数组。但是每个元素最多出现两次。对于两次我们应该如何考虑呢？
枚举每个数的个数？然后大于二只使用两个？其实更好的方式是这个数和它前面第二个数进行比较，如果相等那么可以使用，如果不相等那么无法使用。如下图的比较有效数字就可以看出：
但是我们在原地如何操作这个数组呢？- 双指针
可以用一个fast用来遍历，用slow来表示存储真实有效的区域。
- 在具体的比较上，fast只需要和slow前面第二个元素比较即可(因为slow是真实储存的结果标记)，如果相等，那么直接fast继续，如果不等，那么将数据复制到slow且slow右移一位。
- slow 初始为2，fast初始为2(前面两个即使相同也会放到结果中)
具体看一次模拟过程：
实现代码：
public int removeDuplicates(int[] nums) { if(nums.length<2) return nums.length; int slow=2; for(int fast=2;fast<nums.length;fast++) { if(nums[fast]==nums[slow-2]) { continue; } else { nums[slow++]=nums[fast]; } } return slow; }
LeetCode81.搜索旋转排序数组 II
题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false
进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
分析
在做之前还是要 看下这道题：搜索旋转排序数组 。这题和那题的区别就是需要考虑重复的情况。
而这题最好的方法当然也是二分，但是二分的过程还是需要分类考虑一些情况的。
这题我的方法和其他人的题解不太一样吧，大部分人是按照几种情况进行分类。但是核心也都很相似，要指导当前的mid在那个区间里面(每个区间可能出现的结果)。进行分类讨论情况。
个人ac的代码为：
public static boolean search(int[] nums, int target) { if(nums.length==0)return false; if(nums[0]==target||nums[nums.length-1]==target)return true; int l=0,r=nums.length-1; while (l<r) { //处理重复数字 while (l<r&&nums[l]==nums[l+1]) { l++; } while (r>l&&nums[r]==nums[r-1]) { r--; } int mid=(l+r)/2; //System.out.println(l+" "+r+" "+mid); if(nums[mid]==target) return true; else if (nums[mid]>target) {//中间的比目标值大 if(target>nums[r])//只可能出现在左侧 { r=mid; } else if(target<nums[r])//目标小于最右侧 当前位置可能在左半区域 也可可能在右半区域 { if(nums[mid]>=nums[r])//在左侧区域 { l=mid+1; } else//在右侧区域 { r=mid; } } } else if(nums[mid]<target){//nums[mid]<target 中间的比目标值小 if(target<nums[r])//目标值比最右侧的小 { l=mid+1; } else if(target>nums[r])//目标值比最右侧大 只能往左侧才有希望 { //但是需要分析当前在哪里 if(nums[mid]<nums[l])//在左侧区域 { r=mid; } else//在右侧区域 { l=mid+1; } } } } return false; }
大众方法为：
public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) { return false; } int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right-left) / 2; if (nums[mid] == target) { return true; } if (nums[left] == nums[mid]) { left++; continue; } //前半部分有序 if (nums[left] < nums[mid]) { //target在前半部分 if (nums[mid] > target && nums[left] <= target) { right = mid - 1; } else { //否则，去后半部分找 left = mid + 1; } } else { //后半部分有序 //target在后半部分 if (nums[mid] < target && nums[right] >= target) { left = mid + 1; } else { //否则，去后半部分找 right = mid - 1; } } } //一直没找到，返回false return false; }
结语
原创不易，bigsai请你帮两件事帮忙一下:
- star支持一下， 您的肯定是我在平台创作的源源动力。
- 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见！
