READMEOld.md

Today Update

(Notes: "♥" Welcome to visit or fork or star my LeetCode Manager @ https://github.com/jackzhenguo/LeetCodeManager

Sort

324 Wiggle Sort II

• Github:#324 Wiggle Sort II
• CSDN:#324 Wiggle Sort II
  • This is a great question for it involves a great idea: virtual index

  /// <summary>
   /// WiggleSort
   /// </summary>
   public class WiggleSortSln
   {
       private static int[] _array;
  
       public int[] WiggleSort(int[] array)
       {
           _array = array;
           int median = findKThLargest(_array.Length / 2);
           int left = 0, i = 0, right = _array.Length - 1;
  
           while (i <= right)
           {
               if (_array[newIndex(i)] > median)
               {
                   //put newIndex(i) at odd index(from 1, 3, to 5, ...)
                   swap(newIndex(left++), newIndex(i));
                   i++;
               }
               else if (_array[newIndex(i)] < median)
               {
                   //put newIndex(i) at even index(max even index to little .... ) 
                   swap(newIndex(right--), newIndex(i)); //right--, so i relatively toward right 1 step
               }
               else
               {
                   i++;
               }
           }
           return _array;
       }
  
       private int newIndex(int index)
       {
           return (1 + 2 * index) % (_array.Length | 1);
       }
  
       private void swap(int i, int j)
       {
           int tmp = _array[i];
           _array[i] = _array[j];
           _array[j] = tmp;
       }
  
       //based on quick sort to find the Kth largest in _array
       private int findKThLargest(int k)
       {
           int left = 0;
           int right = _array.Length - 1;
           while (true)
           {
               int pivotIndex = quickSort(left, right);
               if (k == pivotIndex)
                   return _array[pivotIndex];
               else if (k < pivotIndex)
                   right = pivotIndex - 1;
               else
                   left = pivotIndex + 1;
           }
       }
  
       private int quickSort(int lo, int hi)
       {
           int key = _array[lo];
           while (lo < hi)
           {
               while (lo < hi && _array[hi] >= key)
                   hi--;
               //hi is less than key, hi element moves to lo index
               _array[lo] = _array[hi];
               while (lo < hi && _array[lo] < key)
                   lo++;
               //lo is bigger than key, lo element moves to hi index 
               _array[hi] = _array[lo];
           }
           _array[lo] = key;
           return lo;
       }
   }

Bit Mainpulation

342 Power of Four

• Github:#342 Power of Four
• CSDN:#342 Power of Four

---

About it

Algorithm is tool for exercising our thinking patterns, and we can strengthen the ability to convert mathematical models into code. Whether you are engaged in artificial intelligence, in-depth learning, or advanced software development, no matter what language you use, such as C#,C++,Java,python,etc., and applying the most appropriate algorithm is always the most important point when faced with a specific problem. Every problem in practice has its own particularity, which makes it not that easier to choose the most appropriate algorithm. How do we write the algorithm that most efficiently apply to a practical issue? Yes, LeetCode. You can write an algorithm until it accepted, and do not rush to do the next question, and learn the solution someone else has submitted, so you can solve the problem from the ability of solving the problem to that fast and efficient realm.

I create this respository called leetcode-csharp because I apply C# language to solve LeetCode and every day will update it and also publish it in CSDN blog(http://blog.csdn.net/daigualu) my blog column(http://blog.csdn.net/column/details/14761.html) Also, I will put some algorithm ideas that famous scientists have created on My Wiki for this repository such as Flody tortoise and hare and KMP and so on.

Anyway, welcome to view, star and fork, then contribute.

Contributing

1. Fork it!
2. Create your feature branch: git checkout -b my-leetcode-csharp
3. Commit your changes: git commit -am 'Add some questions and better solutions'
4. Push to the branch: git push origin my-leetcode-csharp
5. Submit a pull request and enjoy! :D

Solution List

solutions using C# for leetcode according to tags of questions Tags are following:

• Array
• Hash Table
• Linked List
• Math
• Two Pointers
• String
• Binary Search
• Dynamic Programming
• Stack
• Tree

Details

Array

Number	Title(Blog URL)
35	Search Insert Position
118	Pascal's Triangle
119	Pascal's Triangle II
414	Third Maximum Number
121	Best Time to Buy and Sell Stock
66	Plus One
26	Remove Duplicates from Sorted Array
27	Remove Element
122	Best Time to Buy and Sell Stock II
268	Missing Number
217	Contains Duplicate
532	K-diff Pairs in an Array
189	Rotate Array
169	Majority Element
167	Two Sum II - Input array is sorted
88	Merge Sorted Array
53	Maximum Subarray
485	Max Consecutive Ones
283	Move Zeroes
448	Find All Numbers Disappeared in an Array
1	Two Sum
219	Contains Duplicate II
566	Reshape the Matrix
561	Array Partition I

532 K-diff Pairs in an Array

• Github:#532 K-diff Pairs in an Array
• CSDN:#532 K-diff Pairs in an Array

217 Contains Duplicate

• Github:#217 Contains Duplicate
• CSDN:#217 Contains Duplicate

448 Find All Numbers Disappeared in an Array

• Github:#448 Find All Numbers Disappeared in an Array
• CSDN:#448 Find All Numbers Disappeared in an Array

219 Contains Duplicate II

• Github:219 Contains Duplicate II
• CSDN:219 Contains Duplicate II

189. Rotate Array

• Github:189. Rotate Array
• CSDN:189. Rotate Array

448 Find All Numbers Disappeared in an Array

• Github:#448 Find All Numbers Disappeared in an Array
• CSDN: #448 Find All Numbers Disappeared in an Array

219 Contains Duplicate II

• Github: 485. Max Consecutive Ones
• CSDN: 485. Max Consecutive Ones

566 Reshape the Matrix

• Github:#566 Reshape the Matrix
• CSDN: #566 Reshape the Matrix

561 Array Partition I

• Github: #561 Array Partition I
• CSDN: #561 Array Partition I

Hash Table

• #136 Single number

• #1 Two Sum

• #447 Number of Boomerangs

• #463. Island Perimeter

• #409 Longest Palindrome

242 Valid Anagram

• Github:#242 Valid Anagram
• CSDN: #242 Valid Anagram

561 Array Partition I

• Github: #205 Isomorphic Strings
• CSDN: #205 Isomorphic Strings

438 Find All Anagrams in a String

• Github:#438 Find All Anagrams in a String
• CSDN:#438 Find All Anagrams in a String

204 Count Primes

• Github:#204 Count Primes
• CSDN:#204 Count Primes

500 Keyboard Row

• Github:#500 Keyboard Row
• CSDN:#500 Keyboard Row

389 Find the Difference

• Github:#389 Find the Difference
• CSDN:#389 Find the Difference

380 Insert Delete GetRandom O(1)

• Github:#380 Insert Delete GetRandom O(1)
• CSDN:#380 Insert Delete GetRandom O(1)

451 Sort Characters By Frequency

• Github:#451 Sort Characters By Frequency
• CSDN:#451 Sort Characters By Frequency
  • this problem solving is not by sorting order by frequency of chars! please read it.

575 Distribute Candies

• Github:#575 Distribute Candies
• CSDN:#575 Distribute Candies

381 Insert Delete GetRandom O(1) - Duplicates allowed

• Github:# 381 Insert Delete GetRandom O(1) - Duplicates allowed
• CSDN:#381 Insert Delete GetRandom O(1) - Duplicates allowed

Linked List

• #141 Linked List Cycle

• #237 Delete Node in a Linked List

• #83 Remove Duplicates from Sorted List

• #160 Intersection of Two Linked Lists

• #203 Remove Linked List Elements

• #206 Reverse Linked List

• #234 Palindrome Linked List

• #21 Merge Two Sorted Lists

Math

• #231 Power of Two

• #268 Missing Number

• #507 Perfect Number

7 Reverse Integer

• Github:#7 Reverse Integer
• CSDN:#7 Reverse Integer
• Tips:
  • an interesting way to check if happens overflow.

202 Happy Number

• Github:#202 Happy Number
• CSDN:#202 Happy Number
• Floyd's Tortoise and Hare
• reference:https://en.wikipedia.org/wiki/Cycle_detection

453 Minimum Moves to Equal Array Elements

• Github:#453 Minimum Moves to Equal Array Elements
• CSDN:#453 Minimum Moves to Equal Array Elements
• Tips:
  • using Math equation to solve this issue!

415 Add Strings

• Github:#415 Add Strings
• CSDN:#415 Add Strings
• Tips:
  • this is an interesting question!

400 Nth Digit

• Github:#400 Nth Digit
• CSDN:#400 Nth Digit
  • Tips:
    • careful to prevent overflowing for bas*digits, so declaring bas is long.

69 Sqrt(x)

• Github:#69 Sqrt(x)
• CSDN:#69 Sqrt(x)
  • Tips:
    • careful to prevent overflowing! Again careful to overflow!

9 Palindrome Number

• Github:#9 Palindrome Number
• CSDN:#9 Palindrome Number

171 Excel Sheet Column Number

• Github:#171 Excel Sheet Column Number
• CSDN:#171 Excel Sheet Column Number

258 Add Digits

• Github:#258 Add Digits
• CSDN:#258 Add Digits
  • Tips:
    • https://en.wikipedia.org/wiki/Digital_root#Congruence_formula
    • https://en.wikipedia.org/wiki/Vedic_square
  • In Indian mathematics, a Vedic square is a variation on a typical 9 × 9 multiplication table where the entry in each cell is the digital root of the product of the column and row headings i.e. the remainder when the product of the row and column headings is divided by 9 (with remainder 0 represented by 9). Numerous geometric patterns and symmetries can be observed in a Vedic square some of which can be found in traditional Islamic art.
    

263 Ugly Number

• Github:#263 Ugly Number
• CSDN:#263 Ugly Number

326 Power of Three

• Github:#326 Power of Three
• CSDN:#326 Power of Three

Two Pointers

• #345 Reverse Vowels of a String

• #283 Move Zeroes

• #88 Merge Sorted Array

#234Palindrome Linked List

String

• #58 Length of Last Word

• #20 Valid Parentheses

• #520 Detect Capital

• #459 Repeated Substring Pattern

• #434 Number of Segments in a String

• #14 Longest Common Prefix

• #383 Ransom Note

Binary Search

• #367 Valid Perfect Square

• #167 Two Sum II - Input array is sorted

• #441 Arranging Coins

• #278 First Bad Version

• #349 Intersection of Two Arrays 350. Intersection of Two Arrays II

• #349 Intersection of Two Arrays

Tree

• CSDN: #107 Binary Tree Level Order Traversal II

• CSDN: #257 Binary Tree Paths

• CSDN: #501 Find Mode in Binary Search Tree

• CSDN: #437 Path Sum III

• CSDN: #404 Sum of Left Leaves

• CSDN: #112 Path Sum

• CSDN: #110. Balanced Binary Tree

• CSDN: #108 Convert Sorted Array to Binary Search Tree

• CSDN: #543 Diameter of Binary Tree

• CSDN: #226 Invert Binary Tree

• CSDN: #235 Lowest Common Ancestor of a Binary Search Tree

• CSDN: #104 Maximum Depth of Binary Tree

• CSDN: #111 Minimum Depth of Binary Tree

• CSDN: #101 Symmetric Tree

• CSDN: #100 Same Tree

144 Binary Tree Preorder Traversal Stack version

• Github:#144 Binary Tree Preorder Traversal Stack version
• CSDN:#144 Binary Tree Preorder Traversal Stack version

94 Binary Tree Inorder Traversal Stack version

• Github:#94 Binary Tree Inorder Traversal Stack version
• CSDN:#94 Binary Tree Inorder Traversal Stack version

572 Subtree of Another Tree

• Github:#572 Subtree of Another Tree
• CSDN:#572 Subtree of Another Tree
  • Subtree of Another Tree: it's extended from problem of "is same tree".

103 Binary Tree Zigzag Level Order Traversal

• Github:#103 Binary Tree Zigzag Level Order Traversal
• CSDN:#103 Binary Tree Zigzag Level Order Traversal

95 Unique Binary Search Trees II

• Github:#95 Unique Binary Search Trees II
• CSDN:#95 Unique Binary Search Trees II
  • this is the famous "Catalan number", please reference https://en.wikipedia.org/wiki/Catalan_number
    • apply 1: valid stack oepration: ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd))
    • apply 2:
    • apply 3:
    • apply 4:

105 Construct Binary Tree from Preorder and Inorder Traversal

• Github:#105 Construct Binary Tree from Preorder and Inorder Traversal
• CSDN:#105 Construct Binary Tree from Preorder and Inorder Traversal
• Tips:
  • the most important function in solving this issue is
    • private TreeNode bulidTree(int preStart, int inStart, int inEnd) ;
  • Plus, preStart index in preorder is the root index, which is also the separate point in inorder and it’s left is left subtree and right is right subtree.