🎉🎉🎉写在前面:
博主主页:🌹🌹🌹戳一戳,欢迎大佬指点!
博主秋秋:QQ:1477649017 欢迎志同道合的朋友一起加油喔💪
目标梦想:进大厂,立志成为一个牛掰的Java程序猿,虽然现在还是一个小菜鸟嘿嘿
-----------------------------谢谢你这么帅气美丽还给我点赞!比个心-----------------------------
class CQueue {
LinkedList<Integer> stack1;
LinkedList<Integer> stack2;
public CQueue() {
//进行初始化
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void appendTail(int value) {
//也就是入队操作,固定一个放,一个用来转元素
stack1.push(value);
}
public int deleteHead() {
if(stack1.isEmpty() && stack2.isEmpty()){
return -1;//两个栈都是空
}
if(!stack2.isEmpty()){
//如果stack2不是空,那么队首元素就可以直接pop栈顶元素就好
return stack2.pop();
}else{
//如果是空,那就要从stack1中转元素
while(!stack1.isEmpty()){
//只要stack1不是空,那就把stack1的元素全部转到stack2里面去
int val = stack1.pop();//弹出栈顶元素
stack2.push(val);
}
//然后再次取出栈顶元素
return stack2.pop();
}
}
}
【解析:】
根据题目我们可以知道是要用栈来实现队列,但是栈和队列的特性是完全相反的,所以一个栈肯定是满足不了要求,那就只能用两个栈,一个用来存元素,一个用来协助取队首元素。
class MinStack {
//就是最小栈问题
/** initialize your data structure here. */
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();//保存最小值的栈
}
public void push(int x) {
//刚开始两个都是空那就一起放
if(stack.empty() && minStack.empty()){
stack.push(x);
minStack.push(x);
}else{
//如果不是,存放最小值的栈入栈是有要求的
stack.push(x);
if(x <= minStack.peek()){
//如果x比栈顶元素小或者相等那就入栈
minStack.push(x);
}
}
}
public void pop() {
//弹出元素,注意两个都要弹
if(!stack.empty()){
int val = stack.pop();
if(minStack.peek() == val){
//如果stack弹出的元素和我们的minStack中的栈顶元素一样的话,那么这边同样也要弹出栈顶元素
minStack.pop();
}
}
}
public int top() {
if(!stack.empty()){
return stack.peek();//查看一下stack的栈顶元素
}
return -1;//如果是空就返回-1
}
public int min() {
if(!minStack.empty()){
return minStack.peek();//最小栈的栈顶元素就是现在的最小值
}
return -1;
}
}
【解析:】
特别注意:为什么上面的条件中我们要取到小于等于,这个等于的含义是啥?
因为比如图示情况,存在两个-2,那么如果要出掉stack的栈顶元素,minStack的栈顶元素如果与stack1的栈顶元素相等的话,minStack那也是要随之出掉这个栈顶元素的,因为最小值会发生变化。但是这里是两个-2,你如果右边只放一个-2,那么左右两边同时出掉之后,左边还有一个-2,但是右边就没有-2了,这个时候的最小值关系就是错的。
class Solution {
public int[] reversePrint(ListNode head) {
//栈
// Stack stack = new Stack<>();
// ListNode cur = head;
// while(cur != null){
// stack.push(cur.val);
// cur = cur.next;
// }
// int[] arr = new int[stack.size()];
// int k = 0;
// while(!stack.empty()){
// arr[k] = stack.pop();
// k++;
// }
// return arr;
//反向填充数组
ListNode cur = head;
int len = 0;
while(cur != null){//求一下链表的长度
len++;
cur = cur.next;
}
int[] arr = new int[len];
//开始反向填充
while(head != null){
arr[--len] = head.val;
head = head.next;
}
return arr;
}
}
这个题的解法有很多,比如栈顺序压栈之后链表的元素值在栈顶从上往下就是一个倒置的,所以就只需要挨个出栈就行。也可以顺序遍历链表,但是在填充数组的时候,从后往前填充,那么最终也可以达到一个倒置的效果。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode curNext = cur.next;
cur.next = pre;
pre = cur;
cur = curNext;
}
return pre;
}
}
这个题是老朋友了,反转链表的思想在很多时候还是很有用的,大概的解法无非就是这种两个指针遍历链表,或者利用一个虚拟头也是可以的。
class Solution {
public Node copyRandomList(Node head) {
//利用Map
//先遍历一遍链表,把数值进行复制,并且存储对应关系
Node cur = head;
Map<Node,Node> map = new HashMap<>();//不要用TreeMap因为节点在放进去的
while(cur != null){
Node tmp = new Node(cur.val);
map.put(cur,tmp);
cur = cur.next;
}
//然后就可以对next,random进行连接了
cur = head;
while(cur != null){
(map.get(cur)).next = map.get(cur.next);
(map.get(cur)).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);//返回复制的链表的头节点
}
}
这个题要注意,题目所说的复制的过程其实是一个深拷贝的过程,因为你是要定义出新的节点,但是他们之间的连接关系要和以前一样。所以说到这种对应关系,那么自然就会想到Map。解法也即是用Map,两次遍历链表,第一次首先把数值进行拷贝,顺便把新节点与老节点之间的对应关系存储到Map里面,然后第二次遍历链表就是处理next以及random的问题。
class Solution {
public String replaceSpace(String s) {
//可以用StringBuilder 遇到空格就append("%20"),但是如果不利用额外空间呢就要用双指针
StringBuilder stringBuilder = new StringBuilder();
for(int i = 0;i < s.length();i++){
if(s.charAt(i) != ' '){
stringBuilder.append(s.charAt(i));//append()方法是有重载的
}else{
stringBuilder.append("%20");
}
}
return stringBuilder.toString();
}
}
class Solution {
public void reverseString(int s,int e,char[] arr){
int left = s;
int right = e;
while(left < right){
char tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
}
}
public String reverseLeftWords(String s, int n) {
// StringBuilder stringBuilder = new StringBuilder();
// String ret1 = s.substring(0,n%s.length());
// String ret2 = s.substring(n%s.length());
// stringBuilder.append(ret2);
// stringBuilder.append(ret1);
// return stringBuilder.toString();
//如果说不让用库方法,以及额外空间
//左旋问题 前半部分倒置 后半部分倒置 整个字符串倒置
char[] arr = new char[s.length()];
for(int i = 0;i < s.length();i++){
arr[i] = s.charAt(i);//拷贝到字符数组里面,因为字符串不可变
}
reverseString(0,n%s.length()-1,arr);
reverseString(n%s.length(),s.length()-1,arr);
reverseString(0,s.length()-1,arr);
String ret = new String(arr);
return ret;
}
}
class Solution {
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
int ret = 0;
for(int i = 0;i < nums.length;i++){
if(!set.contains(nums[i])){
set.add(nums[i]);
}else{
ret = nums[i];
}
}
return ret;
}
}
class Solution {
public int search(int[] nums, int target) {
//二分查找只能应用于有序的数组
//两次二分查找
int leftBoundary = 0;
int rightBoundary = 0;
int i = 0;
int j = nums.length - 1;
//1.寻找右边界
while(i <= j){
int mid = (i + j)/2;
if(nums[mid] > target){
j = mid - 1;
}else{
//即使相等,区间继续往右边压缩,寻找右边界
i = mid + 1;
}
}
//跳出循环的时候就说明找到了右边界
rightBoundary = i;
//2.寻找左边界
//优化:先判断一下到底存不存在target
if(j >= 0 && nums[j] != target){
return 0;
}
i = 0;
j = rightBoundary - 1;//寻找左边界就没有必要寻找整个数组了
while(i <= j){
int mid = (i + j)/2;
if(nums[mid] < target){
i = mid + 1;
}else{
j = mid - 1;
}
}
//跳出循环就是找到了左边界
leftBoundary = j;//也有可能直接是-1了,不过不影响后面计算结果还是0
//之间的差值就是出现的次数
return rightBoundary - leftBoundary - 1;
}
}
【解析:】
如图,这是寻找右边界的过程,那么其实寻找左边界的过程差不多,一直往左边压缩区间就好,最终找到的左边界是在下标为2的地方。所以最终8出现的次数就是rightBoundary - leftBoundary - 1。 其中有两个优化的点,就是在找到右边界之后可以先判断一下存不存在target,因为按理来说此时nums[j](j要大于等于0)就是等于target的,所以如果nums[j] != target就可以直接返回0了。另外如果存在target,在找左边界就可以直接从 [0,rightBoundary-1 ]之间找了。
class Solution {
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right)/2;
if(nums[mid] == mid){
left = mid + 1;
}else{
right = mid - 1;
}
}
return left;
}
}
【解析:】
这个题题目说的很绕,你把n-1看成一个整体,其实就是让你找到0到这个整体数值之间缺失的一个数字。
整体的思想其实还是二分查找,一般说数据有序,然后让你找某一个数值,基本都可以往二分查找上靠。这里只不过一个很重要的点就是下标与数值的对应关系,如果不存在缺失的话,那么下标和值一定是相等的。所以我们在二分查找的时候,去比较的就是nums[mid]与mid的大小关系,如果相等,那就说明mid之前是没有发生缺失数字的,所以就把区间往后面压缩,left = mid+1。如果不相等,就说明当前mid以后都是有问题的,所以mid的前面肯定是发生了缺失,则right = mid-1。最终整个循环结束的时候left的值就是我们缺失的元素。(其实也可以理解为一个找边界的过程,只不过找的是即将发生缺失的边界,也就是最终right的值就是最后一个正常的元素,它的下一个元素就不正常了)。
今天关于剑指Offer刷题的总结分享就到这了,后序会继续更新总结,一起加油刷题!最后如果觉得还总结的不错的话,还请帮忙点点赞呢!🥰🥰🥰