数组篇
跳-二分查找-704-力扣
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
if (target < nums[0] || target > nums[nums.length - 1])
return -1;
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 避免溢出
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
跳-移除元素-27-力扣
class Solution {
//方案二：双指针法
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length-1;
int counts = 0;
while(left<=right){
while (left<=right && nums[right]==val){
right--;
}
while (left<=right && nums[left]!=val){
left++;
}
if(left<right){
nums[left]=nums[right];
nums[right]=val;
}
}
return right+1;
}
// // 方案一： 正常遍历
// public int removeElement(int[] nums, int val) {
// int counts = nums.length;
// for(int i=nums.length-1; i>=0; i--) {
// if (nums[i] == val) {
// counts--;
// for(int j=i+1; j<nums.length; j++) {
// nums[j-1] = nums[j];
// }
// nums[nums.length-1] = val;
// }
// }
// return counts;
// }
}
做-有序数组的平方-977-力扣
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
// 双指针法，方法一
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ant = new int[n];
for (int i=0,j=n-1,pos=n-1; i<=j;) {
if (nums[i]*nums[i] > nums[j]*nums[j]) {
ant[pos] = nums[i]*nums[i];
i++;
} else {
ant[pos] = nums[j] * nums[j];
j--;
}
pos--;
}
return ant;
}
}
方法二：
利用数组中元素是升序的这一条件：即如果数组中元素有负有正
-4 -2 1 3
*l *r
左指针向左，右指针向右遍历，然后左右指针进行比较
//方法三：将数组里面的元素平方之后，再进行快排算法
class Solution {
public int[] sortedSquares(int[] nums) {
int len = nums.length;
for (int i=0; i<len; i++) {
nums[i] = nums[i]*nums[i];
}
quickSort(nums, 0, len-1);
return nums;
}
private void quickSort(int[] nums, int low, int high) {
int left, right, temp, t;
if (low >= high){
return;
}
// 左右指针
left = low;
right = high;
temp = nums[low]; //temp就是基准位
while (left < right) {
//先看右边，依次往左递减
while (nums[right]>=temp && left<right) {
right--;
}
//再看左边，依次往右递增
while (nums[left]<=temp && left<right) {
left++;
}
//如果满足条件则交换
if (left < right) {
t = nums[right];
nums[right] = nums[left];
nums[left] = t;
}
}
//最后将基准为与left和right相等位置的数字交换
nums[low] = nums[left];
nums[left] = temp;
//递归调用左半数组
quickSort(nums, low, right-1);
//递归调用右半数组
quickSort(nums, right+1, high);
}
}
思考-长度最小的子数组-209-力扣
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
滑动窗口(就使用这个)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int len = nums.length;
int count = len + 1;
int left = 0;
long sum = 0;
for (int right=0; right<len; right++) {
sum += nums[right];
while (sum >= target) {
count = Math.min(count, right-left+1);
sum -= nums[left++];
}
}
return count==len+1 ? 0 : count;
}
}
我自己写的（有问题）
代码估计没有错误，但是时间超出了限制 O(n^2)级别了
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int len = nums.length;
int count = len+1;
for(int left=len-1; left>=0; left--) {
int sum = 0;
for(int right=left; right<len; right++) {
sum+=nums[right];
if(right-left+1<count && sum>=target){
count = right - left + 1;
break;
}
}
}
return count==len+1 ? 0 : count;
}
}
思考-螺旋矩阵||-59-力扣
题目：给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
class Solution {
public int[][] generateMatrix(int n) {
int[][] nums = new int[n][n];
int startX = 0, startY = 0; // 每一圈的起始点
int offset = 1;
int count = 1; // 矩阵中需要填写的数字
int loop = 1; // 记录当前的圈数
int i, j; // j 代表列, i 代表行;
while (loop <= n/2) {
// 顶部
// 左闭右开，所以判断循环结束时， j 不能等于 n - offset
for (j=startY; j<n-offset; j++) {
nums[startX][j] = count++;
}
// 右列
// 左闭右开，所以判断循环结束时， i 不能等于 n - offset
for (i=startX; i<n-offset; i++) {
nums[i][j] = count++;
}
// 底部
// 左闭右开，所以判断循环结束时， j != startY
for (; j>startY; j--) {
nums[i][j] = count++;
}
// 左列
// 左闭右开，所以判断循环结束时， i != startX
for (; i>startX; i--) {
nums[i][j] = count++;
}
startX++;
startY++;
offset++;
loop++;
}
if (n%2 == 1) {
nums[startX][startY] = count;
}
return nums;
}
}
小结：这道题要注意的地方，就在于整个逻辑。
记录当前的圈数、记录每圈开始的起始位置、记录每圈的偏移量
跳-区间和-58-卡码网
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
代码
import java.util.Scanner;
public class mm {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] vec = new int[n];
int[] p = new int[n];
int presum = 0;
for (int i=0; i<n; i++) {
vec[i] = scanner.nextInt();
presum+=vec[i];
p[i] = presum;
}
while (scanner.hasNextInt()) {
int a = scanner.nextInt();
int b = scanner.nextInt();
int sum = 0;
if (a == 0) {
sum = p[b];
} else {
sum = p[b] -p[a-1];
}
System.out.println(sum);
}
scanner.close();
}
}
思路
第一个位置：前一个和
第二个位置：前二个和
.........
第n个位置：前n个和
跳-开发商购买土地-44-卡码网
题目描述
在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。
现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分。
输入描述
第一行输入两个正整数，代表 n 和 m。
接下来的 n 行，每行输出 m 个正整数。
输出描述
请输出一个整数，代表两个子区域内土地总价值之间的最小差距。
解题思路
和我写的代码一样，用的还是前缀和的思想。
我的代码
import java.util.Scanner;
import java.lang.Math.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] h = new int[n];
int[] c = new int[m];
int[][] p = new int[n][m];
int sum = 0;
int SUM = 0;
for (int i=0; i<n; i++) {
sum = 0;
for (int j=0; j<m; j++) {
p[i][j] = scanner.nextInt();
sum += p[i][j];
SUM += p[i][j];
}
if (i != 0) {
h[i] = h[i-1] + sum;
} else {
h[i] = sum;
}
}
for (int j=0; j<m; j++) {
sum = 0;
for (int i=0; i<n; i++) {
sum += p[i][j];
}
if (j != 0) {
c[j] = c[j-1] + sum;
} else {
c[j] = sum;
}
}
for (int i=0; i<n-1; i++) {
if (Math.abs(h[n-1]-2*h[i]) < SUM) {
SUM = Math.abs(h[n-1]-2*h[i]);
}
}
for (int j=0; j<m-1; j++) {
if (Math.abs(c[m-1]-2*c[j]) < SUM) {
SUM = Math.abs(c[m-1]-2*c[j]);
}
}
System.out.println(SUM);
}
}
总结
