剑指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; } }
