算法入门--java
二分查找
1.在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109nums是一个非递减数组-109 <= target <= 109
class Solution {
public int leftMargin(int[] nums,int target){//查找左边界
int low = 0;
int high = nums.length - 1;
while(low <= high){
int mid = low + (high-low)/2;
if(nums[mid] < target){
low = mid + 1;
}else if(nums[mid] > target){
high = mid - 1;
}else if(nums[mid] == target){
high = mid - 1;
}
}
if (nums[low] == target) {
return low;
} else {
return -1;
}
}
public int rightMargin(int[] nums,int target){//查找右边界
int low = 0;
int high = nums.length - 1;
int rm = 0;
while(low <= high){
int mid = low + (high-low)/2;
if(nums[mid] < target){
low = mid + 1;
}else if(nums[mid] > target){
high = mid - 1;
}else if(nums[mid] == target){
low = mid + 1;
rm = low;
}
}
if (nums[high] == target) {
return high;
} else {
return -1;
}
}
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0 || nums[0] > target || nums[nums.length - 1] < target) {
return new int[] {-1,-1};
}
int lm = leftMargin(nums,target);
int rm = rightMargin(nums,target);
return new int[] {lm,rm};
}
}
2.搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：
输入：nums = [1], target = 0
输出：-1
提示：
1 <= nums.length <= 5000-104 <= nums[i] <= 104nums中的每个值都 独一无二- 题目数据保证
nums在预先未知的某个下标上进行了旋转 -104 <= target <= 104
package lanqiaobei;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Demo01 {
public static void main(String[] args) {
int[] nums = {4,5,6,7,0,1,2};
int target = 0;
System.out.println(search(nums,target));
}
public static int search(int[] nums, int target) {
if(nums == null || nums.length == 0){
return -1;
}
int start = 0;
int end = nums.length;
int mid;
while(start <= end){
mid = start + (end - start) / 2;
if(nums[mid] == target){
return mid;
}
//前半部分有序，注意此处用小于等于
if(nums[start] <= nums[mid]){
//target在前半部分
if(target >= nums[start] && target < nums[mid]){
end = mid - 1;
}else{
start = mid + 1;
}
}else {
if(target <= nums[end] && target > nums[mid]){
start = mid + 1;
}else{
end = mid - 1;
}
}
}
return -1;
}
}
3.搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 100-104 <= matrix[i][j], target <= 104
class Solution {
public boolean searchMatrix(int[][] mat, int t) {
int m = mat.length, n = mat[0].length;
// 第一次二分：定位到所在行（从上往下，找到最后一个满足 mat[x]][0] <= t 的行号）
int l = 0, r = m - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (mat[mid][0] <= t) {
l = mid;
} else {
r = mid - 1;
}
}
int row = r;
if (mat[row][0] == t) return true;
if (mat[row][0] > t) return false;
// 第二次二分：从所在行中定位到列（从左到右，找到最后一个满足 mat[row][x] <= t 的列号）
l = 0; r = n - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (mat[row][mid] <= t) {
l = mid;
} else {
r = mid - 1;
}
}
int col = r;
return mat[row][col] == t;
}
}
4.寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1, len = r;
while (l < r) {
int m = l + r >> 1;
if (nums[m] > nums[len]) l = m + 1;
else r = m;
}
return nums[l];
}
}
5.寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
class Solution {
public int findPeakElement(int[] nums) {
int n = nums.length;
int l = 0, r = n - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return r;
}
}
双指针
1.删除排序链表中的重复元素
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
- 链表中节点数目在范围
[0, 300]内 -100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
//虚拟头节点
ListNode dummyHead = new ListNode();
dummyHead.next = head;
//前置节点
ListNode pre = dummyHead;
//当前节点（pre.next==head）
ListNode cur = pre.next;
while(pre.next != null){
//设置计数器计算是否有重复节点
int count = 0;
//当前节点的下一个节点不为空，且当前节点的下一个节点值和当前节点值相同
while(cur.next != null && cur.next.val == cur.val){
//当前节点就向后移动
cur = cur.next;
//计数器增加
count++;
}
//计数器不为0,需要删除前置节点后面的重复的数
//直接将前置节点的next连接到当前节点的下一个（此时cur是跳出循环后，重复节点的最后一个）
if(count != 0){
pre.next = cur.next;
}else{
//计数器为0，说明没进入循环，没遇到重复节点
//前置节点正常向后移动
pre = cur;
}
//不重复时cur正常向后移动
//重复时，cur是跳出循环后，重复节点的最后一个，因此也需要移动到后一个（也可以合并到if-else里）
cur = cur.next;
}
return dummyHead.next;
}
}
2.三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums);
for(int i = 0; i < len; i++){
if(nums[i] > 0) break;//如果当前数组大于>0,则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue;//去重
int L = i + 1;
int R = len -1;
while(L<R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while(L<R && nums[L] == nums[L+1]) L++;//去重
while(L<R && nums[R] == nums[R-1]) R--;
L++;
R--;
}
else if(sum < 0) L++;
else if(sum > 0) R--;
}
}
return ans;
}
}
BFS实现
//BFS实现
public int maxDepthBFS(TreeNode root){
//考虑树为空的特殊情况 BFS无法自动处理
if(root == null){
return 0;
}
//使用队列来记录各层节点
Queue<TreeNode> queue = new LinkedList<TreeNode>();
//根节点入队
queue.offer(root);
//目标值
int res = 0;
//判断是否还有没有遍历完的节点
while(!queue.isEmpty()){
//开始遍历新一层节点前，队列里即为新一层全部节点
int size = queue.size();
//需将这一层节点全部遍历完
while(size > 0){
//遍历节点
TreeNode node = queue.poll();
//左子树入队列
if(root.left != null){
queue.offer(root.left);
}
if(root.right != null){
queue.offer(root.right);
}
//size - 1
size--;
}
//新一层节点遍历完成 目标值 + 1
res++;
}
return res;
}
快速排序
public class QuickSort {
public static int partition(int[] array, int low, int high) {
// 取最后一个元素作为中心元素
int pivot = array[high];
// 定义指向比中心元素大的指针，首先指向第一个元素
int pointer = low;
// 遍历数组中的所有元素，将比中心元素大的放在右边，比中心元素小的放在左边
for (int i = low; i < high; i++) {
if (array[i] <= pivot) {
// 将比中心元素小的元素和指针指向的元素交换位置
// 如果第一个元素比中心元素小，这里就是自己和自己交换位置，指针和索引都向下一位移动
// 如果元素比中心元素大，索引向下移动，指针指向这个较大的元素，直到找到比中心元素小的元素，并交换位置，指针向下移动
int temp = array[i];
array[i] = array[pointer];
array[pointer] = temp;
pointer++;
}
System.out.println(Arrays.toString(array));
}
// 将中心元素和指针指向的元素交换位置
int temp = array[pointer ];
array[pointer] = array[high];
array[high] = temp;
return pointer;
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// 获取划分子数组的位置
int position = partition(array, low, high);
// 左子数组递归调用
quickSort(array, low, position -1);
// 右子数组递归调用
quickSort(array, position + 1, high);
}
}
public static void main(String[] args) {
int[] array = {6,72,113,11,23};
quickSort(array, 0, array.length -1);
System.out.println("排序后的结果");
System.out.println(Arrays.toString(array));
}
}
截断数组
//一个数组用两刀切成三段
//先使用前缀和(s[i]=s[i-1]+a[i])确定第二刀的位置
//然后再使用前缀和确定第一刀位置
//最后将两个位置可能的点相加
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int N = 100010;
long[] a = new long[N];
long[] s = new long[N];
long res = 0,cnt = 0;
for(int i=1;i<=n;i++){
a[i]=scan.nextInt();
s[i]=s[i-1]+a[i];//构造前缀和数组
}
if(s[n]%3!=0){//如果元素和不能被3整除，就不满足条件
System.out.println("0");
return;
}
for(int i=1;i<n;i++){//确定第二刀位置的个数
if(s[i]==s[n]/3*2) cnt++;
}
for(int i=1;i<n;i++){
if(s[i]==s[n]/3*2) cnt--;
if(s[i]==s[n]/3) res+=cnt;
}
System.out.println(res);
}
}
并查集
import java.util.Scanner;
public class Main{
static int N = 100010;
static int[] p = new int[N];
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); // 全部有n个数
int m = scan.nextInt(); // 读入m个操作
//将n个数每个数各自都在一个集合里面。都指向自己，说明现在有多少个集合
for(int i = 1 ; i <= n ; i ++) p[i] = i;
while(m -- > 0){
String s = scan.next();
int a = scan.nextInt();
int b = scan.nextInt();
//合并集合
if(s.equals("M")) p[find(a)] = find(b); //将a集合的根节点即祖先指向b集合的祖先
else{ //是否同个集合
if(find(a) == find(b))System.out.println("Yes"); //如果两个集合的祖先相同说明两个集合在同个集合中。
else System.out.println("No"); //否则相反
}
}
}
//并查集的核心操作，寻找根节点祖先 + 路径压缩
public static int find(int x){
// 如果这个集合的父节点指向的不是自己，说明不是根节点，递归寻找，
//最后找到根节点之后，把路径上的所有集合都指向根节点、
if(p[x] != x) p[x] = find(p[x]);
return p[x]; // 最后返回根节点
}
}
笨拙的手指
import java.util.*;
public class finger {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
char[] a=sc.next().toCharArray();//将输入的字符串转换成字符数组，便于修改字符
char[] b=sc.next().toCharArray();
Set<Integer> s=new HashSet<Integer>();//Set集合用于存储转换后的数值，看是否存在交集
for(int i=0;i<a.length;i++){
a[i]=(char)((int)a[i]^1);//将该位的0转成1，1转换成0
s.add(Integer.parseInt(new String(a),2));//使用Integer类的进制转换方法，将某进制转换成10进制【对于数组，可以使用String的构造器将其转换成字符串】
a[i]=(char)((int)a[i]^1);//复位
}
for(int i=0;i<b.length;i++){
char t=b[i];//由于三进制有三个数，就不能使用异或了，因此采用遍历的方式寻找
for(int j=0;j<3;j++){
if(j+'0'!=t){//如果该字符与当前字符不同，就可以试一下该字符
b[i]=(char)(j+'0');//将该字符进行更改
int x=Integer.parseInt(new String(b),3);//将其转换成10进制
if(s.contains(x)){//寻找集合里面是否有该十进制说，如果有就说明该三进制字符串转换一个字符与二进制字符串转换1个字符的十进制相等，输出该数
System.out.println(x);
return;
}
}
}
b[i]=t;//如果该数发生了转换【一定会发生转换的】，但是并没有与二进制转换的十进制相匹配，则进行复位【防止以后转换成10进制时，数值不准确】
}
}
}
DFS
public class newText2 {
public static void main(String[] args) {
dfs( step );
}
static void dfs(int step) {
if (暴搜结束的条件) //
{
System.out.println(输出题目答案);
return ; //结束
}
if (x >= n) return; //判断边界
for ( i=1; i<=n; i++) //尝试每一种可能
{
dfs(step+1) //继续下一步
}
}
}