按照代码随想录刷了刷题，但是感觉有点不对劲，只刷题没有总结觉得等于没有刷。
String
String常用的函数
substring(int i,int j)：这个函数的全是小写，用来截取字符串i:截取字符串的起始索引j：截取到 j 索引之前的元素
trim(): 用来去掉首尾空白字符串split(): 用来分割，里面是正则表达式toCharArray(): 将字符串变更为字符数组charAt( int n): 将字符串的第n个元素返回为字符join():String.join("-","a","b","c"),输出结果a-b-c,第二个参数可以是数组或者集合
字符串没有直接的reverse函数，但是可以通过StringBuffer来实现字符串的反转。
// 使用StringBuffer来实现字符串的反转String sReverse = new StringBuffer(s).reverse().toString();
StringBuffer和StringBuilder的区别就是StringBuffer有synchronized同步锁。
常用的排序算法
在写各个排序函数之前，我先写一个公共的调用函数。
public static void main(String[] args) {
int[] arr = {23,5,35,14,1443,154,515,21,524,67};
int[] sorted = function(arr);
for(Integer num: sorted){
System.out.println(num);
}
}
// 所以，下面的排序实现方法就是实现 function()
冒泡排序
比较相邻的元素，如果前面比后面大，就交换他们两个。这样每进行一次，就会把最大的元素通过交换放到了最后一个。
public static int[] function(int[] nums){
int temp = 0; //定义临时变量用于交换
int len = nums.length;
for (int i = 0; i < len; i++) {
for(int j = 0;j<len-i-1;j++){
if(nums[j]>nums[j+1]){
temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
return nums;
}
选择排序
选择排序和冒泡排序一样都是交换排序。
冒泡排序是交换相邻的元素，选择排序是在后面的序列中找到最大的元素与第一个元素交换，之后再找剩下的序列中最大的与第二个交换，以此类推。
public static int[] function(int[] nums){
int len = nums.length;
//进行 n 趟操作
for (int i = 0; i < len; i++) {
int k = i;
for(int j = i;j<len;j++){
// 每趟操作取出剩下序列的最小值的元素，下标为k
if(nums[j]<nums[k]){
k = j;
}
}
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
return nums;
}
插入排序
插入排序和选择排序都是找一个元素放到前面，但是略有不同。
- 选择排序是找到待排序序列的元素中最小值（比较大小在待排序序列中），然后放到已排序序列的结尾。
- 插入排序是找待排序的元素的第一个（比较在已排序序列中），找到合适的插入位置放进去。插入排序带来了数组中的元素大批量的移动。
public static int[] function(int[] nums){
int len = nums.length;
//进行n-1趟排序
for(int i = 1;i<len;i++){
//temp临时存放num[i];
int temp = nums[i], j = i;
//j 向前枚举
while(j>0 && temp < nums[j-1]){
//元素后移
nums[j] = nums[j-1];
j--;
}
nums[j] = temp;
}
return nums;
}
归并排序
该算法采用的是分治法，将已有序的序列合并，得到完全有序的序列。
归并排序是建立在归并操作上的排序算法，就是说，将有序序列进行合并的时候，使用的是二路归并。
所以，整个归并排序就可以分为两个过程，一个是递归一分为二的过程，另一个是有序序列合二为一的归并过程。
public static void main(String[] args) {
int[] arr = {23,5,35,14,1443,154,515,21,524,67};
int len = arr.length;
int[] tmp = new int[len];
mergeSort(arr,0,len-1,tmp);
for(Integer num: arr){
System.out.println(num);
}
}
public static void mergeSort(int[] arr,int low,int high,int[] tmp){
if(low<high){
int mid = (low+high)/2;
mergeSort(arr,low,mid,tmp);
mergeSort(arr,mid+1,high,tmp);
merge(arr,low,mid,high,tmp);
}
}
private static void merge(int[] arr, int low, int mid, int high, int[] tmp) {
int i = 0;
int j = low, k = mid + 1; //左边序列和右边序列起始索引
while (j <= mid && k <= high) {
if (arr[j] < arr[k]) {
tmp[i++] = arr[j++];
} else {
tmp[i++] = arr[k++];
}
}
//若左边序列还有剩余，则将其全部拷贝进tmp[]中
while (j <= mid) {
tmp[i++] = arr[j++];
}
while (k <= high) {
tmp[i++] = arr[k++];
}
for (int t = 0; t < i; t++) {
arr[low + t] = tmp[t];
}
}
快速排序
快速排序是在数列中挑出来一个基准（一般是第一个），然后重新排序序列，比基准小的放在基准前面，比基准大的放在基准后面。然后递归的重复这个操作（有点归并排序那味了）。
public static void main(String[] args) {
int[] arr = {23,5,35,14,1443,154,515,21,524,67};
int len = arr.length;
quickSort(arr,0,len-1);
for(Integer num: arr){
System.out.println(num);
}
}
private static void quickSort(int[] nums, int low, int high) {
if(low<high){
int partation = partation(nums,low,high);
//返回的 low值已经确定了，所以不用参与排序
quickSort(nums,0,low-1);
quickSort(nums,low+1,high);
}
}
//进行一次排序，将待排序序列分为两个部分
private static int partation(int[] nums, int low, int high) {
// select first as pivot
// 选第一个作为基准
int pivot = nums[low];
while(low<high){
while(low<high && nums[high]>=pivot){
high--;
}
nums[low] = nums[high];
while(low<high&&nums[low]<=pivot){
low++;
}
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}
链表的常用操作
二叉树的常用操作
递归
递归的思路
- 找终止条件
- 找返回值：我们需要向上一级返回什么信息，一般是已经完成操作的结果。
- 本级递归应该做什么：只考虑本级，不要多想
若有收获，就点个赞吧
0 人点赞
