藍橋杯刷題JAVA（4）

1.二進制求和

class Solution {
    public String addBinary(String a, String b) {
        int alert = 0;
    	if(a.length() < b.length()) {
    		String cString = b;
    		b = a;
    		a = cString;
    	}
        StringBuffer tempBuffer = new StringBuffer();
    	for(int i = 1; i <= a.length(); i++) {
    		int tempa = Integer.valueOf(a.substring(a.length()-i, a.length() - i + 1));
    		int tempb;
    		if(i > b.length())
    			tempb = 0;
    		else
    			tempb = Integer.valueOf(b.substring(b.length()-i, b.length()-i + 1));
    		tempBuffer.insert(0, String.valueOf((tempa + tempb + alert) % 2));
    		if(tempa + tempb + alert >= 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 <= 1)
    		return x;
    	while(r > 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 < n){
            list[flag] = list[0] + list[1];
            flag = (flag + 1) % 2;
            i++;
        }
        return list[(flag + 1) % 2];
    }
}


//Python利用緩存裝飾器
class Solution:
    # 這裡加了緩存裝飾器！！！
    @functools.lru_cache(100)
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        return self.climbStairs(n - 1) + self.climbStairs(n - 2) if n > 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 < n + m;)
            if(i < m && j < n)
                if(nums1[i] < nums2[j])
                    mergenums[k++] = nums1[i++];
                else
                    mergenums[k++] = nums2[j++];
            else if(i >= m)
                mergenums[k++] = nums2[j++];
            else
                mergenums[k++] = nums1[i++];
        for(int i = 0; i < n + m; i++)
            nums1[i] = mergenums[i];
    }
}

//騷做法
把後面占位0用nums替換，之後就可以直接用array的sort了

//妙解
從後面開始周遊，這樣可省略輔助空間
           

經驗：

第一版比較浪費空間，妙解思想很好，nums1的空間正好可以保證不會覆寫元素。

6.相同的樹

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        else if(p == null && q != null)
            return false;
        else if(p != null && q == null)
            return false;
        else
            if(p.val != q.val)
                return false;
            else
                if(isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
                    return true;
                else
                    return false;
    }
}


           

//python騷解法
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        return str(p) == str(q)
           

經驗：簡單的廣搜遞歸即可解決，python有騷解法，直接比較str