西雅图打卡

本人uw研究生，为找工作刷题打卡。

上周的Contest
1247. Minimum Swaps to Make Strings Equal
Problem: Return the minimum number of swaps required to make s1 and s2 equal, or return -1 if it is impossible to do so.
Solution: 统计两字符串同一位置(x,y)和(y,x)数目，两个分别除以2后得到至少要交换的次数，再判断%2是否都为1，是则再加2。其余情况都为-1

1248. Count Number of Nice Subarrays
Problem: Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.
Return the number of nice sub-arrays.
Solution: sliding window, 统计恰好为K可以变成至多为K减去至多为K-1.

794. Valid Tic-Tac-Toe StateProblem: Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
Solution: Ensure 2 things: 1. Number of 'x' equal to number of 'o' or bigger than 1.
                                     2. 1) if 'o' wins, # of 'x' = # of 'o'
                                         2) if 'x' wins, 1 or 2 line(s) with same symbol
                                         3) if no one wins, 0 line with same symbbol

1268. Search Suggestions System
Problem: Given an array of strings products and a string searchWord.
Solution: 不用Trie，直接排序后找出当前输入字符串最匹配的那个，连续取三个，亚麻OA好像也出现过的样子

1267. Count Servers that Communicate
Problem: Return the number of servers that communicate with any other server.
Solution: 统计columns和rows是否存在1，(m+n)，然后m*n判断为1时行列是否存在1.

1114. Print in Order
Problem: Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().
Solution: multithreading, c++用的是condition variable判断和唤醒

1266. Minimum Time Visiting All Points
Problem: Your task is to find the minimum time in seconds to visit all points.
Solution: 可横，竖，斜着走，所以直接判断max(横，竖)

269. Alien Dictionary
Problem: Given a list of sorted non-empty words based on new lexicographic, return the order of letters.
Solution: topological sort using BFS.

deepforce 发表于 2019-10-7 06:31
269. Alien Dictionary
Problem: Given a list of sorted non-empty words based on new lexicographic, r ...

UW undergrad路过～

yangx388 发表于 2019-10-7 06:47
UW undergrad路过～

哈哈，兄弟加油

347. Top K Frequent Elements
Problem: Given a non-empty array of integers, return the k most frequent elements.
Solution: bucket sort, use frequency of each number as index.

680. Valid Palindrome II
Problem: Given a non-empty string s, delete at most one character, check if make it a palindrome.
Solution: One pass from both left and right side by finding the different pair. Then ignore one of them and check it again.

138. Copy List with Random Pointer
Problem: Return a deep copy of the list that with random pointer.
Solution:
To avoid closed loop, use three time iteration.
first iteration create copy node after each original node.
second iteration add random pointer to each copied node.
third iteration extract each copy node and connect them together.
572. Subtree of Another Tree
Problem: Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s.
Solution: Find the same node first. Set it as root node, then check the structure and value of each node of both tree recursively.

240. Search a 2D Matrix II
Problem: Write an efficient algorithm that searches for a value in an m x n matrix.
Solution: Search target from left-bottom/top-right corner.

59. Spiral Matrix II
Problem: Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Solution: Create n*n matrix, then fill numbers from 1 to n*n using four iterations. (4 directions)

282. Expression Add OperatorsProblem: Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.
Solution: DFS

这道题很有意思。

158. Read N Characters Given Read4 II - Call multiple times
Problem: Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters.
Solution: new another char array, size 4


补充内容 (2019-10-17 13:45):
65. Valid Number
Problem: Validate if a given string can be interpreted as a decimal number.
Solution: DFA https://leetcode.com/problems/va ... My-thought-with-DFA