本文共 44661 字,大约阅读时间需要 148 分钟。
public class Solution { public boolean Find(int target, int [][] array) { int row = array.length; int col = array[0].length; // 从数组的左下角(或者右上角开始判断) int i = row-1, j = 0; while( i>=0 && j< col) { if( target == array[i][j]) { return true; } if( target > array[i][j] ){ j++; } else { i--; } } return false; }}
注解:解题的关键在于找到排好序的规则,左下角和右上角的位置数正好处于一个可以通过大小进行判断上下走向。
public class Solution { public String replaceSpace(StringBuffer str) { if(str.length() == 0 ) return ""; // 找出被替换字符的数目,java可以省略这一步。 int numOfEmpty = 0; for(int i =0; i
/*** public class ListNode {* int val;* ListNode next = null;** ListNode(int val) {* this.val = val;* }* }*/import java.util.Stack;import java.util.ArrayList;public class Solution { public ArrayListprintListFromTailToHead(ListNode listNode) { ArrayList arrayList= new ArrayList<>(); Stack stack = new Stack<>(); if(listNode == null) return arrayList; // 遍历链表存入stack中 while( listNode.next != null ) { stack.push(listNode.val); listNode = listNode.next; } stack.push(listNode.val); // 将stack中的数据放入ArrayList中 while( !stack.isEmpty() ) { arrayList.add(stack.pop()); } return arrayList; }}
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { TreeNode rootNode=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1); return rootNode; } private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) { if(startPre>endPre||startIn>endIn)return null; // 新建根节点 TreeNode rootNode=new TreeNode(pre[startPre]); for(int i=startIn;i<=endIn;i++){ // 找到中序中的根节点 if(in[i]==pre[startPre]){ rootNode.left=reConstructBinaryTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1); rootNode.right=reConstructBinaryTree(pre,i-startIn+startPre+1,endPre,in,i+1,endIn); } } return rootNode; }}
import java.util.Stack;public class Solution { Stackstack1 = new Stack (); Stack stack2 = new Stack (); // 在一个stack中进 public void push(int node) { stack1.push(node); } // 从stack2中出,若stack2为空,则从stack1中把数据输出到stack2中 public int pop() { if(stack2.isEmpty()) { while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } }
注解:先进后出两次为先进先出。
import java.util.ArrayList;public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length == 0) return 0; int left = 0; int right = array.length - 1; // 折半查找 while(left < right) { int mid = (left + right) / 2; // 统一与右边比 if(array[mid] > array[right]) { left = mid + 1; } else if(array[mid] < array[right]){ // 存在向下取整的情况 right = mid; } else { // 相等的情况 right--; } } return array[left]; }}
public class Solution { public int Fibonacci(int n) { if(n<=0) return 0; if(n<=2)return 1; int preNum =1; int pre2Num =1; int outNum = 0; for(int i = 3; i<=n; i++){ outNum = preNum + pre2Num; pre2Num = preNum; preNum = outNum; } return outNum; }}
public class Solution { public int JumpFloor(int target) { if(target<=0) return 0; if(target<=2) return target; int preNum =2; int pre2Num =1; int outNum = 0; for(int i = 3; i<=target; i++){ outNum = preNum + pre2Num; pre2Num = preNum; preNum = outNum; } return outNum; }}
public class Solution { public int JumpFloorII(int target) { if(target<=0) return 0; return 1<<(--target); }}
注解:f(n) = f(n-1)+f(n-2)…f(1)+1; 由于f(1)=1,递推可得:f(n)=2^(n-1);
public class Solution { public int RectCover(int target) { if(target<=0) return 0; if(target<=2) return target; int preNum =2; int pre2Num =1; int outNum = 0; for(int i = 3; i<=target; i++){ outNum = preNum + pre2Num; pre2Num = preNum; preNum = outNum; } return outNum; }}
注解:这题和青蛙跳没区别。
public class Solution { public int NumberOf1(int n) { int temp = 1; int count1 = 0; while(temp!=0) { if( (temp&n)!=0 ) count1++; // 移动1,避免出现负数移动补1的情况 temp = temp <<1; } return count1; }}
public class Solution { public double Power(double base, int exponent) { if(exponent==0) return 1; // 由于要考虑正负数,先统一绝对值计算 int absE = Math.abs(exponent); if(exponent<0) { return 1/subPower(base,absE); } else{ return subPower(base,absE); } } public double subPower(double base, int exponent) { if( exponent>1 ){ //折半乘,提高效率 if( exponent%2 != 0) { return base * subPower(base, exponent/2) * subPower(base, exponent/2); } else{ return subPower(base, exponent/2) * subPower(base, exponent/2); } } return base; }}
import java.util.LinkedList;import java.util.Queue;public class Solution { public void reOrderArray(int [] array) { Queuequeue1 = new LinkedList (); Queue queue2 = new LinkedList (); for(int i=0;i
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/// 双指针实现public class Solution { public ListNode FindKthToTail(ListNode head,int k) { if ( head == null || k <= 0) { return null; } ListNode fastHead = head; // 先走k-1步 for(int i=1; i< k; i++) { if(fastHead.next != null) { fastHead = fastHead.next; } else{ return null; } } // 以前走 while(fastHead.next != null){ head = head.next; fastHead = fastHead.next; } return head; }}
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode ReverseList(ListNode head) { if ( head == null ) { return null; } // 需要前一个,当前,后一个,三个节点处理转向. ListNode preNode = head; ListNode nextNode = null; //处理首节点 if(head.next != null){ head = head.next; preNode.next = null; } else{ return head; } // 递归处理 while(head.next != null) { nextNode = head.next; head.next = preNode; preNode = head; head = nextNode; } // 尾节点处理 head.next = preNode; return head; }}
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if(list1 ==null){ return list2; } if(list2 ==null){ return list1; } ListNode head = new ListNode(0); ListNode indexNode = head; while(list1 != null && list2 !=null){ if(list1.val <= list2.val){ indexNode.next = list1; list1 = list1.next; } else{ indexNode.next = list2; list2 = list2.next; } indexNode = indexNode.next; } if(list1 == null){ indexNode.next = list2; } else{ indexNode.next = list1; } return head.next; }}
/**public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; }}*/public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1 == null || root2 == null){ return false; } if( root1.val == root2.val ){ if(sameHasSubtree( root1.left, root2.left) && sameHasSubtree( root1.right, root2.right)){ return true; } } if( HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2)){ return true; } return false; } public boolean sameHasSubtree(TreeNode root1,TreeNode root2) { if(root2 == null){ return true; } if(root1 == null){ return false; } if( root1.val == root2.val){ if(sameHasSubtree( root1.left, root2.left) && sameHasSubtree( root1.right, root2.right)){ return true; } } return false; }}
public class Solution { public void Mirror(TreeNode root) { if(root == null){ return ; } if(root.left != null ){ Mirror(root.left); } if(root.right != null){ Mirror(root.right); } TreeNode temp = root.left; root.left = root.right; root.right = temp; }}
import java.util.ArrayList;public class Solution { public ArrayListprintMatrix(int [][] matrix) { if(matrix == null){ return null; } ArrayList outList = new ArrayList<>(); int row = matrix.length; int col = matrix[0].length; // 分四个方向讨论遍历,注意截止条件就好。 int left = 0,top = 0,bottom = row - 1,right = col - 1; while(left <= right && top <= bottom){ for(int i = left;i<=right;i++){ outList.add(matrix[top][i]); } for(int j = top+1;j<=bottom;j++){ outList.add(matrix[j][right]); } if (top != bottom){ for(int t = right-1;t>=left;t--){ outList.add(matrix[bottom][t]); } } if(left != right){ for(int k = bottom-1;k>top;k--){ outList.add(matrix[k][left]); } } top++;left++;right--;bottom--; } return outList; } }
import java.util.Stack;public class Solution { Stackstack = new Stack<>(); Stack minStack = new Stack<>(); public void push(int node) { stack.push(node); if( minStack.isEmpty() || node < minStack.peek()){ minStack.push(node); } else{ minStack.push(minStack.peek()); // 压自己 } } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peek(); } public int min() { return minStack.peek(); }}
import java.util.ArrayList;import java.util.Stack;public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { if(pushA.length != popA.length || pushA.length<=0 || popA.length<=0){ return false; } Stackstack = new Stack<>(); stack.push(pushA[0]); for (int i = 0,j = 0; i < popA.length; i++) { while (j < popA.length && stack.peek() != popA[i]) { stack.push(pushA[j++]); } if(stack.peek() != popA[i]){ return false; } stack.pop(); } return true; }}
import java.util.LinkedList;import java.util.Queue;public class Solution { public ArrayListPrintFromTopToBottom(TreeNode root) { Queue queue = new LinkedList (); ArrayList list = new ArrayList<>(); while(root != null){ list.add(root.val); if( root.left != null){ queue.add(root.left); } if( root.right != null){ queue.add(root.right); } root = queue.poll(); } return list; }}
public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length == 0) return false; return IsTreeBST(sequence, 0, sequence.length-1); } public boolean IsTreeBST(int [] sequence,int start,int end ){ if(end <= start) return true; for (int i = start; i < end; i++) { if(sequence[i] > sequence[end]) break; } // 验证后面的是否都大于根值 for (int j = i; j < end; j++) { if(sequence[j] < sequence[end]) return false; } return IsTreeBST(sequence, start, i-1) && IsTreeBST(sequence, i, end-1); } }
import java.util.ArrayList;public class Solution { public ArrayList> FindPath(TreeNode root,int target) { ArrayList a1=new ArrayList (); ArrayList > arr=new ArrayList >(); path( root, target, arr, a1); return arr; } public void path(TreeNode root, int target, ArrayList > arr, ArrayList a1 ){ if(root==null){ return ; } target -= root.val; a1.add(root.val); if(root.left!=null){ path( root.left, target, arr, a1); } if(root.right!=null){ path( root.right, target, arr, a1); } if(root.left==null && root.right==null && target==0){ arr.add(new ArrayList (a1)); } a1.remove(a1.size()-1); }}
注解:本题为保证数组长度大的在前也通过,若需要保证,只要加一级的排序就好。
public class Solution { public RandomListNode Clone(RandomListNode pHead){ if(pHead == null){ return null; } RandomListNode p=pHead; RandomListNode t=pHead; // next 赋值 while(p!=null){ RandomListNode q=new RandomListNode(p.label); q.next=p.next; p.next=q; p=q.next; } // random 赋值 while(t!=null){ RandomListNode q=t.next; if(t.random!=null) q.random=t.random.next; t=q.next; } // 拆分 RandomListNode s = new RandomListNode(0); RandomListNode s1 = s; while (pHead != null) { RandomListNode q = pHead.next; pHead.next = q.next; s.next = q; s = s.next; pHead = pHead.next; } return s1.next; }}
public class Solution { TreeNode head = null; TreeNode realHead = null; public TreeNode Convert(TreeNode pRootOfTree) { if (pRootOfTree == null) return null; Convert(pRootOfTree.left); if (realHead == null) { head = pRootOfTree; realHead = pRootOfTree; } else { head.right = pRootOfTree; pRootOfTree.left = head; head = pRootOfTree; } Convert(pRootOfTree.right); return realHead; }}
import java.util.ArrayList;import java.util.Collections;public class Solution { public ArrayListPermutation(String str) { ArrayList res=new ArrayList (); if(str.length()==0||str==null)return res; char[] chars = str.toCharArray(); Permutation(chars, 0, res); // 字典序排序 Collections.sort(res); return res; } public void Permutation(char[] chars, int begin, ArrayList result) { if(chars==null || chars.length==0 || begin<0 || begin>chars.length-1) { return ; } if(begin==chars.length-1){ result.add(new String(chars)); } // 最初自己的排序也是要算上的 for(int i=begin;i
注解:这种都是典型的回溯法(1,n-1)
import java.util.HashMap;public class Solution { public int MoreThanHalfNum_Solution(int [] array) { HashMapmap = new HashMap<>(); for(int i = 0; i array.length/2){ return key; } } return 0; }}
注解:由于不存在的可能性,故剑指offer中的技巧不能用。
import java.util.Collections;import java.util.ArrayList;public class Solution { public ArrayListGetLeastNumbers_Solution(int [] input, int k) { ArrayList res = new ArrayList (); if(input.length < 1 || k > input.length) return res; for(int i =0; i out = new ArrayList (); for(int i =0; i
注解:这题真扯淡
public class Solution { public int FindGreatestSumOfSubArray(int[] array) { if(array == null){ return 0; } int[] arr2 = new int[array.length]; arr2[0] = array[0]; for(int i=1; i< array.length; i++){ // 核心思想 if(arr2[i-1] < 0){ arr2[i] = array[i]; } else{ arr2[i] = arr2[i-1] + array[i]; } } int max = arr2[0]; for(int i=1; i< array.length; i++){ if(arr2[i]>max){ max = arr2[i]; } } return max; }}
public class Solution { public int NumberOf1Between1AndN_Solution(int n) { int base = 1; int count =0; int round = n; int weight = 0; while(round>0){ weight = round%10; round = round /10; // 按位计算1的数目 count += round * base; if(weight==1){ count += (n % base) + 1; } else if (weight>1) { count += base; } base *= 10; } return count; }}
import java.util.ArrayList;import java.util.Arrays;import java.util.Comparator;public class Solution { public String PrintMinNumber(int [] numbers) { if(numbers == null || numbers.length == 0) return ""; int len = numbers.length; String[] str = new String[len]; StringBuilder sb = new StringBuilder(); // 数字可能越界,转字符串计算 for(int i = 0; i < len; i++){ str[i] = String.valueOf(numbers[i]); } Arrays.sort(str,new Comparator(){ @Override public int compare(String s1, String s2) { String c1 = s1 + s2; String c2 = s2 + s1; return c1.compareTo(c2); } }); for(int i = 0; i < len; i++){ sb.append(str[i]); } return sb.toString(); }}
public class Solution { public int GetUglyNumber_Solution(int index) { if( index<=1 ) return index; int[] list = new int[index]; list[0] = 1; int temp2=0,temp3=0,temp5=0; int count = 0; while( count
注解:空间换时间算法
import java.util.LinkedHashMap;public class Solution { public static int FirstNotRepeatingChar(String str) { LinkedHashMapmap = new LinkedHashMap (); for(int i=0;i
注解:借助hashmap
public class Solution { public static int InversePairs(int [] array) { if(array==null||array.length==0){ return 0; } int[] copy = new int[array.length]; int count = InversePairsCore( array, copy, 0, array.length-1);//数值过大求余 return count; } private static int InversePairsCore( int[] array, int[] copy, int low, int high) { if(low==high){ return 0; } int mid = (low+high)>>1; int leftCount = InversePairsCore( array, copy, low, mid); int rightCount = InversePairsCore( array, copy, mid+1, high); int count = 0; int i=mid; int j=high; int locCopy = high; // 归并排序,保证有序 while(i>=low&&j>mid){ if(array[i]>array[j]){ count += j-mid; // 核心计算逆序对代码 copy[locCopy--] = array[i--]; if(count>=1000000007){ count%=1000000007; } } else{ copy[locCopy--] = array[j--]; } } for(;i>=low;i--) { copy[locCopy--]=array[i]; } for(;j>mid;j--) { copy[locCopy--]=array[j]; } // 复制回去,保证有序 for(int s=low;s<=high;s++) { array[s] = copy[s]; } return (leftCount+rightCount+count)%1000000007; }}
注解:这一题肯定可以简化,懒得改了
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { if(pHead1==null||pHead2==null){ return null; } if(pHead1==pHead2){ return pHead1; } int len1=0; int len2=0; ListNode curr1=pHead1; ListNode curr2=pHead2; while(curr1!=null){ len1++; curr1=curr1.next; } while(curr2!=null){ len2++; curr2=curr2.next; } curr1=pHead1; curr2=pHead2; if(len1>len2){ int moreLen=len1-len2; while(moreLen!=0){ curr1=curr1.next; moreLen--; } } else{ int moreLen=len2-len1; while(moreLen!=0){ curr2=curr2.next; moreLen--; } } while(curr1!=curr2&&curr1!=null){ curr1=curr1.next; curr2=curr2.next; } return curr1; }}
public class Solution { public int GetNumberOfK(int [] array , int k) { if(array.length<1) return 0; int begin =0; int end = array.length-1; return GetNumberOfK(array , k, begin, end); } public int GetNumberOfK(int[] array,int k, int begin, int end){ if(begin>end) return 0; int mid=(end-begin)/2+begin; if(k>array[mid]) return GetNumberOfK(array,k,mid+1,end); else if(k
注解:折半查找提高效率
public class Solution { public int TreeDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1; }}
public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if (root == null) { return true; } int left = getTreeDepth(root.left); int right = getTreeDepth(root.right); int diff = Math.abs(left - right); if (diff > 1) return false; return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); } public int getTreeDepth(TreeNode root) { if (root == null) return 0; else return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1; }}
//num1,num2分别为长度为1的数组。传出参数//将num1[0],num2[0]设置为返回结果public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { if (array == null) return ; int binaryVal = array[0]; for(int i=1; i< array.length; i++){ binaryVal ^= array[i]; } // 找到第一个bit不为1的数 int binary1 = 1; while((binary1&binaryVal)==0){ binary1 = binary1<<1; } boolean flag1 = true; boolean flag2 = true; for(int i=0; i< array.length; i++){ if( (binary1 & array[i]) !=0 && flag1){ num1[0] = array[i]; flag1 = false; } else if( (binary1 & array[i]) !=0){ num1[0] = num1[0] ^array[i]; } else if(flag2){ num2[0] = array[i]; flag2 = false; } else{ num2[0] = num2[0] ^array[i]; } } }}
import java.util.ArrayList;public class Solution { public ArrayList> FindContinuousSequence(int sum) { ArrayList > list = new ArrayList > (); if(sum<=1)return list; // 这里是一个优化,前提单个数为100不行 for(int i=1;i<=sum/2;i++){ ArrayList List2=new ArrayList (); int count=0; for(int j=i;j sum) break; else if(count==sum){ list.add(List2); break; } } } return list; }}
import java.util.ArrayList;public class Solution { public ArrayListFindNumbersWithSum(int [] array,int sum) { ArrayList list = new ArrayList<>(); if(array.length<2) return list; int begin = 0; int end = array.length - 1; while(begin sum){ end--; } else{ list.add(array[begin]); list.add(array[end]); break; } } return list; }}
public class Solution { public String LeftRotateString(String str,int n) { if(str.length()<0 || n<0 || n>str.length()) return str; char[] chars = str.toCharArray(); for(int i = 0; i
注解:不借助辅助空间的算法,需要两次翻转。为了避免混乱,也可以使用前后两指针交换的算法。
public class Solution { public String ReverseSentence(String str) { if(str.length()<1 ) return str; char[] chars = str.toCharArray(); // 先翻转 for(int i = 0; i
注解:上一题的一般化
import java.util.Arrays;public class Solution { public boolean isContinuous(int [] numbers) { if(numbers.length <1) return false; Arrays.sort(numbers); //先排序 int zero = 0, i = 0; for(; i < numbers.length && numbers[i] == 0; i++){ zero ++; //统计0的个数 } for(i = zero; i < numbers.length - 1; i++){ if(numbers[i] == numbers[i+1]) //有对子,则返回false return false; } if( (numbers[numbers.length -1] - numbers[zero]+1) <=5 ) return true; else return false; }}
public class Solution { public int LastRemaining_Solution(int n, int m) { if(n==0||m==0)return -1; int s=0; for(int i=2;i<=n;i++) { s=(s+m)%i; } return s ; }}
注解:每一次都看成一个新的排序f[i-1],但是下标是从k=m%n开始的。所以上一次的结果f[i]等于(f[i-1]+k)%n。于是有:
public class Solution {
public int Sum_Solution(int n) { int sum = n; boolean flag = (n>0)&&((sum +=Sum_Solution(n-1))>0); return sum; } } 注解:利用了逻辑&&的截断功能。public class Solution {
public int Add(int num1, int num2) { int num3; int num4; do { num3 = num1 ^ num2; num4 = (num1 & num2) << 1; num1 = num3; num2 = num4; } while (num4 != 0); return num1; } } 注解:通过位运算public class Solution { public int StrToInt(String str) { if ( str.length() < 1) return 0; char[] a = str.toCharArray(); boolean fuhao = true; int begin = 0; if (a[0] == '-'){ fuhao = false; begin = 1; } else if(a[0] == '+'){ begin = 1; } int sum = 0; for (int i = begin; i < a.length; i++){ if (a[i] < 48 || a[i] > 57) return 0; sum = sum * 10 + a[i] - 48; } return fuhao ? sum : sum * -1; }}
注解:主要符号的判断。字符0的ASCII码是48
public boolean duplicate(int numbers[],int length,int [] duplication) { if(length <1 ) return false; for(int i=0;i
注解:利用数组值与下标的关系
import java.util.ArrayList;public class Solution { public int[] multiply(int[] A) { if(A.length<1) return A; int[] B = new int[A.length]; B[0] = 1; for(int i=1; i< A.length; i++){ B[i] = B[i-1] * A[i-1]; } int temp = 1; for(int i=A.length-2; i>=0; i--){ temp *= A[i+1]; B[i] = B[i] * temp; } return B; }}
注解:利用前后两次乘,逃离中间乘。
public class Solution { public boolean match(char[] str, char[] pattern) { return matchTwo(str, 0, str.length, pattern, 0, pattern.length); } private boolean matchTwo(char[] str, int i, int length1, char[] pattern, int j, int length2) { if (i == length1 && j == length2) { return true; } if (i == length1 && j != length2) { while (j != length2) { if (pattern[j] != '*' && (j + 1 >= length2 || pattern[j + 1] != '*')) { return false; } j++; } return true; } if (i != length1 && j == length2) { return false; } if (j + 1 == length2) { if (str[i] == pattern[j] || pattern[j] == '.') return matchTwo(str, i + 1, length1, pattern, j + 1, length2); else { return false; } } if ((str[i] == pattern[j] || pattern[j] == '.') && pattern[j + 1] != '*') return matchTwo(str, i + 1, length1, pattern, j + 1, length2); if ((str[i] == pattern[j] || pattern[j] == '.') && pattern[j + 1] == '*') return matchTwo(str, i, length1, pattern, j + 2, length2) || matchTwo(str, i + 1, length1, pattern, j, length2); if (pattern[j + 1] == '*') return matchTwo(str, i, length1, pattern, j + 2, length2); return false; }}
注解:不是我说,让你写一个这种函数还真不好写!!!!
public class Solution { public boolean isNumeric(char[] str) { String s=String.valueOf(str); return s.matches("[+-]?[0-9]*(\\.[0-9]*)?([eE][+-]?[0-9]+)?"); }}
import java.util.HashMap;import java.util.ArrayList;public class Solution { HashMapmap=new HashMap<>(); ArrayList list=new ArrayList (); public void Insert(char ch) { if(map.containsKey(ch)){ map.put(ch,map.get(ch)+1); }else{ map.put(ch,1); } list.add(ch); } public char FirstAppearingOnce() { char c='#'; for(char key : list){ if(map.get(key)==1){ c=key; break; } } return c; }}
public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead){ if (pHead == null || pHead.next == null || pHead.next.next == null) return null; ListNode slow = pHead.next; ListNode quick = pHead.next.next; // 1 找到是否有环,两个指针 while (slow != quick) { if (slow.next != null && quick.next.next != null) { slow = slow.next; quick = quick.next.next; } else{ return null; } } // 2 确定环的大小k 但是其大小正好是 slow走的距离。 // 3 先走k步,相遇点为入口。 quick = pHead; while (quick != slow) { quick = quick.next; slow = slow.next; } return slow; }}
public class Solution { public ListNode deleteDuplication(ListNode pHead) { ListNode result; ListNode temp = pHead; ListNode index = new ListNode(1); index.next = pHead; result = index; while (temp != null) { if (temp.next != null && temp.next.val == temp.val) { while (temp.next != null && temp.next.val == temp.val) { temp = temp.next; } temp = temp.next; index.next = temp; } else { index = index.next; temp = temp.next; } } return result.next; }}
public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode==null) return null; // 右节点不为空 if(pNode.right!=null) { // 找到右节点的最左节点 pNode=pNode.right; while(pNode.left!=null) { pNode=pNode.left; } return pNode; } // 右节点为空,找到其为父节点的左节点的那个最近的父节点。 while(pNode.next!=null) { if(pNode.next.left==pNode) return pNode.next; pNode=pNode.next; } return null; } }
public class Solution { public boolean isSymmetrical(TreeNode pRoot) { if(pRoot==null) return true; return isSymmetrical(pRoot.left,pRoot.right); } public boolean isSymmetrical(TreeNode left, TreeNode right) { if (left == null && right == null) return true; if (left == null || right == null) return false; if (left.val == right.val) // 左左相比,右右相比,这是最核心的思想了。 return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left); return false; }}
import java.util.ArrayList;import java.util.Queue;import java.util.LinkedList;public class Solution { public ArrayList> Print(TreeNode pRoot) { ArrayList > res=new ArrayList >(); if(pRoot==null){ return res; } ArrayList list; Queue queue=new LinkedList (); int rows=1; queue.add(pRoot); while(!queue.isEmpty()){ list=new ArrayList<>(); int size=queue.size(); for(int i=0;i
public class Solution { ArrayList> Print(TreeNode pRoot) { ArrayList > result = new ArrayList<>(); if(pRoot == null) { return result; } ArrayList nodes = new ArrayList<>(); nodes.add(pRoot); Print(result, nodes); return result; } public void Print(ArrayList > result, ArrayList nodes) { if(!nodes.isEmpty()) { ArrayList temp = new ArrayList<>(); ArrayList next = new ArrayList<>(); for(TreeNode t : nodes) { temp.add(t.val); if(t.left != null) { next.add(t.left); } if(t.right != null) { next.add(t.right); } } result.add(temp); Print(result, next); } }}
注解:借助队列会更好做吧
public class Solution { int index = 0; TreeNode KthNode(TreeNode root, int k) { if (root != null) { // 中序遍历寻找第k个 TreeNode node = KthNode(root.left, k); if (node != null) return node; index++; if (index == k) return root; node = KthNode(root.right, k); if (node != null) return node; } return null; }}
import java.util.ArrayList;import java.util.Collections;public class Solution { ArrayListal = new ArrayList (); public void Insert(Integer num) { al.add(num); Collections.sort(al); } public Double GetMedian() { int mid = al.size() / 2; if ((al.size() & 1) == 0) { Integer n1 = al.get(mid); Integer n2 = al.get(mid - 1); double s = (Double.valueOf(n1 + "") + Double.valueOf(n2 + "")) / 2; return s; } else { double s = Double.valueOf(al.get(mid) + ""); return s; } }}
public class Solution { // 65 public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { int []flag=new int[matrix.length]; // 可选开始值 for(int i=0;i=rows||j<0||j>=cols||flag[index]==1||matrix[index]!=str[k])return false; if(k==str.length-1) return true; flag[index]=1; // 核心遍历 if(hasPath(matrix,rows,cols,i+1,j,k+1,str,flag)||hasPath(matrix,rows,cols,i-1,j,k+1,str,flag)||hasPath(matrix,rows,cols,i,j+1,k+1,str,flag)||hasPath(matrix,rows,cols,i,j-1,k+1,str,flag)) return true; flag[index]=0; return false; }}
public class Solution { public int movingCount(int threshold, int rows, int cols) { boolean[] visited=new boolean[rows*cols]; // 与上一题相比,课题初始值只有一个 return movingCountCore(threshold, rows, cols, 0,0,visited); } private int movingCountCore(int threshold, int rows, int cols, int row,int col,boolean[] visited) { if(row<0||row>=rows||col<0||col>=cols) return 0; int i=row*cols+col; if(visited[i]||!checkSum(threshold,row,col)) return 0; visited[i]=true; // 这里保持统一,而在返回推荐控制越界。 return 1+movingCountCore(threshold, rows, cols,row,col+1,visited) +movingCountCore(threshold, rows, cols,row,col-1,visited) +movingCountCore(threshold, rows, cols,row+1,col,visited) +movingCountCore(threshold, rows, cols,row-1,col,visited); } //指定规则 private boolean checkSum(int threshold, int row, int col) { int sum=0; while(row!=0){ sum+=row%10; row=row/10; } while(col!=0){ sum+=col%10; col=col/10; } if(sum>threshold) return false; return true; }}
作者:小张同学_loveZY
链接:https://www.jianshu.com/p/62cf4055617d 来源:简书 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。