A + B Problem, LintCode 解题笔记

For given numbers a and b in function aplusb, return the sum of them.

Note
You don’t need to parse the input and output. Just calculate and return.

Example
If a=1 and b=2 return 3

Challenge
Can you do it with out + operation?

Clarification
Are a and b both 32-bit integers?
– Yes.

位运算实现整数加法本质就是用二进制进行运算。
其主要用了两个基本表达式:
x^y //执行加法,不考虑进位。
(x&y)<<1 //进位操作
令x=x^y ;y=(x&y)<<1 进行迭代,每迭代一次进位操作右面就多一位0,最多需要“加数二进制位长度”次迭代就没有进位了,此时x^y的值就是结果。

我们来做个3位数的加法:
101+011=1000 //正常加法
位运算加法:
(1) 101 ^ 011 = 110
(101 & 011)<<1 = 010
(2) 110 ^ 010 = 100
(110 & 010)<<1 = 100
(3) 100 ^ 100 = 000
(100 & 100)<<1 = 1000
此时进行相加操作就没有进位了,即000 ^ 1000=1000即是最后结果。

class Solution {
    /*
     * param a: The first integer
     * param b: The second integer
     * return: The sum of a and b
     */
    public int aplusb(int a, int b) {
        while(b != 0){
            int carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }
}
Advertisements

Intersection of Two Linked Lists, Leetcode 解题笔记

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2 → c1 → c2 → c3

B: b1 → b2 → b3 → c1 → c2 → c3
begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

一开始想的是直接同时遍历A和B,A走一步,B走一步,后来发现这样其实等于是两个循环套在一起的意思,时间复杂度变成了O(m*n)。
一个巧妙的方法是先找到list A和list B的长度差,然后让长的那个list先把长出来的那一段走完,此时两个list是一样长的,然后同时向后走直到重合。这样时间复杂度是O(m+n),并且只需要常量的空间。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int numA = 0;
        int numB = 0;
        ListNode cur = headA;
        ListNode cur2 = null;
        while(cur != null){
            cur = cur.next;
            numA++;
        }
        cur = headB;
        while(cur != null){
            cur = cur.next;
            numB++;
        }
        int diff = Math.abs(numA - numB);
        if(numA > numB){
            cur = headA;
            cur2 = headB;
        }
        else{
            cur = headB;
            cur2 = headA;
        }
        for(int i = 0; i < diff; i++){
            cur = cur.next;
        }
        while(cur != null){
            if(cur == cur2) return cur;
            cur = cur.next;
            cur2 = cur2.next;
        }
        return null;
    }
}

Min Stack, Leetcode 解题笔记

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.

这题很简单,维护一个list就可以了,定义一个新的类StackNode,存当前的值和当前的最小值。

class MinStack {
    StackNode stackHead = null;
    
    public void push(int x) {
        StackNode element = new StackNode(x);
        if(stackHead != null){
            element.next = stackHead;
            element.min = Math.min(x, stackHead.min);
            stackHead = element;
        }
        else{
            element.next = null;
            element.min = x;
            stackHead = element;
        }
        
    }

    public void pop() {
        if(stackHead != null)
            stackHead = stackHead.next;
    }

    public int top() {
        if(stackHead != null)
            return stackHead.val;
        else
            return 0;
    }

    public int getMin() {
        if(stackHead != null)
            return stackHead.min;
        else
            return 0;
    }
}
class StackNode {
    StackNode next;
    int val;
    int min;
    StackNode(int val) {
        next = null;
        this.val = val;
        min = 0;
    }
}

Find Minimum in Rotated Sorted Array II, Leetcode 解题笔记

Follow up for “Find Minimum in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

此题已经在上题中讨论过了,最坏复杂度变成了O(n)。

public class Solution {
    public int findMin(int[] num) {
        int left = 0;
        int right = num.length-1;
        int min = Integer.MAX_VALUE;
        while(left < right-1){
            int mid = (left + right)/2;
            if(num[mid] > num[left]){
                min = Math.min(min, num[left]);
                left = mid + 1;
            }
            else if(num[mid] < num[left]){
                min = Math.min(min, num[mid]);
                right = mid - 1;
            }
            else{
                left++;
            }
        }
        min = Math.min(Math.min(min, num[left]), num[right]);
        return min;
    }
}

Find Minimum in Rotated Sorted Array, Leetcode 解题笔记

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

对于数组里找某个值得问题显然首选二分法,对于此题有两种情况:
1. 中间值大于左值,此时左半边数组是有序的,所以左半边最小值是左半边第一个。
2. 中间值小于左值,此时右半边数组是有序的,所以右半边最小值是右半边第一个。
*3. 如果数组中有重复元素,则还有可能是中间值等于左值,此时只需要左值右移一位即可。

public class Solution {
    public int findMin(int[] num) {
        int left = 0;
        int right = num.length-1;
        int min = Integer.MAX_VALUE;
        while(left < right-1){
            int mid = (left + right)/2;
            if(num[mid] > num[left]){
                min = Math.min(min, num[left]);
                left = mid + 1;
            }
            else if(num[mid] < num[left]){
                min = Math.min(min, num[mid]);
                right = mid - 1;
            }
            else{
                left++;
            }
        }
        min = Math.min(Math.min(min, num[left]), num[right]);
        return min;
    }
}

Maximum Product Subarray, Leetcode 解题笔记

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

求最值问题一般要考虑DP的解法,对于乘法,当前的连续乘积最大值有几种可能:
1. 如果当前值是正数,那么max = Math.max(A[i], A[i]*max)
2. 如果当前值是负数,那么max = Math.max(Math.max(A[i], A[i]*max), A[i]*min)
所以,不同于加法,这里我们要维护两个最值:当前的最大值和当前的最小值。

public class Solution {
    public int maxProduct(int[] A) {
        int curMax = A[0];
        int curMin = A[0];
        int totalMax = A[0];
        for(int i = 1; i < A.length; ++i){
            int curMax_copy = curMax;
            curMax = Math.max(Math.max(curMax*A[i], A[i]), curMin*A[i]);
            curMin = Math.min(Math.min(curMax_copy*A[i], A[i]), curMin*A[i]);
            totalMax = Math.max(curMax, totalMax);
        }
        return totalMax;
    }
}

Reverse Words in a String, Leetcode 解题笔记

Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

click to show clarification.

Clarification:
What constitutes a word?
A sequence of non-space characters constitutes a word.
Could the input string contain leading or trailing spaces?
Yes. However, your reversed string should not contain leading or trailing spaces.
How about multiple spaces between two words?
Reduce them to a single space in the reversed string.

一开始想复杂了,还想到用stack去了,其实就是把string split成数组形式,然后倒序合并就行了,这里利用StringBuilder比较方便。

public class Solution {
    public String reverseWords(String s) {
        if(s == null || s.length() == 0) return "";
        String[] arr = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = arr.length-1; i >= 0; i--){
            if(!arr[i].equals(""))
                sb.append(arr[i]).append(" "); 
        }
        if(sb.length() == 0) return "";
        else return sb.substring(0, sb.length()-1);
    }
}