剑指offer
03 数组中重复的数字
public int findRepeatNumber(int[] nums){ //排序后的数组，重复元素必然相邻 Arrays.sort(nums); //结果集 int res=0; for(int i=0;i<nums.length-1;i ){ //找到重复元素 if(nums[i]==nums[i 1]){ res=nums[i 1]; break; } } return res;}一个萝卜一个坑
如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture
public int findRepeatNumber(int[] nums){ int temp; for(int i=0;i<nums.length;i ){ while(nums[i]!=i){ if(nums[i]==nums[nums[i]]) return nums[i]; temp=nums[i]; nums[i]=nums[temp]; nums[temp]=temp; } } return -1; }04 二维数组中的查找
右上角
public boolean findNumberIn2DArray(int[][] matrix, int target) { if(matrix==null||matrix.length==0||(matrix.length==1&&matrix[0].length==0)) return false; int xl = matrix.length; int yl = matrix[0].length; int i=0,j=yl-1; while(i<xl&&j>=0){ if(matrix[i][j]==target){ return true; }else if(matrix[i][j]<target){ i ; }else{ j--; } } return false; }05 替换空格
public String replaceSpace(String s) { StringBuilder res = new StringBuilder(); for(int i=0;i<s.length();i ){ if(s.charAt(i)==' '){ res.append(" "); }else{ res.append(s.charAt(i)); } } return res.toString();}06 从尾到头打印链表
public int[] reversePrint(ListNode head) { LinkedList<Integer> stack = new LinkedList<Integer>(); while(head!=null){ stack.addLast(head.val); head=head.next; } int[] res = new int[stack.size()]; for(int i=0;i<res.length;i ){ res[i]=stack.removeLast(); } return res;}07 重建二叉树
Map<Integer,Integer> hash = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { int np=preorder.length,n=inorder.length; for(int i=0;i<n;i ){ hash.put(inorder[i],i); } return dfs(preorder,inorder,0,np-1,0,n-1); } public TreeNode dfs(int[] pre,int[] in,int pl,int pr,int il,int ir){ if(pl>pr){return null;} TreeNode root = new TreeNode(pre[pl]); int k = hash.get(root.val)-il; //left 前序中的下标区间，中序中的下标区间 root.left=dfs(pre,in,pl 1,pl k,il,il k-1); //right root.right=dfs(pre,in,pl k 1,pr,il k 1,ir); return root; }09 用两个栈实现队列
class CQueue { Deque<Integer> stack1; Deque<Integer> stack2; public CQueue() { stack1=new LinkedList<Integer>(); stack2 = new LinkedList<Integer>(); } //添加元素 public void appendTail(int value) { stack1.push(value); } //删除头元素 public int deleteHead() { if(stack2.isEmpty()){ while(!stack1.isEmpty()) stack2.push(stack1.pop()); } if(stack2.isEmpty()){ return -1; }else{ return stack2.pop(); } }}10-1 斐波那契
public int fib(int n){ int a=0,b=1,sum; for(int i=0;i<n;i ){ sum=(a b)00000007; a=b; b=sum; } return a;}10-2 青蛙跳台阶
class Solution { public int numWays(int n) { int a=1,b=1,sum; for(int i=0;i<n;i ){ sum=(a b)00000007; a=b; b=sum; } return a; }}11 旋转数组的最小数字
class Solution { public int minArray(int[] numbers) { int l=0,r=numbers.length-1; while(l<r){ int m=(l r)/2; if(numbers[m]>numbers[r]) l=m 1; else if(numbers[m]<numbers[r]) r=m; else{ int x=l; for(int k=l 1;k<r;k ){ if(numbers[k]<numbers[x]) x=k; } return numbers[x]; } } return numbers[l]; }}12 矩阵中的路径
class Solution { public boolean exist(char[][] board, String word) { char[] words = word.toCharArray(); for(int i=0;i<board.length;i ){ for(int j=0;j<board[0].length;j ){ if(dfs(board,words,i,j,0)) return true; } } return false; } public boolean dfs(char[][] board,char[] words,int i,int j,int k){ //超出范围或者不相等 if(i<0||i>board.length-1||j<0||j>board[0].length-1||board[i][j]!=words[k]) return false; //base case k长度==word长度 if(k==words.length-1) return true; //做选择 board[i][j]='\0'; //递归 boolean res=dfs(board,words,i 1,j,k 1)||dfs(board,words,i-1,j,k 1) ||dfs(board,words,i,j 1,k 1)||dfs(board,words,i,j-1,k 1); //撤销选择 board[i][j]=words[k]; return res; }}13 机器人的运动范围
class Solution { int count; public int movingCount(int m, int n, int k) { int[][] visited=new int[m][n]; count=0; dfs(m,n,k,visited,0,0); return count; } public void dfs(int m,int n,int k,int[][] visited,int i,int j){ //1.索引越界2.大于数位之和3.走过 if(i>m-1||i<0||j>n-1||j<0||visited[i][j]==1||(k<sums(i) sums(j))) return; //当前已经走过 visited[i][j]=1; count ; //递归 int[] dx=new int[]{-1,0,1,0};int[] dy=new int[]{0,1,0,-1}; for(int s=0;s<4;s ){ dfs(m,n,k,visited,i dx[s],j dy[s]); } //不需要撤销选择 } //数位之和 int sums(int x){ int s=0; while(x!=0){ s =x; x=x/10; } return s; }} 赞 (0)