月度归档:2017年02月

RecyclerView只显示一项的问题

使用RecyclerView的时候发生了个奇怪的现象,无论我怎么调,始终只显示一项,onBindView也只执行一次,到最后发现这是个傻逼的错误:item布局里面高度为match_parent,第一项就占了一页,所以后面的不会显示,记录下傻逼的自己。

0206-0217

新年新任务

boss 分配了个拼团项目过来,大概就是商城的模式吧,数据库没设计好,现在几乎都是在补坑。

看书复习落后

没怎么刷题,也怎么看书,需好好反省下了。

数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

//用亦或思想
    public void FindNumsAppearOnce(int [] a,int num1[] , int num2[]) {
        if(a.length < 2) return ;
        int x = 0;
        int flag = 1;
        for(int i = 0 ; i < a.length; ++ i )
            x ^= a[i];

        /*
            找出任一一个 '1',即flag是这样的 000010000...
            1的位置是两个不相同的数亦或的位置,也就是说在这里,1所在的位 这两个数一定不同
            以此来分组
        */
        while((x & flag) == 0) flag <<= 1;
        num1[0]=num2[0]=0;
        //分组异或出答案
        for(int i = 0; i < a.length; ++ i ){
            if((flag & a[i]) == 0) num2[0]^= a[i];
            else num1[0]^= a[i];
        }

    }

连续子数组的最大和

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住?(子向量的长度至少是1)

public int FindGreatestSumOfSubArray(int[] a) {
          int sum=0,max=-1;
           for(int i=0;i<a.length;i++){
               if(sum+a[i]>=0){
                   sum+=a[i];
                   if(sum>max)max=sum;
               }else{
                   sum=0;
               }
           }
           return max;
      }

数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

思路

待补充

public class Solution {
      public int MoreThanHalfNum_Solution(int [] a) {
          if(a==null||a.length==0)return 0;
          if(a.length==1)return a[0];
          int t=0,cnt=1;
          for(int i=1;i<a.length;i++){
              if(cnt==0){
                  cnt=1;
                  t=a[i];
              }
              if(t==a[i])cnt++;
              else cnt--;

          }
          cnt=0;
          for(int i=0;i<a.length;i++){
              if(t==a[i])cnt++;
          }
          if(cnt>=(a.length/2+1))return t;
          return 0;
      }
}

二叉搜索树的后序遍历序列

题目描述

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

思路

二叉查找书的特性是左子树都比跟元素小,右子树都比跟元素大,而后序序列的最后一个元素是跟元素,所以可以形成递归

import java.util.Arrays;
public class Solution {
    public boolean VerifySquenceOfBST2(int [] sequence) {
        if(sequence.length==1||sequence.length==0)return true;
        int root=sequence[sequence.length-1];
        int i=0;
        while(i<sequence.length-2&&sequence[i]<root)i++;
        for(int j=i;j<sequence.length-2;j++){
            if(sequence[j]<root)return false;
        }
        return VerifySquenceOfBST2(Arrays.copyOfRange(sequence, 0, i))
            &&VerifySquenceOfBST2(Arrays.copyOfRange(sequence,i,sequence.length-1));
    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)return false;
        return VerifySquenceOfBST2(sequence);
    }
}

从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

思路

使用队列,感觉和BFS思路差不多吧

代码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
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 res=new ArrayList<>();
        Queue<TreeNode> q=new LinkedList<TreeNode>();
        if(root!=null){
            q.add(root);
        }
        while(!q.isEmpty()){
            TreeNode front=q.poll();
            if(front.left!=null)q.add(front.left);
            if(front.right!=null)q.add(front.right);
            res.add(front.val);
        }
        return res;
    }
}

合并两个排序的链表

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode p = new ListNode(0);
        ListNode head=p;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                p.next=list1;
                p=list1;
                list1=list1.next;
            }else {
                p.next=list2;
                p=list2;
                list2=list2.next;
            }
        }
        while(list1!=null){
            p.next=list1;
            p=list1;
            list1=list1.next;
        }
        while(list2!=null){
            p.next=list2;
            p=list2;
            list2=list2.next;
        }
        return head.next;
    }
}

还可以有递归版本

/*
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;
        if(list1.val<list2.val){
            head=list1;
            head.next = Merge(list1.next, list2);
        }else{
            head=list2;
            head.next = Merge(list1, list2.next);
        }
        return head;
    }
}

翻转链表

题目描述

输入一个链表,反转链表后,输出链表的所有元素。

代码

public ListNode ReverseList(ListNode head) {
              if(head==null||head.next==null)return head;
              ListNode pre=head,newHead=head.next,p=head.next;
              while(p!=null){
                  ListNode tp=p.next;
                  if(p.next!=null){
                    newHead=p.next;
                  }
                  p.next=pre;
                  pre=p;
                  p=tp;
              }
              head.next=null;
              return newHead;
          }

链表中倒数第k个结点

直接上代码 考虑周到点就好了

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
              int len=0;
              ListNode p=head;
              while(p!=null){
                  len++;
                  p=p.next;
              }
              if(k>len) return null;
              if(len-k==0)return head;
              p=head;
              int n=len-k;
              while(n>0){
                  p=p.next;
                  n--;
              }
              return p;
    }

}