这是我练题笔记，加油！（题目和思路方法均来自题库和网上，写在这方便自己回顾）
队列
岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
示例1.
输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1示例2.
输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。思路
根据题目的意思我们可以得到当一片相连’1’周围都是’0’时，则这是一个岛屿。
- 示例1中所有的’1’都是相连的只有1个岛屿。
- 示例2中相连的’1’只有左上方、中间还有右下方,所以有3个岛屿。
每块岛屿可以看成相连的一个个节点，只要把所有的节点遍历殆尽并标记以记录该点已经访问过，遍历完成后则证明找到一块岛屿。
解题方法
- DFS(深度优先搜索): 从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是0），依次访问其他相邻1节点到顶点。
class Solution {
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0) return 0;
int row = grid.length, columns = grid[0].length, count = 0;
for(int i = 0; i < row; i++){//遍历所有点
for(int j = 0; j < columns; j++){
if(grid[i][j] == '1'){
dfs(grid, i, j, row, columns);
count ++;
}
}
}
return count;
}
public void dfs(char[][] grid, int i, int j, int row, int columns){
if(i < 0 || j < 0 || i >= row || j >= columns || grid[i][j] == '0' ) return ;
grid[i][j] = '0';
dfs(grid, i + 1, j, row, columns);
dfs(grid, i, j + 1, row, columns);
dfs(grid, i - 1, j, row, columns);
dfs(grid, i, j - 1, row, columns);
}
}排序
快速排序
分治算法
该方法的基本思想是：
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
排序要求 运行时间：599ms 占用内存：53632KB 使用语言：Java 如果使用冒泡排序 时间需要2001ms 占用内存：10956KB，可知分治算法节省空间和时间接近一半
对{64,23,55,78,43,12,2,1,4,5,77,54,22}进行排序
import java.util.Arrays;
public class Sort {
public static void main(String[] args){
int[] a = {64,23,55,78,43,12,2,1,4,5,77,54,22};
System.out.println(Arrays.toString(mySort(a)));
}
public static int[] mySort(int[] arr){
return Sort(arr,0,arr.length-1);
}
public static int[] Sort(int[] s,int l,int h){
if(l < h){
int i = l, j = h;
int x = s[i];//以s[i]为基准数 两边与之比较
while(i < j){ //走一遍
while(i<j && s[j]>=x) //从右向前找小于x的数填入s[i]
j--;
if(i < j){
s[i] = s[j]; //s[j]填入s[i]后，s[j]等待新的数填入
i++;
}
while(i<j && s[i]<x) //从左往右找大于或等于x的数填入s[j]
i++;
if(i < j){
s[j] = s[i]; //s[i]填入s[j]后，s[i]等待新的数填入
j--;
}
}
s[i] = x; //走完一遍此时i等于这个区间的中点，把比较的数x填入
Sort(s,l,i-1); //递归调用将前半区间继续按照上面的方法比较换位
Sort(s,i+1,h); //递归调用将后半区间继续按照上面的方法比较换位
}
return s;
}
}二分查找
排序数组中找值
public static void main(String[] args){
// 二分查找 前提是一个有序数组
int[] a = {1,2,3,4,5,7,8,9,10};
System.out.println(findIndex(a,7));
}
// 返回要找到的那个数字的下标
public static int findIndex(int[] arr, int key){
int l = 0, h = arr.length-1; // 定义最左边和最右边的下标
//如果要找的值超出数组的范围
if (key < arr[l] || key > arr[h]){
return -1;
}
while(l <= h){
int mid = (h - l)/2 + l; //可以防止相减溢出为负数
if(arr[mid] == key){
return mid; // 找到key的下标返回
}else if(arr[mid] <= key ){ //当前比key小 则从mid的后半段重新二分查找
l = mid + 1;
}else { //否则从mid的前半段二分查找
h = mid - 1;
}
}
// 此时说明 要找的数不在数组中
return -1;
}找x的平方根
题目
计算返回x的平方根，其中x为非负数.(由于返回类型是int整数，结果只保留整数部分，小数部分被舍去)
例子
- 输入：8
- 返回：2
- 原因：8的平方根是2*根号2（2.82842…）由于返回类型是int 所以小数部分被舍去。
思路
x的平方根一定比x小，可以吧0到x的范围当作一个区间，利用二分查找的思想找到x的平方根。
public static void main(String[] args){
// 通过二分思想找 x的平方根
System.out.println(mySqrt(9));
}
//找出x的平方根
public static int mySqrt(int x){
int l = 0, h = x, ans = -1;
while( l <= h){
int mid = (h - l)/2 + l;
if(mid*mid <= x){
ans = mid;
l = mid + 1;
}else {
h = mid - 1;
}
}
return ans;
}
面试题
求字符数组的交集、并集、差集
public class t2{
public static void main(String[] args) {
String[] arr1 = {"a", "d", "c"};
String[] arr2 = {"a", "c", "k", "b", "l"};
System.out.println("===========求交集===========");
String[] s1 = intersect(arr1,arr2);
for (String s : s1){
System.out.print(s);
}
System.out.println();
System.out.println("===========求并集===========");
String[] s2 = union(arr1,arr2);
for (String s : s2){
System.out.print(s);
}
System.out.println();
System.out.println("===========求差集===========");
String[] s3 = minus(arr1,arr2);
for (String s : s3){
System.out.print(s);
}
}
//求交集的方法
public static String[] intersect(String[] arr1,String[] arr2){
//通过Map的containsKey方法判断是否存在相同的key
Map<String,Boolean> map = new HashMap<String,Boolean>();
List<String> list = new LinkedList<String>(); // 利用链表存放相同的值
for (String s : arr1){
if(!map.containsKey(s)){ // 如果不存在key == s
map.put(s,Boolean.FALSE); //存放当前值为key，并设置标记为false
}
}
for (String s : arr2){
if(map.containsKey(s)){ //遍历第二个数组，如果存在相同的值（key）
map.put(s,Boolean.TRUE); //将相同的key 改变标记为true （在map中其实是用新的替换旧的）
}
}
for (Map.Entry<String,Boolean> entry : map.entrySet()){ //Map.Entry<>是Map的内部接口 可以用来接收 Map的entrySet方法返回的映射关系，可以使用Entry的getValue和getKey获取值和key
if(Boolean.TRUE.equals(entry.getValue())){//找出map中值为true的（表示是重复的（交集））
list.add(entry.getKey());//将key放进链表中
}
}
String[] result = {}; // 用于接收toArray的值
return list.toArray(result) ; //通过toArray[T[]] 返回一个数组
}
// 求并集(利用set的特性 将两个数组都加进去)
public static String[] union(String[] arr1,String[] arr2){
//利用Set集合的唯一性，求出两个数组的并集
Set<String> set = new HashSet<String>();
for (String s : arr1){
set.add(s);
}
for (String s : arr2){
set.add(s);
}
String[] result = {};
return set.toArray(result);
}
//求差集（以一个为底 另一个来便利 存在相同则去除 存入历史记录，不相同的放进新数组返回新的数组）
public static String[] minus(String[] arr1,String[] arr2){
List<String> historyList = new LinkedList<String>(); //利用LinkedList的 contains方法判断是否重复
List<String> list = new LinkedList<String>();
for (String s : arr1){
if(!list.contains(s)){ //以arr1为底 判断不存在这个值则存进去
list.add(s);
}
}
for (String s : arr2){
if(list.contains(s)){ // 现在遍历arr2找到重复的值
historyList.add(s); //将重复的存进历史
list.remove(s); //list中去掉重复的
}else if (!historyList.contains(s)){ //上一个判断不存在的情况下 还要进行一次在历史中查找存不存在的判断 避免之前因为重复被去除放进历史导致又有同样的元素进入的情况
list.add(s);
}
}
String[] result = {};
return list.toArray(result); //返回结果
}
}求两个日期间隔的天数
public class time {
public static void main(String[] args){
//使用了jdk1.8新加入的元素
Temporal begin = LocalDateTime.of(2021,3,1,0,0);
Temporal end = LocalDateTime.of(2021,3,9,0,0);
Duration duration = Duration.between(begin, end);
//相差时间
System.out.println(duration.toDays());
}
}
