剑指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<n;i++) { while(nums[i]!=i&&nums[i]!=nums[nums[i]]) swap(nums,i,nums[i]); if(nums[i]!=i&&nums[i]==nums[nums[i]]) return nums[i]; } return -1; } }
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<matrix.length;i++) for (j=0;j<matrix[0].length;j++) if(matrix[i][j]==target) return true; return false; } }
- 线性查找
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<matrix[i][j]) j--; } return false; } }
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) break; //左 for(int i=right;i>=left;i--) res[num++]=matrix[down][i]; if(--down<up) break; //上 for(int i=down;i>=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<nums.length;i++) if(nums[i]==target) res++; return res; } }
- 二分查找法【有序数组优先考虑二分查找】
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个节点
| [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zjjaWHAc-1599804497564)(https://cdn.jsdelivr.net/gh/JackieLing/mage1/img/20200905211117.png)] |
/** * 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<aim){ current=current.next; ptr++; } return current; } }
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<Node,Node> 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<Integer> set=new HashSet<Integer>(); int repeat=0; for(int i=0;i<nums.length;i++){ if(!set.add(nums[i])){ repeat=nums[i]; break; } } return repeat; } }
13、最长不含重复字符的子字符串
 |
class Solution { public int lengthOfLongestSubstring(String s) { HashMap<Character,Integer> hash=new HashMap<>(); int res=0,left=0; for (int i=0;i<s.length();i++){ char c=s.charAt(i); //判断c是否出现过 //abcabcbb if (hash.containsKey(c)){ left=Math.max(left,hash.get(c)+1); } hash.put(c,i); res=Math.max(res,i-left+1); } return res; } }
14、第一个只出现一次的字符
 |
class Solution { public char firstUniqChar(String s) { HashMap<Character,Boolean> 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<Integer> stk1,stk2; Stack<Integer> stk1=new Stack<Integer>(); Stack<Integer> stk2=new Stack<Integer>(); int size; public CQueue() { //stk1=new Stack<Integer>(); //stk2=new Stack<Integer>(); 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(); */
