题目：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
//从右上角开始查找target元素 public boolean find(int [][]array, int target){ //首先判断数组不为空，否则直接返回false if(array!=null && array.length > 0 && array[0].length > 0){ int row = 0; //初始化行的值 int col = array[0].length - 1; //初始化列的值 //循环遍历判断，寻找target while(row <= array.length-1 && col >= 0){ if(target == array[row][col]){ return true; }else if(target < array[row][col]){ col--; }else{ row++; } } } return false; }
题目
一个链表中包含环，请找出该链表的环的入口结点
public ListNode EntryNodeOfLoop2(ListNode pHead){ ListNode fast = pHead; ListNode slow = pHead; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; //当快指针 与 慢指针相遇时 if(fast == slow){ fast = pHead; //再次相遇 while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; } } return null; }
题目
输入一个链表，反转链表后，输出新链表的表头。
public Node reverse(Node node) { Node prev = null; Node now = node; while (now != null) { Node next = now.next; now.next = prev; prev = now; now = next; } return prev; }
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
public int MoreThanHalfNum_Solution1(int [] array){ HashMap<Integer,Integer> map=new HashMap<>(); for(int i=0;i<array.length;i++){ if(!map.containsKey(array[i])){ map.put(array[i],1); }else{ int count=map.get(array[i]); map.put(array[i],++count); } int time=map.get(array[i]); if(time>array.length>>1) return array[i]; } return 0; } public int MoreThanHalfNum_Solution2(int [] array){ if(array.length<=0) return 0; int result=array[0]; int count=1; for(int i=1;i<array.length;i++){ if(array[i]==result){ count++; }else{ count--; } if(count==0){ result=array[i]; count=1; } } int time=0; for(int i=0;i<array.length;i++){ if(array[i]==result){ time++; } } if(time>array.length/2){ return result; }else{ return 0; } }
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
public int Add(int num1,int num2) { while (num2!=0) { int temp = num1^num2; num2 = (num1&num2)<<1; num1 = temp; } return num1; }
题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。
public String replaceSpace(StringBuffer str) { String str1=str.toString(); String str2=str1.replace(" ","%20"); return str2; } public String replaceSpace(StringBuffer str) { int spacenum = 0; for(int i=0;i<str.length();i++) { if(str.charAt(i)==' ') spacenum++; } int indexold = str.length()-1; int newlength = str.length()+spacenum*2; int indexnew = newlength-1; str.setLength(newlength); for(;indexold>=0 && indexold<newlength;indexold--) { if(str.charAt(indexold) == ' ') { str.setCharAt(indexnew--, '0'); str.setCharAt(indexnew--, '2'); str.setCharAt(indexnew--, '%'); } else { str.setCharAt(indexnew--, str.charAt(indexold)); } } return str.toString(); }
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
public static ArrayList<Integer> printListFromTailToHead_Stack(ListNode node) { if(node==null){ return null; } ArrayList<Integer> list=new ArrayList<Integer>(); Stack<Integer> s=new Stack<Integer>(); ListNode temp=node; while(temp!=null){ s.push(temp.val); temp=temp.next; } while(!s.empty()){ list.add(s.pop()); } return list; }
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); //入栈函数 public void push(int num) { stack1.push(num); //要往栈中压入什么就直接用栈的push方法就好了 } //出栈函数 public int pop() { Integer re=null; if(!stack2.empty()){ // 如果栈2不是空的，那么把最上面那个取出来 re=stack2.pop(); }else{ //如果栈2是空的，就把栈1里的数一个个取出来，放到栈2里 while(!stack1.empty()){ re=stack1.pop(); stack2.push(re); } //栈2里有数之后，再次把里面的数取出来 if(!stack2.empty()){ re=stack2.pop(); } } return re;
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/* 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 list0=null;//定义一个链表作为返回值 if(list1.val<list2.val){//判断此时的值，如果list1比较小，就先把list1赋值给list0，反之亦然 list0=list1; list0.next=Merge(list1.next, list2);//做递归，求链表的下一跳的值 }else{ list0=list2; list0.next=Merge(list1, list2.next); } return list0; } }
public ListNode Merge(ListNode list1,ListNode list2) { if(list1 == null) return list2; if(list2 == null ) return list1; ListNode tmp1 = list1; ListNode tmp2 = list2; ListNode head = new ListNode(0);//这里不能把返回链表赋值为null，因为下一行马上就要把它赋值给另一链表，得让它在内存里有位置才行 ListNode headptr = head; while(tmp1 != null && tmp2!=null){ if(tmp1.val <= tmp2.val) { head.next=tmp1; head = head.next; tmp1 = tmp1.next; }else{ head.next=tmp2; head = head.next; tmp2=tmp2.next; } } //其中一个链表已经跑到头之后，继续单链表的合并 while(tmp1 != null){ head.next = tmp1; head = head.next; tmp1= tmp1.next; } while(tmp2 != null){ head.next = tmp2; head = head.next; tmp2= tmp2.next; } head = headptr.next; return head; }
题目描述
输入一个链表，输出该链表中倒数第k个结点。
public ListNode FindKthToTail(ListNode head,int k) { if(head==null||k<=0){ return null; } ListNode last=head; for(int i=1;i<k;i++){ if(head.next!=null){ head=head.next; }else{ return null; } } while(head.next!=null){ head = head.next; last=last.next; } return last;
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public class Solution { public void reOrderArray(int [] array) { int length = array.length; int count = 0; if(length == 0){ return; } for(int i = 0; i < length; i++){ if(array[i] % 2 != 0){ count++; } } int[] temp = new int[length]; int a = 0; int b = count; for(int j= 0; j < length; j ++){ if(array[j] % 2 == 0){ temp[b++] = array[j]; }else{ temp[a++] = array[j]; } } for(int i = 0; i < length; i ++){ array[i] = temp[i]; } }
public void reOrderArray(int [] array) { int length = array.length; for(int i = 0; i < length; i ++){ for(int j = length - 1; j > 0; j --){ if(array[j] % 2 == 1 && array[j - 1] % 2 == 0){ int temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } }
题目：
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。例如：如果输入如下矩阵：
public ArrayList<Integer> printMatrixClockwisely(int [][]nums){ ArrayList<Integer> list = new ArrayList<Integer>(); int rows = nums.length; int cols = nums[0].length; if(nums == null || cols <= 0 || rows <= 0){ return null; } int start = 0; while(cols > start*2 && rows > start*2){ printMatrixInCircle(list, nums, cols, rows, start); ++start; } return list; }
private void printMatrixInCircle(ArrayList<Integer> list, int[][] nums, int cols, int rows, int start) { int endX = cols - 1 - start; int endY = rows - 1 - start; //从左到右打印一行 for (int i = start; i <= endX; ++i) { int number = nums[start][i]; list.add(number); } //从上到下打印一列 if(start < endY){ for (int i = start + 1; i <= endY; ++i) { int number = nums[i][endX]; list.add(number); } } //从右向左打印一行 if(start < endX && start < endY){ for (int i = endX-1; i >= start; --i) { int number = nums[endY][i]; list.add(number); } } //从下向上打印一列 if(start < endX && start < endY - 1){ for (int i = endY-1; i >= start + 1; --i) { int number = nums[i][start]; list.add(number); } } }
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1，10，11和12，1一共出现了5次。
public int count(int n){ if(n<1) return 0; int count = 0; int base = 1; int round = n; while(round>0){ int weight = round%10; round/=10; count += round*base; if(weight==1) count+=(n%base)+1; else if(weight>1) count+=base; base*=10; } return count; }
题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
import java.util.Stack; public class Solution { Stack<Integer> stack = new Stack<>(); Stack<Integer> minStack = new Stack<>(); public void push(int node) { stack.push(node); if (minStack.isEmpty()) { minStack.push(node); } else { minStack.push(Math.min(node, minStack.peek())); } } public void pop() { if (!stack.isEmpty()) { stack.pop(); minStack.pop(); } } public int top() { return stack.peek(); } public int min() { if (minStack.isEmpty()) return Integer.MIN_VALUE; return minStack.peek(); } }
题目：
给定一浮点数base和int类型的整数exponent。求base的exponent次方
public class Solution { public double Power(double base, int exponent) { // 当底数为0，指数为负数时，则抛出异常或者返回0.0 if (equal(base, 0) && exponent < 0) { return 0.0; } // 先对指数进行取绝对值计算 int absExponent = Math.abs(exponent); double result = powerWithExponent(base, absExponent); // 判断如果传入的指数是负数，进行取反，否则直接返回 if (exponent < 0) { result = 1.0 / result; } return result; } // 计算数值的整数次方 public double powerWithExponent(double base, int absExponent) { double result = 1.0; for (int i = 1; i <= absExponent; ++i) { result *= base; } return result; } // 判断两个double类型的数值是否相等 public boolean equal(double num1, double num2) { if ((num1 - num2 > -0.0000001) && (num1 - num2 < 0.0000001)) { return true; } else return false; } }
题目：
统计一个数字在排序数组中出现的次数，比如排序数组为{1,2,3,3,3,4,5}，那么数字3出现的次数就是3。
public int getFirstK(int[] data,int k,int start,int end){ while(start<=end){ int mid=start+((end-start)>>1); if(data[mid]==k){ if((mid>0 && data[mid-1]!=k) || mid==0) return mid; else end=mid-1; } else if(data[mid]>k) end=mid-1; else start=mid+1; } return -1; } public int getLastK(int[] data,int length,int k,int start,int end){ while(start<=end){ int mid=start+((end-start)>>1); if(data[mid]==k){ if((mid<length-1 && data[mid+1]!=k) || mid==length-1) return mid; else start=mid+1; } else if(data[mid]<k) start=mid+1; else end=mid-1; } return -1; } public int getNumberOfK(int[] data,int length,int k){ if(data==null || length<=0) return 0; int first=getFirstK(data,k,0,length-1); int last=getLastK(data,length,k,0,length-1); if(first!=-1 && last!=-1) return last-first+1; return 0; }
题目：第一个只出现一次的字符
public Character firstNotRepeating(String str){ if(str == null) return null; char[] strChar = str.toCharArray(); LinkedHashMap<Character,Integer> hash = new LinkedHashMap<Character,Integer>(); for(char item:strChar){ if(hash.containsKey(item)) hash.put(item, hash.get(item)+1); else hash.put(item, 1); } for(char key:hash.keySet()) { if(hash.get(key)== 1) return key; } return null;
题目：
我们把只包含因子2,3和5的数称为丑数（Ugly Number),求从小到大的顺序第n的丑数，例如6,8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当作第1个丑数
public int GetUglyNumber_Solution(int index) { if(index==0) return 0; int[] a = new int[index]; int count = 1; a[0] = 1; int index2 = 0; int index3 = 0; int index5 = 0; while(count<index){ int min = min(a[index2]*2,a[index3]*3,a[index5]*5); a[count] = min; while(a[index2]*2<=a[count]) index2++; while(a[index3]*3<=a[count]) index3++; while(a[index5]*5<=a[count]) index5++; count++; } int result = a[index-1]; return result; } public int min(int a,int b,int c){ int temp = a>b?b:a; return temp>c?c:temp; }
【题目描述】在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
public boolean duplicate(int numbers[],int length,int [] duplication) { boolean flag = false; if(numbers==null || length==0){ return flag; } HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int num: numbers){ if(map.containsKey(num)){ flag = true; duplication[0] = num; break; } map.put(num, 0); } return flag; }
public boolean duplicate(int numbers[],int length,int [] duplication) { boolean flag = false; if(numbers==null || length==0){ return flag; } for(int i=0; i<length; i++){ int index = numbers[i]; if (index < 0){ index += length; } if(numbers[index] < 0){ //因为index<0时，有一个还原+length的操作，所以返回的就是原来的重复的数字 duplication[0] = index; flag = true; break; } numbers[index] -= length; } return flag; }
题目：旋转数组的最小数字
import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { if(array == null || array.length == 0) { return 0; } int p1 = 0;//从前往后走 int p2 = array.length-1;//从后往前走 int min = array[p1];//如果没发生旋转，直接将array[0]的值返回， int mid = 0; //当数组发生旋转了， while(array[p1] >= array[p2]) { //当两个指针走到挨着的位置时，p2就是最小数了 if(p2 - p1 == 1) { min = array[p2]; break; } mid = (p1 + p2)/2; //如果中间位置的数既等于p1位置的数又等于P2位置的数 if(array[p1] == array[mid]&&array[p2]==array[mid]) { min = minInorder(array,p1,p2); } if(array[p1] <= array[mid])//若中间位置的数位于数组1，让p1走到mid的位置 { p1 = mid; } else if(array[p2] >= array[mid])//若中间位置的数位于数组2，让p2走到mid的位置 { p2 = mid; } } return min; } private int minInorder(int[]array,int p1,int p2) { int min = array[p1]; for (int i = p1 + 1; i <= p2; i++) { if(min > array[i]) { min = array[i]; } } return min; } }
获取Activity视图层级的最大深度
public static int getViewHierarchyMaxDeep(Activity activity) { View decorView = activity.getWindow().getDecorView(); int height = getDeep(decorView, 1); Log.e("TAG", activity.getClass().getSimpleName() + " height is:" + height); return height; } // curr为当前View的层级 private static int getDeep(View view, int curr) { if (view instanceof ViewGroup) { ViewGroup parent = (ViewGroup) view; int childCount = parent.getChildCount(); if (childCount > 0) { // 层级+1 int max = curr + 1; for (int i = 0; i < childCount; i++) { View child = parent.getChildAt(i); int height = getDeep(child, curr + 1); if (max < height) { max = height; } } return max; } else { return curr; } } else { return curr; } }
连续子数组的最大和
public static int FindGreatestSumOfSubArray(int[] array) { if (array.length==0 || array==null) { return 0; } int currentSum = 0; //存储当前连续n项的和 int max = 0; //存储连续子元素和的最大值 for (int i = 0; i < array.length; i++) { //核心部分，好好理解. if(currentSum<=0){ //如过当前连续n项的和小于等于0,则没必要与后面的元素相加 currentSum = array[i]; //currentSum重新赋值 }else{ currentSum += array[i]; //如果currentSum的值大于0,则继续与后面的元素相加, } if(currentSum>max){ //每次改变currentSum的值都有与max进行比较 max = currentSum; //如果currentSum的值大于max,则将currentSum的值赋值给max } } return max; }
孩子们的游戏（圆圈中最后剩下的数）
public class Solution { public int LastRemaining_Solution(int n, int m) { if(n<1||m<1) return -1; int[] array = new int[n]; int i = -1,step = 0, count = n; while(count>0){ i++; if(array[i%n] == -1) continue; step++; if(step==m) { array[i%n]=-1; step = 0; count--; } } return i%n; } }