### Get K-th Row of Pascal's Triangle - LeetCode 119 (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/notes/LeetCode第118号问题：杨辉三角.md

This Java code solves LeetCode Problem 119, which asks to return the k-th row of Pascal's Triangle with an optimized O(k) space complexity. Instead of generating the full triangle, it leverages a combinatorial property: the (i+1)-th element of row k can be derived from the i-th element using the formula current_element * (k - i) / (i + 1).

```java
class Solution {
  public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<>(rowIndex + 1);
        long index = 1;
        for (int i = 0; i <= rowIndex; i++) {
            res.add((int) index);
            index = index * ( rowIndex - i ) / ( i + 1 );
        }
        return res; 
  }
}
```

--------------------------------

### C++ Implementation of Autocomplete System using Trie and Priority Queue

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/0642-Design-Search-Autocomplete-System/Article/0642-Design-Search-Autocomplete-System.md

This C++ code defines an AutocompleteSystem class to implement the search autocomplete functionality. It utilizes a TrieNode structure to build a Trie for efficient prefix matching. Sentences are inserted into the Trie with their corresponding frequencies. The input method processes each character, traversing the Trie and using a custom comparator with a priority_queue to retrieve and sort the top 3 matching sentences by frequency and then ASCII order. The dfs helper function recursively collects all matching sentences from the current Trie node, and the insert function adds new sentences or updates existing ones.

```C++
class TrieNode{
  public:
    string str;
    int cnt;
    unordered_map<char, TrieNode*> child;
    TrieNode(): str(""), cnt(0){};
};

struct cmp{
    bool operator() (const pair<string, int> &p1, const pair<string, int> &p2){
        return p1.second < p2.second || (p1.second == p2.second && p1.first > p2.first);
    }
};

class AutocompleteSystem {
public:
    AutocompleteSystem(vector<string> sentences, vector<int> times) {
        root = new TrieNode();
        for(int i = 0; i < sentences.size(); i++){
            insert(sentences[i], times[i]);
        }
        curNode = root;
        stn = "";
    }
    
    vector<string> input(char c) {
        if(c == '#'){
            insert(stn, 1);
            stn.clear();
            curNode = root;
            return {};
        }
        stn.push_back(c);
        if(curNode && curNode->child.count(c)){
            curNode = curNode->child[c];
        }else{
            curNode = NULL;
            return {};
        }
        
        dfs(curNode);
        
        vector<string> ret;
        int n = 3;
        while(n > 0 && !q.empty()){
            ret.push_back(q.top().first);
            q.pop();
            n--;
        }
        while(!q.empty()) q.pop();
        
        return ret;
    }
    
    void dfs(TrieNode* n){
        if(n->str != ""){
            q.push({n->str, n->cnt});
        }
        for(auto p : n->child){
            dfs(p.second);
        }
    }
    
    void insert(string s, int cnt){
        TrieNode* cur = root;
        for(auto c : s){
            if(cur->child.count(c) == 0){
                cur->child[c] = new TrieNode();
            }
            cur = cur->child[c];
        }
        cur->str = s;
        cur->cnt += cnt;
    }
    
private:
    TrieNode *root, *curNode;
    string stn;
    priority_queue<pair<string,int>, vector<pair<string, int>>, cmp > q;
    
};
```

--------------------------------

### Solve Perfect Squares using Breadth-First Search (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/notes/LeetCode第279号问题：完全平方数.md

This Java code provides an alternative solution using Breadth-First Search (BFS). It treats the problem as finding the shortest path in a graph where nodes are numbers and edges represent subtracting a perfect square. It uses a LinkedList as a queue to manage states (current number, steps) and a boolean array 'visited' to prevent redundant computations. The algorithm returns the minimum steps when the target number 0 is reached.

```java
import java.util.LinkedList;
import javafx.util.Pair;
class Solution {
    public int numSquares(int n) {
         if(n == 0)
            return 0;
            
        LinkedList<Pair<Integer, Integer>> queue = new LinkedList<Pair<Integer, Integer>>();
        queue.addLast(new Pair<Integer, Integer>(n, 0));

        boolean[] visited = new boolean[n+1];
        visited[n] = true;

        while(!queue.isEmpty()){
            Pair<Integer, Integer> front = queue.removeFirst();
            int num = front.getKey();
            int step = front.getValue();

            if(num == 0)
                return step;

            for(int i = 1 ; num - i*i >= 0 ; i ++){
                int a = num - i*i;
                if(!visited[a]){
                    if(a == 0) return step + 1;
                    queue.addLast(new Pair(num - i * i, step + 1));
                    visited[num - i * i] = true;
                }
            }
        }
        return 0;
    }
}
```

--------------------------------

### Dynamic Programming States for Max Profit with Two Transactions (LeetCode 123)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/notes/LeetCode第121号问题：买卖股票的最佳时机.md

This section outlines the key dynamic programming states required to solve the problem of calculating maximum profit with at most two stock transactions. It defines four distinct states that track the profit after the first buy, first sell, second buy, and second sell, respectively. Understanding these states is crucial for formulating the state transition equations for this more complex dynamic programming problem.

```APIDOC
States for Best Time to Buy and Sell Stock III:
- fstBuy: Represents the maximum profit after the first buy transaction.
- fstSell: Represents the maximum profit after the first sell transaction.
- secBuy: Represents the maximum profit after the second buy transaction.
- secSell: Represents the maximum profit after the second sell transaction.
```

--------------------------------

### Majority Element: Hash Map Solution (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/0169-Majority-Element/Article/0169-Majority-Element.md

This solution uses a hash map to store the frequency of each number. It performs a single pass through the array, updating counts in the map and tracking the number with the highest frequency. This approach improves time complexity to O(n) but uses O(n) space for the hash map.

```Java
class Solution {
    public int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    // maxNum 表示元素，maxCount 表示元素出现的次数
    int maxNum = 0, maxCount = 0;
    for (int num: nums) {
      int count = map.getOrDefault(num, 0) + 1;
      map.put(num, count);
      if (count > maxCount) {
        maxCount = count;
        maxNum = num;
      }
    }
    return maxNum;
  }
}
```

--------------------------------

### Majority Element: Boyer-Moore Majority Vote Algorithm (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/0169-Majority-Element/Article/0169-Majority-Element.md

This highly efficient algorithm leverages the property that the majority element appears more than half the time. It maintains a candidate element and a counter. When iterating, if the current element matches the candidate, the counter increments; otherwise, it decrements. If the counter reaches zero, a new candidate is chosen. This method achieves optimal O(n) time complexity with O(1) space complexity.

```Java
class Solution {
    public int majorityElement(int[] nums) {
    int candidate = nums[0], count = 1;
    for (int i = 1; i < nums.length; ++i) {
      if (count == 0) {
        candidate = nums[i];
        count = 1;
      } else if (nums[i] == candidate) {
        count++;
      } else{
        count--;
      }
    }
    return candidate;
  }
}
```

--------------------------------

### Calculate Max Profit for Multiple Stock Transactions (LeetCode 122)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/notes/LeetCode第121号问题：买卖股票的最佳时机.md

This snippet calculates the maximum profit achievable from an unlimited number of stock transactions. Unlike the single transaction problem, here, a 'buy' state can follow a 'sell' state, enabling continuous trading. The dynamic programming approach maintains 'buy' and 'sell' states, updating them daily. The 'buy' state considers either holding a previously bought stock or buying a new one after a previous sale. The 'sell' state considers either holding a previously sold stock or selling a newly bought one. Initial boundary conditions are set for the first day.

```Java
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int buy = -prices[0], sell = 0;
        for(int i = 1; i < prices.length; i++) {
            sell = Math.max(sell, prices[i] + buy);
            buy = Math.max( buy,sell - prices[i]);
        }
        return sell;
    }
}
```

--------------------------------

### Solve Perfect Squares using Four-Square Theorem (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/notes/LeetCode第279号问题：完全平方数.md

This Java code implements a solution for the Perfect Squares problem based on the Four-Square Theorem and its corollary. It first reduces 'n' by repeatedly dividing by 4. Then, it checks if the reduced 'n' satisfies the '8b + 7' condition, which implies a result of 4. Otherwise, it attempts to find if 'n' can be represented as the sum of one or two perfect squares, returning 1 or 2 accordingly. If none of these conditions are met, the result is 3.

```java
public int numSquares(int n) {
        while (n % 4 == 0){
            n /= 4;
        }
        if ( n % 8 == 7){
            return 4;
        }
        int a = 0;
        while ( (a * a) <= n){
            int b = (int)Math.pow((n - a * a),0.5);
             if(a * a + b * b == n) {
            //如果可以 在这里返回
            if(a != 0 && b != 0) {
                return 2;
            } else{
                return 1;
            }
        }
        a++;
     }
        return 3;
}
```

--------------------------------

### Calculate Max Profit for Single Stock Transaction (LeetCode 121)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/notes/LeetCode第121号问题：买卖股票的最佳时机.md

This snippet calculates the maximum profit achievable from at most one stock transaction. It employs dynamic programming to track the maximum profit by considering two states: 'buy' (representing the maximum money one could have after buying a stock, thus a negative value) and 'sell' (representing the maximum profit after selling a stock). The state transition equations update these values daily, and the final 'sell' value represents the overall maximum profit. Initial boundary conditions are set for the first day.

```Java
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int buy = -prices[0], sell = 0;
        for(int i = 1; i < prices.length; i++) {
            buy = Math.max(buy, -prices[i]);
            sell = Math.max(sell, prices[i] + buy);
        
        }
        return sell;
    }
}
```

--------------------------------

### Generate Pascal's Triangle - LeetCode 118 (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/notes/LeetCode第118号问题：杨辉三角.md

This Java code implements a solution to LeetCode Problem 118, which requires generating the first numRows of Pascal's Triangle. The algorithm initializes each row with 1s at the beginning and end, and calculates intermediate values by summing the two numbers directly above them from the previous row. It returns a list of lists representing the triangle.

```java
class Solution {
    public List<List<Integer>> generate(int numRows) {
        
     List<List<Integer>> result = new ArrayList<>();
     if (numRows < 1) return result;

    for (int i = 0; i < numRows; ++i) {
      //扩容
      List<Integer> list = Arrays.asList(new Integer[i+1]);
      list.set(0, 1); list.set(i, 1);
      for (int j = 1; j < i; ++j) {
        //等于上一行的左右两个数字之和
        list.set(j, result.get(i-1).get(j-1) + result.get(i-1).get(j));
      }
      result.add(list);
     }
    return result;   
        
    }
}
```

--------------------------------

### Python Solution for LeetCode 6 Zigzag Conversion

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/0006-ZigZag Conversion/Article/0006-ZigZag Conversion.md

This Python solution implements the zigzag conversion algorithm. It initializes a list of strings to represent each row, then iterates through the input string, appending characters to the current row. It manages a `cur_row` index and a `forward` boolean to control the direction of movement (down or up) between rows, switching direction when `cur_row` reaches 0 or `numRows - 1`. Finally, it concatenates all row strings to form the result.

```Python
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        # 记录每一行摆放的字母
        rows = ['' for _ in range(numRows)]
        # 记录当前行号
        cur_row = 0
        # 记录当前摆放顺序是否从上往下， False代表从下往上
        forward = True
        # numRows = 1直接返回
        if numRows == 1:
            return s
        
        for i, c in enumerate(s):
            rows[cur_row] += c
            # 根据顺序变更行号
            if forward:
                cur_row += 1
            else:
                cur_row -= 1
            # 根据行号和当前顺序判断需不需要转向
            if cur_row == numRows - 1 and forward:
                forward = False
            
            if cur_row == 0 and not forward:
                forward = True
            
        ret = ''
        for sc in rows:
            ret += sc
        return ret
```

--------------------------------

### Java Solution for Median of Two Sorted Arrays (O(log(m+n)))

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/0004-median-of-two-sorted-arrays/Article/0004-median-of-two-sorted-arrays.md

This Java code implements an efficient O(log(m+n)) solution for finding the median of two sorted arrays. It first ensures `nums1` is the shorter array to optimize the binary search. The algorithm performs a binary search on `nums1` to find a partition point (`count1`) such that, when combined with a corresponding partition point in `nums2` (`count2`), the elements in the left half of the merged array are less than or equal to those in the right half. It correctly identifies the median for both odd and even total lengths of the combined arrays, handling edge cases where one partition might be empty or at the array's boundary. The `isOdd` helper function checks for odd numbers.

```Java
public class Solution {
  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // 使nums1成为较短数组,不仅可以提高检索速度,同时可以避免一些边界问题
    if (nums1.length > nums2.length) {
      int[] temp = nums1;
      nums1 = nums2;
      nums2 = temp;
    }

    int len1 = nums1.length;
    int len2 = nums2.length;
    int leftLen = (len1 + len2 + 1) / 2; //两数组合并&排序后,左半边的长度
    
    // 对数组1进行二分检索
    int start = 0;
    int end = len1;
    while (start <= end) {
      // 两个数组的被测数A,B的位置(从1开始计算)
      // count1 = 2 表示 num1 数组的第2个数字
      // 比index大1
      int count1 = start + ((end - start) / 2);
      int count2 = leftLen - count1;
      
      if (count1 > 0 && nums1[count1 - 1] > nums2[count2]) {
        // A比B的next还要大
        end = count1 - 1;
      } else if (count1 < len1 && nums2[count2 - 1] > nums1[count1]) {
        // B比A的next还要大
        start = count1 + 1;
      } else {
        // 获取中位数
        int result =  (count1 == 0)? nums2[count2 - 1]: // 当num1数组的数都在总数组右边
                      (count2 == 0)? nums1[count1 - 1]: // 当num2数组的数都在总数组右边
                      Math.max(nums1[count1 - 1], nums2[count2 - 1]); // 比较A,B
        if (isOdd(len1 + len2)) {
          return result;
        }

        // 处理偶数个数的情况
        int nextValue = (count1 == len1) ? nums2[count2]:
                        (count2 == len2) ? nums1[count1]:
                        Math.min(nums1[count1], nums2[count2]);
        return (result + nextValue) / 2.0;
      }
    }

    return Integer.MIN_VALUE; // 绝对到不了这里
  }

  // 奇数返回true,偶数返回false
  private boolean isOdd(int x) {
    return (x & 1) == 1;
  }
}
```

--------------------------------

### Majority Element: Brute Force Solution (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/0169-Majority-Element/Article/0169-Majority-Element.md

This solution iterates through the array for each element to count its occurrences. If an element's count exceeds half the array's length, it is returned. This approach has a time complexity of O(n^2) due to nested loops and a space complexity of O(1).

```Java
class Solution {
    public int majorityElement(int[] nums) {
        int majorityCount = nums.length/2;

        for (int num : nums) {
            int count = 0;
            for (int elem : nums) {
                if (elem == num) {
                    count += 1;
                }
            }
            if (count > majorityCount) {
                return num;
            }

        }  
    }
}
```

--------------------------------

### Detect Cycle in Linked List using Fast and Slow Pointers (Java)

Source: https://github.com/misterbooo/leetcodeanimation/blob/master/0141-Linked-List-Cycle/Article/0141-Linked-List-Cycle.md

This Java code implements the fast and slow pointer algorithm to determine if a given linked list contains a cycle. The slow pointer moves one step at a time, while the fast pointer moves two steps. If they meet, a cycle exists; if the fast pointer reaches the end (null), no cycle is present. This solution achieves O(1) space complexity.

```Java
//author:程序员小吴
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
}
```

=== COMPLETE CONTENT === This response contains all available snippets from this library. No additional content exists. Do not make further requests.