704.二分查找 easy
简单，注意处理二分的边界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int search(vector<int>& nums, int target) {
int i = 0;
int j = nums.size() - 1;
int mid = (i + j) / 2;
while(nums[mid] != target){
if (nums[mid] > target){
j = mid - 1;
}else{
i = mid + 1;
}
if (i > j) return -1;
mid = (i + j) / 2;
}
return mid;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int search(int[] nums, int target) {
int i = 0;
int j = nums.length - 1;
int mid = (i + j) / 2;
while(nums[mid] != target){
if (nums[mid] > target){
j = mid - 1;
}else{
i = mid + 1;
}
if (i > j) return -1;
mid = (i + j) / 2;
}
return mid;
}
}
|
27.移除元素 easy
利用双指针，注意当nums[left] == val时，不要进行left++操作，防止nums[right-1]==val情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int right = nums.size();
int left = 0;
while(left < right){
if(nums[left] == val){
nums[left] = nums[right-1];
right--;
}else
left++;
}
return left;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length;
while(left < right){
if(nums[left] == val){
nums[left] = nums[right-1];
right--;
}else
left++;
}
return left;
}
}
|
977.有序数组的平方 easy
正序插入，主要问题是找到负数与正数的过渡点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int flag = -1;
for(int i = 0; i < nums.length-1; i++){
if(nums[i] < 0 && nums[i+1] >=0){
flag = i;
break;
}
}
int f = 0;
if(flag == -1){
if(nums[0] >= 0){
for(int i = 0; i < nums.length; i++){
res[i] = nums[i]*nums[i];
}
}else{
for(int j = nums.length-1; j>=0; j--){
res[nums.length-j-1] = nums[j]*nums[j];
}
}
}
else{
int i = flag;
int j = flag+1;
while(i >= 0 && j < nums.length){
if(nums[i] + nums[j] > 0){
res[f++] = nums[i]*nums[i--];
}else{
res[f++] = nums[j]*nums[j++];
}
}
while(i >= 0){
res[f++] = nums[i]*nums[i--];
}
while(j<nums.length){
res[f++] = nums[j]*nums[j++];
}
}
return res;
}
}
|
逆序插入，利用双指针，代码更为简洁，边界条件更少
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
ans[pos] = nums[i] * nums[i];
++i;
} else {
ans[pos] = nums[j] * nums[j];
--j;
}
--pos;
}
return ans;
}
}
|
209.长度最小的子数组 middle
经典的双指针构造滑动窗口的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int minSubArrayLen(int target, int[] nums) {
int res = Integer.MAX_VALUE;
int add = 0;
for(int right = 0, left = 0; right < nums.length; right++){
add += nums[right];
if(add >= target){
while(add - nums[left] >= target){
add -= nums[left];
left++;
}
res = Math.min(res, right-left + 1);
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
|
59. 螺旋矩阵 II middle
注意边界条件，前闭后开，以及n为奇数/偶数的不同情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int[][] generateMatrix(int n) {
int [][]res = new int[n][n];
int flag = 0;
int count = 1;
while(flag < n/2){
for(int i = flag; i < n-flag-1; i++){
res[flag][i] = count++;
}
for(int j = flag; j < n-flag-1; j++){
res[j][n-flag-1] = count++;
}
for(int i = n-flag-1; i > flag; i--){
res[n-flag-1][i] = count++;
}
for(int j = n-flag-1; j > flag; j--){
res[j][flag] = count++;
}
flag++;
}
if (n % 2 == 1){
res[n/2][n/2] = count;
}
return res;
}
}
|
卡码网 58.区间和 easy
一维前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner (System.in);
int n = input.nextInt();
int [] arr = new int[n];
int [] add = new int[n+1];
add[0] = 0;
for(int i = 0; i<n; i++){
arr[i] = input.nextInt();
add[i+1] = add[i] + arr[i];
}
int a,b;
while(input.hasNextInt()){
a = input.nextInt();
b = input.nextInt();
System.out.println(add[b+1]-add[a]);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> arr(n);
vector<int> add(n+1,0);
for(int i = 0; i<n; i++){
cin>>arr[i];
add[i+1] = add[i] + arr[i];
}
int a,b;
while( cin>>a>>b){
cout<<add[b+1]-add[a]<<endl;
}
}
|
卡码网 44. 开发商购买土地 middle
二维前缀和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| import java.util.*;
public class Main{
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n,m;
n = input.nextInt();
m = input.nextInt();
int [][] arr = new int[n][m];
int [][] add = new int[n+1][m+1];
int total = 0;
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
arr[i][j] = input.nextInt();
total += arr[i][j];
add[i+1][j+1] = add[i][j+1] + add[i+1][j] - add[i][j] + arr[i][j];
}
}
int minDis = Integer.MAX_VALUE;
for(int i = 0; i<n; i++){
minDis = Math.min(minDis, Math.abs(total - 2*add[i][m]));
}
for(int j = 0; j<m; j++){
minDis = Math.min(minDis, Math.abs(total - 2*add[n][j]));
}
System.out.println(minDis);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include <bits/stdc++.h>
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
vector<vector<int>> arr(n,vector<int>(m));
vector<vector<int>> add(n+1,vector<int>(m+1,0));
int total = 0;
for(int i = 0; i<n; i++){
for(int j = 0; j<m; j++){
cin>>arr[i][j];
total += arr[i][j];
add[i+1][j+1] = add[i][j+1] + add[i+1][j] - add[i][j] + arr[i][j];
}
}
int minDis = INT_MAX;
for(int i = 0; i<n; i++){
minDis = min(minDis, abs(total - 2*add[i][m]));
}
for(int j = 0; j<m; j++){
minDis = min(minDis, abs(total - 2*add[n][j]));
}
cout<<minDis;
}
|