喜刷刷
Time 2021-10-18 08:03:28Web Name: 喜刷刷
WebSite: http://bangbingsyb.blogspot.com
ID:206403
Keywords:
喜刷刷,Description:
keywords: description:Overloadinggenerally means that you have two or more functions in the same scope having the same name. The function that better matches the arguments when a call is made wins and is called. Important to note, as opposed to calling a virtual function, is that the function that's called is selected at compile time. It all depends on the static type of the argument. If you have an overload for
Band one forD, and the argument is a reference toB, but it really points to aDobject, then the overload forBis chosen in C++. That's calledstatic dispatchas opposed todynamic dispatch. You overload if you want to do the same as another function having the same name, but you want to do that for another argument type. Example:void print(Foo const f) { // print a foo}void print(Bar const bar) { // print a bar}void print(Foo f, PrintAttributes b) { /* ... */ }void print(Foo f, std::string const header, bool printBold) { print(f, PrintAttributes(header, printBold));}struct base { virtual void print() { cout "base!"; }}struct derived: base { virtual void print() { cout "derived!"; }}printmember function, the print function of the derived is always called, because it overrides the one of the base. If the functionprintwasn't virtual, then the function in the derived wouldn't override the base function, but would merelyhideit. Overriding can be useful if you have a function that accepts a base class, and every one that's derived from it:void doit(base b) { // and sometimes, we want to print it b.print();}You overloadfunctions for three reasons:To provide two (or more) functions that perform similar, closely related things, differentiated by the types and/or number of arguments it accepts. Contrived example:
void Log(std::string msg); // logs a message to standard outvoid Log(std::string msg, std::ofstream); // logs a message to a filevoid Plot(Point pt); // plots a point at (pt.x, pt.y)void Plot(int x, int y); // plots a point at (x, y)wchar_t ToUnicode(char c);std::wstring ToUnicode(std::string s);Overridinga function is entirely different, and serves an entirely different purpose. Function overriding is how polymorphism works in C++. You override a function to change the behavior of that function in a derived class. In this way, a base class provides interface, and the derived class provides implementation.No comments: Labels:c++,concept,interview,languageMicrosoft Onsite Interview Checklist1. Resume preparation
2. Basic data structure/algorithm
3. Design question
4. Behavior question
5. C++ language specific question
6. Knowledge about ASP.NET
2 comments: 基础data structure/algorithm列表1. Implementation of stack/queue (array and linked list)
Implement queue using array: circular array - when meet end, wrap around to the beginning.
An array with size n can implement an queue with size n-1 (related to the queue full condition)
Queue empty: head == tail
Queue full: head == tail+1 or head == tail wrap around
Enqueue: tail++ or wrap around
Dequeue: head++ or wrap around
2. Binary search tree: insertion, deletion,successor, traversal,balance.
(1) Insertion: always insert to leaf; need to find the parent of the insertion position, O(h).
(2) Deletion: assume delete z.
z has not child: just delete.
z has only one child: replace z by its child.
z has both left/right child: find leftmost node in z's right subtree y. If y==z.right, replace z by y. Otherwise replace y by y's right child, and then replace z by y.
http://geeksquiz.com/binary-search-tree-set-2-delete/
(3) Successor: http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
(4) Preorder, in-order, and post-order traversal using iterative methods.
3. Heap: creation, insertion.
(1) Concept: nearly complete binary tree, implemented using array
Parent-child relation: for 0-based array (A[0:n-1])
parent(i) = (i-1)/2
left(i) = 2*i+1
right(i) = 2*i+2
(2) Properties:
Max heap: A[parent(i)] = A[i] - heap sort
Min heap: A[parent(i)] = A[i] - priority queue
(3) Heapify: find the largest among y = {A[i], A[left(i)], A[ right(i)]}.
If y = A[i], done; else, swap A[i] with y, and heapify y
(4) Build max heap: for each i from heap.size/2 to 0, heapify(i).
4. Hash table: array + linked list implementation, collision
5. Sorting: (1) merge sort, (2) quick sort, (3) counting sort
Merge sort:
http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Merge_sort
http://www.sanfoundry.com/cpp-program-implement-merge-sort/
Quick sort:
http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort
https://gsamaras.wordpress.com/code/quicksort-c/
6. Master theorem
Key: compare logb(a) and c: http://en.wikipedia.org/wiki/Master_theorem
1. Stack implementation using array in C++:
1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344
#include stringusing namespace std; class Stack {private: int top; int capacity; int *storage;public: Stack(int capacity) { if (capacity = 0) throw string("Stack's capacity must be positive"); storage = new int[capacity]; this-capacity = capacity; top = -1; } void push(int value) { if (top == capacity) throw string("Stack's underlying storage is overflow"); top++; storage[top] = value; } int peek() { if (top == -1) throw string("Stack is empty"); return storage[top]; } void pop() { if (top == -1) throw string("Stack is empty"); top--; } bool isEmpty() { return (top == -1); } ~Stack() { delete[] storage; }};
2. Min Binary Heap Implementation in C++:
http://www.codeproject.com/Tips/816934/Min-Binary-Heap-Implementation-in-CplusplusNo comments: Labels:interview,summary面试中的clarifying questions面试题经常有意无意字面上很含糊这个时候一定需要和面世官交流搞清楚确切的意思总结一下每个topic需要澄清的地方
1. Array:(1) Sorted or not?(2) How many elements?(3) Element type? Int, float, double?(4) What's the range of those numbers? Positive or negative?(5) Contain duplicates or not?(6) Subsequence: adjacent or not?
2. Binary tree:(1) Binary search tree or normal binary tree?(2) Balanced or not?(3) Complete or not?(4) Has parent pointer or not?
3. Linked list:(1) Singly or doubly linked list?(2) Has duplicated nodal value or not?
4. String:(1) Need to remove white spaces? Tab and newline?(2) Only has digits? English letters? Upper or lower case?
5. Graph:(1) How many nodes and edges?(2) Directed or undirected?(3) Edges have weights? If so, what's the range?(4) Has loops? Negative sum loops?
6. Return value:
(1) What should my method return?
(2) If there are multiple solutions to the problem, which one should be returned?
(3) If it should return multiple values, do you have any preference on what to return?
(4) What should I do/return if the input is invalid / does not match the constraints?
No comments: Labels:interview,summary Saturday, November 29, 2014 [LeetCode] Wildcard MatchingImplement wildcard pattern matching with support for
'?'and'*'.'?' Matches any single character.'*' Matches any sequence of characters (including the empty sequence).The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") falseisMatch("aa","aa") trueisMatch("aaa","aa") falseisMatch("aa", "*") trueisMatch("aa", "a*") trueisMatch("ab", "?*") trueisMatch("aab", "c*a*b") false思路1DP
和Regular Expression Matching很像这里的'?'相当于Regular Expression中的'.'但'*'的用法不一样这里'*'与前一个字符没有联系并且无法消去前一个字符但可以表示任意一串字符递推公式的推导和Regular Expression Matching也基本类似
p[j-1] == s[i-1] || p[j-1] == '?'dp[i][j] = dp[i-1][j-1]p[j-1] == '*'1. 匹配0个字符dp[i][j] = dp[i][j-1]2. 匹配1个字符dp[i][j] = dp[i-1][j-1]3. 匹配多个字符dp[i][j] = dp[i-1][j]
先用二维数组写发现会Memory Limit Exceeded
1 2 3 4 5 6 7 8 91011121314151617
class Solution {public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vectorvectorbool dp(m+1, vectorbool(n+1,false)); dp[0][0] = true; for(int i=0; im; i++) { for(int j=1; jn; j++) { if(p[j-1]==s[i-1] || p[j-1]=='?') dp[i][j] = i0 dp[i-1][j-1]; else if(p[j-1]=='*') dp[i][j] = dp[i][j-1] || (i0 (dp[i-1][j-1] || dp[i-1][j])); } } return dp[m][n]; }};
然后用一维滚动数组改写发现会Time Limit Exceeded
1 2 3 4 5 6 7 8 91011121314151617181920
class Solution {public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vectorbool dp(m+1, false); for(int i=0; im; i++) { bool diag = dp[0]; dp[0] = i==0 ? true : false; for(int j=1; jn; j++) { int temp = dp[j]; if(p[j-1]==s[i-1] || p[j-1]=='?') dp[j] = i0 diag; else if(p[j-1]=='*') dp[j] = dp[j-1] || (i0 (diag || dp[j])); diag = temp; } } return dp[n]; }};
思路2双指针扫描
用DP会TLE那么一定有其他好的方法
3 comments: Labels:algorithm,dynamic programming,Leetcode,string,string match,two pointers[LeetCode] Regular Expression MatchingImplement regular expression matching with support for
'.'and'*'.'.' Matches any single character.'*' Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).The function prototype should be:bool isMatch(const char *s, const char *p)Some examples:isMatch("aa","a") falseisMatch("aa","aa") trueisMatch("aaa","aa") falseisMatch("aa", "a*") trueisMatch("aa", ".*") trueisMatch("ab", ".*") trueisMatch("aab", "c*a*b") true思路1: DP
关键在于如何处理这个'*'号
状态和Mininum Edit Distance这类题目一样dp[i][j]表示s[0:i-1]是否能和p[0:j-1]匹配
递推公式由于只有p中会含有regular expression所以以p[j-1]来进行分类p[j-1] != '.' p[j-1] != '*'dp[i][j] = dp[i-1][j-1] (s[i-1] == p[j-1])p[j-1] == '.'dp[i][j] = dp[i-1][j-1]
而关键的难点在于 p[j-1] = '*'由于星号可以匹配01乃至多个p[j-2]1. 匹配0个元素即消去p[j-2]此时p[0: j-1] = p[0: j-3]dp[i][j] = dp[i][j-2]
2. 匹配1个元素此时p[0: j-1] = p[0: j-2]dp[i][j] = dp[i][j-1]
3. 匹配多个元素此时p[0: j-1] = { p[0: j-2], p[j-2], ... , p[j-2] }dp[i][j] = dp[i-1][j] (p[j-2]=='.' || s[i-2]==p[j-2])
1 2 3 4 5 6 7 8 910111213141516171819202122232425262728
class Solution {public: bool isMatch(const char *s, const char *p) { int m = strlen(s), n = strlen(p); vectorvectorbool dp(m+1, vectorbool(n+1,false)); dp[0][0] = true; for(int i=0; i=m; i++) { for(int j=1; j=n; j++) { if(p[j-1]!='.' p[j-1]!='*') { if(i0 s[i-1]==p[j-1] dp[i-1][j-1]) dp[i][j] = true; } else if(p[j-1]=='.') { if(i0 dp[i-1][j-1]) dp[i][j] = true; } else if(j1) { //'*' cannot be the 1st element if(dp[i][j-1] || dp[i][j-2]) // match 0 or 1 preceding element dp[i][j] = true; else if(i0 (p[j-2]==s[i-1] || p[j-2]=='.') dp[i-1][j]) // match multiple preceding elements dp[i][j] = true; } } } return dp[m][n]; }};
思路2: 双指针扫描
LeetCode作者给的解法非常巧妙
http://leetcode.com/2011/09/regular-expression-matching.html8 comments: Labels:algorithm,dynamic programming,Leetcode,string,string match Thursday, November 27, 2014 [LeetCode] Max Points on a LineGivennpoints on a 2D plane, find the maximum number of points that lie on the same straight line.
思路
解这个平面几何题有3个要点
1. 如何判断共线?两点成一直线所以两点没有共线不共线之说对于点p1(x1, y1)p2(x2, y2)p3(x3, y3)来说共线的条件是p1-p2连线的斜率与p1-p3连线的斜率相同即(y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)所以对共线的n点其中任意两点连线的斜率相同
2. 如何判断最多的共线点?对于每个点p出发计算该点到所有其他点qi的斜率对每个斜率统计有多少个点符合其中最多的个数加1出发点本身即为最多的共线点
3. 特殊情况当x1 = x2y1!=y2时为垂直连线计算斜率时分母为0会出错当x1 = x2y1 = y2时两点重合则(x2, y2)和所有(x1, y1)的连线共线
1 2 3 4 5 6 7 8 9101112131415161718192021222324252627
class Solution {public: int maxPoints(vectorPoint points) { int maxPts = 0; for(int i=0; ipoints.size(); i++) { int nMax = 0, nSame = 0, nInf = 0; unordered_mapfloat,int comSlopes; for(int j=i+1; jpoints.size(); j++) { if(points[j].x==points[i].x) { if(points[j].y==points[i].y) nSame++; else nInf++; continue; } float slope = (float)(points[j].y-points[i].y)/(float)(points[j].x-points[i].x); comSlopes[slope]++; nMax = max(nMax, comSlopes[slope]); } nMax = max(nMax, nInf)+nSame+1; maxPts = max(maxPts,nMax); } return maxPts; }};1 comment: Labels:hash table,Leetcode,math Older PostsHomeSubscribe to:Posts (Atom)About MeYanbing ShiView my complete profileBlog Archive 2014(130) November(130)C++ Specific Questions - Overloading VS OverridingMicrosoft Onsite Interview Checklist基础data structure/algorithm列表面试中的clarifying questions[LeetCode] Wildcard Matching[LeetCode] Regular Expression Matching[LeetCode] Max Points on a Line[LeetCode] Word Ladder I, II[LeetCode新题] Intersection of Two Linked Lists[LeetCode] First Missing Positive[LeetCode] Simplify Path[LeetCode] LRU Cache[LeetCode] Merge Intervals[LeetCode] Insert Interval[LeetCode] Longest Valid Parentheses[LeetCode] Largest Rectangle in Histogram[LeetCode] Unique Binary Search Trees I, II[LeetCode] Distinct Subsequences[LeetCode] Longest Consecutive Sequence[LeetCode] Permutation Sequence[LeetCode] Next Permutation[LeetCode] Palindrome Partitioning I, II[LeetCode] Text Justification[LeetCode] Edit Distance[LeetCode] Decode Ways[LeetCode] ZigZag Conversion[LeetCode] Reverse Words in a String[LeetCode] Longest Palindromic Substring[LeetCode] Surrounded Regions[LeetCode] Set Matrix Zeroes[LeetCode] Unique Paths I, II[LeetCode] Triangle[LeetCode] Gas Station[LeetCode] Best Time to Buy and Sell Stock I, II, II[LeetCode] Jump Game I, II[LeetCode] Maximum Product Subarray[LeetCode] Maximum Subarray[LeetCode] Word Break I, II[LeetCode] Anagrams[LeetCode] Spiral Matrix I, II[LeetCode] Rotate Image[LeetCode] Climbing Stairs[LeetCode] Multiply Strings[LeetCode] Length of Last Word[LeetCode] Roman to Integer[LeetCode] Integer to Roman[LeetCode] String to Integer (atoi)[LeetCode] Count and Say[LeetCode] Longest Common Prefix[LeetCode] Palindrome Number[LeetCode] Reverse Integer[LeetCode] Plus One[LeetCode] Pascals Triangle I, II[LeetCode] Single Number I, II[LeetCode] Merge k Sorted Lists[LeetCode] Reverse Nodes in k-Group[LeetCode] Add Binary[LeetCode] Add Two Numbers[LeetCode] Swap Nodes in Pairs[LeetCode新题] Read N Characters Given Read4[LeetCode] Reverse Linked List II[LeetCode] Reorder List[Leetcode] Partition List[LeetCode] Rotate List[LeetCode] Clone Graph[LeetCode] Copy List with Random Pointer[LeetCode] Insertion Sort List[LeetCode] Merge Two Sorted Lists[LeetCode] Remove Duplicates from Sorted List I, II[LeetCode] Remove Nth Node From End of List[LeetCode] Valid Parentheses[LeetCode] Evaluate Reverse Polish Notation[LeetCode新题] Min Stack[LeetCode] Restore IP Addresses[LeetCode] Generate Parentheses[LeetCode] Word Search[LeetCode] Gray Code[LeetCode] Valid Sudoku, Sudoku Solver[LeetCode] N-Queens I, II[LeetCode] Letter Combinations of a Phone Number[LeetCode] Permutations I, II[LeetCode] Subsets I, II[LeetCode] Combination Sum I, II[LeetCode] Combinations[LeetCode] Substring with Concatenation of All Words[LeetCode] Implement strStr() - KMP解法[LeetCode] Merge Sorted Array[LeetCode新题] Binary Tree Upside Down[LeetCode] Trapping Rain Water[LeetCode] Linked List Cycle I, II[LeetCode] Minimum Window Substring[LeetCode] Longest Substring Without Repeating Cha...[LeetCode] Valid Palindrome[LeetCode] Remove Duplicates from Sorted Array I, II[LeetCode] Remove Element[LeetCode] Sort Colors[LeetCode] Container With Most Water[LeetCode] 4Sum[LeetCode] 3Sum Closest[LeetCode] 3Sum
TAGS:喜刷刷
<<< Thank you for your visit >>>
Websites to related : Java Hungry
keywords:
description:
-->Java HungryJava developers tutorials and coding.HOMESTRINGCOLLECTIONSINTERVIEWEXCEPTIONDATA-STRUCTURESOOPS THREADS BOOKS/C
keywords:田原市,うどん,そば
description:
あずみののホーム
keywords:?
description:
American Ethnography Quasimonthly is history.You can see some of our past glory in the Wayback Machine.
keywords:
description:The Open Definition - Open Definition - Defining Open in Open Data, Open Content and Open Knowledge
keywords:chandlery, yacht, sailing, yachting, offshore, keelboat, watersports, boating, mail order, purple, marine, purple marine, purplemarine. smock
mambolookcom keywords:
description:
keywords:
description:
Alan's Chemistry Site "If you're not part of the solution, you're part of the precipitate." -Henry J. Tillman
keywords:
description:
The Master Musicians of Joujouka Festival, Joujouka, Morocco, 5-7 June 2020Official Master Musicians of Joujouka Festival Blog,
keywords:
description:
brain of mat kelcey... high performance ML with JAX September 12, 2021 at 12:30 PM | categories:j
keywords:
description:
Hot Websites