Leetcode[LeetCode]4 两个有序数组的中位数

标签：node ListNode val 中位数 next 链表 Leetcode root LeetCode

Leetcode[LeetCode]4 两个有序数组的中位数_链表

上图为剑指Offer之字符串的排列，基于回溯法的思想。

简单算法

01数组中第二大的数

02合并排序链表

03链表反转

04判断链表环

05两个链表的首个交点

06数组中出现大与一般的数

07手写堆排序，快速排序，二分查找

网易实习生

网易买苹果（动态规划和贪心）

https://www.nowcoder.com/questionTerminal/61cfbb2e62104bc8aa3da5d44d38a6ef

130 Surrounded Regions

143 Reorder List（分割逆转合并，不用头结点辅助结点的方式（跳跃））

208Implement Trie

139Word Break

排序

the solution of the word ladder

花花酱 LeetCode

http://i.youku.com/i/UMjcyMzg0NzY0OA==?spm=a2hzp.8253869.0.0

117. Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/37811

/**
  * Definition for binary tree with next pointer.
  * struct TreeLinkNode {
  *  int val;
  *  TreeLinkNode *left, *right, *next;
  *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
  * };
  */
 class Solution {
 public:
     void connect(TreeLinkNode *root) {
         TreeLinkNode* temp = new TreeLinkNode(0);
         while(root){
             TreeLinkNode* cur = temp;
             while(root){
                 if(root->left != NULL){
                     cur->next = root->left;
                     cur = cur->next;
                 }
                 if(root->right != NULL){
                     cur->next = root->right;
                     cur = cur->next;
                 }
                 root = root->next;
             }
             root = temp->next;
             temp->next = NULL;
         }
     }
 };

TreeLinkNode tempChild = new TreeLinkNode(0); this is a temporary node.TreeLinkNode currentChild = tempChild; here currentChild points to temporary node. currentChild.next = root.left after this line currentChild has made tempChild next to point to root’s left which is effectively one level below the root. That is where we want to go after first iteration, to the next level so after the while root = tempChild.next; is done so that root points to next level beg now.

vector<vector<int> > dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

54Spiral Matrix

59Spiral Matrix II

79Word Search

简化路径名字/...

华为2017

简单题Plus One

全排列next permutation,permutation sequence

动态规划

平年闰年

1. #include <iostream>  
2. using namespace std;  
3. int main()  
4. {  
5.     int year;  
6.     while(cin>>year)  
7.     {  
8.         if((year%4==0&&year%100!=0 )|| year%400==0)  
9. "yes"<<endl;  
10.         else  
11. "no"<<endl;  
12.     }  
13.     return 0;  
14. }

关于回溯： if "(i > cur &&nums[i] == nums[i-1]) continue;

backtracking就是个不断试错的过程。比如input=[1,3,4,4,4,5,6,8]. target = 11
那么首先，我们的第一个数字先试input[0]=1，如果所有第一个数字为1的情况都试遍了还是不行；就试第一个数字为input[1] = 3的情况；如果还不行就试第一个数字为input[2] = 4的情况。。。以此类推。所以我们用一个循环来表示**试遍当前数字的所有可能**，而每次循环里的递归来表示**在取当前数字的情况下，进一步尝试**

那好，问题来了，如果我们发现第一个数字为input[2] = 4时的所有情况都试遍了以后，发现还是没有解。那这时你还需要再去试input[3]=4吗？当然不需要，因为第一个数字为4的所有情况都已经试过了啊。所以这时候，就应该跳过input[3]了。

那么具体什么时候该跳过？就是取了当前这个数字后的所有情况都已经被试过一次。因此，它必须是本次循环之前被试过的数字，因此判定方法是cand[ i ] == cand[ i - 1]。 i > cur是为了保证 i- 1是个合法的值。

递归https://en.wikipedia.org/wiki/Flood_fill

https://leetcode.com/problems/course-schedule/description/

随机访问的STL数据结构的选择

vector->deque 随机访问->首位快速增改(无法快速增改中间)

list 快速增改(无法随机访问，一个一个来)

快速排序https://wenku.baidu.com/view/a73aa85c7cd184254b353585.html

最新算法http://www.geeksforgeeks.org/company-interview-corner/

-----------------------------------------------------------

LCS

int LCS(vector<int> &nums) {
    vector<int> result;
     for (int i = 0; i < nums.size(); i++) {
         auto it = lower_bound(result.begin(), result.end(), nums[i]);
         if (it != result.end()) {
             *it = nums[i];
         } else {
             result.push_back(nums[i]);
         }
     }
     return result.size();}

是设计分布式缓存系统，需要考虑负载均衡以及增删设备，一致性哈希

一个月有余，今天终于刷完142题（最后一题word ladder2是看答案copy的），纪念一下，并总结下这段时间狂刷题的感觉：

从做上面的题，我发现我更擅长一些数学技巧不高的程序题，习惯靠直觉立马书写代码，而非严格推理之后，再书写代码
对于链表的题比较擅长，链表可以在纸上画画，关键要考虑的问题，就是链表指针在运算中会改变，如何保存需要保存的链表指针值是难点，除了那题拷贝具有random指针的链表题，其他链表题我都比较快速的AC掉
对于树的题，常见的方法有：BFS和递归（可以看作是DFS），整体来说，难度也不大，其中递归应该是最常用的，递归的方法需要注意的就是边界判定；当然另一个问题，就是很多情况下，会被要求写非递归的解法，比如说树的遍历，或者知先序中序构建树，这些问题我得好好研究
对于求解题的BFS和DFS得到了比较大的锻炼，之前一直感觉模糊的掌握了DFS和BFS这两种搜索方法，事实上，直到现在才算是掌握的比较不错，对于leetcode上面的很多题，如果不限时的话，我都能以DFS搞定（起码能有20题以上），BFS往往在求解最先到达或者最短时间的时候用到，用起来感觉还不错
对于DP还是不算很熟悉，除了LCS，LIS还有编辑距离这样的经典DP题，其他我都很少往DP想，为什么我总觉得DP有点难理解呢？
关于DP和BFS，DFS求解的选择问题：一般来说，需要记录解（由哪些组成）优先选择BFS和DFS，它们在运算的时候能够很好的保存中间结果；对于DP，适合求解最终结果是怎么的情况，比如求值（最长公共子序列），或者判断是否存在（bool），DP如果要输出最优路径的话，是个比较麻烦的问题，一般还需要设置一个观测DP在选择表中如何移动的数组，关于DP我要好好训练下。
STL:set,map,hash_set(unordered_set),hash_map(unordered_map),multimap,multiset(?好像这个我没用过),vector,string,pair,stack,queue等等，以及algorithm的函数，比如sort, unique,这些STL提供的，真是极大的方便了生活，以前经常得自己写一些基本数据结构，然而，自己写的再好哪有STL的好用啊！
对于在电脑面前写一些简单的算法程序应该是没很大问题了，但接下来的问题是：1,手写我要跪，虽然现在用vim，但我思路经常很跳，经常想起来就在前面插入，纸上可没这条件；2,一些基本的算法还不够熟练，比如快排，堆排，归并，KMP，等等，要立马写出一个bug free并且efficient&&elegant的代码是件不容易的时，我以后得专门在github上面建一个repo好好练习，自己写给自己看
leetcode上的大部分题都有不止一种解法，得好好看看其他人的解法，并且总结总结自己的解法

对做leetcode的总结大致如此了。

一般数据结构题占试卷的分数也就30%的样子，所以一大波书在等待着我

时间不多了，得好好努力！！

LCS LIS LICS

链表

/**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode(int x) : val(x), next(NULL) {}
  * };
  */
 class Solution {
 public:
     void deleteNode(ListNode* node) {
         //*node = *node->next;
         //node->val = node->next->val;
         //node->next = node->next->next;
         ListNode* del = node->next;
         node->val = del->val;
         node->next = del->next;
         delete del;
     }
 };

动态规划排序链表数组二叉树

做链表时想图单链表的容易实现之处在于，其更改只需要更改next指针（并且在新建头节点为空时反转链表只需要curr->next = preNode即可）。

树的遍历

合并K个链表

class Solution {
 public:
     struct compare {
         bool operator()(const ListNode* l, const ListNode* r) {
             return l->val > r->val;
         }
     };
     ListNode *mergeKLists(vector<ListNode *> &lists) { //priority_queue
         priority_queue<ListNode *, vector<ListNode *>, compare> q;
         for(auto l : lists) {
             if(l)
                 q.push(l);
         }
         if(q.empty())  return NULL;
         ListNode* result = q.top();
         q.pop();
         if(result->next) q.push(result->next);
         ListNode* tail = result;            
         while(!q.empty()) {
             tail->next = q.top();
             q.pop();
             tail = tail->next;
             if(tail->next) q.push(tail->next);
         }
         return result;
     }
 };-------------------------------------
public ListNode mergeKLists(ListNode[] lists) {
         if (lists.length == 0) return null;
   PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>() {
     @Override
     public int compare(ListNode o1, ListNode o2) {
       return o1.val - o2.val;
     }
   });
   // initialization
   for (ListNode node : lists) {
     if (node != null)
       minHeap.offer(node);
   }
   ListNode head = new ListNode(-1);
   for (ListNode p = head; !minHeap.isEmpty(); ) {
     ListNode top = minHeap.poll();
     p.next = top;
     p = p.next;
     if (top.next != null)
       minHeap.offer(top.next);
   }
   return head.next;
     }------------------------------------------