目录
283. 移动零
https://leetcode.cn/problems/move-zeroes/
class Solution {
//方法一：简单覆盖
//非零的从下标0添加，数组剩下位置都填0
// public void moveZeroes(int[] nums) {
// int len=nums.length;
// int k=0;
// for(int i=0;i<len;i++){
// if(nums[i]!=0){
// nums[k++]=nums[i];
// }
// }
// while(k<len){
// nums[k++]=0;
// }
// }
//方法二：双指针
//解释一下：如果数组没有0，那么快慢指针始终指向同一个位置，每个位置自己和自己交换；
//如果数组有0，快指针先走一步，此时慢指针对应的就是0，所以要交换。
public void moveZeroes(int[] nums) {
int len=nums.length;
int left=0;
int right=0;
while(right<len){
if(nums[right]!=0){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
}
right++;
}
}
}
11. 盛最多水的容器
https://leetcode.cn/problems/container-with-most-water/
class Solution {
public int maxArea(int[] height) {
//若向内 移动短板 ，水槽可能变大，因此下个水槽的面积 可能增大 。
//若向内 移动长板 ，下个水槽的面积 可能会变小（或者不变）
int left=0;
int right=height.length-1;
int res=0;
while(left<right){
int area= Math.min(height[left],height[right])*(right-left);
res=Math.max(res,area);
if(height[right]>=height[left]){
left++;
}else{
right--;
}
}
return res;
}
}
15. 三数之和
https://leetcode.cn/problems/3sum/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int len=nums.length;
Arrays.sort(nums);//先排序
List<List<Integer>> res=new ArrayList<>();
for(int i=0;i<len;i++){
if(nums[i]>0){
return res;
}
if(i>0 && nums[i]==nums[i-1]){
continue;//去重
}
int left=i+1;
int right=len-1;
while(right>left){
int sum=nums[i]+nums[left]+nums[right];
if(sum<0){
left++;
}else if(sum>0){
right--;
}else{
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
left++;
right--;
while(right>left && nums[left]==nums[left-1]){
left++;
}
while(right>left && nums[right]==nums[right+1]){
right--;
}
}
}
}
return res;
}
}
42. 接雨水*(暴力，双指针优化暴力，单调栈)
https://leetcode.cn/problems/trapping-rain-water/
class Solution {
public int trap(int[] height) {
//3.单调栈
int len=height.length;
if (len <= 2) return 0;
int res=0;
Stack<Integer> s=new Stack<>();
s.push(0);
for(int i=1;i<len;i++){
int top=s.peek();
if(height[top]>height[i]){
s.push(i);
}else if(height[top]>height[i]){
s.pop();
s.push(i);
}else{
int curHigh=height[i];//目前节点的高度
while(!s.isEmpty() && (curHigh>height[s.peek()])){
int mid=s.pop();
if(!s.isEmpty()){
int left=s.peek();
int h=Math.min(height[left],curHigh)-height[mid];
int w=i-left-1;
int area=h*w;
if(area>0){
res+=area;
}
}
}
s.push(i);
}
}
return res;
//2.双指针
/* 为了得到两边的最高高度，使用了双指针来遍历，每到一个柱子都向两边遍历一遍， 这其实是有重复计算的。我们把每一个位置的左边最高高度记录在一个数组上（maxLeft[]） 右边最高高度记录在一个数组上（maxRight[]），这样就避免了重复计算。 */
int len=height.length;
if (len <= 2) return 0;
int res=0;
int maxLeft[]=new int[len];
int maxRight[]=new int[len];
// 记录每个柱子左边柱子最大高度
maxLeft[0]=height[0];
for(int i=1;i<len;i++){
maxLeft[i]=Math.max(maxLeft[i-1],height[i]);
}
// 记录每个柱子右边柱子最大高度
maxRight[len-1]=height[len-1];
for(int i=len-2;i>=0;i--){
maxRight[i]=Math.max(maxRight[i+1],height[i]);
}
for(int i=0;i<len;i++){
if(i==0 || i==len-1){
continue;
}
int h=Math.min(maxLeft[i],maxRight[i])-height[i];
res+=h;
}
return res;
//1.暴力解法
//每一列雨水的高度，取决于该列左侧最高的柱子和右侧最高的柱子中最矮的
//那个柱子的高度减去当前列的高度h=Math.min(maxLeft,maxRight)-height[i]
int len=height.length;
int res=0;
for(int i=0;i<len;i++){
if(i==0 || i==len-1){
continue;
}
int maxLeft=0;
int maxRight=0;
for(int j=i;j<len;j++){
maxRight=Math.max(maxRight,height[j]);
}
for(int j=i;j>=0;j--){
maxLeft=Math.max(maxLeft,height[j]);
}
int h=Math.min(maxLeft,maxRight)-height[i];
res+=h;
}
return res;
}
}
27. 移除元素
https://leetcode.cn/problems/remove-element/description/
class Solution {
public int removeElement(int[] nums, int val) {
//1.快慢指针
int slow=0;
for(int fast=0;fast<nums.length;fast++){
if(nums[fast]!=val){
nums[slow++]=nums[fast];
}
}
return slow;
//2.相向双指针
int leftIndex = 0;
int rightIndex = nums.length - 1;
while (leftIndex <= rightIndex) {
// 找左边等于val的元素
while (leftIndex <= rightIndex && nums[leftIndex] != val){
++leftIndex;
}
// 找右边不等于val的元素
while (leftIndex <= rightIndex && nums[rightIndex] == val) {
-- rightIndex;
}
// 将右边不等于val的元素覆盖左边等于val的元素
if (leftIndex < rightIndex) {
nums[leftIndex++] = nums[rightIndex--];
}
}
return leftIndex; // leftIndex一定指向了最终数组末尾的下一个元素
}
}
344. 反转字符串
https://leetcode.cn/problems/reverse-string/description/
class Solution {
public void reverseString(char[] s) {
int len=s.length;
int left=0;
int rigtht=len-1;
while(left<rigtht){
char t=s[left];
s[left++]=s[rigtht];
s[rigtht--]=t;
}
}
}
54. 替换数字（第八期模拟笔试）
https://kamacoder.com/problempage.php?pid=1064
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
sb.append("number");
}else sb.append(s.charAt(i));
}
System.out.println(sb);
}
}
151. 反转字符串中的单词
https://leetcode.cn/problems/reverse-words-in-a-string/description/
class Solution {
public String reverseWords(String s) {
//去掉字符串中的多余空格
StringBuilder sb=clearSpace(s);
//对整个字符串进行翻转
reverseAll(sb,0,sb.length()-1);
//对每个单词进行翻转
reverseStr(sb);
return sb.toString();
}
//去掉字符串中的多余空格
public StringBuilder clearSpace(String s){
int len=s.length();
int start=0;
int end=len-1;
while(s.charAt(start)==' ')start++;
while(s.charAt(end)==' ')end--;
StringBuilder sb=new StringBuilder();
while(start<=end){
char c=s.charAt(start);
if(c!=' ' || sb.charAt(sb.length()-1)!=' '){
sb.append(c);
}
start++;
}
return sb;
}
//对整个字符串进行翻转
public void reverseAll(StringBuilder sb,int start,int end){
while(start<end){
char temp=sb.charAt(start);
sb.setCharAt(start++,sb.charAt(end));
sb.setCharAt(end--,temp);
}
}
//对每个单词进行翻转
public void reverseStr(StringBuilder sb){
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseAll(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}
206. 反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur=head;
ListNode pre=null;
ListNode temp=null;
while(cur!=null){
temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
return pre;
}
}
19. 删除链表的倒数第 N 个结点.
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//2.双指针，快慢指针
//如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，
//fast和slow中间永远差n个节点，直到fast指向链表末尾。
//删掉slow所指向的节点就可以了。
ListNode preHead=new ListNode(0);
preHead.next=head;
ListNode slow=preHead;
ListNode fast=preHead;
while(n>0){
fast=fast.next;
n--;
}
fast=fast.next;
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return preHead.next;
//1.普通方法
ListNode cur=head;
int size=0;
while(cur!=null){
cur=cur.next;
size++;
}
if(n==size){
head=head.next;
return head;
}
cur=head;
for(int i=0;i<size-n-1;i++){
cur=cur.next;
}
if(cur.next!=null)
cur.next=cur.next.next;
return head;
}
}
面试题 02.07. 链表相交
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
交点不是数值相等，而是指针相等
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA=headA;
ListNode pB=headB;
int lenA=0;
int lenB=0;
while(pA!=null){
pA=pA.next;
lenA++;
}
while(pB!=null){
pB=pB.next;
lenB++;
}
pA=headA;
pB=headB;
if(lenA>lenB){
int gap=lenA-lenB;
while(gap>0){
pA=pA.next;
gap--;
}
while(pA!=null){
if(pA==pB){
return pA;
}
pA=pA.next;
pB=pB.next;
}
}else{
int gap=lenB-lenA;
while(gap>0){
pB=pB.next;
gap--;
}
while(pA!=null){
if(pA==pB){
return pA;
}
pA=pA.next;
pB=pB.next;
}
}
return null;
}
}
142. 环形链表 II
https://leetcode.cn/problems/linked-list-cycle-ii/
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(slow==fast){
ListNode index01=head;
ListNode index02=fast;
while(index01!=index02){
index01=index01.next;
index02=index02.next;
}
return index01;
}
}
return null;
}
}
文章评论