剑指offer(一)——java
2017-04-28 本文已影响0人
秋风落叶黄
1.题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
//建议画个图理解下
public class Solution {
public boolean Find(int target, int [][] array) {
if(array==null || array.length == 0){
return false;
}
int row = 0;
int col = array[0].length-1; //数组最后一列的下标
while(row <=array.length-1 && col >=0){
if(array[row][col] > target){//当该列最小的一个值都大于target
col --; //向左移一列
}else if(array[row][col] < target){//当该最小的一个小于target
row ++; //向下移一行
}else{ //如果该值等于target,返回true
return true;
}
}
return false;
}
}
2.题目描述:请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy
public class Solution {
public String replaceSpace(StringBuffer str) {
if(str == null || str.length() <= 0){
return "";
}
int spaceCount = 0;
for(int i=0; i<str.length(); i++){//计算空格个数
if(str.charAt(i)==' '){
spaceCount++;
}
}
//设置初始下标
int index = str.length()-1;
int length = str.length()+spaceCount * 2;//设置新的StringBuilder大小
//新StringBuilder最后一个字符下标
int newIndex = length - 1;
str.setLength(length);
while(index >=0){
//当前下标的字符
char c = str.charAt(index);
if(c != ' '){
str.setCharAt(newIndex--, c);
}else{
str.setCharAt(newIndex--,'0');
str.setCharAt(newIndex--,'2');
str.setCharAt(newIndex--,'%');
}
index --;
}
return str.toString();
}
}
3.题目描述:输入一个链表，从尾到头打印链表每个节点的值
import java.util.ArrayList;
public class Solution {
private ArrayList<Integer> list = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode != null){
printListFromTailToHead(listNode.next);//递归
list.add(listNode.val);
}
return list;
}
}
4.题目描述:输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
import java.util.*;
public class Solution {
private Map<Integer,Integer> map = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
for(int i=0; i<pre.length; i++){
map.put(in[i],i);//存放中序中值对应的下标
}
return rebuild(pre,0, pre.length-1, 0, pre.length-1);
}
public TreeNode rebuild(int[] pre, int pi, int pj, int ni, int nj){
if(pi>pj)
return null;
int index = map.get(pre[pi]);//前序该值该中序中的位置
TreeNode root = new TreeNode(pre[pi]);//创建根节点
root.left = rebuild(pre, pi+1, pi+ index-ni, ni, index-1);//建立根节点的左子树
root.right = rebuild(pre,pi+index-ni+1,pj, index+1, nj);//建立根节点右子树
return root;//返回根节点
}
}
5.题目描述:用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
import java.util.Stack;
import java.util.*;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();//保存插入
Stack<Integer> stack2 = new Stack<Integer>();//处理删除
public void push(int node) {
stack1.push(node);
}
//如果stack2不为空，直接从stack2删除
//如果stack2为空，将stack1的内容，删除放入stack2中
public int pop() {
if(stack2.size() == 0 && stack1.size() == 0){
throw new EmptyStackException();
}
if(stack2.size() == 0){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
6. 题目描述:把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
import java.util.ArrayList;
public class Solution_1 {
public static void main(String[] args) {
int[] array = {4,1,1, 2, 3};
int i = minNumberInRotateArray(array);
System.out.println(i);
}
//本题考查二分查找
public static int minNumberInRotateArray(int [] array) {
if(array == null || array.length == 0){
return 0;
}
if(array.length == 1){
return array[0];
}
int index1 = 0;
int index2 = array.length-1;
int mid = index1;
while(array[index1] >= array[index2]){
mid = (index2-index1) / 2;
if(index2-index1 == 1){ //当两个相邻时
mid = index2;
break;
}
if(array[index1] <= array[mid] && array[mid] > array[index2]){// 3 3 3 0 2情况
index1 = mid;
}else if(array[index2] >= array[mid] && array[index1] > array[mid]){// 3 0 0 0 2情况
index2 = mid;
}else{// 3 3 3 0 3, 3 0 0 0 3两种情况无法判断哪个属于旋转部分
mid = getMin(array,index1, index2);//采用顺序查找
break;
}
}
return array[mid];
}
public static int getMin(int[] array, int index1, int index2){
int min = index1;
for(int i=index1+1; i<= index2; i++){
if(array[min] > array[i]){
min = i;
}
}
return min;
}
}
7.题目描述:大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
public class Solution {
public int Fibonacci(int n) {
if(n < 2){
return n;
}
int f1 = 0;
int f2 = 1;
int f = f2;
for(int i=2; i<= n; i++){
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f2;
}
}
8.题目描述:一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
public class Solution {
public int JumpFloor(int target) {
if(target <= 2){
return target;
}
int f1 = 1;
int f2 = 2;
int f = f2;
for(int i=3; i<=target; i++){
f = f1 +f2;
f1 = f2;
f2 = f;
}
return f2;
}
}
9.题目描述:一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
import java.util.*;
public class Solution {
public int JumpFloorII(int target) {
//f(n) = f(n-1) + f(n-2) + ... + f(1); f(n) = 2 * f(n-1);
//f(1) = 1 f(2) = 2 , f(n-1) = 2 xy(n-1)
return (int)Math.pow(2,target-1);
}
}
10.题目描述我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
public class Solution {
public int RectCover(int target) {
if(target <=2){
return target;
}
int f1 = 1;
int f2 = 2;
int sum = 0;
for(int i=3; i<= target; i++){
sum = f1 + f2;
f1 = f2;
f2 = sum;
}
return sum;
}
}
11.题目描述:输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
## 位运算 ##
/**负数是用补码表示的，补码求法位原码取反加一(原码是数的绝对值的二进制)
补码转换成原码为：取反加一(符号位不变)
例如: -16 二进制8位的 (原码)0001 0000 反码:1110 1111 补码:1111 0000
然后-16 / 2 = -8 相当于补码右移一位: 1111 1000 反码:1000 0111 原码: 1000 1000 = -8
移位运算:右移时，如果是负数，左边补1
*/
public class Solution {
public int NumberOf1(int n) {
//思路: 一个数减去1，然后与上这个数，这样这个数从右到左的第一个1变为0
int count = 0;
while(n != 0){
++ count;
n = (n-1) & n;
}
return count;
}
}
12.题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
public class Solution {
public double Power(double base, int exponent) {
if(equal(base,0.0)){
throw new IllegalArgumentException("底数不能为0");
}
int absExponent = exponent;
if(exponent < 0){//将指数先转换成正的
absExponent = -exponent;
}
double result = PowerWithUnsignedExponent(base, absExponent);
if(exponent < 0){//如果指数为负
result = 1.0 / result;
}
return result;
}
//非递归下的求法
public static double PowerWithUnsignedExponent(double base, int exponent){
double result = 1;
double temp = base;
while(exponent != 0){
if((exponent & 0x1) == 1){
result =result * temp;
}
exponent >>= 1;
temp *= temp;
}
return result;
}
public boolean equal(double num1, double num2){
if(num1-num2 > -0.0000001 && num1-num2 < 0.0000001){
return true;
}else{
return false;
}
}
}
13题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public class Solution {
public void reOrderArray(int [] array) {
if(array == null || array.length == 0){
return ;
}
int begin = 0;
int end = begin+1;
while(end < array.length){
while(begin < array.length-1 && (array[begin] & 0x1) != 0){//找到偶数
begin ++;
}
end = begin +1;
while(end <= array.length-1 && (array[end] & 0x1) == 0){//找到奇数
end ++;
}
if(end == array.length)
break;
int temp = array[end];
for(int i=end; i > begin; i--){//偶数后移
array[i] = array[i-1];
}
array[begin] = temp;
begin ++;
}
}
}
14.题目描述：输入一个链表，输出该链表中倒数第k个结点
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
ListNode pHead = head;
ListNode pBehind = null;
for(int i=0; i<k-1; i++){//先走k-1个节点
if(pHead.next != null){
pHead = pHead.next;
}else{
return null;
}
}
pBehind = head;
while(pHead.next != null){
pHead = pHead.next;
pBehind = pBehind.next;
}
return pBehind;
}
}
15.题目描述:输入一个链表，反转链表后，输出链表的所有元素
/*
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 = null;
ListNode nextNode = null;
while(head != null){
nextNode = head.next;
head.next = preNode;
preNode = head;
head = nextNode;
}
return preNode;
}
}
16.题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
else if(list2 == null)
return list1;
ListNode head = null;
//递归思想实现
if(list1.val < list2.val){
head = list1;
head.next = Merge(list1.next, list2);
}else{
head = list2;
head.next = Merge(list1, list2.next);
}
return head;
}
}
17.题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
//使用先序遍历找到root1 == root2
//当root1 = root2时，采用先序遍历判断两个子树是否相同
boolean isChild = false;
if(root1 == null || root2 == null){
return false;
}
if(root1.val == root2.val){
isChild = isTheSame(root1, root2);
}
if(!isChild){
isChild = HasSubtree(root1.left,root2);
}
if(!isChild){
isChild = HasSubtree(root1.right,root2);
}
return isChild;
}
public boolean isTheSame(TreeNode root1, TreeNode root2){
if(root2 == null) //递归结束条件
return true;
if(root1 == null)
return false;
if(root1.val != root2.val)
return false;
return isTheSame(root1.left,root2.left) && isTheSame(root1.right,root2.right);
}
}
18.题目描述:操作给定的二叉树，将其变换为源二叉树的镜像。
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){//递归退出条件
return;
}
if(root.left == null && root.right == null)//递归退出条件
return;
//交换左右子树
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
if(root.left != null){
Mirror(root.left);
}
if(root.right != null){
Mirror(root.right);
}
}
}
19.题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
//这题没有按照剑指Offer来
// 1 2 3 4
// 5 6 7 8
// 9 10 11 12
// 13 14 15 16
// 每先从上右下左各取3个数，刚好取完外圈
//当到达最后一圈时可能有如下几种情况:
// a b c 剩下一个长大于宽的矩形
//-----------------------------------
// a 剩下一个宽大于长的矩形
// b
// c
// ---------------------------------
// a 剩下一个值
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if(matrix == null || (matrix.length <=0 && matrix[0].length == 0))
return list;
int columns = matrix[0].length;
int rows = matrix.length;
int rowStart = 0; //第一行
int rowEnd = rows-1; //最后一行
int colStart = 0; //第一列
int colEnd = columns - 1; //最后一列
while(rowStart <= rowEnd && colStart <= colEnd){
if(rowStart < rowEnd && colStart < colEnd){
for(int i= colStart; i<= colEnd-1; i++){//左到右第一行
list.add(matrix[rowStart][i]);
}
for(int i= rowStart; i<= rowEnd-1; i++){//上到下第一列
list.add(matrix[i][colEnd]);
}
for(int i=colEnd; i >= colStart + 1; i--){//右到左第一行
list.add(matrix[rowEnd][i]);
}
for(int i=rowEnd; i >= rowStart + 1; i--){//下到上第一列
list.add(matrix[i][colStart]);
}
}else if(colStart < colEnd && rowStart == rowEnd){//剩下一个长大于宽的矩形
for(int i= colStart; i<= colEnd; i++){
list.add(matrix[rowStart][i]);
}
}else if(rowStart < rowEnd && colStart == colEnd){//剩下一个宽大于长的矩形
for(int i = rowStart; i<= rowEnd; i++){
list.add(matrix[i][colStart]);
}
}else{// 剩下一个值
list.add(matrix[rowStart][colStart]);
}
rowStart ++;
colStart ++;
rowEnd --;
colEnd --;
}
return list;
}
}
20.题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
import java.util.Stack;
public class Solution {
private Stack<Integer> minStack = new Stack();//存放最小的
private Stack<Integer> stack = new Stack();//存放添加的
public void push(int node) {
if(minStack.isEmpty() || node < minStack.peek())
minStack.push(node);
stack.push(node);
}
public void pop() {
if(stack.isEmpty())
return;
if(!minStack.isEmpty() && minStack.peek() == stack.peek()){
minStack.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
21.题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack();
int index = 0;
for(int i=0; i<popA.length; i++){
int num = popA[i];
if(stack.isEmpty()){//栈为空时添加节点
stack.push(pushA[index++]);
}
while(stack.peek()!= num && index < pushA.length){
stack.push(pushA[index++]);
}
if(stack.peek()!=num && index >= pushA.length)//当栈顶元素不等于num且pushA元素已经都入栈
return false;
stack.pop();
}
return true;
}
}
22.题目描述:从上往下打印出二叉树的每个节点，同层节点从左至右打印。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList();
LinkedList<TreeNode> queue = new LinkedList();
if(root == null)
return list;
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
return list;
}
}
23.题目描述:输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length <=0)
return false;
return isPostBST(sequence, 0, sequence.length-1);
}
public boolean isPostBST(int[] array, int start, int end){
//根节点的值
int root = array[end];
//找到左子树是否满足后序遍历
int i=start;
for(; i<end; i++){
if(array[i] > root){
break;
}
}
int j=i;
for(; j<end; j++){
if(array[j] < root)
return false;
}
boolean left = true;
//判断左子树是不是二叉搜索树
if(i > start){
left = isPostBST(array,start, start + i -1);
}
boolean right = true;
if(j < end){
right = isPostBST(array, start+i, end-1);
}
return left && right;
}
}
24.题目描述:输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> roads = new ArrayList();//存储所有路径
private ArrayList<Integer> road = new ArrayList();//存放当前路径
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root == null)
return roads;
road.add(root.val);
if(root.left == null && root.right == null){//当到达叶节点时
if(target == root.val)
roads.add(new ArrayList<>(road));
}
if(root.left != null){//当左子树不为空
FindPath(root.left, target-root.val);
}
if(root.right != null){//当右子树不为空
FindPath(root.right, target-root.val);
}
road.remove(road.size()-1);
return roads;
}
}
25.题目描述:输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
//分成三步1.复制每个节点放置在该节点的后面
//2.修改节点的random指针
//3.修改节点的next指针
public static RandomListNode Clone(RandomListNode pHead)
{
if(pHead == null)
return null;
copy(pHead);
changeRandom(pHead);
return changeNext(pHead);
}
public static RandomListNode changeNext(RandomListNode pHead){//修改next指针
RandomListNode root = pHead;
RandomListNode head = pHead.next;
while(root != null){
RandomListNode copy = root.next;
root.next = copy.next;
root = copy.next;
if(root != null)
copy.next = root.next;
else
copy.next = null;
}
return head;
}
public static void changeRandom(RandomListNode pHead){//修改随机指针
RandomListNode root = pHead;
while(root != null){
if(root.random != null){
root.next.random = root.random.next;
}
root = root.next.next;
}
}
public static void copy(RandomListNode pHead){//复制节点
RandomListNode root = pHead;
while(root != null){
RandomListNode node = new RandomListNode(root.label);//复制节点
node.next = root.next;
node.random = root.random;
root.next = node;//修改原节点吓一跳指针
root = node.next;//root指向下一个节点
}
}
}
26.题目描述:输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private TreeNode head = null;//记录链表起始节点
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null){
return null;
}
if(pRootOfTree.left == null && pRootOfTree.right == null)
return pRootOfTree;
if(head == null){//找到初始节点
head = pRootOfTree;
while(head.left != null){
head = head.left;
}
}
Convert(pRootOfTree.left);//左子树构成一个双向链表
Convert(pRootOfTree.right);//右子树构成一个双向链表
TreeNode leftLast = null;
if(pRootOfTree.left != null){//找到左子树最右边一个就节点
leftLast = pRootOfTree.left;
while(leftLast.right != null){
leftLast = leftLast.right;
}
}
TreeNode rightFirst = null;
if(pRootOfTree.right != null){//找到右子树最左边的一个点
rightFirst = pRootOfTree.right;
while(rightFirst.left != null){
rightFirst = rightFirst.left;
}
}
if(leftLast != null){//左子树最大的点不为空
leftLast.right = pRootOfTree;
pRootOfTree.left = leftLast;
}
if(rightFirst != null){//右子树最小的点不为空
rightFirst.left = pRootOfTree;
pRootOfTree.right = rightFirst;
}
return head;
}
}
27.题目描述:输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
import java.util.*;
public class Solution {
private char [] seqs;
private Integer [] book;
//用于结果去重
private HashSet<String> result = new HashSet<String>();
/**
* 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
* 例如输入字符串abc,则打印出由字符a,b,c
* 所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。\
* @param str
* @return
*/
public ArrayList<String> Permutation(String str) {
ArrayList<String> arrange = new ArrayList<String>();
if(str == null || str.isEmpty()) return arrange;
char[] strs = str.toCharArray();
seqs = new char[strs.length];
book = new Integer[strs.length];
for (int i = 0; i < book.length; i++) {
book[i] = 0;
}
dfs(strs, 0);
arrange.addAll(result);
Collections.sort(arrange);
return arrange;
}
/**
* 深度遍历法
*/
private void dfs(char[] arrs, int step){
//走完所有可能 记录排列
if(arrs.length == step){
String str = "";
for (int i = 0; i < seqs.length; i++) {
str += seqs[i];
}
result.add(str);
return; //返回上一步
}
//遍历整个序列,尝试每一种可能
for (int i = 0; i < arrs.length; i++) {
//是否走过
if(book[i] == 0){
seqs[step] = arrs[i];
book[i] = 1;
//下一步
dfs(arrs, step + 1);
//走完最后一步 后退一步
book[i] = 0;
}
}
}
}
28.题目描述:数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)
return 0;
int num = 0;
int count = 0;
for(int i=0; i<array.length; i++){
if(count == 0){
num = array[i];
count = 1;
}else if(num == array[i]){
count++;
}else{
count--;
}
}
count = 0;
for(int i=0; i<array.length; i++){
if(array[i] == num)
count++;
}
if((count << 1) <= array.length){
return 0;
}
return num;
}
}
29.题目描述:输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,
import java.util.*;
public class Solution {
public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(input == null || k <=0 || input.length < k)
return list;
int start = 0;
int end = input.length -1;
int index = partition(input, start, end);
while(index != k-1){
if(index > k-1){
end = index-1;
index = partition(input,start,end);
}else{
start = index + 1;
index = partition(input,start,end);
}
}
for(int i=0; i<k; i++)
list.add(input[i]);
return list;
}
public static int partition(int[] array, int start, int end){
if(array == null || array.length <= 0 || start< 0 || end >= array.length)
throw new RuntimeException("输入不正确");
int index = (int)(Math.random() *(end-start +1)) + start;//获取随机数
swap(array,index,start);
while(start < end){
while(array[end] > array[start])
end --;
if(start < end){
swap(array, start, end);
start ++;
}
while(array[start] < array[end])
start ++;
if(start < end){
swap(array,start, end);
end--;
}
}
return start;
}
public static void swap(int[] array, int index, int start){//交换数组位置
int tmp = array[index];
array[index] = array[start];
array[start] = tmp;
}
}
30.题目描述:HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array== null || array.length <=0)
throw new RuntimeException("数组长度不正确");
int max = Integer.MIN_VALUE;
int curSum = Integer.MIN_VALUE;
for(int i=0; i<array.length; i++){
if(curSum < 0)
curSum = array[i];
else
curSum = array[i] + curSum;
if(curSum > max)
max = curSum;
}
return max;
}
}
