数组
二分查找
704.二分查找
这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件
第一种写法：左闭右闭 [left, right]
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
mid = left +( (right - left) >>1 );
if (nums[mid] < target) {
left = mid + 1;
}else if (nums[mid] > target) {
right = mid - 1;
}else {
return mid;
}
}
return -1;
}
}
第二种写法：左闭右开 [left, right)
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length;//定义区间：[left, right)
int mid;
while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
mid = left +( (right - left) >>1 );
if (nums[mid] < target) {
left = mid + 1;//target 在右区间，在[middle + 1, right)中
}else if (nums[mid] > target) {
right = mid; // target 在左区间，在[left, middle)中
}else {
return mid;
}
}
return -1;
}
}
35.搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
思路：无非就是四种情况
- 目标值在数组所有元素之前
- 目标值等于数组中某一个元素
- 目标值插入数组中的位置
- 目标值在数组所有元素之后
暴力尝试
class Solution {
public int searchInsert(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] >= target) return i;
}
return nums.length;
}
}
二分法
左闭右闭版本
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + (( right - left ) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
//处理数组中找不到对应数字的三种情况
return left;//这里也可以写return right+1;
}
}
左闭右开版本
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(left < right) {
int mid = (left + right) / 2;
if ( nums[mid] = target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return right;//left
}
}
34.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路：三种情况
- 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
- 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
- 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}
接下来，分别编写两个方法来寻找左右边界,再处理左右边界对应三种情况
注意：写的方法查询的边界不包含target
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = left(nums, target);
int right = right(nums, target);
//情况1,一直大于或者小于，有一个边界一定未曾赋值
if (left == -2 || right == -2 ) return new int[] {-1, -1};
//情况3
if (right - left > 1) return new int[] {left + 1, right - 1};
//情况2
return new int[] {-1, -1};
}
public int left(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] >= target) { // 寻找左边界，nums[middle] == target的时候更新right
right = middle - 1;
leftBorder = right;
} else {
left = middle + 1;
}
}
return leftBorder;
}
public int right(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 定义target在左闭右闭的区间里，[left, right]
int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况，处理情况一target在数组范围的左边，例如数组[3,3]，target为2
while (left <= right) { // 当left==right，区间[left, right]依然有效
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else { // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
}
解法二
// 解法2
// 1、首先，在 nums 数组中二分查找 target；
// 2、如果二分查找失败，则 binarySearch 返回 -1，表明 nums 中没有 target。此时，searchRange 直接返回 {-1, -1}；
// 3、如果二分查找成功，则 binarySearch 返回 nums 中值为 target 的一个下标。然后，通过左右滑动指针，来找到符合题意的区间
class Solution {
public int[] searchRange(int[] nums, int target) {
int index = binarySearch(nums, target); // 二分查找
if (index == -1) { // nums 中不存在 target，直接返回 {-1, -1}
return new int[] {-1, -1}; // 匿名数组
}
// nums 中存在 targe，则左右滑动指针，来找到符合题意的区间
int left = index;
int right = index;
// 向左滑动，找左边界
while (left - 1 >= 0 && nums[left - 1] == nums[index]) { // 防止数组越界。逻辑短路，两个条件顺序不能换
left--;
}
// 向左滑动，找右边界
while (right + 1 < nums.length && nums[right + 1] == nums[index]) { // 防止数组越界。
right++;
}
return new int[] {left, right};
}
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int mid;
while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
mid = left +( (right - left) >>1 );
if (nums[mid] < target) {
left = mid + 1;
}else if (nums[mid] > target) {
right = mid - 1;
}else {
return mid;
}
}
return -1;
}
}
上方两种摘自代码随想录
我的方法
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = left(nums, target);
int right = right(nums, target);
//针对情况一和情况二
//情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返 回{-1, -1}
//例如数组{3, 4, 5}，target为2-----这种情况left = 0, right = -1
//例如数组{3, 4, 5}，target为6-----这种情况left = length, right = length - 1
//情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
//left == right后，要么是left + 1, 要么是right - 1
if (left > right ) return new int[] {-1, -1};
return new int[] {left, right};
}
//left的另一种写法，这种方法求出的leftborder就是target
public int left(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if (arr[mid] >= target) {
right = mid - 1;
}else if(arr[mid] < target){
left = mid + 1;
}
}
return left;
}
//right的另一种写法
public int right(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while(left <= right) {
int mid = (left + right) / 2;
if (arr[mid] <= target) {
left = mid + 1;
}else if(arr[mid] > target){
right = mid - 1;
}
}
return right;
}
}
69.x的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5
思路：利用二分法查找满足 k^2 <= x的k值
class Solution {
public int mySqrt(int x) {
int left = 0;
int right = x;
while(left <= right) {
int mid = left + ((right-left) >> 1);
if ((long) mid * mid <= x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
}
367.有效的完全平方数
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0;
int right = x;
while(left <= right) {
int mid = left + ((right-left) >> 1);
if ((long) mid * mid <= num) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if(right * right == num) return true;
return false;
}
}
移除元素
27.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
暴力法
public static int removeElement(int[] nums, int val) {
int count = nums.length;
for (int j = 0; j < count; j++) {
if (nums[j] == val) {
//System.out.println(j);
count--;
for (int i = j; i < nums.length - 1; i++) {
nums[i] = nums[i+1];
}
j--;//因为之后j++所以这里需要j--,因为后面的数覆盖当前位置后当前位置没有判断过
}
}
return count;
}
进阶法
public static int removeElement(int[] nums, int val) {
int slow = 0;//slow指的是最后的结果中需要的数组
for (int fast = 0; fast < nums.length; fast++){
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
26.删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
我的版本
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 0;
int val = nums[0];
for (int fast = 1; fast < nums.length; fast++){
if (nums[fast] != val) {
slow++;
val = nums[fast];
}
if (fast == nums.length - 1) {
nums[slow] = nums[fast];
break;
}
if (nums[fast] == val && nums[fast+1] != val) {
nums[slow] = nums[fast];
slow++;
val = nums[fast+1];
} else if (nums[fast] == val && nums[fast+1] == val){
continue;
}
}
return (slow+1);
}
}
优化版本
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int j = 0;
for (int i = 0; i < n; i++) {
if (nums[i] != nums[j]) {
nums[++j] = nums[i];
}
}
return j + 1;
}
}
283.移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[slow] == 0 && nums[i] != 0) {
int temp = nums[slow];
nums[slow] = nums[i];
nums[i] = temp;
slow++;
} else if (nums[slow] != 0 && nums[i] != 0) {
slow++;
}
//nums[slow] != 0 && nums[i] == 0这种情况不存在
//slow == 0且i == 0什么也不做, i++
}
}
}
力扣官方版
class Solution {
public void moveZeroes(int[] nums) {
int n = nums.length, left = 0, right = 0;
while (right < n) {
if (nums[right] != 0) {
swap(nums, left, right);
left++;
}
right++;
}
}
public void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
844.比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
方法一：
利用栈，读到#就弹出栈顶元素，其余元素均压入
class Solution {
public boolean backspaceCompare(String s, String t) {
return build(s).equals(build(t));
}
public String build(String str) {
String re = "";
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) != '#') {
re += str.charAt(i);
} else {
if(re.length() > 0)
re = re.substring(0, re.length() - 1);
}
}
//System.out.println(re);
return re;
}
}
方法二：双指针法
class Solution {
public boolean backspaceCompare(String s, String t) {
int sCount = 0, tCount = 0;
int i = s.length() - 1, j = t.length() - 1;
//保证两个字符串都遍历完
while ( i >= 0 || j >= 0) {
while ( i >= 0 ) {
if (s.charAt(i) == '#') {
sCount++;
} else if ( sCount != 0) {
sCount--;
} else {
//这个字符不需要被删除就退出循环
break;
}
i--;
}
while ( j >= 0 ) {
if (t.charAt(j) == '#') {
tCount++;
} else if( tCount != 0) {
tCount--;
} else {
break;
}
j--;
}
//如果有一个到头就退出，防止异常
if(i < 0 || j < 0) break;
if(s.charAt(i) != t.charAt(j)) return false;
i--;j--;
}
if(i == -1 && j == -1) return true;
return false;
}
}
有序数组的平方
977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
普通方法：数组全部平方再赋值原位置，再排序，时间复杂度为O(N*logN)
双指针法：
倒着确定每个数，先确定大的数
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int k = nums.length - 1;//从后往前确定每一位数
int m = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
if (k == -1) return result;
if (nums[i] * nums[i] < nums[m] * nums[m]) {
result[k--] = nums[m] * nums[m];
m--;
i--;//m向前移动后再次和i位置比较
} else {
result[k--] = nums[i] * nums[i];
}
}
return result;
}
长度最小的子数组
209.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0
示例
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
暴力法：两层for循环遍历所有区间情况
滑动窗口法：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;//定义左边界
int result = Integer.MAX_VALUE;
int sum = 0;
for (int j = 0; j < nums.length; j++) {//j是右边界，每次向右移一位
sum += nums[j];
//注意是用的while不是if，因为if只能让左边界右移一位，而while可以让左边界右移到不满足条件为止
while (sum >= target) {
int length = j - left + 1;
result = result < length ? result : length;
sum -= nums[left++];
}
}
//result等于初始值返回0
return result == Integer.MAX_VALUE ? 0 : result;
}
}
904.水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树的种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
//我的答案
class Solution {
public int totalFruit(int[] fruits) {
int i = 0;
int result = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int j = 0; j < fruits.length; j++) {
//分两种情况
//fruits[j]在哈希表中，更新value
//fruits[j]不在哈希表中，向哈希表插入数据
//这个if else可以进一步简化 getOrDefault(fruits[right], 0) 简化后就是下面的力扣CV版
if (map.containsKey(fruits[j]) ){
map.put(fruits[j], map.get(fruits[j]) + 1);
} else {
map.put(fruits[j], 1);
}
//一旦哈希表size大于2，一直右移左边界直到哈希表size=2
while(map.size() > 2) {
map.put(fruits[i], map.get(fruits[i]) - 1);
if (map.get(fruits[i]) == 0) map.remove(fruits[i]);
i++;
}
//如果数组只有2种数，保证result可以更新
result = Math.max(result, j - i + 1);
}
return result;
}
}
力扣题解CV版本—找了两个版本的
class Solution {
public int totalFruit(int[] fs) {
int n = fs.length, ans = 0;
int[] cnts = new int[n + 10];
for (int i = 0, j = 0, tot = 0; i < n; i++) {
if (++cnts[fs[i]] == 1) tot++;
while (tot > 2) {
if (--cnts[fs[j++]] == 0) tot--;
}
ans = Math.max(ans, i - j + 1);
}
return ans;
}
}
class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length;
Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
int left = 0, ans = 0;
for (int right = 0; right < n; ++right) {
cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
while (cnt.size() > 2) {
cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
if (cnt.get(fruits[left]) == 0) {
cnt.remove(fruits[left]);
}
++left;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
76.最小覆盖子串
class Solution {
public String minWindow(String s, String t) {
String result = "";
int left = 0, len = Integer.MAX_VALUE;
HashMap<Character, Integer> tmap = new HashMap<>();//字符串t的哈希表
HashMap<Character, Integer> smap = new HashMap<>();//字符串s的哈希表
for (int i = 0; i < t.length(); i++) {
//将t存放到哈希表
tmap.put(t.charAt(i), tmap.getOrDefault(t.charAt(i), 0) + 1);
}
for (int right = 0; right < s.length(); right++) {
//将S存放到哈希表
smap.put(s.charAt(right), smap.getOrDefault(s.charAt(right), 0) + 1);
/*可以略微加速
if (right - left + 1 >= t.length() ) {
}*/
while (check(smap, tmap)) {//check返回true就右移左边界
//当现在的窗口长度小于上次的窗口长度时，更新result
result = len < (right - left + 1) ? result : s.substring(left, right + 1);
//注意substring方法的参数，begin-index到end-index，但是不含end-index
len = result.length();
//更新s的哈希表
smap.put(s.charAt(left), smap.get(s.charAt(left)) - 1);
left++;
}
}
return result;
}
//判断两个哈希表是否相同
public boolean check(HashMap<Character, Integer> h1, HashMap<Character, Integer> h2) {
Iterator iter = h2.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (h1.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
力扣官方版
class Solution {
Map<Character, Integer> ori = new HashMap<Character, Integer>();
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
int tLen = t.length();
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
int l = 0, r = -1;
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
while (r < sLen) {
++r;
if (r < sLen && ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
while (check() && l <= r) {
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {
Iterator iter = ori.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Character key = (Character) entry.getKey();
Integer val = (Integer) entry.getValue();
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
return true;
}
}
螺旋矩阵
59.螺旋矩阵
class Solution {
public int[][] generateMatrix(int n) {
int[][] arr = new int[n][n];
int count = 1,z = 0;
int x = 0, y = 0, off = 1;
while( z < n/2) {
int i,j;
for (j = x; j < n - off; j++) {
arr[x][j] = count++;
}
for (i = x; i < n - off; i++) {
arr[i][j] = count++;
}
for (;j > y; j--) {
arr[i][j] = count++;
}
for (;i > y; i--) {//也可以>off - 1
arr[i][j] = count++;//也可以arr[i][y]，以此和第一个for对应起来
}
z++;
x++;
y++;
off++;
}
if (n % 2 == 1) {
arr[n/2][n/2] = count++;
}
return arr;
}
}
