立贴！从今天开始刷题。

新人报道，和大家打个招呼，混个脸熟，也顺便求一点大米。

77年出生的老程序员了，工作19年。去年年底前意外获得一个脸书的onsite机会，兴致勃勃得从外地飞去西雅图，然后当场跪了。

四轮面试，两轮应该获得比较高的评价，特别是design题应该获得了比较高的分。另外两轮就脆跪了，一点思路都没有。

面过脸书才知道原来现在面试要要靠刷题的。（作为老码农刚知道leetcode真是汗颜！）

从今天开始准备积极刷题！争取每天刷至少一题。立帖为证！大家有大米的尽管砸我吧。

顺便吐槽一下，本论坛居然没有C#的代码支持。

617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input:
        Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                           
        3   2                     1   3                        
       /                           \   \                     
      5                             4   7                  
Output:
Merged tree:
             3
            / \
           4   5
          / \   \
         5   4   7



Note: The merging process must start from the root nodes of both trees.

贴一下答案。

    public int numIslands(char[][] grid) {
        int count = 0;
        
        if(grid == null) return count;
        int y = grid.length;
        if(y==0) return count;
        int x = grid[0].length;
        if(x==0) return count;
        
        for(int j=0;j<y;j++){
            for(int i=0;i<x;i++){
                if(grid[j][i]=='1'){
                    count++;
                    marklands(grid,j,i);
                }
            }
        }
        return count;
    }
    public void marklands(char[][] grid,int j, int i)
    {
        int y = grid.length;
        int x = grid[0].length;
        if((j<0)||(i<0)) return;
        if((j>=y)||(i>=x)) return;
        
        if(grid[j][i]=='1'){
            grid[j][i] = '0';
            marklands(grid,j+1,i);
            marklands(grid,j-1,i);
            marklands(grid,j,i+1);
            marklands(grid,j,i-1);
        }
    }

这里还有个系统设计版，“design题应该获得了比较高的分”，还望不吝赐教。

14417335 发表于 2019-5-3 04:37
这里还有个系统设计版，“design题应该获得了比较高的分”，还望不吝赐教。

哦，原来还有design题的子版块。我有空去看看。

#1
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

输入：一个array，一个target。
输出：如果找到target则输出一个坐标array，如果没有应该返回空。

最直接的方法取出一个数字，然后把后面的数字每个都取出来，然后加一下，看看是否是target。

当然最好的办法就是用hash表的方法。

167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

    Your returned answers (both index1 and index2) are not zero-based.
    You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

这题最简单办法就是遍历，然后发现和大于target就换一组。

但是最好的办法如果使用hash好像不会有啥提升。

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

遍历数组，然后假设第一个买进，计算所有的卖出值只要卖出值比现有最大值大就替换掉现有最大值。