包年seo和整站优化,华为品牌策划方案,别墅庭院园林景观设计公司,网站一级页面标题怎么做的一、二分查找
1. 704【二分查找】
题目#xff1a; 给定一个 n 个元素 有序的#xff08;升序#xff09; 整型数组 nums 和一个目标值 target #xff0c;写一个函数搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。代码#xff1a;…一、二分查找
1. 704【二分查找】
题目 给定一个 n 个元素 有序的升序 整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。代码
class Solution {public int search(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 -1;}
}2. 35【搜索插入位置】 题目 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 代码
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){right mid - 1;}else if(nums[mid] target){left mid 1;}else{return mid;}}return left;}
}3. 34【在排序数组中查找元素的第一个和最后一个位置】 题目 给你一个按照非递减顺序 排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 代码
class Solution {public int[] searchRange(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){right mid - 1;}else if(nums[mid] target){left mid 1;}else{left mid;right mid;while(left0 nums[left] target){left--;}while(rightnums.length nums[right] target){right;}return new int[]{left,--right};}}return new int[]{-1,-1};}
}4. 69【x 的平方根】 题目 给你一个非负整数 x 计算并返回 x 的 算术平方根 。由于返回类型是整数结果只保留 整数部分 小数部分将被舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 代码
class Solution {public int mySqrt(int x) {if(x0 || x1){return x;}int left 1; //注意这里需要由1开始int right x1 ;while (left right){int sqrt left ((right-left)1);if(sqrt x/sqrt){right sqrt- 1;}else if(sqrt x/sqrt){left sqrt 1;}else{return sqrt;}}return right;}
}5. 367【有效的完全平方数】
题目 给你一个正整数 num 。如果 num 是一个完全平方数则返回 true 否则返回 false 。 完全平方数 是一个可以写成某个整数的平方的整数。换句话说它可以写成某个整数和自身的乘积。 不能使用任何内置的库函数如 sqrt 。代码
class Solution {public boolean isPerfectSquare(int num) {if(num0 || num1){return true;}int left 1; //注意这里需要由1开始int right num1 ;while (left right){int sqrt left ((right-left)1);if(sqrt num/sqrt){right sqrt- 1;}else if(sqrt num/sqrt){left sqrt 1;}else{right sqrt;break;}}if(right * right num){return true;}else{return false;}
}二、双指针快慢指针
1. 27【移除元素】 题目 给你一个数组 nums 和一个值 val你需要原地移除所有数值等于 val 的元素并返回移除后数组的新长度。不要使用额外的数组空间你必须仅使用 O(1)额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 代码
class Solution {public int removeElement(int[] nums, int val) {int len 0;for(int j0;jnums.length;j){if(nums[j] ! val){nums[len] nums[j];}}return len;}
}2. 26【删除排序数组中的重复项】
题目 给你一个非严格递增排列的数组 nums 请你原地删除重复出现的元素使每个元素只出现一次 返回删除后数组的新长度。元素的相对顺序应该保持一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过 更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。代码
class Solution {public int removeDuplicates(int[] nums) {int k 1;for(int i1;inums.length;i){if(nums[i] ! nums[k-1]){nums[k] nums[i];}}return k;}
}3. 283【移动零】
题目 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。 请注意 必须在不复制数组的情况下原地对数组进行操作。代码
class Solution {public void moveZeroes(int[] nums) {int len 0;for(int i0;inums.length;i){if(nums[i] ! 0){nums[len] nums[i];}}for(len;lennums.lenght;len){nums[len] 0;}}
}4. 977【有序数组的平方】
题目 给你一个按非递减顺序排序的整数数组 nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。代码
class Solution {public int[] sortedSquares(int[] nums) {for(int i0;inums.length;i){nums[i] nums[i] * nums[i];}int[] newNums new int [nums.length];int left 0;int right nums.length-1;int i nums.length-1;while(left right){if(nums[left] nums[right]){newNums[i--] nums[right--];}else{newNums[i--] nums[left]}}return newNums;}
}三、滑动窗口
1. 209【长度最小的子数组】
题目 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的连续子数组 [ n u m s l , n u m s l 1 , . . . , n u m s r − 1 , n u m s r ] [nums_l, nums_{l1}, ..., nums_{r-1}, nums_r] [numsl,numsl1,...,numsr−1,numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int len nums.length 1;int sum 0;int j 0;for(int i0;inums.length;i){sum nums[i];while(sum target){len i - j 1 len ? (i - j 1):len;sum - sum[j];j;}}if(len nums.length 1){return 0;}else{return len;}}
}2. 904【水果成篮】
题目 你正在探访一家农场农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示其中 fruits[i] 是第 i 棵树上的水果种类 。 你想要尽可能多地收集水果。然而农场的主人设定了一些严格的规矩你必须按照要求采摘水果 你只有两个篮子并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘你必须从每棵树包括开始采摘的树上恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次你将会向右移动到下一棵树并继续采摘。一旦你走到某棵树前但水果不符合篮子的水果类型那么就必须停止采摘。 给你一个整数数组 fruits 返回你可以收集的水果的最大数目。 代码
class Solution {public int totalFruit(int[] fruits) {int left 0;int maxNum 0;MapInteger,Integer types new HashMapInteger,Integer();for (int right 0; right fruits.length; right) {int count types.getOrDefault(fruits[right],0) 1;types.put(fruits[right],count);while (types.size()2){types.put(fruits[left],types.get(fruits[left])-1);if(types.get(fruits[left]) 0){types.remove(fruits[left]);}left;}maxNum maxNum right-left1 ? maxNum:right-left1;}return maxNum;}
}3. 76【最小覆盖子串】
题目 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。 注意对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。代码
class Solution {MapCharacter,Integer sMap new HashMapCharacter,Integer();MapCharacter,Integer tMap new HashMapCharacter,Integer();public String minWindow(String s, String t) {if(s.equals(t)){return s;}String minSubStr ;int left 0;int subLeft -1;int subRight -1;int len s.length();for (int i 0; i t.length(); i) {int count tMap.getOrDefault(t.charAt(i),0) 1;tMap.put(t.charAt(i),count);}for (int i 0; i s.length(); i) {char sChar s.charAt(i);if(tMap.containsKey(sChar)){int count sMap.getOrDefault(sChar,0) 1;sMap.put(sChar,count);}while (hasSubStr() lefti){if(len i-left1){subLeft left;subRight i;len i-left1;}if(sMap.containsKey(s.charAt(left))){int count sMap.get(s.charAt(left)) - 1;sMap.put(s.charAt(left),count);}left;}}if(subLeft subRight subLeft-1){return ;}return s.substring(subLeft,subRight1);}public boolean hasSubStr(){Set tkeys tMap.keySet();Iterator iterator tkeys.iterator();while (iterator.hasNext()){Object tChar iterator.next();if(sMap.containsKey(tChar)){if(sMap.get(tChar) tMap.get(tChar)){return false;}}else {return false;}}return true;}
}四、模拟行为
1. 59【螺旋矩阵Ⅱ】
题目 给你一个正整数 n 生成一个包含 1 到 n 2 n^2 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。代码
class Solution {public int[][] generateMatrix(int n) {int[][] arr new int [n][n];int num 1;for (int i 0; i n/2; i) {for (int j i; j n-i; j) {arr[i][j] num;}for (int j i1; j n-i; j) {arr[j][n-i-1] num;}for (int j n-i-2; j i ; j--) {arr[n-i-1][j] num;}for (int j n-i-2; j i ; j--) {arr[j][i] num;}}if(n%2 ! 0){int i n/2;arr[i][i] num;}return arr;}
}2. 54【螺旋矩阵】
题目 给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。代码
class Solution {public ListInteger spiralOrder(int[][] matrix) {int n matrix.length;int m matrix[0].length;ListInteger l new ArrayList(n*m);for (int i 0; i m/2; i) {if(l.size() ! n*m){for (int j i; j m-i; j) {l.add(matrix[i][j]);}}if(l.size() ! n*m) {for (int j i 1; j n - i; j) {l.add(matrix[j][m - i - 1]);}}if(l.size() ! n*m) {for (int j m - i - 2; j i; j--) {l.add(matrix[n - i - 1][j]);}}if(l.size() ! n*m){for (int j n-i-2; j i ; j--) {l.add(matrix[j][i]);}}}return l;}
}3. 146【螺旋遍历二维数组】 题目 给定一个二维数组 array请返回「螺旋遍历」该数组的结果。 螺旋遍历从左上角开始按照向右、向下、向左、向上的顺序依次提取元素然后再进入内部一层重复相同的步骤直到提取完所有元素。 代码
class Solution {public int[] spiralArray(int[][] array) {if (array.length 0)return new int[]{};int n array.length;int m array[0].length;int[] arr new int[n*m];int index 0;for (int i 0; i m/2; i) {if(index ! n*m){for (int j i; j m-i; j) {arr[index] array[i][j];}}if(index ! n*m) {for (int j i 1; j n - i; j) {arr[index] array[j][m - i - 1];}}if(index ! n*m) {for (int j m - i - 2; j i; j--) {arr[index] array[n - i - 1][j];}}if(index ! n*m){for (int j n-i-2; j i ; j--) {arr[index] array[j][i];}}}return arr;}
}
