240. Search a 2D Matrix II -M

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

 

Example 1:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• All the integers in each row are sorted in ascending order.
• All the integers in each column are sorted in ascending order.
• -109 <= target <= 109

A:

思路是，对角线寻找。  复杂度 O(m+n)

如果从左上角开始，到一个点，如果A[i][i] > target了。 则不可能在右下角的区间。同样。也不能在左上角的区间。

因此只可能在左下角和右上角的区间里

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        return helper(matrix,target, 0,0,m-1,n-1);
    }
private:
    bool helper(vector<vector<int>>& matrix, int target, int topX, int topY, int botX, int botY){ // bot -> bottom
        if(topX > botX || topY > botY || matrix[topX][topY] > target){
            return false;
        }
        // from [topX, topY] ,going diagnally ,to find a node that's bigger
        int x = topX, y = topY;
        while(x <= botX && y<= botY && matrix[x][y] <= target){
            if(matrix[x][y] == target){
                return true;
            }
            ++x;
            ++y;
        }
        // now matrix[x][y] is bigger than target
        return helper(matrix, target,topX, y, x-1, botY) || helper(matrix, target, x, topY,botX, y-1);
    }
};

当然还有一种方法是逐行查找。 从右上角 开始    复杂度 O(m+n)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0,j=n-1;
        while(i<m&& j>=0){
            if(matrix[i][j] == target){
                return true;
            }else if(matrix[i][j] < target){
                ++i;
            }else{
                --j;
            }
        }
        return false;
    }
};

260. Single Number III -------------- M

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

A

就是 先全部XOR， 结果 != 0 ， 找到某一位不为0 的。 然后按照这一位来分成2堆。

分别XOR即可。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int totalOR=0;
        for(auto v:nums)
            totalOR ^= v;
        
        // find a mask bit that totalOR is not 0
        int mask = totalOR  - (totalOR & (totalOR-1));
        int a=0, b =0;
        for(auto v:nums){
            if(mask&v)
                a ^= v;
            else
                b ^= v;
        }
        return vector<int>{a,b};
    }
};
 

---------------------同样的思路， 另一种实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 1) get sum of two non-repeating elements, with bit manipulation
        int sum = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        // 2) get first rightmost set-bit and set everything else to zero. this is where the two-numbers start to differ.
        int mask = (sum & -sum);
        // 3) separate the bits into two parts. all duplicate nums will cancel out with XOR operation. 
        int a =0, b = 0;

        for (auto &v: nums) {
            if (v & mask) 

                a ^= num;   // not set.
            else 

                b ^= num;  // bit is set.
        }
        return vector<int>{a,b};
    }
};

Mistakes:

287. Find the Duplicate Number -M !!!

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

 

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

 

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

 

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

A:

解法1：二分法

此题的二分法思想非常巧妙，将所有元素和n/2进行比较，如果大于n/2的个数多于n/2个，说明重复的元素必定在n/2到n之间。以此类推，可以不断缩小折半考察范围。  

举个general的例子，如果考察范围是left~right，则考察 mid = left+(right-left)/2。如果比mid大的元素个数，多于mid~n之间的个数，则说明重复的元素在mid~n之间。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // binary search of the range of from 1 to n
        int n = nums.size() -1; 
        int bottom = 1, top = n; // inclusive
        while(bottom < top){
            int mid = (bottom + top)/2;
            // count that # is bigger than range
            int count = 0;
            for(const auto &val : nums){
                if(val >= bottom && val <= mid){
                    ++count;
                }
            }
            if(count > mid-bottom +1){
                top = mid;
            }else{
                bottom = mid+1;
            }
        }
        return bottom;
    }
};

解法2： 按照digit 数数，1如果超过一半，就是1,否则就是0

              这个方法思路就不对

解法2：快慢指针

此题还有一个非常绝妙的算法。将1~N个数放在N+1个位置上，那么val->index将会出现一个一对多的映射，反之，index->val将会有一个多对一的映射。而其余的则是一一映射。于是这些index和val势必会有一部分构成一个环。

举个例子：2,4,1,3,1 从index到val的映射关系是：1->2, 2->4, {3,5}->1, 4->3，其中1->2->4->3->1就构成了一个环。可见，这个环的入口就是重复的数字。

于是此题可以联想到 142. Linked List Cycle II，用快慢指针来确定一个linked list中环的入口。算法是，先用快慢指针做追及（快指针的速度比慢指针快一倍），直到他们相遇的位置；再用一个慢指针从起点开始，和在追及位置的慢指针共同前进。他们再次相遇的地方就是环的入口。

Mistakes:

Count of Smaller Numbers After Self

Q:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

A:


Mistakes:

Peeking Iterator

Q:

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek()operation -- it essentially peek() at the element that will be returned by the next call to next().

---

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Show Hint 

A:

就是保存当前的值。   为了得到这个值，需要用原本的next（）。 这样， 原本的next()就要指向下下一个。  （similarly to   hasNext()  )

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    private Integer curVal = null;
    private Iterator<Integer> iterator = null;
    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator = iterator;
        this.next();
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return curVal;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        Integer res =  curVal;
        curVal = iterator.hasNext()?iterator.next() : null;
        return res;
    }

    @Override
    public boolean hasNext() {
        return curVal != null;
    }
}

Google Guava是用了isPeeked 的boolean值来表示，如果没有，就正常next()。 否则不调用next(). 转而直接给出原本的位置，即可.

Mistakes:

1. 没有保存 constructor中传进来的iterator   （一开始都去调用super了）
2. 一开始，看了Hint，因此多用了一个变量记录是否到达end