zuisixian / leetcode Goto Github PK

• 完成401题

• 404 Sum of Left leaves

直接使用递归，3行就可以解决.

-[] 可以使用循环或者BFS来做？

-[] 使用python来做？

• 405 Convert a Number to Hexadecimal

count++<8 因为每次处理4为，int总共32位，一共8次就可以处理完。 0xF的二进制为0b1111, 所以每四位bits&0xf就等于他自己。

• 406. Queue Reconstruction by Height

思路

先把身高最高的先排序，k值大的靠后。 然后把第二高的插入进去。 依次第三、第四...完成排序。

• 409. Longest Palindrome

统计数量为奇数的字符，然后用总的字符减去这些数量再+(奇数>0)

• 412. Fizz Buzz 比较简单，可以看看C语言/python怎么写的。

• 415 Add Strings

直接从低位(string中索引最高)相加，最后reverse。

• 43 Multiply Strings 之前校招已经刷过一次，有时间再刷一回

参考blog

• 414 Third Maximum Number

需要熟练使用标准库，set刚好非常适用于此题。也可以适用vector,自己手动维护里面3个值得大小顺序。

• 416. Partition Equal Subset Sum

bits的第i位为1的话表示此数组里面存在组合使得该组合的和为i。

• 434. Number of Segments in a String

这个题比较简单

• 417. Pacific Atlantic Water Flow DFS算法，需要好好研究相关问题

待完成

• 448. Find All Numbers Disappeared in an Array

同442Find All Duplicates in an Array 遍历 index为value-1处将value置位相反数，那么1-n中没有遍历的index初的值就还是正数，这些值就是nums中没有出现的值。

• 423. Reconstruct Original Digits from English

找到每个数字英文字母的特殊性，也就是独有的字母，如果字母非独有，那就总数减去已知数字中含有该字母的数量。

• 453. Minimum Moves to Equal Array Elements solution 数学问题

• 443. String Compression solution

• 445. Add Two Numbers II

solution

• 402. Remove K Digits

Solution

• 403. Frog Jump solution

TODO:使用DFS 外加 map来记录在每个位置不同步长情况下是否能到达对端。 map<int,bool> m; key = i + step<<11;

• 437. Path Sum III solution

使用递归方法

• 438. Find All Anagrams in a String solution

• 441. Arranging Coins solution

• 442. Find All Duplicates in an Array solution

• 697. Degree of an Array

solution

• 450. Delete Node in a BST solution

• 654. Maximum Binary Tree TODO 复习map相关用法 使用stack，维持stack里面是降序的，也就是第一个数(栈底)是最大的(root)，然后新的数与栈顶-->栈底的数以此比较，如果新的数较小，直接push_back，设为栈顶数的rightchild,如果比栈的数大，这栈的数为新数的leftchild，pop_back，然后push_back新数。 solution

669. Trim a Binary Search Tree solution

653. Two Sum IV - Input is a BST soluiton

二叉搜索树

538. Convert BST to Greater Tree solution inorder search

572. Subtree of Another Tree solution

TODO 月度总结

455. Assign Cookies

solution todo复习[priority_queue](notes/priority_queue学习总结.md)用法

454. 4Sum II solution pysolution

todo:Python Algorithm: Mastering Basic Algorithms in the Python Language

658. Find K Closest Elements solution 二分法查找arr[index]，比arr[index+k]离x更近。

567. Permutation in String solution

参考

446. Arithmetic Slices II - Subsequence

cpp solution

python solution

DP[i][d] = the number of arithmetic subsequences ending with A[i], difference is d. (NOTE here the length of valid subsequences can be 2)

参考

463. Island Perimeter solution

695. Max Area of Island solution

747. Largest Number At Least Twice of Others solution

561. Array Partition I solution

TODO 复习multiset的用法。

458. Poor Pigs

solution

好惨的猪。。

prepare to go home!

2018年，开工！

476. Number Complement

solution

1. 使用mask来标记leading zero.
2. 按位XOR(i<<num).

485. Max Consecutive Ones solution

for (auto& item:nums)
{
    sum = (sum+item)* item;// so brilliant
    if(max<sum){max=sum;}
}
//so clover

500. Keyboard Row solution

class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        return filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match,words)

**TODO** `(?i)`是什么意思

• 482. License Key Formatting solution

从end->start处理然后再reverse。

• 496. Next Greater Element I solution

• 504. Base 7 solution

• 507. Perfect Number solution

• 520. Detect Capital

solution

• 可以使用正则表达式 regex_match(word, regex("[A-Z]+|[a-z]+|[A-Z][a-z]*"))

• 541. Reverse String II

solution

• 543. Diameter of Binary Tree

solution

• 515. Find Largest Value in Each Tree Row

solution

• 576. Out of Boundary Paths

solution

• 501. Find Mode in Binary Search Tree

solution

• 551. StudentAttendanceRecordI

思路： 直接判断是否有两个A或者连续3个L

solution

• 552. Student Attendance Record II

思路:动态规划，太难了。。

solution

• 553. Optimal Division

思路:

1. 这个答案是固定的，x1/x2/x3..../xn,其中x1肯定是被除数，x2肯定是除数，要想最大化，就需要将x3,x4 , x5 都是成绩，也就是这样的结果： x1/(x2/x3/.../xn) = x1/x2 x3 x4* ...* xn;
2. 可以使用动态规划

solution

• 554.Brick Wall

思路: 对每行从左到右记录每块砖的累计长度，用map来表示每个距离出现的次数，遍历所有行，得到每个距离与其出现的次数，取最大者，用总函数减去该值即可

solution

• 506. Relative Ranks

思路:使用优先队列来排序，存储nums[i]和其位置i

solution

• 547. Friend Circles

思路:

1. 动态规划
2. todo:并查集

solution

• 513. Find Bottom Left Tree Value

思路:

1. 从右往左边，宽度优先搜索加入队列中，则队列中最后的指就是最底层中最左边的值。
2. 深度优先搜索，同depth中只取最左边的值。

solution

• 526. Beautiful Arrangement 思路:在每个位置尝试每个number,使用dfs来遍历，已经遍历过的数组用visited数组来标记，知道全部完成遍历

solution

• 557. Reverse Words in a String III 思路:

1. 使用streamstream来分割字符串.

solution

• 592. Fraction Addition and Subtraction

思路:

1. 使用streamstream来分割字符串.可以直接把-1/2分成int:-1, char:/, int:2，也就是分子分母都出来了
2. 每个分式运算时，都是不可约简的，则可以直接算出结果，然后共同除以分子分母的最大公约数即可

solution

• 746. Min Cost Climbing Stairs

思路 动态规划

递推公式为： val[i] = min(val[i-1] + cost[i-1], val[i-2] + cost[i-2])

注意初始值val[0], val[1]都为0

solution

• 638. Shopping Offers

思路

DFS

记得递归调用返回时恢复修改的内容，使得回到上层时内容保持不变

solution

• 690. Employee Importance

思路

• 此题比较简单，先从employees这个List遍历查找到需要的id，然后加上自身的importance, 再从subordinates中遍历，对该list中的值递归调用本函数即可。

• 思路2：先对employees这个List建立id到employee的Hash映射表，这样更方便查找。

• 思路3：将id加入Queue中，然后循环，直到该queue为空为止。

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = employees.stream()
            .collect(Collectors.toMap(e -> e.id, e -> e));
        Queue<Integer> ids = new LinkedList<>();
        ids.add(id);
        int result = 0;
        while (!ids.isEmpty()) {
            id = ids.remove();
            Employee e = map.get(id);
            result += e.importance;
            e.subordinates.stream().forEach(s -> ids.add(s));
        }
        return result;
    }
}

• 721. Accounts Merge

思路

• 并查集
• DFS

solution

• 752. Open the Lock

思路

• BFS

solution

• 733. Flood Fill

思路

• DFS

Solution

• 932. Beautiful Array

思路

Devide and Conquer

• devide之后如何merge

solution

• 973. K Closest Points to Origin

有效队列

• 掌握如何使用最大堆和最小堆
• C++默认最大堆，java默认最小堆
• compare比较器的使用方法，严格验证弱序排列

soluton

*903. Valid Permutations for DI Sequence 思路

• Hard
• 动态规划
• so diffcult...

solution

*725. Split Linked List in Parts

思路

• 复习操作链表的方法

solution

*430. Flatten a Multilevel Doubly Linked List

思路

• 递归调用
• Stack

solution