每日一题(14)――找到符合要求的整数 - 小熊不去实验室 - 博客频道 - CSDN.NET


问题描述:
任意给定一个正整数N,求一个最小的整数M(M>1),使得M*N的十进制结果只含有1和0;
原问题可以转化为:求一个只含有1与0正整数,能被N整除;
观察X的取值:1,10, 11, 100, 101, 110, 111,1000……
再引入一个变量 j=X%N, 直接遍历X,
通过一个队列存储值和余数j,当j出现过时,乘以10,乘以10加1,跟余数相同的前面那个数效果一样,所以可以不计算。

  1. struct QNode  
  2. {  
  3.     int v,r;//v is value, r is remainder  
  4.     QNode(int vv, int rr): v(vv), r(rr){}  
  5.     QNode():v(0),r(0){}  
  6. };  
  7.   
  8. int main()  
  9. {  
  10.     int N;  
  11.     while(cin>>N)  
  12.     {  
  13.         queue<QNode> q;  
  14.         q.push(QNode(1,1));  
  15.         while(!q.empty())  
  16.         {  
  17.             vector<bool> bN(N,false);  
  18.             int s = q.size();  
  19.             while(s--)  
  20.             {  
  21.                 QNode t = q.front();  
  22.                 if(t.r==0)  
  23.                 {  
  24.                     cout<<"N:"<<N<<"  M:"<<t.v/N<<"  n*m:"<<t.v<<endl;  
  25.                     goto ok;  
  26.                 }  
  27.                 q.pop();  
  28.                 if(!bN[t.r*10 % N])  
  29.                 {  
  30.                     bN[t.r*10 % N] = true;  
  31.                     q.push(QNode(t.v*10, t.r*10 % N));  
  32.                 }  
  33.                 if(!bN[(t.r*10+1)%N])  
  34.                 {  
  35.                     bN[(t.r*10+1)%N] = true;  
  36.                     q.push(QNode((t.v*10+1), (t.r*10+1) % N));  
  37.                 }  
  38.             }  
  39.         }  
  40.         ok:;  
  41.     }  
  42.     return 0;  
  43. }  
问题描述:
是否能从数组中迅速找出两个数字使得这两个数字的和为一个给定的数字Sum。
2.对于每个数字a[i], 查找Sum-a[i]是否在数组中,已经变为一个查找问题:
可以先排序(只需一次),然后二分,O(N*logN)

或者hash映射,查找另一个数字是否在数组中,time:O(1), space:O(n)

3.先排序 time:O(N*logN);(排序算法总结
令i=0,j=n-1,看a[i]+a[j]是否等于Sum;
若大于Sum,j往前移j--, 若小于Sum,i往后移i++.

扩展问题:
1.若是“三个数字”呢?
对于“三个数字”其实就是对于数组中的每个数字array[i]判断数组中的其他数字是否存在两个数字的和为sum-array[i],以此递归下去。
2.若找不到满足条件的一对数字,问怎样找到最优解?
2. 如果找不到结果,可以保存做差的结果,找出差值最小的解

总结:
不论原序列是有序还是无序,解决这类题有以下三种办法:
1二分(若无序,先排序后二分),时间复杂度总为O(n*logn),空间复杂度为O(1);
2扫描一遍X-S[i] 映射到一个数组或构造hash表,时间复杂度为O(n),空间复杂度为O(n);
3两个指针两端扫描(若无序,先排序后扫描),时间复杂度最后为:有序O(n),无序O(n*logn+n)=O(n*logn),空间复杂度都为O(1)。所以,要想达到时间O(N),空间O(1)的目标,除非原数组是有序的(指针扫描法),不然,当数组无序的话,就只能先排序,后指针扫描法或二分(时间n*logn,空间O(1)),或映射或hash(时间O(n),空间O(n))。时间或空间,必须牺牲一个,自个权衡吧。
 综上,若是数组有序的情况下,优先考虑两个指针两端扫描法,以达到最佳的时(ON)),空(O1))效应。否则,如果要排序的话,时间复杂度最快当然是只能达到N*logN,空间O1.
Read full article from 每日一题(14)――找到符合要求的整数 - 小熊不去实验室 - 博客频道 - CSDN.NET

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts