数组
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
//双指针法，采用快慢指针，左指针left用来占位，右指针right用来遍历元素，当与到与val相等的值时，将left位置的元素值进行覆盖
//(left会停留在上一个与val相等的值的位置上)最后返回left即为修改后需要打印的元素数量
public int removeElement(int[] nums, int val) {
int left=0;
for(int right=0;right<nums.length;right++){
if(nums[right]!=val){
nums[left++]=nums[right];
}
}
return left;
}
26. 删除有序数组中的重复项 - 力扣（Leetcode）
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。 - 返回
k。
//双指针
public int removeDuplicates(int[] nums) {
int left=0;
for(int right=1;right<nums.length;right++){
if(nums[left]!=nums[right]){
nums[++left]=nums[right];
}
}
return left+1;
}
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作
//双指针
public void moveZeroes(int[] nums) {
int left=0;
for(int right=0;right<nums.length;right++){
while(left<nums.length&&nums[left]!=0){//让left指向一个为0的为主的索引
left++;
}
if(left<nums.length&&right>left){//交换时必须保证right在left后面(right始终应该比left快)
nums[left]=nums[right];
nums[right]=0;
}
}
}
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
//重构字符串
public boolean backspaceCompare(String s, String t) {
if(s.equals(t))return true;
String s1=backspace(s);
String t1=backspace(t);
return s1.equals(t1);
}
public String backspace(String s){
int n=s.length();
StringBuffer str=new StringBuffer();
int count=0;//占位，判断#数量
for(int i=n-1,j=0;i>=0;i--){//从后往前遍历,count为0时可以直接添加字符（该字符不会被退格）
char c=s.charAt(i);
if(c=='#'){//
count++;
continue;
}
if(count>0){//count!=0,该字符被退格符覆盖，不将其追加到字符串中
count--;
}else{//count=0，该字符可以被添加到字符串中
str.append(c);
}
}
return str.toString();
}
//双指针,从字符串末尾开始遍历,每次只比较一个字符
public boolean backspaceCompare(String s, String t) {
int i=s.length()-1;
int j=t.length()-1;
while(i>=0||j>=0){//从字符串末尾开始遍历
int count=0;//充当第二个指针，表示待删除字符的数量
while(i>=0){//获取字符串中一个不被退格字符影响的字符
char ch=s.charAt(i);
if(ch=='#'){//遇到#,count++
count++;
i--;
continue;
}
if(count>0){//count>0,当前字符被退格，直接跳过
count--;
i--;
}else{//满足条件，取出当前i所对应的字符
break;}
}
count =0;//计数位归零，反之字符串的最后至少#的情况
while(j>=0){
char ch=t.charAt(j);
if(ch=='#'){
count++;
j--;
continue;
}
if(count>0){
count--;
j--;
}
else break;
}
if(i>=0&&j>=0){//当首位为#,i,j会为-1，当i=-1,j=-1时应该为真
if(s.charAt(i)!=t.charAt(j))//当前位字符不相同
return false;
}else{
if(i>=0|| j>=0)
return false;
}
i--;
j--;
}
return true;
}
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
//双指针,数组中有负数，且是递增排序，平方后的最大值不是在左就是在右
public int[] sortedSquares(int[] nums) {
int j=0;
int []temp=new int[nums.length];
int i=nums.length-1;
for(int k=nums.length-1;k>=0;k--){
if(nums[j]*nums[j]>nums[i]*nums[i]){
temp[k]=nums[j]*nums[j];
j++;
}else{
temp[k]=nums[i]*nums[i];
i--;
}
}
return temp;
}
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
//滑动窗口,
public int minSubArrayLen(int target, int[] nums) {
int left=0;
int right=0;
int count=0;
int l=Integer.MAX_VALUE; |
while(right>=left){ | while(right<nums.length){
if(count>=target){ | count += nums[right];
count-=nums[left++]; | while(count>=target){
int l1=right-left+1; | int l1=right-left+1;
l=l1<l?l1:l; | l=l1<l?l1:l;
}else{ | count-=nums[left++];
if(right<nums.length) | }
count+=nums[right]; | right++;
else left++; |
} }
return l==Integer.MAX_VALUE?0:l;
}
//前缀和+二分
//计算最短子数组可以通过计算前K项的和减去前n项的和，此时K-n就是第n到k项的的连续子数组
//数组中元素均为正数，所以前缀和递增，可以用二分法寻找此时因满足 temp[k]-temp[n]>=target-->temp[K]>temp[n]+target
public int minSubArrayLen(int target, int[] nums) {
int n=nums.length;
int[]temp=new int[n+1];
for(int i=1;i<n+1;i++){//求前缀和
temp[i]=temp[i-1]+nums[i-1];
}
int binary=Integer.MAX_VALUE;
for(int i=0;i<n+1;i++){//找到最小的满足条件值temp[k]-temp[n]>=target-->temp[K]>temp[n]+target
int k=binarySearch(temp,target+temp[i]);
if(k<=nums.length)//插入元素必须在数组索引范围内
binary=binary<k-i?binary:k-i;
}
return binary==Integer.MAX_VALUE?0:binary;
}
public int binarySearch(int []temp,int target){//找到目标元素或其插入的位置
int right=temp.length-1;
int left=0;
while(left<=right){
int n=left+(right-left)/2;
if(temp[n]>target){
right=n-1;
}else if(temp[n]<target){
left=n+1;
}
else{
return n;
}
}
return left;
}
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
public int[][] generateMatrix(int n) {
int [][]temp=new int[n][n];
int num=1;
int loop=0;
int start=0;//第几次旋转
int i,j;
while(loop++<n/2){//loop控制旋转的圈数，n=3时旋转1圈，n=4转2圈
//左->右
for(i=start;i<n-loop;i++){
temp[start][i]=num++;
}
//上->下
for(j=start;j<n-loop;j++){
temp[j][i]=num++;
}
//右->左
for(;j>start;j--){//start是第几圈，仅需要填到第几层
temp[i][j]=num++;
}
//下->上
for(;i>start;i--){
temp[i][j]=num++;
}
start++;
}
if(n%2!=0){//n为奇数时,中间会空出一格
temp[n/2][n/2]=num;
}
return temp;
}
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer>list=new ArrayList<>();
int start=0;
int loop=0;
int n=matrix.length;
int m=matrix[0].length;
int i,j;
while(loop++<Math.min(n,m)/2){//循环的圈数只与最短边有关
i=start;j=start;
for(;j<m-loop;j++){
list.add(matrix[i][j]);
}
for(;i<n-loop;i++){
list.add(matrix[i][j]);
}
for(;j>start;j--){
list.add(matrix[i][j]);
}
for(;i>start;i--){
list.add(matrix[i][j]);
}
start++;
}
//找到m,n和剩余行列的关系
if(Math.min(n,m)%2!=0){//当最短边为奇数是由于行,列的长度不同,会出现中间一行或中间一列没有遍历的情况
if(m>n){//列数>行数，中间一行没有遍历，控制行不边，将该行上的每一列元素遍历
for(i=start,j=start;j<m-start;j++){
list.add(matrix[i][j]);
}
}
else{
for(i=start,j=start;i<n-start;i++){
list.add(matrix[i][j]);
}
}
}
return list;
}