June LeetCoding Challenge

machecazzo 发表于 2020-6-2 17:55
[mw_shl_code=python,true]class Solution:
    def deleteNode(self, node):
        """

只给node本身的话要怎么循环呀？

6/2 https://leetcode.com/problems/delete-node-in-a-linked-list/

1. var deleteNode = function(node) {
   
2.     node.val = node.next.val;
   
3.     node.next = node.next.next;
   
4. };

复制代码

Reborn2beCoder 发表于 2020-6-3 12:18
只给node本身的话要怎么循环呀？

好像这个题目要你删除第一个给的node，所以删除第一个。。

1. class Solution:
   
2.     def twoCitySchedCost(self, costs: List[List[int]]) -> int:  
   
3.         diff = sorted(costs, key = lambda x: x[0]-x[1])
   
4.         N = len(costs)//2
   
5.         total = 0
   
6.         for i in range(N):
   
7.             total+= diff[i][0]
   
8.         for j in range(N, 2*N):
   
9.             total += diff[j][1]
   
10.         return total

复制代码

第一反应dp，但是dp太慢了。

6/3 https://leetcode.com/problems/two-city-scheduling/
一开始看到题目有点懵逼，在纸上写写画画半天终于找到了灵感。Greedy类的问题真的很需要灵光一闪的瞬间lol

1. var twoCitySchedCost = function(costs) {
   
2.     if(!costs || !costs.length || !costs.length % 2) return 0;
   
3.     costs.sort((p1, p2) => p1[0] - p1[1] - (p2[0] - p2[1]));
   
4.     let sum = 0;
   
5.     costs.forEach((val, idx) => sum += idx < costs.length/2 ? val[0] : val[1]);
   
6.     return sum;
   
7. };

复制代码

ichwaredu 发表于 2020-6-3 18:37
[mw_shl_code=python,true]class Solution:
    def twoCitySchedCost(self, costs: List]) -> int:  
   ...

这个dp要怎么做呀？想了半天没找到思路。。

[size={"x":491,"y":1,"w":338,"h":24,"abs_x":515,"abs_y":419}][size={&quot;x&quot;:502,&quot;y&quot;:1,&quot;w&quot;:338,&quot;h&quot;:24,&quot;abs_x&quot;:526,&quot;abs_y&quot;:419}]Reborn2beCoder 发表于 2020-6-4 14:02
这个dp要怎么做呀？想了半天没找到思路。。

感觉没必要dp，单纯贪心就行了，我的解法就是楼上老哥的算法再优化一点，后面两个2/N的循环其实可以合成一个，但其实也没影响时间复杂度
另外吐槽一下今天的reverse string，货真价实的easy……

1. class Solution:
   
2.     def twoCitySchedCost(self, costs: List[List[int]]) -> int:
   
3.         costs.sort(key=lambda l:(l[0]-l[1]))
   
4.         res=0
   
5.         for i in range(0,len(costs)//2):
   
6.             res+=costs[i][0]+costs[len(costs)//2+i][1]
   
7.         return res

复制代码

Reborn2beCoder 发表于 2020-6-4 14:02
这个dp要怎么做呀？想了半天没找到思路。。

dp没有必要，超级慢。我找不到之前submit的code了，思路是从假设所有人都去B，选N个人去A，minimize cost

6/4 https://leetcode.com/problems/reverse-string/

1. var reverseString = function(s) {
   
2.     if(!s || s.length < 2) return;
   
3.     let i=0, j=s.length-1;
   
4.     while(i<j) {
   
5.         [s[i++], s[j--]] = [s[j], s[i]];
   
6.     }
   
7.     return;
   
8. };

复制代码

machecazzo 发表于 2020-6-4 01:01
Reborn2beCoder 发表于 2020-6-4 14:02
这个dp要怎么做呀？想了半天没找到思路。。

确实是lol 是怕一开始太难把大家劝退吗。。