-
Notifications
You must be signed in to change notification settings - Fork 116
数组相关算法
zhangpan edited this page Aug 20, 2021
·
19 revisions
public static int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int result = target - nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == result) {
return new int[] { i, j };
}
}
}
return null;
}
public static int[] twoSum1(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[] { map.get(target - nums[i]), i };
}
map.put(nums[i], i);
}
return null;
}
public static boolean isPalindrome(String s) {
int right = s.length() - 1;
int left = 0;
while (left < right) {
char leftChar = s.charAt(left);
while (!Character.isLetterOrDigit(leftChar) && left < right) {
leftChar = s.charAt(++left);
}
char rightChar = s.charAt(right);
while (!Character.isLetterOrDigit(rightChar) && left < right) {
rightChar = s.charAt(--right);
}
if (Character.toLowerCase(leftChar) != Character.toLowerCase(rightChar)) {
return false;
}
left++;
right--;
}
return true;
}
// 解法1
class NumArray {
private final int[] nums;
public NumArray(int[] nums) {
this.nums=nums;
}
public int sumRange(int left, int right) {
if(nums==null){
return 0;
}
int sum = 0;
for(;left<=right;left++){
sum += nums[left];
}
return sum;
}
}
// 解法2
public class NumArray {
private final int[] sums;
public NumArray(int[] nums) {
int n = nums.length;
sums = new int[n + 1];
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + sums[i + 1];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}
public double findMaxAverage(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
if (nums.length == k) {
return (double) sum / k;
}
int maxSum = sum;
if (k == 1) {
for (int i = 1; i < nums.length - 1; i++) {
maxSum = Math.max(maxSum, nums[i]);
}
return maxSum;
}
for (int i = 0; i < nums.length - k; i++) {
sum = sum - nums[i] + nums[i + k];
maxSum = Math.max(maxSum, sum);
}
return (double) maxSum / k;
}
- JMM与volatile关键字
- synchronized的实现原理
- synchronized等待与唤醒机制
- AQS的实现原理
- ReentrantLock的实现原理
- ReentrantLock等待与唤醒机制
- CAS、Unsafe类以及Automic并发包
- ThreadLocal的实现原理
- 线程池的实现原理
- Java线程中断机制
- 多线程与并发常见面试题
- Android基础知识汇总
- MVC、MVP与MVVM
- SparseArray实现原理
- ArrayMap的实现原理
- SharedPreferences
- Bitmap
- Activity的启动模式
- Fragment核心原理
- 组件化项目架构搭建
- 组件化WebView架构搭建
- 为什么 Activity.finish() 之后 10s 才 onDestroy ?
- Binder与AIDL
- Binder实现原理
- Android系统启动流程
- InputManagerService
- WindowManagerService
- Choreographer详解
- SurfaceFlinger
- ViewRootImpl
- ActivityManagerService
- APP启动流程
- PMS安装与签名校验
- Dalvik与ART
- 内存优化策略
- UI界面及卡顿优化
- App启动优化
- ANR问题
- 包体积优化
- APK打包流程
- 电池电量优化
- Android屏幕适配
- 线上性能监控1--线上监控切入点
- 线上性能监控2--Matrix实现原理
- Glide实现原理
- OkHttp实现原理
- Retrofit实现原理
- RxJava实现原理
- RxJava中的线程切换与线程池
- LeakCanary实现原理
- ButterKnife实现原理
- ARouter实现原理
- Tinker实现原理
- 2. 两数相加
- 19.删除链表的倒数第 N 个结点
- 21. 合并两个有序链表
- 24. 两两交换链表中的节点
- 61. 旋转链表
- 86. 分隔链表
- 92. 反转链表 II
- 141. 环形链表
- 160. 相交链表
- 206. 反转链表
- 206 反转链表 扩展
- 234. 回文链表
- 237. 删除链表中的节点
- 445. 两数相加 II
- 面试题 02.02. 返回倒数第 k 个节点
- 面试题 02.08. 环路检测
- 剑指 Offer 06. 从尾到头打印链表
- 剑指 Offer 18. 删除链表的节点
- 剑指 Offer 22. 链表中倒数第k个节点
- 剑指 Offer 35. 复杂链表的复制
- 1. 两数之和
- 11. 盛最多水的容器
- 53. 最大子序和
- 75. 颜色分类
- 124.验证回文串
- 167. 两数之和 II - 输入有序数组 -169. 多数元素
- 189.旋转数组
- 209. 长度最小的子数组
- 283.移动0
- 303.区域和检索 - 数组不可变
- 338. 比特位计数
- 448. 找到所有数组中消失的数字
- 643.有序数组的平方
- 977. 有序数组的平方