数组
二分查找
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
题解：如果等于nums[middle],返回middle;否则返回left或者low。
移除元素
在排序数组中查找target的开始位置和结束位置。
二分法不可能会漏掉正确结果的。
思路：将开始位置和结束位置的查找分为两部分代码：findLeft()和findRight();
如何循环能够得到左部的最小值和右部的最大值？
finLeft():当已经找到nums[mid]==target时，让right=mid-1，继续二分查找，重复上述步骤，若还有更新的nums[mid]==target，则更新左边界值。
findRight()同理。
关键代码：
findLeft(): 
findRight(): 
找到非负数x的平方根
1）首先是左闭右闭，所以while(left<=right)
2)搞清楚二分法是从中间开始向两边，当middle值小于Target值后，先记录此时的middle值，然后继续往右移进行试探看还有没有符合的值，因为只可能出现在大于该middle值的情况，直到left>right。和上题findRight()思路相同
有效的完全平方数
num/middle用double型 ，middle是int型 比较时会进行类型转换由int转换为double，只有当为整数时才算是平方根。
滑动窗口
有序数组的平方
数组元素是非递减的，因此平方之后最大值只有可能在数组的最左端和最右端，因此可以使用两边指针进行遍历，进行大小的比较并赋给新的数组。
长度最小的子数组⭐
使用滑动窗口的思想，外层循环控制结束位置j，内层循环控制起始位置i，看似是双层循环，但时间复杂度是o(2n)。
水果成篮
自己想法：使用backet1和backet2表示篮子1和篮子2；使用backet1Account和backet2Account分别表示两个篮子里水果的数量，内层循环将i指针向前移动。
查看代码
public int totalFruit(int[] fruits) {
int backet1=fruits[0];
int backet2=0;
int backet1Account=0;
int backet2Account=0;
int result=0;
int i=0;
for (int j = 0; j < fruits.length; j++) {
if (fruits[j]==backet1){
backet1Account++;
}else if (fruits[j]==backet2 ||backet2Account==0 ){
backet2=fruits[j];
backet2Account++;
}else{
while (backet1Account>0 && backet2Account>0){
if (fruits[i]==backet1){
backet1Account--;
}else {
backet2Account--;
}
i++;
}
if (backet1Account==0){
backet1=fruits[j];
backet1Account++;
}
if(backet2Account==0){
backet2=fruits[j];
backet2Account++;
}
}
result=result>backet1Account+backet2Account?result:backet1Account+backet2Account;
}
return result;
}最优想法：不需要单独设置表示两个篮子里水果数量的参数，一旦下一个水果不在已有篮子里，i=j-1;内层循环将i指针向前移动，得到i位置后，将i位置的水果放入篮子1，当前j位置的水果放入篮子2，总的数量用下标表示。
public int totalFruit(int[] fruits) {
int backet1=fruits[0];
int backet2=0;
int result=0;
int i=0;
for (int j = 0; j < fruits.length; j++) {
if (fruits[j]!=backet1 && fruits[j]!=backet2){
i=j-1;
while(i>=1 && fruits[i]==fruits[i-1]){
i--;
}
backet1=fruits[i];
backet2=fruits[j];
}
result=result>(j-i+1)?result:(j-i+1);
}
return result;
}
滑动窗口的模板
//[left,right)窗口左闭右开
int left=0;
int right=0;
while(right<s.length)
{
//此时先将当前right指向的内容移入窗口
移入窗口之后需要改变的变量和进行的操作
right++;
while(left<right && 窗口满足要求）{
//将当前left指向的内容移出窗口
移出之后改变相关变量和进行操作
left++;
}
}
对于最小覆盖子串，除了使用Map外，也可以用字符的ascII码来进行计算，使用int[]存储子串中含有的字符串个数，一旦在s中发现有的话，就将int[]中对应字符的数量--，然后count--
字符串的排列、找到字符串中所有字母异位词
如果给两个字符串s和t，判断t是否为s的子串或是否s包含t的排列，用t的长度固定滑动窗口的大小，初始化将s的前t.length()个长度的字符情况存储在int数组中，int数组的大小由字符串中字符的类型决定，最大为ascii表的长度，为128。
每次循环滑动窗口向前移一位，即left++，right++,移完之后和存储t字符串情况的数组进行比较，Arrays.equal(int[] a,int[] b)。
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
无重复字符的最长子串
对于找不重复的最长子串，可以用int[]数组是否大于1来判断，大于1时则right指向的字符子串中已经包含，此时先将left指向的字符移出，然后再left++(而不是直接移到right的位置×！！)。
例：3. 无重复字符的最长子串 - 力扣（LeetCode）
具体代码
public int lengthOfLongestSubstring(String s) {
int left=0;
int right=0;
int count=0;
int[] curr=new int[128];
while (right<s.length()){
if (curr[s.charAt(right)]<1){
curr[s.charAt(right)]++;
right++;
} else if (curr[s.charAt(right)]>=1) {
curr[s.charAt(left)]--;
left++;
}
count= count>right-left?count:right-left;
}
return count;
}
螺旋矩阵
当输入的矩阵并不一定行数列数相等时，要考虑到四种不同的情况，分别是：
-
- 行数为1行或者列数为1列 直接从左往右 或者从上往下遍历
- 行数（列数）为2的倍数且行数≤列数(列数≤行数） 遍历完整个循环之后 就可以结束 不需要后续操作
- 行数=列数，且为奇数时 只需要在循环结束后再遍历一下当前最中心的值
- 行数（列数）为奇数且行数<列数（列数＜行数） 在循环结束之后再继续遍历（列数-行数+1）个中心列元素或者是再继续遍历（行数-列数+1）个中心行元素
螺旋矩阵代码
public List<Integer> spiralOrder(int[][] matrix) {
int row=matrix.length;//行数
int column=matrix[0].length;//列数
ArrayList<Integer> list = new ArrayList<>();
int x=0;//矩阵的行位置
int y=0;//矩阵列位置
int loop=1;//循环的次数
int offset=1;//遍历的长度 每次循环一遍右边界减一
int i=0,j=0;
//针对一行或者一列的情况
if (column==1 ){
while (x<row)
{
list.add(matrix[x++][0]);
}
}else if (row==1){
while (y<column){
list.add(matrix[0][y++]);
}
}
//循环主体
while (loop<=Math.min(row/2,column/2)){
for (j=y;j<column-offset;j++){
list.add(matrix[x][j]);
}
for (i = x;i < row-offset; i++) {
list.add(matrix[i][j]);
}
for (;j>y;j--){//注意：j是大于y而不是大于0
list.add(matrix[i][j]);
}
for (;i>x;i--){//注意：i是大于x而不是大于0
list.add(matrix[i][j]);
}
loop++;//循环次数++
x++;//行位置往里移动一位
y++;//列位置往下移动一位
offset++;//行和列中不需要遍历的个数+1
}
//如果存在列的个数是2的倍数且行数>=列数时，循环完正好结束，没有里层剩余，列和行反过来一样
if ((column%2==0 && column<row) ||(row%2==0 && column>row)){
return list;
}
//当里层有剩余时
i=x;
j=y;
if ( i<column && j<row){ //因为上面while大循环中最后x++,y++ 所以需要进行一下判断
if (row==column && row%2==1){//如果行数和列数相等且为奇数，那么只剩最中间一个没有遍历
list.add(matrix[i][j]);
} else if (row>column) {//如果行数>列数 且列数是奇数 那么中间有有一小列元素没有遍历
while (i-j <=row-column){//没有遍历的个数是行数-列数+1
list.add(matrix[i++][j]);
}
}else if (row<column){//行数列数反过来 同上
while (j-i <=column-row){
list.add(matrix[i][j++]);
}
}
}
return list;
}区间和
直接每次输入区间后，都需要遍历一次区间中的数据，因此时间消耗为0(m*n) m表示输入区间的次数，n为数组的元素个数
解决方法：使用前缀和，将前i个元素之和存储在一个数组中，每次输入区间之后，直接用末位置的和➖（初位置-1）的和，当初位置为0时区间和就为末位置之和。
区间和代码
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner scan= new Scanner(System.in);
int arrLength=scan.nextInt();
int[] Array=new int[arrLength];
int[] p=new int[arrLength];
int i=0;
Array[i]=scan.nextInt();
p[i]=Array[0];
for(i=1;i<arrLength;i++){
Array[i]=scan.nextInt();
p[i]=p[i-1]+Array[i];
}
while(scan.hasNextInt()){
int a=scan.nextInt();
int b=scan.nextInt();
if (a==0){
System.out.println(p[b]);
}else{
System.out.println(p[b]-p[a-1]);
}
}
scan.close();
}
}开发商购买土地
其核心在于，划分要么横着一刀，要么竖着一刀，且只能是一刀。
思路：先验证横着一刀得到两个区域差的最小值：遍历每一行，在每行最后一个位置加入后计算区域差，sum-count-count,其中（sum-count)表示此一刀下面的区域，count表示一刀上面的区域，用abs(下面的区域和➖上面区域和)则表示区域差；同理再试竖着的一刀。
前缀和和优化暴力求解都是o(m*n)
暴力求解代码
public class Main{
public static void main (String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int m=scanner.nextInt();
int[][] vec=new int[n][m];
int sum=0;
int result=Integer.MAX_VALUE;
for (int i=0;i<n ;i++ ){
for (int j=0;j<m ;j++ ){
vec[i][j]=scanner.nextInt();
sum+=vec[i][j];
}
}
int count=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
count+=vec[i][j];
if (j==m-1){
result=Math.min(result,Math.abs(sum-count-count));
}
}
}
count=0;
for(int j=0;j<m;j++){
for(int i=0;i<n;i++){
count+=vec[i][j];
if(i==n-1){
result=Math.min(result,Math.abs(sum-count-count));
}
}
}
System.out.println(result);
scanner.close();
}
}数组基础总结
数组的元素是不能删除的，只能覆盖！！
二维数组在内存中并不是连续的，其实质是一维数组的一维数组，即对象中存储着一个一维数组的地址，这个一维数组中存储着每行数组的起始地址。
标签：right,int,++,算法,数组,fruits,left From： https://www.cnblogs.com/exo123/p/18609594