Leetcode Part.2

20 Oct 2020 in Study on Writeup

Leetcode Part.2

Leetcode Part.2

前言

刷Leetcode的第二部分链表部分没有用go写感觉有点鸡肋

11. Container With Most Water

经典贪心算法左右两边两开花，从左右往中间遍历

// 24ms

class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size() < 2) return 0;
        int left = 0;
        int right = height.size() - 1;
        int area = 0;
        int maxArea = 0;
        while(left < right)
        {
            area = (height[left] < height[right] ? height[left] : height[right]) * (right - left);
            maxArea = area > maxArea ? area : maxArea;
            if(height[left] > height[right])
            {
                right--;
            }
            else
            {
                left++;
            }
        }
        return maxArea;
    }
};

//12ms
func maxArea(height []int) int {
    if len(height) < 2{
        return 0
    }
    left, right := 0, len(height) - 1
    area ,maxArea := 0, 0
    for(left < right){
        if height[left] < height[right]{
            area = height[left] * (right - left)
        } else {
            area = height[right] * (right - left)
        }
        if area > maxArea{
            maxArea = area
        } 
        if(height[left] > height[right]){
            right--
        } else {
            left++
        }
    }
    return maxArea;
}

12. Integer to Roman

由整数转成罗马数字类似于int to char 大概思路是从最大的位数开始分离原int数字中的内容，并同时在char中加入对应罗马文字

// 16ms
class Solution {
public:
    string intToRoman(int num) {
        string res = "";
        vector<int> value{1000,900,500,400,100,90,50,40,10,9,5,4,1};
        vector<string> symbol{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        for(int i = 0; i < value.size(); i++)
        {
            while(num >= value[i])
            {
                res += symbol[i];
                num -= value[i];
            }
        }
        return res;
    }
};

突然get到了go的坏处 go的map是无序的所有需要筛选才可以遍历
筛选map的效率还不如两个切片效率高

//8ms-20ms
import (
    "sort"
)

func intToRoman(num int) string {
	mapper := map[int]string{1000: "M", 900: "CM", 500: "D", 400: "CD", 100: "C", 90: "XC", 50: "L", 40: "XL", 10: "X", 9: "IX", 5: "V", 4: "IV", 1: "I"}
	var keys []int
    for k := range mapper {
        keys = append(keys, k)
    }
	sort.Ints(keys)
	
	var ret string
	for i := 12; i>=0; i-- {
		for num >= keys[i] {
			ret += mapper[keys[i]]
			num -= keys[i]
		}
	}
    return ret
}

//0-12ms avg.8ms
func intToRoman(num int) string {
	keys := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    values := []string{"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"}

	var ret string
	for i := range keys {
		for num >= keys[i] {
			ret += values[i]
			num -= keys[i]
		}
	}
	return ret
}

15. 3Sum

还记得2Sum吗，这道题可以看成先选定一个数字，再按照2Sum找后面两个值，但是这样会因为map的映射而少很多的结果，同时如果按照左右指针单纯寻找时会导致结果出现重复值，所以需要对重复值进行去除，同时，为了加快程序，应该先分析逻辑，进行合理的剪枝，在这里，减去了最小的数字大于0，最大的数字小于0的分支

// 72ms
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        if(nums.empty() || nums.front() > 0 || nums.back() < 0) return {};
        for(int k = 0; k < (int)nums.size() - 2; k++)
        {
            if(nums[k] > 0) break;
            if(k > 0 && nums[k - 1] == nums[k]) continue;
            int target = 0 - nums[k];
            int i = k + 1;
            int j = (int)nums.size() - 1;
            while(i < j)
            {
                if(nums[i] + nums[j] == target)
                {
                    res.push_back({nums[k], nums[i], nums[j]});
                    while(i < j && nums[i] == nums[i + 1]) i++;
                    while(i < j && nums[j] == nums[j - 1]) j--;
                    i++;
                    j--;
                }
                else if(nums[i] + nums[j] < target)
                {
                    i++;
                }
                else
                {
                    j--;
                }
            }
        }
        return res;
    }
};

//28ms
import (
	"sort"
)

func threeSum(nums []int) [][]int {
	if nums == nil || len(nums) < 3 {
		return nil
	}
	sort.Ints(nums)

	ans := [][]int{}
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] > 0 {
			break
		}
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		j := i + 1
		k := len(nums) - 1
		for j < k {
			sum := nums[i] + nums[j] + nums[k]
			if sum == 0 {
				ans = append(ans, []int{nums[i], nums[j], nums[k]})
				for j < k && nums[j] == nums[j+1] {
					j++
				}
				for j < k && nums[k] == nums[k-1] {
					k--
				}
				j++
				k--
			} else if sum > 0 {
				k--
			} else {
				j++
			}
		}
	}
	return ans
}

16. 3Sum Closest

这道题与上一题类似，但是需要加上绝对值逼近的思想

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int closest = nums[0] + nums[1] + nums[2];
        int diff = abs(target - closest);
        for(int k = 0; k < nums.size() - 2; k++)
        {
            int left = k + 1;
            int right = nums.size() - 1;
            while(left < right)
            {
                int temp = nums[k] + nums[left] + nums[right];
                int newDiff = abs(temp - target);
                if(newDiff < diff)
                {
                    closest = temp;
                    diff = newDiff;
                }
                if(temp > target)
                {
                    right--;
                }
                else if(temp < target)
                {
                    left++;
                }
                else
                {
                    return closest;
                }
            }
        }
        return closest;
    }
};

看了下别人写的感觉不如我这个好用我这个可以稳定4ms

//4ms
import (
	"math"
	"sort"
)

func threeSumClosest(nums []int, target int) int {
	for len(nums) < 3 || nums == nil {
		return 0
	}
	sort.Ints(nums)
	closest := nums[0] + nums[1] + nums[2]
	for i := range nums {
		j := i + 1
		k := len(nums) - 1
		for j < k {
			sum := nums[i] + nums[j] + nums[k]
			if sum == target {
				return sum
			}
			closestdiff := math.Abs(float64(closest - target))
			nowdiff := math.Abs(float64(sum - target))

			if nowdiff < closestdiff {
				closest = sum
			}
			if sum < target {
				j++
			}
			if sum > target {
				k--
			}
		}
	}
	return closest
}

17. Letter Combinations of a Phone Number

// 12ms 特别慢的速度
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return {};
        vector<string> res;
        vector<vector<string>> intermidiary{ {}, {}, {"a", "b", "c"}, {"d", "e", "f"}, {"g", "h", "i"}, {"j", "k", "l"}, {"m", "n", "o"}, {"p", "q", "r", "s"}, {"t", "u", "v"}, {"w", "x", "y", "z"} };
        vector<vector<string>> v;
        for(int i = 0; i < digits.size(); i++)
        {
            v.push_back(intermidiary[digits[i] - '0']);
        }
        DFS_searchres(v, res, 0, digits.length(), "");
        return res;
    }
    void DFS_searchres(vector<vector<string>> v, vector<string>& res, int level, int length, string out)
    {
        if(level == length)
        {
            res.push_back(out);
            return;
        }
        vector<string> s = v[level];
        for(int i = 0; i < s.size(); i++)
        {
            DFS_searchres(v, res, level + 1, length, out + s[i]);
        }
    }
};

学到了学到了。。。。

//0ms
func letterCombinations(digits string) []string {
	table := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	ret := []string{}
	if len(digits) > 0 {
		help(&ret, digits, "", 0, table)
	}
	return ret
}

func help(ret *[]string, digits string, cur string, index int, table []string) {
	if index == len(digits) {
		*ret = append(*ret, cur)
		return
	}
	tmp := table[digits[index]-48] //ascii to bumber
	for _, t := range tmp {
		help(ret, digits, cur+string(t), index+1, table)
	}
}

18. 4Sum

// 68ms 这道题类似前面几道题的思路，不过就是多套了一层循环，同时也需要合理剪枝
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        if(nums.size() < 4) return {};
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        for(int i = 0; i < nums.size() - 3; i++)
        {
            int t = target - nums[i];
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            for(int j = i + 1; j < nums.size() - 2; j++)
            {
                if(t < 0 && nums[j] > 0) break;
                if(t > 0 && nums[nums.size() - 1] < 0) return res;
                if(j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1;
                int right = nums.size() - 1;
                while(left < right)
                {
                    if(nums[j] + nums[left] + nums[right] == t)
                    {
                        res.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while(left < right && nums[left] == nums[left + 1]) left++;
                        while(left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    }
                    else if(nums[j] + nums[left] + nums[right] < t)
                    {
                        left++;
                    }
                    else
                    {
                        right--;
                    }
                }
            }
        }
        return res;
    }
};

自己的逻辑能力太差了写了估计几个小时还缺胳膊少腿的。。。

//8ms
import (
	"sort"
)

func fourSum(nums []int, target int) [][]int {
	if nums == nil || len(nums) < 4 {
		return nil
	}
	sort.Ints(nums)
	ret := [][]int{}
	for i := 0; i < len(nums)-3; i++ {
		newtarget := target - nums[i]
		if i > 0 && nums[i] == nums[i-1] {
			continue
		}
		for j := i + 1; j < len(nums)-2; j++ {
			if newtarget < 0 && nums[j] > 0 {
				break
			}
            if newtarget > 0 && nums[len(nums)-1] < 0 {
				return ret
			}
			if j > i+1 && nums[j] == nums[j-1] {
				continue
			}
			k := j + 1
			l := len(nums) - 1
			for k < l {
				allsum := nums[i] + nums[j] + nums[k] + nums[l]
				sum := nums[j] + nums[k] + nums[l]
				if allsum == target {
					ans := []int{nums[i], nums[j], nums[k], nums[l]}
					ret = append(ret, ans)
					for k < l && nums[k] == nums[k+1] {
						k++
					}
					for k < l && nums[l] == nums[l-1] {
						l--
					}

					k++
					l--
				} else if sum >= newtarget {
					l--
				} else {
					k++
				}
			}
		}

	}
	return ret
}

35. Search Insert Position

Easy easy ```cpp // 8ms class Solution { public:
int searchInsert(vector<int>& nums, int target) {
    if(nums.size() < 1) return 0;
    int res = 0;
    while(res < nums.size() && nums[res] < target)
    {
        res++;
    }
    return res;
} }; ``` 快乐排序。。。 ```go //4ms import (
"sort" )

func searchInsert(nums []int, target int) int { nums = append(nums,target) sort.Ints(nums) for i,v := range nums{ if v == target{ return i } } return 0 }

试了一下另一种写法 发现无论是速度还是内存 没有任何的提升
```go
//4ms
func searchInsert(nums []int, target int) int {
	if len(nums) < 1 {
		return 0
	}
	var i int
	for i < len(nums) && nums[i] < target {
		i++
	}
	return i
}

53. Maximum Subarray

// 16ms 解法一O(n)
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int Curmax = 0;
        for(int num: nums)
        {
            Curmax = std::max(Curmax + num, num);
            res = std::max(Curmax, res);
        }
        return res;
    }
};

// 28ms 解法二 分治 不见得就加快了...
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        return find_max(nums, 0, (int)nums.size() - 1);
    }
    
    int find_max(vector<int>& nums, int left, int right)
    {
        if(left >= right) return nums[left];
        int mid = left + (right - left) / 2;
        int lmax = find_max(nums, left, mid - 1);
        int rmax = find_max(nums, mid + 1, right);
        int mmax = nums[mid];
        int t = mmax;
        for(int i = mid - 1; i >= left; i--)
        {
            t += nums[i];
            mmax = max(mmax, t);
        }
        t = mmax;
        for(int i = mid + 1; i <= right; i++)
        {
            t += nums[i];
            mmax = max(mmax, t);
        }
        return max(mmax, max(lmax, rmax));
    }
};

朴素的解法

//4ms
func maxSubArray(nums []int) int {
	max := math.MinInt32
	tmp := 0
	for _, v := range nums {
		if tmp > 0 {
			tmp += v
		} else {
			tmp = v
		}
		if max < tmp {
			max = tmp
		}
	}
	return max
}

用了分治似乎也没什么提升

//4ms
func maxPart(nums []int, left int, right int) int {
	if left == right {
		return nums[left]
	}
	if left > right {
		return math.MinInt32
	}
	mid := (left + right) >> 1 //右移一位相当于除以二
	maxLeft := maxPart(nums, left, mid-1)
	maxRight := maxPart(nums, mid+1, right)
	partLeftMax := 0
	partRightMax := 0
	sum := 0
	for i := mid - 1; i >= left; i-- {
		sum += nums[i]
		if sum > partLeftMax {
			partLeftMax = sum
		}
	}
	sum = 0
	for i := mid + 1; i <= right; i++ {
		sum += nums[i]
		if sum > partRightMax {
			partRightMax = sum
		}
	}
	partMidMax := partLeftMax + partRightMax + nums[mid]
	tmp := 0
	if maxLeft > maxRight {
		tmp = maxLeft
	} else {
		tmp = maxRight
	}
	if tmp < partMidMax {
		tmp = partMidMax
	}
	return tmp
}

func maxSubArray(nums []int) int {
	return maxPart(nums, 0, len(nums)-1)
}

67. Add Binary

 这道题类似于前面做过的那道链表加法的题

//	8 ms
class Solution {
public:
    string addBinary(string a, string b) {
        if(a.empty()) return b;
        if(b.empty()) return a;
        int length_a = a.length() - 1;
        int length_b = b.length() - 1;
        string res = "";
        int flag = 0;
        while(length_a >= 0 || length_b >= 0)
        {
            int var_1 = length_a >= 0 ? (a[length_a] - '0') : 0;
            int var_2 = length_b >= 0 ? (b[length_b] - '0') : 0;
            int t = var_1 + var_2 + flag;
            flag = t / 2;
            t = t % 2;
            res = to_string(t) + res;
            if(length_a >= 0) length_a--;
            if(length_b >= 0) length_b--;
        }
        if(flag) res = "1" + res;
        return res;
    }
};

70. Climbing Stairs

经典爬梯子题

// 0ms 不出所料，用递归直接当场螺旋爆炸了，这个方法我是真的忘记了，勉强算是dp的（其实算不上）
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;
        vector<int> dp(n);
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2; i < n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
};

没搞懂原理。。。放在这膜拜吧。。。

//0ms 1.9mb all 100%
func climbStairs(n int) int {
	a, b := 1, 1
	n--
	for n > 0 {
		n--
		b = b + a
		a = b - a
	}
	return b
}

83. Remove Duplicates from Sorted List

Easy ```cpp // 16ms class Solution { public:
ListNode* deleteDuplicates(ListNode* head) {
    ListNode* curPoint = head;
    while(curPoint && curPoint->next)
    {
        while(curPoint->next  && curPoint->val == curPoint->next->val)
        {
            ListNode* p = curPoint->next;
            curPoint->next = curPoint->next->next;
            delete p;
        }
        curPoint = curPoint->next;
    }
    return head;
} }; ``` ```go

## 100. Same Tree
    看到树直接递归就完事了
```cpp
// 0ms
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        if((p && !q) || (!p && q) || (p->val != q->val)) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

101. Symmetric Tree

这道题还是树，自然而然想到递归，但是这道题要注意的是树的左右两边要对称，所以遍历的时候应该注意左右子树分开同时遍历 ```cpp // 0ms class Solution { public:
bool isSymmetric(TreeNode* root) {
    if(!root) return true;
    return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode* left, TreeNode* right)
{
    if(!left && !right) return true;
    if(left && !right || right && !left || right->val != left->val) return false;
    return isSymmetric(left->right, right->left) && isSymmetric(left->left, right->right);
} }; ```

104. Maximum Depth of Binary Tree

Easy 看到树还是递归就行，注意使用递归对深度进行保存 ```cpp class Solution { public:
int maxDepth(TreeNode* root) {
    if(!root) return 0;
    return max(curDepth(root->left, 1), curDepth(root->right, 1));
}
int curDepth(TreeNode* node, int depth)
{
    if(!node) return depth;
    depth++;
    return max(curDepth(node->left, depth), curDepth(node->right, depth));
} }; ```

107. Binary Tree Level Order Traversal II

看到树递归就完事了,不过我这个速度实在是垃圾 ```cpp // 8ms class Solution { public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
    if(!root) return {};
    vector<vector<int>> res;
    foreach_tree(res, root, 0);
    return vector<vector<int>> (res.rbegin(), res.rend());
}
void foreach_tree(vector<vector<int>>& res, TreeNode* node, int depth)
{
    if(!node) return;
    if(res.size() == depth) res.push_back({});
    if(node->left) foreach_tree(res, node->left, depth + 1);
    if(node->right) foreach_tree(res, node->right, depth + 1);
    res[depth].push_back(node->val);
} }; ```

108. Convert Sorted Array to Binary Search Tree

把一个数组变成二叉排序树
这道题如果以前没有接触过二分法之类的还是挺难的，因为它要求要左右子树度差不大于1，就得用二叉法来做 ```cpp // 24ms class Solution { public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
    if(nums.empty()) return nullptr;
    int mid = nums.size() / 2;
    TreeNode* cur = new TreeNode(nums[mid]);
    vector<int> left(nums.begin(),nums.begin() + mid);
    vector<int> right(nums.begin() + mid + 1, nums.end());
    cur->left = sortedArrayToBST(left);
    cur->right = sortedArrayToBST(right);
    return cur;
} }; ```

Leetcode Part.2

Leetcode Part.2

前言

11. Container With Most Water

12. Integer to Roman

15. 3Sum

16. 3Sum Closest

17. Letter Combinations of a Phone Number

18. 4Sum

35. Search Insert Position

53. Maximum Subarray

67. Add Binary

70. Climbing Stairs

83. Remove Duplicates from Sorted List

101. Symmetric Tree

104. Maximum Depth of Binary Tree

107. Binary Tree Level Order Traversal II

108. Convert Sorted Array to Binary Search Tree

ZYA's Blog

Error

Leetcode Part.2

前言

11. Container With Most Water

12. Integer to Roman

15. 3Sum

16. 3Sum Closest

17. Letter Combinations of a Phone Number

18. 4Sum

35. Search Insert Position

53. Maximum Subarray

67. Add Binary

70. Climbing Stairs

83. Remove Duplicates from Sorted List

101. Symmetric Tree

104. Maximum Depth of Binary Tree

107. Binary Tree Level Order Traversal II

108. Convert Sorted Array to Binary Search Tree

Templates:

Error