2020-8-26 剑指offer编程小哥令狐 075211

2020-8-26 剑指offer编程小哥令狐 075211

剑指offer~编程小哥令狐

一、数组类~

03、数组中重复的数字

class Solution { public void swap(int[] nums,int i,int j) { int temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } public int findRepeatNumber(int[] nums) { int n=nums.length; for(int num:nums) if(num<0||num>=n) return -1; for(int i=0;i

04、二维数组中的查找

暴力查找

class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { int i,j; if((matrix==null||matrix.length==0)||(matrix.length==1&&matrix[0].length==0)) return false; for (i=0;i

线性查找

class Solution { public boolean findNumberIn2DArray(int[][] matrix, int target) { if((matrix==null||matrix.length==0)||(matrix.length==1&&matrix[0].length==0)) return false; int i=0,j=matrix[0].length-1; while(i<=matrix.length-1&&j>=0){ if(target==matrix[i][j]) return true; if(target>matrix[i][j]) i++; else if(target

05、顺时针打印矩阵

class Solution { public int[] spiralOrder(int[][] matrix) { //判断边界 if(matrix.length==0) return new int[0];//因为返回值是数组，所以实例化一个数组进行返回 //右下左上 int left=0,right=matrix[0].length-1,up=0,down=matrix.length-1; int num=0; int []res=new int[(right+1)*(down+1)]; while(true){ //右 for(int i=left;i<=right;i++) res[num++]=matrix[up][i]; if(++up>down) break;///判断边界 //下 for(int i=up;i<=down;i++) res[num++]=matrix[i][right]; if(--right=left;i--) res[num++]=matrix[down][i]; if(--down=up;i--) res[num++]=matrix[i][left]; if(++left>right) break; } return res; }}

06、在排序数组中查找数字

暴力查找法

class Solution { public int search(int[] nums, int target) { int res=0; for(int i=0;i

二分查找法【有序数组优先考虑二分查找】

class Solution { public int search(int[] nums, int target) { int left = 0, right = nums.length; int ans = 0; while (left < right){ int mid = left + ((right - left)/2); if (nums[mid] >= target){ right = mid; } else { left = mid + 1; } } while (left < nums.length && nums[left++] == target){ ans++; } return ans; }}

07、剑指 Offer 53 - II. 0～n-1中缺失的数字

class Solution { public int missingNumber(int[] nums) { int left = 0, right = nums.length; while(left < right){ int mid = left + (right - left) / 2; if (nums[mid] == mid) { left = mid + 1; } else { right = mid; } } return left; }}

二、链表类~

06、从尾到头打印链表

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public int[] reversePrint(ListNode head) { ListNode temp=head; int size=0; while(temp!=null){ size++; temp=temp.next; } int[] res=new int[size]; temp=head; for(int i=size-1;i>=0;i--){ res[i]=temp.val; temp=temp.next; } return res; }}

07、删除链表节点

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode deleteNode(ListNode head, int val) { if(head.val==val) return head.next; ListNode pre=head; ListNode cur=head.next; while(cur.val!=val&&cur!=null){ pre=cur; cur=cur.next; } if(cur.val==val){ pre.next=cur.next; } return head; }}

08、删除倒数第k个节点

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode current=head; int n=0; while(current!=null){ n++; current=current.next; } if(k>n) return null; int aim=n-k+1; int ptr=1; current=head; while(ptr

09、反转链表

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode reverseList(ListNode head) { ListNode pre=null; ListNode cur=head; while (cur!=null){ ListNode temp=cur.next; cur.next=pre; pre=cur; cur=temp; } return pre; }}

10、复杂链表的复制

/*// Definition for a Node.class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }}*/class Solution { public Node copyRandomList(Node head) { Node cur=head; HashMap map=new HashMap<>(); while(cur!=null){ map.put(cur,new Node(cur.val)); cur=cur.next; } 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); }}

11、两个链表的第一个公共点

/** * 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 a=headA; ListNode b=headB; while(a!=b){ if(a==null) a=headB; else a=a.next; if(b==null) b=headA; else b=b.next; } return a; }}

三、哈希表~

12、数组中重复的数字

class Solution { public int findRepeatNumber(int[] nums) { Set set=new HashSet(); int repeat=0; for(int i=0;i

13、最长不含重复字符的子字符串

class Solution { public int lengthOfLongestSubstring(String s) { HashMap hash=new HashMap<>(); int res=0,left=0; for (int i=0;i

14、第一个只出现一次的字符

class Solution { public char firstUniqChar(String s) { HashMap hash=new HashMap<>(); char []ch=s.toCharArray(); for(char c:ch) hash.put(c,!hash.containsKey(c)); for(char c:ch) if(hash.get(c)) return c; return ' '; }}

四、栈~

15、用两个栈实现队列

import java.util.HashMap;import java.util.Stack;class CQueue { //栈 先进后出 //队列 先进先出 //Stack stk1,stk2; Stack stk1=new Stack(); Stack stk2=new Stack(); int size; public CQueue() { //stk1=new Stack(); //stk2=new Stack(); size=0; } public void appendTail(int value) { //插入一个元素 //stk1保存 底部存新插入的 顶部存老的 while(!stk1.isEmpty()) stk2.push(stk1.pop()); stk1.push(value); while (!stk2.isEmpty()) stk1.push(stk2.pop()); size++; } public int deleteHead() { //删除队列首部元素 //删除栈顶 if(size==0) return -1; int res=stk1.pop(); size--; return res; }}/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。