赞
踩
// 声明及默认初始化
int [] a = new int [10]; // 这里必须要给定数组的大小,数组中每个元素都是默认值,其中大小也可以为0,即 new int [0],表示一个空数组。
// 声明及手动初始化
int [] b = new int []{1,2,3};// 这里只要后面用{}进行了初始化,就不能在[]中指定大小。
int [] c = {1,2,3}; // 也可以不使用new int[]
//PS: 数组一旦创建,就无法改变其大小,如果想要创建大小动态变化的数组,应该使用ArrayList类。
// 用下标遍历访问
for(int i=0;i<a.length;i++){
System.out.println(a[i]);
}
// 用foreach遍历访问
for(int i:a){
System.out.println(i);
}
// 快速打印数组元素的方法
System.out.println(Arrays.toString(a));
(1)浅拷贝:
// Java中的数据类型包括基本数据类型和引用数据类型,其中引用数据类型包括类、接口、数组
// 浅拷贝对于基本数据类型来说,就是进行值传递,修改b的值不会改变a的值
int a = 2;
int b = a;
b = 3;
System.out.println(a);//2
// 浅拷贝对于引用数据类型来说,就是进行地址的传递,其不会对该对象重新开辟一个内存空间进行存放,而是相当于两个引用指向了同一个内存地址。此时修改b的值,a的值也会随之改变。
int [] a = {1,2,3};
int [] b = a;
b[0] = 2;
System.out.println(Arrays.toString(a));//[2,2,3]
(2)深拷贝:
// 深拷贝
// 对于基本数据类型来说,浅拷贝和深拷贝相同,因为对于Java中的基本数据类型,内存会在栈上为其分配一个位置,并将其值直接存储在该位置上,因此没有引用这一说。
// 而对于引用数据类型来说,当声明一个引用数据类型的变量时,变量存储的是对象的引用,而不是对象本身。对象本身存储在堆内存中,而对象的引用变量则存储在栈内存中。因此,浅拷贝只拷贝了对象的引用,其创建了一个新对象,新对象跟原始对象共享相同的内部引用。而深拷贝则不仅拷贝对象,而且还拷贝对象包含的引用所指向的对象。
int [] a = {1,2,3};
int [] b = Arrays.copyOf(a,a.length); // 注意这里要有两个参数,若第二个参数小于a的长度,则表明只复制一部分过来。
b[0] = 2;
System.out.println(Arrays.toString(a));//[1,2,3]
常用方法:
Arrays.sort(xxx[] a);
Arrays.copyOf(xxx[],int end);
Arrays.copyOfRange(xxx[],int start,int end);
Arrays.toString();
Array.equals(xxx [] a, xxx[] b) ;
Arrays.fill(xxx[] a,xxx v) //用值v填充数组a
Arrays.asList(a); // 将数组a转换为ArrayList类型
// 创建一个ArrayList,并默认初始化
ArrayList<Integer> alist = new ArrayList<>();
// 根据数组a来创建一个ArrayList
Integer [] a ={1,2,3}; // 注意这里必须要是Integer类型,不能是int类型
ArrayList<Integer> alist2 = new ArrayList<>{Arrays.asList(a)};
System.out.println(aList.size());// 大小
aList.get(0);// 获取元素
aList.remove(0); // 移除元素
aList.remove(Object o)
aList.add(int index, E element) //在特定位置处插入元素
aList.add(E e) // 在列表末尾插入元素
aList.contains(Object o) // 判断是否包含元素
aList.equals(aList2) // 判断两个数组列表是否完全相同
aList.indexOf(Object o) // 查找元素的下表
aList.isEmpty() // 判空
aList.set(int index, E element) // 更改元素
aList.toArray(); // 转换为数组
String greeting = "Hello";
greeting.substring(0,3);//表示提取下标范围在[0,3)的子串,即Hel
PS:s.substring(a,b)的长度为b-a
String str1 = "hello";
String str2 = "world";
String str3 = str1+str2;
// PS:当将一个字符串与一个非字符串的值进行拼接时,后者会转换成字符串
int age = 13;
String s = "PG"+age
String.valueOf(Object obj) // 调用API将任意对象转化为字符串
// 如果需要将多个字符串拼接起来,并使用一个符号分隔开,可以使用join方法
String all = String.join(" ",["How","are","you"]);//用空格分隔
// 使用repeat(n)方法可以将原始字符串重复n次
"lzs".repeat(6)
a.equals(b);//检验字符串a和b是否相等
PS:这里补充一下关于判断数组是否相等
例如:
char[] sa = a.toCharArray();
char[] sb = b.toCharArray();
Arrays.equals(sa,sb);//比较两个字符数组是否相等
sa.equals(sb);//判断sa,sb是否指向同一个对象
// 在java中字符串类型是不可变类型,只能访问,不能修改
// 使用s.charAt(i)来访问元素
s.charAt(0);
// 但Java也提供了另一种可变的字符串类型,即StringBuffer以及StringBuilder
// 其中StringBuffer可以确保线程安全,而在单线程环境下,用StringBuilder即可
append(char[] str, int offset, int len)//添加
delete(int start, int end)
deleteCharAt(int index)//删除
insert(int offset, char[] str)//插入
setCharAt(int index, char ch)//修改
toString()//转化为字符串
// Java提供了非常多的字符串API,在刷题时会很有用
1.int compareTo(String other);
按照字典序,若该字符串位于other之前,返回一个负数;若位于other之后,返回一个正数;否则,返回0;
2. indexOf(String str)
返回str在该字符串中出现的第一个位置
2. indexOf(String str,int fromIndex)
返回str在该字符串中出现的第一个位置,从fromIndex开始搜索
3.startWith(String perfix)
4.endWith(String perfix)
判断字符串是否以perfix开头或结尾
5.replace(CharSequence oldString,CharSequence newString)
用newString代替oldString,返回一个新的String,可以用String或者StringBuilder作为charSequence参数
6.toLowerCase()
7.toUpperCase()
返回大写或小写后的字符串
8.trim()
9.strip()
删除原始字符串头部和尾部小于等于U+0020(trim)[空格,制表符,换行],的字符或者空格(strip)
10.split()
将字符串按照一定的分隔符拆分成字符串数组
使用二分查找可以用O(logn)的时间复杂度代替时间复杂度为O(n)的暴力查找,而使用二分法的前提有两个:
其中,第一个条件是必须要满足的,否则使用二分查找完全不合理。而第二个条件不满足时,也可以查找到一个下标,但可能需要查找的下标不是唯一的。
循环不变量原则:「循环不变量」是指在编写代码的过程中,要一直循序不变的性质,这样的性质是根据要解决的问题,由自己定义的。「循环不变量」是我们写对一个问题的基础,保证了在「初始化」「循环遍历」「结束」这三个阶段相同的性质,使得一个问题能够被正确解决。
(1)模板一:左闭右闭
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int middle =0;
while(left<=right){
middle = left + (right - left)/2; // 防止left和right都很大时直接加和,造成溢出
if(nums[middle]==target){
return middle;
}else if(nums[middle] > target){
right = middle -1; //目标值在左半区间,right在middle左边一个
}else{
left = middle +1; // 目标值在右半区间,left在middle右边一个
}
}
return -1;
}
}
以上模板的循环不变量是假定target在一个左闭右闭的区间[left,right]中,因此while中的条件是left<=right,因为left = right 也是合理的。并且当nums[mid]<target时,说明target对应的左闭右闭区间在mid的右边,即[mid+1,right]。同理当nums[mid]<target时,说明target对应的左闭右闭区间在mid的左边,即[left,mid-1]。
(2)模板二:左闭右开
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int middle =0;
while(left<right){
middle = left + (right - left)/2; // 防止left和right都很大时直接加和,造成溢出
if(nums[middle]==target){
return middle;
}else if(nums[middle] > target){
right = middle; //目标值在[left,middle)
}else{
left = middle+1 ; // 目标值在[middle+1,right)
}
}
return -1;
}
}
第二个模板的循环不变量是假定target在一个左闭右开的区间[left,right)中,因此while中的条件是left<right,因为left = right 是不合理的。并且当nums[mid]<target时,说明target对应的左闭右开区间在mid的右边,即[mid+1,right)。同理当nums[mid]<target时,说明target对应的左闭右开区间在mid的左边,即[left,mid)。
34.在排序数组中查找元素的第一个和最后一个位置{不满足第二个前提条件}
双指针法的主要思想就是通过一个快指针和慢指针在一个for循环下完成两个for循环的工作,从而将O( n 2 n^2 n2)的时间复杂度降为O(n),而双指针法通常还分为快慢指针法和对撞指针法。
快慢指针法的经典题目是27.移除元素,即:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,必须仅使用 O(1) 额外空间并原地修改输入数组。
**解题思路:**两个指针都从下标0处开始,用一个快指针去遍历该数组,只要快指针指向的值nums[fast]不等于val,就让慢指针去修改数组的值为当前值,并使慢指针完成自增,即:nums[slow++] = nums[fast];而如果快指针指向的值等于val,则慢指针不做改变,最终慢指针之前的元素即为不包含val的其他所有元素。
Java代码:
class Solution {
public int removeElement(int[] nums, int val) {
int k = 0;//慢指针
for(int i = 0;i<nums.length;i++){ // i为快指针
if(nums[i]!=val){
nums[k++] = nums[i];
}
}
return k;
}
}
leetcode上的类似题目:
同样作为双指针法,对撞指针法是两个指针在数组的两端同时向中间收缩,直到对撞。经典的对撞指针的题目是167.两数之和Ⅱ,输入有序数组,在经典的两数之和题目中,解法是时间复杂度为 O ( n 2 ) O(n^2) O(n2)的暴力搜索,而在第167题中,规定输入为有序数组,并且不能使用暴力搜索的方法。
**解题思路:**让两个指针first,last分别位于数组的头部和尾部,并将二者之和与target比较,如果相等则返回。如果大于target,则说明last应该前移;如果小于target,则说明first应该后移;最终,当first == last的时候,如果还没有返回,说明不存在这样的两个数。
Java代码:
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length - 1;
while(i<j){
if(numbers[i]+numbers[j]>target){
j--;
}else if(numbers[i] + numbers[j]< target){
i++;
}else{
return new int[]{i+1,j+1};
}
}
return new int[]{0,0};
}
}
leetcode中的相关题目还有:
**所谓滑动窗口,顾名思义就是一个区间[start,end],通过不断移动该区间来找到满足一定条件的最长/最短子序列的长度。**针对两类问题,有不同的模板。
思路:
start、end都在起始点,end向右逐位滑动循环,在每次循环过程中:
直到end到达结尾。
初始化start、end、ans
while(end指针没有到达结尾){
窗口扩大,加入end对应的元素,更新当前ans;// PS:注意这里不需要判断end对应的元素是否满足窗口需要满足的条件,而是直接将其加入,判断是在后面的while循环中进行的。
while(窗口不满足条件){
窗口缩小,移除start对应的元素,start右移;
}
更新最优结果ans;
end++;
}
返回ans
思路:
start、end都在起始点,end向右逐位滑动循环,在每次循环过程中:
直到end到达结尾。
初始化start、end、ans
while(end指针没有到达结尾){
窗口扩大,加入end对应的元素,更新当前ans;// PS:注意这里不需要判断end对应的元素是否满足窗口需要满足的条件,而是直接将其加入,判断是在后面的while循环中进行的。
while(窗口满足条件){
更新最优结果ans;
窗口缩小,移除start对应的元素,start右移;
}
end++;
}
返回ans
模拟方法不涉及什么算法,就是模拟或刻画题目中要求的过程,有一点像找规律,通常是在二维矩阵情形下,有以下题目:
字符串也可以看作数组的一种,其中也有很多涉及到双指针的题目:
PS:
Java代码:
class Solution {
//前缀表(不减一)Java实现
public int strStr(String s, String t) {
if (t.length() == 0) return 0;
int[] next = new int[t.length()];
getNext(next, t);
int j = 0; // j指向模式串
// i不后退,母串和模式串相等时i++,冲突时i不动。
for (int i = 0; i < s.length(); i++) {
// 冲突时找前一个位置对应的next数组值,并令j指向该值对应的下标,然后继续判断是否匹配
// 注意这里一定要用while,而不是if,因为j移动一次之后,s[i]与t[j]可能还是不匹配的,你并且此时next[j-1]可能仍然不为0,这就说明模式串还可以继续移动。因此如果用if的话,反而是只移动了一次模式串,不管其是否匹配,就去移动母串了。而正确的方法应该是,只要遇到不匹配的情况,就先固定母串指针i,而根据next数组去一直移动模式串,直到移动完了之后i与j匹配或者是j已经移动到开头了。如果是i与j匹配,那么就继续后面的部分,即j++,i++,继续判断。如果是j已经等于0了,此时可能匹配也可能不匹配,匹配的话跟前面一样,j++,i++。不匹配的话就只有i++,再去比较。
while (j > 0 && t.charAt(j) != s.charAt(i)){
j = next[j - 1];
}
// 匹配时j++,i在for循环中完成自增
if (t.charAt(j) == s.charAt(i)){
j++;
}
if (j == t.length())
return i - t.length() + 1;
// 最后一位也完成匹配时,返回第一个匹配的下表
}
return -1;
}
private void getNext(int[] next, String s) {
// PS1: 这里next[i]表示[0,i]闭区间对应的字符串中最大公共前后缀的长度
// PS2: 其中前缀的要求就是:包含首元素而不能包含尾元素;后缀的要求就是:包含尾元素而不包含首元素。
int j = 0;// j表示已经匹配的前缀的后一个位置(第一个元素没有前前后缀而言,因此其后一个位置可记为0)
next[0] = 0; // 第一个元素没有前后缀,直接赋为0
for (int i = 1; i < s.length(); i++) {
// i表示已经已经匹配的后缀的后一个位置,由于next[0] = 0,因此i从1开始
// 如果已经匹配的前后缀的后一位对应的字符不相符:
// 那么需要在已经匹配的前缀中寻找有没有更短的公共前后缀长度,找的方法就是让j移动到next[j-1]的位置处
while (j > 0 && s.charAt(j) != s.charAt(i)){
j = next[j - 1]; //j回退
}
// 前缀后一位和后缀后一位相等:最大公共前后缀长度+1,前缀后缀的后一位也++
if (s.charAt(j) == s.charAt(i)){
j++;
}
next[i] = j; // 当前位置i对应的最大公共前后缀长度就等于当前j的值
}
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。