成功人士從不刷Leetcode(4)

大家好，我是Java程序員@矮米粒，接管我的朋友立黨的知乎帳號。

366. Find Leaves of Binary Tree(https://leetcode.com/problems/find-leaves-of-binary-tree/)

今天發現了一道新的送分題。思路很清晰，recursive的解法在下面。

class Solution {npublic:n int find_func(TreeNode* node, vector<vector<int>>& ret) {n if (!node) return -1;n int left = find_func(node->left, ret);n int right = find_func(node->right, ret);n if (ret.size() <= max(left,right) + 1) ret.push_back(vector<int>());n ret[ max(left,right) + 1].push_back(node->val);n return max(left,right) + 1;n }n vector<vector<int>> findLeaves(TreeNode* root) {n vector<vector<int>> ret;n find_func(root,ret);n return ret;n }n};n

169. Majority Element (https://leetcode.com/problems/majority-element/)

提示：由於提示了尋找一個佔有數量大於O? n/2 ?次數的數，因此不用hashmap，可以最少用O(N)的時間和O(1)的空間來機智地求解（我是看了別人的答案才學會這個奇技淫巧的，我自己的方法沒有這個靈巧）。具體思路是，設置一個major作為當前的majority，一個cnt用來計數，當讀取下一個數時，如果nums[i]和major相等，則計數器cnt++，否則cnt--，當cnt==0時將major替換成當前的nums[i]。因為真正的major的數量大於其他數的數量之和，因此總能保證最後一個major的cnt在全部讀取完時cnt>0。

class Solution {npublic:n int majorityElement(vector<int>& nums) {n int major = nums[0], cnt = 1; n for (int i=1;i<nums.size();i++) {n if (cnt == 0) { n major = nums[i];n cnt = 1;n }n else if (nums[i] == major) cnt++;n else cnt--;n }n return major;n }nn};n

237. Delete Node in a Linked List(https://leetcode.com/problems/delete-node-in-a-linked-list/)

class Solution {npublic:n void deleteNode(ListNode* node) {n *node = *node->next;n }nn};n

13. Roman to Integer (https://leetcode.com/problems/roman-to-integer/)

提示：從後向前讀取，如果該羅馬字母大於等於之前最大的羅馬字母，則在結果上加上該羅馬數字；如果該羅馬字母小於之前的最大羅馬字母，則在結果上減去該羅馬數字。

class Solution(object):n def romanToInt(self, s):n """n :type s: strn :rtype: intn """n d = {I:1,V:5,X:10,L:50,C:100,D:500,M:1000}n result = 0n s_max = 0n for i in range(len(s)-1,-1,-1):n if d[s[i]] >= s_max:n result += d[s[i]]n s_max = d[s[i]]n else:n result -= d[s[i]]nn return resultn

推薦閱讀：