蓝桥杯刷题JAVA（4）

1.二进制求和

class Solution {
    public String addBinary(String a, String b) {
        int alert = 0;
    	if(a.length() = 2)
    			alert = 1;
    		else
    			alert = 0;
    	}
    	if(alert == 1)
    		tempBuffer.insert(0, "1");
    	return tempBuffer.toString();
    }
}

//题解中较好的算法
    public String addBinary(String a, String b) {
        if(a == null || a.length() == 0) return b;
        if(b == null || b.length() == 0) return a;

        StringBuilder stb = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        
        int c = 0;  // 进位
        while(i >= 0 || j >= 0) {
            if(i >= 0) c += a.charAt(i --) - '0';
            if(j >= 0) c += b.charAt(j --) - '0';
            stb.append(c % 2);
            c >>= 1;
        }
        
        String res = stb.reverse().toString();
        return c > 0 ? '1' + res : res;
    }

经验： （1）int转string–String.valueOf() （2）String转int–>Integer.ValueOf()，需要注意的是，Integer会判断String还是Character，如果是字符该函数会返回其ASCII码，虽然取模的地方不影响，但是下面的进位更新会被波及到。 （3）insert（offset=0）这种方法太消耗时间，选择直接append在最后reverse是一个不错的选择。 （4）在最开头需要考虑a,b长度问题，有一种做法是补齐长度 2.x的平方根

class Solution {
    public int mySqrt(int x) {
    	long r = x;
    	if(x  x / r) 
    		r = (r + x / r) / 2;
    	return (int)r;
    }
}

经验： （1）牛顿迭代法 （2）对于平方与源数据比较会存在溢出的问题，因此需要将比较式变形，r与x/r比较方可成功 （3）加法也同样存在溢出的问题，通过long数据类型和下转型解决。

3.爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n == 1 || n == 2)
            return n;
        int[] list = new int[2];
        list[0] = 1;
        list[1] = 2;
        int i = 2;
        int flag = 0;
        while(i  2 else n

经验： （1）简单思想的DP。 （2）通过反复修改数组的方法节省内存。

4.删除排序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return null;
        ListNode dummyhead = head;
        while(dummyhead.next != null){
            ListNode temp = dummyhead.next;
            if(dummyhead.val == temp.val){
                dummyhead.next = temp.next;
            }else{
                dummyhead = dummyhead.next;
            }
        }
        return head;
    }
}

经验： 做过数组了做这个就是水题了，eclipse都没用直接在线解决~。

5.合并两个有序列表

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] mergenums = new int[n + m];
        for(int i = 0, j = 0, k = 0; k