LeetCode [325] Maximum Size Subarray Sum Equals k

325. Maximum Size Subarray Sum Equals k

Medium

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Input: nums = [1, -1, 5, -2, 3], k = 3
Output: 4 
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

Example 2:

Input: nums = [-2, -1, 2, 1], k = 1
Output: 2 
Explanation: The subarray [-1, 2] sums to 1 and is the longest.

Follow Up:
Can you do it in O(n) time?

//C++: 96ms
class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sums(n+1, 0);
        unordered_map<int, int> hash;//sum, index
        hash[0] = 0;
        int ret = 0;
        for(int i=1; i<=n; ++i){
            sums[i] = sums[i-1]+nums[i-1];
            if(hash.count(sums[i])==0) hash[sums[i]] = i;
            int diff = sums[i]-k;
            if(hash.count(diff)){
                ret = max(ret, i-hash[diff]);
            }
        }
        return ret;
    }
};

//Java
class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int s = 0;
        int r = 0;
        map.put(0, -1);
        for(int i=0; i<nums.length; ++i){
            s += nums[i];
            int d = s-k;
            if(map.containsKey(d)){
                int len = i-map.get(d);
                r = Math.max(r, len);
            }
            if(!map.containsKey(s))
                map.put(s, i);
        }
        return r;
    }
}

LeetCode [314] Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]

Examples 2:

Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

Examples 3:

Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \
   5   2

Output:

[
  [4],
  [9,5],
  [3,0,1],
  [8,2],
  [7]
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<vector<int>> verticalOrder(TreeNode* root) { int l = 0, r = 0; vector<vector<int>> ret; if(!root) return ret; ret.resize(1); queue<pair<TreeNode*, int>> que;//node. column index que.push(make_pair(root, 0)); while(!que.empty()) { TreeNode *node = que.front().first; int index = que.front().second; que.pop(); if(index<l) { l--; ret.insert(ret.begin(), vector<int>()); } else if(index>r) { r++; ret.insert(ret.end(), vector<int>()); } ret[index-l].push_back(node->val); if(node->left) que.push(make_pair(node->left, index-1)); if(node->right) que.push(make_pair(node->right, index+1)); } return ret; } };

LeetCode [311] Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

Input:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]

Output:

     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

class Solution { public: vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) { unordered_map<int, unordered_set<int>> A1, B1; int ma = A.size(), na = A[0].size(); int mb = B.size(), nb = B[0].size(); for(int i=0; i<ma; ++i){ for(int j=0; j<na; ++j){ if(A[i][j]){ A1[i].insert(j); } } } for(int j=0; j<nb; ++j){ for(int i=0; i<mb; ++i){ if(B[i][j]){ B1[j].insert(i); } } } vector<vector<int>> ret(ma, vector<int>(nb, 0)); for(int i=0; i<ma; ++i){ for(int j=0; j<nb; ++j){ int s = 0; if(A1.count(i) && B1.count(j)){ for(auto k:A1[i]){ if(B1[j].count(k)){ s += A[i][k]*B[k][j]; } } } ret[i][j] = s; } } return ret; } };

//Java
class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int am = A.length, an = A[0].length;
        int bm = B.length, bn = B[0].length;
        List<Map<Integer, Integer>> mapA = new ArrayList<Map<Integer, Integer>>(am);
        List<Map<Integer, Integer>> mapB = new ArrayList<Map<Integer, Integer>>(bn);

        for(int i=0; i<am; ++i){
            mapA.add(new HashMap<>());
            for(int j=0; j<an; ++j){
                if(A[i][j]!=0){
                    mapA.get(i).put(j, A[i][j]);
                }
            }
        }

        for(int j=0; j<bn; ++j){
            mapB.add(new HashMap<>());
            for(int i=0; i<bm; ++i){
                if(B[i][j]!=0){
                    mapB.get(j).put(i, B[i][j]);
                }
            }
        }

        int[][] ret = new int[am][bn];
        for(int i=0; i<am; ++i){
            for(int j=0; j<bn; ++j){
                int s = 0;
                for(Map.Entry<Integer, Integer> e : mapA.get(i).entrySet()){
                    int k = e.getKey(), v = e.getValue();
                    if(mapB.get(j).containsKey(k)){
                        s += v*mapB.get(j).get(k);
                    }
                }
                ret[i][j] = s;
            }
        }
        return ret;
    }
}

LeetCode [299] Bulls and Cows

 299. Bulls and Cows

Easy

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.

Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. 

Please note that both secret number and friend's guess may contain duplicate digits.

Example 1:

Input: secret = "1807", guess = "7810"

Output: "1A3B"

Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.

Example 2:

Input: secret = "1123", guess = "0111"

Output: "1A1B"

Explanation: The 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow.

Note: You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

//C++: two pass, 8 ms class Solution { public: string getHint(string secret, string guess) { int n = secret.size(); int b = 0, c = 0; int nums[10] = {0}; for(int i=0; i<n; ++i){ if(secret[i]==guess[i]){ b++; }else{ nums[secret[i]-'0']++; } } for(int i=0; i<n; ++i){ if(secret[i]!=guess[i]){ if(nums[guess[i]-'0']>0){ c++; nums[guess[i]-'0']--; } } } return to_string(b)+"A"+to_string(c)+"B"; } }; //C++: one pass, 4 ms class Solution { public: string getHint(string secret, string guess) { int n = secret.size(); int b = 0, c = 0; int nums[10] = {0}; for(int i=0; i<n; ++i){ if(secret[i]==guess[i]){ b++; }else{ if(nums[secret[i]-'0']<0) c++; if(nums[guess[i]-'0']>0) c++; nums[secret[i]-'0']++; nums[guess[i]-'0']--; } } return to_string(b)+"A"+to_string(c)+"B"; } }; //Java class Solution { public String getHint(String secret, String guess) { int[] numbers = new int[256]; int n = secret.length(); int b=0, c=0; for(int i=0; i<n; ++i){ if(secret.charAt(i)!=guess.charAt(i)){ numbers[secret.charAt(i)]++; } } for(int i=0; i<n; ++i){ if(secret.charAt(i)==guess.charAt(i)) b++; else{ if(numbers[guess.charAt(i)]>0){ c++; numbers[guess.charAt(i)]--; } } } return b+"A"+c+"B"; } }

YMSF

第五轮，白人小哥，刷题网没刷到过 （题刷太少了我。。），给两个长度为4的都是数字0-9的字符串A和B，如果B对应A的位置数字相同就是一个correct，如果对应数字不同，但是存在与A别的位置，就算是一个miss，设计个函数求最后correct和miss的数量。 比方A=1166，B=1116， 结果是3 correct，0 miss （因为A只有俩1，B第三个1不算miss），再比方A=2780，B=0782，就是2 correct，2 miss。 Followup是如何用这个函数把B最后修改成为A，assume一定能把B改成A，时间不够了，写的伪代码，大概思路是每个位置都放0-9测试，如果放的数字使correct+miss总和比上次的情况好，说明猜对了那个数字，就往下一个位置走，结束条件是correct+miss的总和等于4，最后再permute这4个数字的位置然后使用函数，直到correct=4，miss=0，大概率也不是最优解，说了下时间空间复杂度，小哥只是点了点头，问我还有啥问题没有就拜拜了

感觉第五题的 follow up 有点像843

第五轮是刷题网原题，楼上有人回复了，follow up可能是面试官临时想出来的，也没让我写代码，就口述

第五题的typo，

但是存在与A别的位置 =》 但是存在于A别的位置

题目有点绕，第一步是不是可以这么解？

strA, strB， 用countA[] 和countB[] 分别count出现数字的个数。

[C++] 纯文本查看 复制代码

?

01 02 03 04

if strA[i][i] == strB[i]   correct ++; else if countA[strA[i]] != countB[strB[i]]   miss ++

差不多这个思路，可能是我解释得不清楚，如果B(i) 不存在A里，那这个既不算correct也不算miss，就continue就行, 比如A: 1234, B: 7890, 结果就是(0,0)

YMSF

1. 给两个长度一样string S和T，如果在同一个位置上，两个string的字符不同，就是一个diff。比如“abc”和"abd"，最后一个字符分别是'c'和'd'，这两个string的diff就是1。现在我们要在S里交换两个字符的位置，使把S和T之间的diff尽量减到最小，返回两个被交换的字符的位置。面试官应该要求的是O（n）

请问群主如何在O(n)时间使用map找到S和T中是否存在一对相同的 character pair呢， 尤其在有重复character的情况下

前面一道题简单， 维护一个 Map<Character,List<Integer>>  对象，保存所有没有找到match的t 的character以及位置， 任何时候看到一个不匹配的character，去找这个map里面有没有现成的t 的character，如果有，查一下list，看看list里面这些位置s上有没有正好是当前t的char，如果有调换这两个，如果没有选择第一个调换，然后更新map

第一题的解法看的不太明白。如果这样做最坏情况下的时间复杂度不是O(n^2) 吗

是的，正常情况下是O(n)的复杂度 类似2Sum的算法

但是在找这个dif-2调换的时候，要做一个循环，但是再怎样应该每次找的时候到不了O(n)的复杂度，当然理论上还是得说这是个O(n)的循环

如果有调换这两个，如果没有选择第一个调换，然后更新map

请问这句是什么意思呀，会存在调换一次只减少一个diff的情况吗

这个第一种情况可以严格O(n)

建立一个Map<String, Integer>，然后当我遇见两个字符是a和b时，存入string "ab" 作为key，index作为value，生成这个String key的时候，总是把小的字符放在前面。

这样当我又遇见ab的时候，我只需要查一下Map里的index，看看是不是ab还是ba就可以了，如果是a都在同一个字符里，就无视，如果是a分别在两个字符里，就找到答案

啊是这个意思 我理解错题了以为是t和s里的字符相互调换。。 谢谢！

第一题就是bulls and cows的变体而且变更简单了

LeetCode [291] Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Example 1:

Input: pattern = "abab", str = "redblueredblue"
Output: true

Example 2:

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"
Output: true

Example 3:

Input: pattern = "aabb", str = "xyzabcxzyabc"
Output: false

Notes:
You may assume both pattern and str contains only lowercase letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

class Solution { public: bool wordPatternMatch(string pattern, string str) { unordered_map<char, string> hash1; unordered_map<string, char> hash2; return bt(pattern, str, 0, 0, pattern.size(), str.size(), hash1, hash2); } bool bt(string &pattern, string &str, int p, int s, int np, int ns, unordered_map<char, string> &hash1, unordered_map<string, char> &hash2){ if(p==np && s==ns){ return true; }else if(p<np && s<ns){ char c = pattern[p]; if(hash1.count(c)){ int len = hash1[c].size(); if(s+len<=ns && str.substr(s, len)==hash1[c] && bt(pattern, str, p+1, s+len, np, ns, hash1, hash2)){ return true; }else{ return false; } }else{ for(int i=s; i<ns; ++i){ string ss = str.substr(s, i-s+1); if(hash2.count(ss)==0){ hash1[c] = ss; hash2[ss] = c; if(bt(pattern, str, p+1, i+1, np, ns, hash1, hash2)) return true; hash2.erase(ss); hash1.erase(c); } } } } return false; } };

LeetCode [290] Word Pattern

Ref
[1] https://leetcode.com/problems/word-pattern/

LeetCode [288] Unique Word Abbreviation

Ref
[1] https://leetcode.com/problems/unique-word-abbreviation/

MJ [39] Valid Parentheses

Question:
Given a string with parentheses, return a string with balanced parentheses by removing the fewest characters possible. You cannot add anything to the string.
Examples:
balance("()") -> "()"
balance(")(") -> "".
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
Note：balance(")(())(") != "()()"

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/32913437_0_1.html