面试150题-数组部分
📕文章题目选自LeetCode面试150题-数组部分
😊该文章内容基于作者本人思考总结，如有错误欢迎指正
🏠题单地址：https://leetcode.cn/studyplan/top-interview-150/
数组/字符串
LeetCode150-移除元素-LC27
/**
* @Author DSXRIIIII
* @Project mounts
* @Package cn.dsxriiiii.LeetCode.LC150
* @Date 2024/8/20 9:59
* @Description: 移除元素
*/
public class LC27 {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length;
while(left < right){
if(nums[left] == val){
nums[left] = nums[right - 1];
right--;
}else{
left++;
}
}
return left;
}
}LeetCode150-删除有序数组中的重复项-LC26
/**
* @Author DSXRIIIII
* @Project mounts
* @Package cn.dsxriiiii.LeetCode
* @Date 2024/8/20 10:08
* @Description: 删除有序数组的重复项
* 快指针匹配相等时会往后一直匹配 当匹配不相同的时候会将快指针的值给慢指针
*/
public class LC26 {
public int removeDuplicates(int[] nums) {
int len = nums.length;
if(len == 0) return 0;
int slow = 1;
int fast = 1;
while(fast!=len){
if(nums[fast] != nums[fast-1]){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}LeetCode150-删除有序数组中的重复项II-LC80
//题目要求将出现两次以上的数让其只出现过两次
//原地操作（空间复杂度为O(1)） 采用覆盖操作咯 考虑快慢指针
public static int removeDuplicates(int[] nums){
int len = nums.length;
if(len < 2) return 2;
int fast = 2;
int slow = 2;
while(fast != len){
if(nums[slow-2] ！=nums[fast]){ //这个地方就限制了 数组元素只能出现两次
//这里不是赋值给nums[slow-2]
nums[slow++] = nums[fast];
}
fast++;
}
return slow; //翻新后的数组长度
//println()直接打印
}
//如何理解快慢指针逻辑
//1.快指针每一次循环都会向前++
//2.慢指针只有当nums[slow - 2] ！= nums[fast] 此时slow处于位置重复元素长度为3的位置，此时进行快指针的覆盖
//3.覆盖操作完成 快慢指针都会继续判断
//4.慢指针永远记录被修改的位置 快慢指针指向同一位置 也会进行赋值操作 并且原地不变LeetCode150-轮转数组-LC189
//方法一 数组拷贝
public void rotate(int[] nums,int k){
int len = nums.length;
int[] arr = new int[len];
for(int i = 0; i < len;i++){
arr[(i + k) % n] = nums[i];
//使用取余操作进行覆盖
}
System.arraycopy(arr,0,nums,0,len);
//调用拷贝函数 将新数组数据拷贝到旧数组
}
//方法二 使用翻转数组元素方式
public void rotate(int nums[],int k){
k = k % (nums.length);
reverse(0,nums.length-1,k);
reverse(0,k - 1,k);
reverse(k,nums.length,k);
}
public static void reverse(int start,int end,int[] nums){
while(start < end){ // 判断条件是 <
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start+=1;
end-=1;
}
}
}LeetCode150-买卖股票的最佳时机-LC189
//暴力枚举每一项时间复杂度为O(n**2)
//以下方法可以每一次判断当求到最小值时 ，保存最小值
//往后的每次都按照当前值与最小值的差值 与 保存的最大值进行比较
//最后求得最大的股票差值
public int maxProfit(int nums[]){
int minValue = Integer.MAX_VALUE;
int maxValue = 0;
for(int i = 0;i < nums.length;i++){
if(nums[i] < minValue){
minValue = nums[i];//保存最小值
}else{
if(nums[i] - minValue > maxValue){
maxValue = nums[i] - minValue;//计算差值
}
}
}
return maxValue;
}LeetCode150-买卖股票的最佳时机II-LC189
//动态规划思路
//讲实话真的很难懂
//假如股票的价格为{7,1,5,3,6,4}
//还是很难理解 。。。。。
public int maxProfit(int[] prices){
int len = prices.length;
if(len < 2) return 0;
int[] cash = new int[len];
int[] gupiao = new int[len];
cash[0] = 0;
gupiao[0] = -prices[i];
for(int i = 1;i < len;i++){
cash[i] = Math.max(cash[i-1],gupiao[i - 1] + prices[i]) //买股票和不买股票的最大值
gupiao[i] = Math.max(gupiao[i - 1],cash[i- 1] - prices[i]);
}
return cash[len - 1];
}
//使用贪心算法 每次计算出差值进行比较 这样的方法比较通俗易懂 时间复杂度O(n) 空间复杂度O(1)
public int maxProfit(int[] prices){
int len = prices.length;
if(len < 2) return 0;
int res = 0;
for(int i = 1;i < len;i++){
int diff = prices[i] - prices[i - 1];
if(diff > 0){
res += diff;
}
}
return res;
}
LeetCode150-跳跃游戏-LC55
/**
* 题目：跳跃游戏
* 算法思路-1：贪心算法
* 具体思路：遍历每一个位置，思考每一个位置可以到达的最远举例，前提条件是位置i可以到达
*/
public class LC55 {
public static void main(String[] args) {
int[] nums = {3,2,1,0,4};
System.out.println(canJump(nums));
}
public static boolean canJump(int[] nums) {
int maxIndex = 0;
for(int i = 0; i < nums.length;i++){
int curIndex = i + nums[i];
if(i <= maxIndex){ //这里必须要满足的条件 maxIndex记录的是要到达的最远距离
//如果 i > maxIndex 进行操作是无效的 因为永远到达不了这个位置
maxIndex = Math.max(curIndex,maxIndex);
}
if(maxIndex >= nums.length - 1){ //这里必须满足>=的条件 {0} 这样的情况也是可以到达的
return true;
}
}
return false;
}
}LeetCode150-跳跃游戏II-LC45
/**
* 题目：跳跃游戏II
* 算法思路-1：贪心算法
* 具体思路：遍历每一个位置，思考每一个位置可以到达的最远距离
* 当到达边界时此时 res++ 表示跳跃一次 我可以到达的最远距离赋值给边界
* 边界不断更新 那么跳跃次数也会不断更新 知道最后边界值大于等于数组长度
* 要注意遍历的范围[0，len - 1] 避免i走到数组末尾再一次+1
*/
public class LC45 {
public static int jump(int[] nums) {
int len = nums.length;
int maxIndex = 0;
int Border = 0;
int res = 0;
for(int i = 0; i < len;i++){
/*
* 此处i < len - 1
* 在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，
* 否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下
* 我们会增加一次「不必要的跳跃次数」 如何理解呢
* 假如数组int[] nums = {2,3,1,1,4}; 此时i走到了最后的位置 i = 4；此时边界border = 4；
* 此时会再一次走到i == border判断条件 此时res++ 就多余了
*/
maxIndex = Math.max(maxIndex,i+nums[i]);
if(i == Border){
Border = maxIndex;
res++;
}
}
return res;
}
public static void main(String[] args) {
int[] nums = {2,3,1,1,4};
System.out.println(jump(nums));
}
}LeetCode150-H指数-LC274
/**
* 题目：H指数
* 算法思路-1：贪心算法
* 具体思路：对于数组的每一个值 判断大于其值的个数是否等于i
*/
public int hIndex(int[] citations) {
Arrays.sort(citations);
int h = 0, i = citations.length - 1;
while (i >= 0 && citations[i] > h) {
h++;
i--;
}
return h;
}LeetCode150-O(1)时间插入删除获取随机元素-LC380
/**
* 题目：O(1)时间插入删除获取随机元素数
* 算法思路-1：贪心算法
* 具体思路：对于数组的每一个值 判断大于其值的个数是否等于i
*/
class RandomizedSet {
List<Integer> list;
Map<Integer,Integer> map;
Random random;
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
random = new Random();
}
public boolean insert(int val) {
if(map.containsKey(val)){
return false;
}
int index = list.size();
list.add(val);
map.put(val,index);
return true;
}
public boolean remove(int val) {
if(!map.containsKey(val)){
return false;
}
int index = map.get(val);
int lastnum = list.get(list.size()-1);
list.set(index,lastnum);
map.put(lastnum,index);
map.remove(val);
list.remove(list.size()-1);
return true;
}
public int getRandom() {
int randomIndex = random.nextInt(list.size());
return list.get(randomIndex);
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/LeetCode150-除自身以外数组的乘积-LC238
/**
* 题目：除自身以外数组的乘积
* 算法思路：遍历
* 具体思路：观察测试用例发现结果数组 保存的是除本身之外的左右所有值的乘积
* 分为两次循环更新数组
*/
public class LC238 {
public int[] productExceptSelf(int[] nums) {
int len = nums.length;
int[] answer = new int[len];
answer[0] = 1;
for(int i = 1; i < len;i++){
answer[i] = nums[i - 1] * answer[i - 1];
//对于数组 从左往右遍历 answer保存当前坐标（不包括自己）的所有乘积
}
int right = 1;
for(int i = len - 1;i >= 0;i--){
answer[i] = answer[i] * right;
//对于数组从右往左遍历 answer更新 right保存当前坐标（不包括当前坐标的值所有乘积
right = right * nums[i]; //right实时更新
}
return answer;
}
}LeetCode150-加油站-LC134
/**
* 题目：加油站
* 算法思路：遍历
* 具体思路：1.循环数组实现
* 2.剪枝 更新i时 考虑index
* 3.计算每次的油量
*/
public class LC134 {
public int canCompleteCircuit(int[] gas, int[] cost) {
int len = gas.length;
int i = 0;
//思路
while(i < len) {
int gasCapacity = 0;
int costCapacity = 0;
int index = 0;//保存遍历长度 这个坐标可以表示走了index步 是否成功
while(index < len){//index表示要走的步数 总共要走len步 走到len步就说明成功了
int cur = (index + i) % len;
gasCapacity += gas[cur];
costCapacity += cost[cur];
if(costCapacity > gasCapacity){ //不满足条件会走break退出while循环 下一步index也不会更新
break;
}
index++;
}
//长度为len满足条件返回坐标
if(index == len){
return i;
}else{
i = i + 1 + index;//优化手段
//为什么不采用以下的方式
//i = i + 1;
//因为index已经走了index++自增步数 如果break退出证明index + i这个范围都不合适
//为什么不合适 如果下一步还是从i + 1开始走 走到 前一个index + i位置时还是不满足条件 所以选择剪枝
//在更新时将i = i + index + 1；此时从这个地方走可以节约很多时间
}
}
return -1;
}
}LeetCode150-分发糖果-LC135
/**
* 题目：分发糖果
* 算法思路：两次遍历
* 具体思路：1.从左向右遍历 当i > i-1 数组更新++,否则arr[i] = 1;
* 2.从右向左遍历 同上 记录right值是为了当不断递增时 res 可以 加上 比较中的最大值
*/
public class LC135 {
public static void main(String[] args) {
int[] nums = {1,0,2};
System.out.println(candy(nums));
}
public static int candy(int[] ratings) {
int res = 0;
int len = ratings.length;
int[] arr = new int[len];
for(int i = 0; i < ratings.length;i++){
if(i > 0 && ratings[i] > ratings[i - 1]){
arr[i] = arr[i - 1] + 1;
}else{
arr[i] = 1;
}
}
int right = 0;
for(int j = ratings.length - 1;j >= 0;j--){
if(j < len - 1 && ratings[j] > ratings[j + 1]) {
right++;
}else{
right = 1;
}
//res += arr[j]; 保存的right值是用来当左边值大于右边值时 right会right++
//例如下面这个数组{1,3,5,3,2,1} 第三个人比左右两边都要高 但是 从右向左right == 4 arr[i] = 3 所以要取大值4
res += Math.max(arr[j],right);
}
//System.out.println(Arrays.toString(arr));
return res;
}
}
LeetCode150-接雨水-LC42
/**
* 题目：接雨水
* 算法思路：双指针
* 具体思路：1.维护左右leftMax,rightMax记录左右的最大值
* 2.如果 height[left] < height[right],则必有leftMax < rightMax或者leftMax > rightMax那么此时就可能会有雨水
* 3.雨水值就为leftMax - height[left] 或者 rightMax - height[right]
* 4.最后res用来保存雨水值 当左右left与right指针相遇时结束
*/
public class LC42 {
public int trap(int[] height) {
int res = 0;
int left = 0,right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
while(left < right){
leftMax = Math.max(height[left],leftMax);
rightMax = Math.max(height[right],rightMax);
if(height[left] < height[right]){
res+=leftMax - height[left];
left++;
}else{
res+=rightMax - height[right];
right--;
}
}
return res;
}
}
LeetCode150-罗马数字转整数-LC13
import java.util.HashMap;
import java.util.Map;
/**
* 题目：罗马数字转整数
* 算法思路：遍历找特殊条件
* 具体思路：1.列举特殊条件即可
*/
public class LC13 {
public static void main(String[] args) {
String s = "LVIII"; //1000 + 900 + 90 + 4
System.out.println(romanToInt(s));
}
public static int romanToInt(String s) {
Map<Character,Integer> map = new HashMap<>();
map.put('I',1);
map.put('V',5);
map.put('X',10);
map.put('L',50);
map.put('C',100);
map.put('D',500);
map.put('M',1000);
int res = 0;
res += map.get(s.charAt(0));
for(int i = 1;i < s.length();i++){
if(
(s.charAt(i) == 'V' || s.charAt(i) == 'X') && s.charAt(i - 1) == 'I' ||
(s.charAt(i) == 'L' || s.charAt(i) == 'C') && s.charAt(i - 1) == 'X' ||
(s.charAt(i) == 'D' || s.charAt(i) == 'M') && s.charAt(i - 1) == 'C'
//记得加（）维持条件
){
res -= map.get(s.charAt(i - 1));
res += map.get(s.charAt(i)) - map.get(s.charAt(i - 1));
}else{
res += map.get(s.charAt(i));
}
}
return res;
}
}LeetCode150-整数转罗马数字-LC12
/**
* 题目：整数转罗马数字
* 算法思路：遍历找特殊条件
* 具体思路：1.列举特殊条件即可 使用StringBuilder拼接
*/
public class LC12 {
public static void main(String[] args) {
System.out.println(intToRoman(58));
}
public static String intToRoman(int num) {
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
StringBuilder sb = new StringBuilder();
for (int i = 0; i < values.length; i++) {
while(num >= values[i]){
num-=values[i];
sb.append(symbols[i]);
}
if(num == 0){
break;
}
}
return sb.toString();
}
}
LeetCode150-最后一个单词的长度-LC58
/**
* 题目：最后一个单词的长度
* 算法思路：遍历
* 具体思路：1.去掉前后的空格 trim()方法
* 2.遍历到‘ ’处停止
*/
public class LC58 {
public static void main(String[] args) {
String s = "a";
System.out.println(lengthOfLastWord(s));
}
public static int lengthOfLastWord(String s) {
s = s.trim();
int res = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if(s.charAt(i) != ' '){
res++;
}else{
break;
}
}
return res;
}
}
LeetCode150-最长公共前缀-LC14
/**
* 题目：最长公共前缀
* 算法思路：遍历
* 具体思路：1.字符数组的第一个字符串为比较串
* 2.横向比较法 两两比较
* 3.纵向比较法 全部比较
* 4.时间复杂度都为O(mn) 空间复杂度为O(1) 常数
*/
public class LC14 {
/**
* 横向比较法 每一次取两个字符串比较 取得的相似值放到下一次比较中
*/
public String longestCommonPrefix(String[] strs) {
int len = strs.length;
if(len == 0) return "";
String SameString = strs[0];
for(int i = 1; i < len;i++){
SameString = getSameString(SameString,strs[i]); //返回得到两个字符串的最长序列 在进入到下一次循环中
// if(SameString == null){
// break;
// }
}
return SameString;
}
/**
* 纵向比较法 将初始字符串的每一个字符与后续的所有字符串进行比较
*/
public String longestCommonPrefix_2(String[] strs) {
int len = strs[0].length();
if(len == 0) return "";
for(int i = 0; i < len;i++){
char c = strs[0].charAt(i);
for(int j = 1;j < strs.length;j++){
if(i == strs[j].length() || strs[j].charAt(i) != c){
//i == strs[j].length() 此时短的字符串走完了
//strs[j].charAt(i) != c 与当前字符比较不相等 i为公共最长长度
//i 记录公共长度
strs[0] = strs[0].substring(0,i);
}
}
}
return strs[0];
}
private String getSameString(String sameString, String str) {
int index = 0;
int length = Math.max(sameString.length(),str.length());
while(index < length && sameString.charAt(index) == str.charAt(index)){
index++;
}
return sameString.substring(0,index);
}
}
LeetCode150-反转字符串中的单词-LC151
/**
* 题目：反转字符串中的单词
* 算法思路：调用方法（正则表达式）
* 具体思路：1.字符数组的第一个字符串为比较串
* 2.横向比较法 两两比较
* 3.纵向比较法 全部比较
* 4.时间复杂度都为O(mn) 空间复杂度为O(1) 常数
* 补充：正则表达式：
* 1.“_” 匹配任何单个字符
* 2."*" 匹配0个或者多个在它面前的字符
* 3."%" 匹配任意数字字符
* 4."[]" 匹配方括号中的任意字符
*/
public class LC151 {
public static void main(String[] args) {
String s = "the sky is blue";
System.out.println(reverseWords_queue(s));
}
public static String reverseWords_function(String s) {
s = s.trim();
List<String> list = Arrays.asList(s.split("\\s+"));
// "\\s+" 表示一个或者多个连续的空白字符串
Collections.reverse(list);//翻转list中的所有单词
System.out.println(list);//[blue, is, sky, the]
return String.join(" ",list);
}
/**
* 使用双端队列Deque在头部插入新数据
*/
public static String reverseWords_queue(String s) {
s = s.trim();
Deque<String> queue = new LinkedList<>();
StringBuilder word = new StringBuilder();
int left = 0;
int right = s.length() - 1;
while(left <= right){ //从左向右遍历 遇到字符添加进入word 当遇到空白字符时添加进入队列并且重置word
char c = s.charAt(left);
if(word.length() != 0 && c == ' '){
queue.offerFirst(word.toString());
word.setLength(0);
}else if(c != ' '){//"example good a" 确保这样的方式也能通过 避免中间的多余空格
word.append(c);
}
left++;
}
queue.offerFirst(word.toString());
return String.join(" ",queue);
}
}LeetCode150-Z字形变换-LC6
import java.util.ArrayList;
import java.util.List;
/**
* 题目：Z字形变换
* 算法思路：StringBuilder拼接字符串
* 具体思路：1.flag 用于调转方向 比如 1,2,3 -> 3,2,1 -> 1,2,3
*/
public class LC6 {
public String convert(String s, int numRows) {
if (numRows < 2) return s;
List<StringBuilder> res = new ArrayList<>();
int index = 0,flag = 1;
for(int i = 0; i < numRows;i++){
res.add(new StringBuilder());
}
for(char c : s.toCharArray()){
res.get(index).append(c);
index+=flag;
if(index == 0 || index == numRows - 1){
flag = - flag;
}
}
StringBuilder sb = new StringBuilder();
for (StringBuilder stringBuilder : res){
sb.append(stringBuilder.toString());
}
return sb.toString();
}
}LeetCode150-找出字符串中第一个匹配项的下标-LC28
/**
* 题目：找出字符串中第一个匹配项的下标
* 算法：KMP
* 思路 1.KMP算法计算出needle的具体数值
* 2.利用next数组进行回退 当遇到字符不匹配时
* 3.j坐标回退 如果j == m说明此时已经匹配到了主串
* 4.返回结果i - m + 1
*/
public class LC28 {
public static void main(String[] args) {
String haystack = "mississippi", needle = "issip";
System.out.println(strStr_kmp(haystack,needle));
}
public static int strStr_kmp(String haystack, String needle) {
int j = 0;
int[] next = new int[needle.length()];
for(int i = 1;i < needle.length();i++){
while(j > 0 && needle.charAt(i) != needle.charAt(j)){
j = next[j - 1];
}
if(needle.charAt(i) == needle.charAt(j)){
j++;
}
next[i] = j;
}
for(int i = 0,k = 0;i < haystack.length();i++){
while(j > 0 && needle.charAt(j) != haystack.charAt(i)){
j = next[j - 1];
}
if(needle.charAt(j) == haystack.charAt(i)){
j++;
}
if(j == needle.length()){
return i - needle.length() + 1;
}
}
return -1;
}
@Deprecated
public static int strStr_index(String haystack, String needle) {
int targetLen = needle.length();
int index = 0;
for(int i = 0;i < haystack.length();i++){
if(haystack.charAt(i) == needle.charAt(index)){
index++;
}else{
index = 0;
}
if(index == targetLen){
return i - targetLen + 1;
}
}
return -1;
}
}数组字符串总结
1.移除元素
2.删除有序数组中的重复项
双指针->if(nums[fast-1]!=nums[fast])
3.删除有序数组中的重复项II
双指针->if(nums[slow-2]!=nums[fast]) -> nums[slow] = nums[fast]
4.轮转数组
arr[(i+k)%n]=arr[i] -> System.arraycopy()
5.买卖股票的最佳时机
for循环-> 保存最小值pre -> 当前节点-pre不断保存最大ans
6.买卖股票的最佳时机II
贪心 保存每一次的差值
7.跳跃游戏
满足i <= maxIndex 才会更新最大坐标 如果不满足代表当前位置不可达 return true的条件 满足>=最后一位即可
8.跳跃游戏II
记录每一次的最大边界值 当到达最大边界值时 ans++ 并且更新最新的最大边界值 但是注意最后一个坐标可能会重复++ 修改区间[0，length-2]
9.H指数
在len >= 0 && h < citations[len]条件下 寻找h的最大值 h++ len--
10.O(1) 时间插入、删除和获取随机元素
Set+List+Random
11.除自身以外数组的乘积
从左到右将结果数字相乘[1,len) 从右到左将结果数组相乘 [len-1,0]
12.加油站
记录坐标位置i 步数index 记录对应每一个坐标每一步所需要的开销和油量 坐标更替要用到(i+k)%n 开销大于油量break index走到len说明走到了原位返回即可 剪枝优化i=i+1+index [i,j]不行 [i+1,j]也不行
13.分发糖果
ans数组从左到右更新当前值 从右到左比对 起点为1 right不断++ res记录right值和ans[i] 谁最大添加谁
14.接雨水
双指针 [left,right]区间 记录最大的left_max和right_max 使用最大的max值减去当前值即可获取水池的大小 保证水池是最小的 左右指针每次只移动一个
15.罗马数字转整数
罗马数字保存到map中 如果匹配到特殊组合将其从结果减去并添加特殊值
16.整数转罗马数字
values对应上字母symbols for循环对于每一位字符使用while循环不断减去 sb添加坐标位置字符
17.最后一个单词的长度
trim()去掉首尾空格 匹配或者split()
18.最长公共前缀
两两比较放到下一次比较中
19.反转字符串中的单词
双端队列
20.Z字形变换
反转flag 对应多个StringBuilder stringBuilder的坐标位置根据index变化
21.找出字符串中第一个匹配项的坐标
KMP算法的简单应用
KMP模版
int[] next = new int[haystack.length()];
// i 从 1 开始 0号坐标没有前后缀
for(int i = 1,j = 0; i < haystack.length();i++){
while(j > 0 && haystack.charAt(i) != needle.charAt(j)){
j = next[j - 1];
}
if(haystack.charAt(i) == needle.charAt(j)){
j++;
}
next[i] = j;
}