題目

Find the largest palindrome made from the product of two n-digit numbers.
Since the result could be very large, you should return the largest palindrome mod 1337.

Example:

Input: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note:
The range of n is [1,8].

解題過程

這題要找出 N 位數相乘後且結果是迴文的數字
例如：N = 2 最大數字等於 99，那就要找出最大 99 最小 10 的兩位數相乘後且結果是迴文的數字。

最初我用一個很笨的方法迴圈慢慢跑，最後當然是直接逾時，後來改成先取最大數字相乘後的前半段數字，再用迴圈去產生迴文並篩選資料，這樣比前面的笨方法快非常多。
閱讀更多

題目

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and – as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

題目會傳入兩個參數 nums (數字陣列)、S (整數)，限制只能使用兩個運算符號 +、- 改變數字陣列 nums 的數字讓總和等於 S

解題過程

我自己比較少接觸演算法的東西(大學沒學好)，就算去翻解答也看不懂別人在寫什麼東西，後來看了 演算法筆記- Backtracking 的圖解後終於理解解答再寫什麼東西

閱讀更多

題目

You need to find the largest value in each row of a binary tree.

Example:

Input: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

Output: [1, 3, 9]

解題過程

這題要找出二元樹中同階層最大的數字，我的作法是先將每層的數字收集起來，最後再一起比較。

答案

Dictionary<int, List<int>> dict = new Dictionary<int, List<int>>();

public IList<int> LargestValues(TreeNode root)
{
    List<int> list = new List<int>();

    if (root == null)
    {
        return list;
    }

    list.Add(root.val);
    FindNum(0, root.left, root.right);
    list.AddRange(dict.Keys.Select(x => dict[x].Max()));

    return list;
}

public void FindNum(int idx, TreeNode left, TreeNode right)
{
    if (left == null && right == null)
    {
        return;
    }

    if (!dict.ContainsKey(idx))
    {
        dict[idx] = new List<int>();
    }

    if (left != null)
    {
        dict[idx].Add(left.val);
        FindNum(idx + 1, left.left, left.right);
    }

    if (right != null)
    {
        dict[idx].Add(right.val);
        FindNum(idx + 1, right.left, right.right);
    }
}

從傳入參數 haystack 中找出參數 needle 中的索引位置，非常基礎的一題

我的答案

public class Solution {
    public int StrStr(string haystack, string needle) {
        if(needle == null || needle == string.Empty){
            return 0;
        } else if(haystack == null){
            return -1;
        }
        
        return haystack.IndexOf(needle);
    }
}

輸入兩個 ListNode 物件並將兩個相同層數的數值加總，其值若超過 10 需進位到下個節點，這題我覺得迴圈解法比遞迴更讓人腦袋卡住，可能是我功力不夠吧。

我的遞迴解答：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        return Add(l1, l2, 0);
    }
    
    public ListNode Add(ListNode l1, ListNode l2, int addNum = 0)
    {
        if(l1 == null && l2 == null)
        {
            return null;                 
        }
        
        l1 = l1 ?? new ListNode(0);
        l2 = l2 ?? new ListNode(0);
        
        int i = (l1.val + l2.val) + addNum;
        ListNode totalNode = new ListNode(i % 10);
        if(l1.next != null || l2.next != null)
        {
            totalNode.next = Add(l1.next, l2.next, (i / 10));
        }
        
        if(i >= 10 && totalNode.next == null)
        {
            totalNode.next = new ListNode(1);
        }
             
        return totalNode;
    }
}

我的迴圈作法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        
        int sumValue = 0;
        int carryValue = 0;
        
        ListNode ansNode = new ListNode(-1);
        
        // 將 ansNode 的記憶體位置指向給 node
        ListNode node = ansNode;
        
        while(l1 != null || l2 != null)
        {
            sumValue = carryValue;
            
            if(l1 != null)
            {
                sumValue += l1.val;
                l1 = l1.next;
            }
            
            if(l2 != null)
            {
                sumValue += l2.val;
                l2 = l2.next;
            }
            
            carryValue = (sumValue / 10);
            if(carryValue > 0)
            {
                sumValue = (sumValue % 10);
                
                // 若大於 10 且 l1 與 l2 都沒有下個節點，那就自己創造一個
                if(l1 == null && l2 == null)
                {
                    l1 = new ListNode(0);
                }
            }
                        
            if(ansNode.val == -1)
            {
                ansNode.val = sumValue;
            }
            else
            {                
                node.next = new ListNode(sumValue);
                
                // 將當前物件 node.next 的記憶體位置指向到 node，這樣就可以達到一層一層改變 ansNode.next 值的效果
                node = node.next;
            }
        }
        
        return ansNode;
    }

    
}

外部輸入一個字串，若開頭為數字的話或 +- 符號的話則轉換為 int 的型態，且若超過 int 的最大或最小值則取極限值為準。

我的第一版答案如下：

public class Solution {
    public int MyAtoi(string str) {
        var arrNum = "0123456789".ToList();
        var arrSymbol = "-".ToList();

        if (string.IsNullOrWhiteSpace(str))
        {
            return 0;
        }
        else
        {
            str = str.Trim();
        }

        bool isFirstAddSymbol = (str[0] == '+');

        if (isFirstAddSymbol)
        {
            str = str.Substring(1);
        }

        if (string.IsNullOrWhiteSpace(str))
        {
            return 0;
        }

        bool isFirstNum = (arrNum.IndexOf(str[0]) != -1);
        bool isFirstSymbol = (arrSymbol.IndexOf(str[0]) != -1);

        if ((isFirstAddSymbol && isFirstSymbol) ||
            (!isFirstNum && !isFirstSymbol) ||
            (isFirstSymbol && str.All(x => arrNum.IndexOf(x) == -1)) ||
            (isFirstSymbol && str.Length > 1 && (arrNum.IndexOf(str[1]) == -1)))
        {
            return 0;
        }

        string numString = string.Empty;
        str = isFirstSymbol ? str.Substring(1) : str;

        for (int i = 0; i < str.Length; i++)
        {

            bool isNum = (arrNum.IndexOf(str[i]) != -1);

            if (!isNum)
            {
                break;
            }

            if (numString == "0")
            {
                numString = str[i].ToString();
            }
            else
            {
                numString += str[i].ToString();
            }

        }

        int maxValueLength = int.MaxValue.ToString().Length;
        long ans = int.MaxValue;

        bool isMoreMax = (numString.Length > maxValueLength) || (long.Parse(numString) > int.MaxValue);

        if (!isMoreMax)
        {
            ans = long.Parse(numString);
        }

        if (isFirstSymbol && isMoreMax)
        {
            ans += 1;
        }

        return Convert.ToInt32(isFirstSymbol ? -ans : ans);
    }
}

參考最佳解答後的優化版：

public class Solution {
    public int MyAtoi(string str) {
        str = (str ?? string.Empty).Trim();
        
        if (string.IsNullOrWhiteSpace(str))
        {
            return 0;
        }
        
        bool isMinusSign = (str[0] == '-');
        if (isMinusSign || (str[0] == '+'))
        {
            
            if ((str.Length == 1) ||
                ((str.Length > 1) && (str[1] < '0' || str[1] > '9')))
            {
                return 0;
            }
            
            str = str.Substring(1);
        }
        
        string numString = string.Empty;
        foreach (var item in str)
        {
            bool isNum = (item >= '0' && item <= '9');
            
            if (!isNum) {
                break;
            }
            
            if (numString == "0")
            {
                numString = item.ToString();
            }
            else
            {
                numString += item.ToString();
            }
        }
        
        if (numString == string.Empty)
        {
            return 0;
        }

        int maxValueLength = int.MaxValue.ToString().Length;
        long ans = int.MaxValue;

        bool isMoreMax = (numString.Length > maxValueLength) || (long.Parse(numString) > int.MaxValue);

        if (!isMoreMax)
        {
            ans = long.Parse(numString);
        }

        if (isMinusSign && isMoreMax)
        {
            ans += 1;
        }

        return Convert.ToInt32(isMinusSign ? -ans : ans);
    }
}