#LeetCode# Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

自从来法国接触了OCaml，对递归从本能地抵触到现在本能地依赖...以前抵触是因为在国内刚讲C语言，老师就说递归不好效率低一般我们要避免使用，然后一个学期的OCaml课老师对于递归的洗脑，让我也变成了又懒又笨的依赖递归的人了。废话不多说，上代码。

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public int maxDepth(TreeNode root) {

        if (root == null)

            return 0;

        return Math.max(maxDepth (root.left), maxDepth (root.right)) + 1 ;

    }

}

直接手写代码，不过三次才Accepted，说说遇到的问题吧。

1.顾着高兴，直接return  (maxDepth (root.left), maxDepth (root.right)) + 1

2.root==null，刚开始二逼写成val=null...

3.第一次用Java的max，以为也是max(int, int)，谁知是Math.max(int, int)

一会儿吃完长棍，有心情了再写非递归的吧

LOL

再来完成下非递归的代码。

先说下思路，递归我们考虑的是DFS-深度优先，不使用递归的话，可以考虑BFS-广度优先。即层序遍历，遍历到最后一层（叶子）就是树的深度，这个时候再选择最大值即可。


public int maxDepth(TreeNode root) {
    if(root == null)
        return 0;
    int level = 0;
    LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    int curNum = 1; //当前层剩余的节点数目
    int nextNum = 0; //下一层的节点数目
    while(!queue.isEmpty())
    {
        TreeNode n = queue.poll();
        curNum--;
        if(n.left!=null)
        {
            queue.add(n.left);
            nextNum++;
        }
        if(n.right!=null)
        {
            queue.add(n.right);
            nextNum++;
        }
        if(curNum == 0)
        {
            curNum = nextNum;
            nextNum = 0;
            level++;
        }
    }
    return level;

}

这个不是太好理解，再来一个好理解的版本。

public class Solution {

    public int maxDepth(TreeNode root) {

        if(root == null)    return 0;

         

        // Non-recursive, use level order triversal

        ArrayList<TreeNode> q = new ArrayList<TreeNode>();

        q.add(root);

        int depth = 0;

         

        while(!q.isEmpty()) {

            ArrayList<TreeNode> next = new ArrayList<TreeNode>();

            for(TreeNode node : q) {

                if(node.left != null)   next.add(node.left);

                if(node.right != null)  next.add(node.right);

            }

            q = new ArrayList<TreeNode>(next);

            depth++;

        }

         

        return depth;

    }

}

#LeetCode# Tenth Line

How would you print just the 10th line of a file?

For example, assume that file.txt has the following content:

Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10

Your script should output the tenth line, which is:

Line 10

三种方法。

1.AWK，我也只会这一种，后边俩是谷歌来的

awk "NR == 10" file.txt

这里的NR就是number of rows的意思，即第几行

2.SED

sed -n '10p' file.txt

3.Tail and Head

NR = ' cat file.txt | wc -1 '
if [ $NR -ge 10 ] ; then
   tail -n +10 file.txt | head -1
fi

加入if...fi条件语句，先判断文件是否超出10行

tail从第十行开始执行，输出重定向为head，head提取此时的第一行，正好是文件的第十行。

LOL

#LeetCode# Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

首先想到的是两层循环，显然不符合线性时间；那先排序再比较呢？引入sort的话，时间复杂度也是nlogn起跳，同样不符合。一层循环，不用额外空间，可愁死人了。

点击TAG有惊喜，TAG显示Hash Table和Bit Manipulation，哈希表好久没碰过，不过位操作让我好奇心大作。位操作不就是&，^，| 这些么？顺手谷歌重新学习下位操作。

C语言提供了六种位运算符：
    &     按位与
    |      按位或
    ^      按位异或
    ~      取反
    <<    左移
    >>    右移 

........

基本可以锁定^ 按位异或 了。

a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

a ⊕ b ⊕ a = b

enough，我的问题可以解决了，感恩戴德交换律！

手写代码，

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        for(int i=0;i<A.length;i++){
            res=res^A[i];
        }
        return res;
    }
}
Accepted
LOL

SharedPreferences实现记住密码功能

本文介绍通过SharedPreferences存储来实现记住密码功能，不过此处为不够安全的明文密码。

先看下登陆布局，如图所示，

布局文件如下，注意CheckBox部分为“记住密码”复选框部分。娘希匹的，对xml支持不够好。

<?xml version="1.0" encoding="utf-8"?>
<TableLayout xmlns:android="http://schemas.android.com/apk/res/android"
    android:layout_width="match_parent"
    android:layout_height="match_parent" 
    android:stretchColumns="1">
    
    <TableRow >    
       <TextView 
            android:layout_height="wrap_content"
            android:text="Account:"
            />    
        <EditText
            android:id="@+id/account"
            android:layout_height="wrap_content"
            android:hint="Input your account"/>       
    </TableRow>
    
    <TableRow >       
        <TextView 
            android:layout_height="wrap_content"
            android:text="Password:"
            />       
        <EditText 
            android:id="@+id/password"
            android:layout_height="wrap_content"
            android:inputType="textPassword"
            />        
    </TableRow>
    
    <TableRow >
        <CheckBox 
            android:id="@+id/remember_pass"
            android:layout_height="wrap_content"
            />
        <TextView 
            android:layout_height="wrap_content"
            android:text="Remember password"
            />
    </TableRow>
    
    <TableRow >                
        <Button
            android:id="@+id/laogin"
            android:layout_height="wrap_content"
            android:layout_span="2"
            android:text="Login" />   
    </TableRow>
  
</TableLayout>


下面介绍核心部分——SharedPreferences实现记住密码。

我们需要记住的是账号和密码，而SharedPreferences的使用也分两个部分，一将数据（账号密码）存储到SharedPreferences中，二从SharedPreferences中读取数据（账号和密码）。那么我们的记住密码功能的逻辑是，登陆时选择“记住密码”->登陆成功->账号和密码存储到SharedPreferences中->下线->回到登陆界面->账号密码从SharedPreferences中读取，写在输入框中。是不是很简单呐，看看我的核心代码吧，

public class LoginActivity extends BaseActivity {

 private SharedPreferences pref;

 private SharedPreferences.Editor editor;

 private EditText accountEdit;

 private EditText passwordEdit;

 private Button login;

 private CheckBox rememberPass;

 @Override
 protected void onCreate(Bundle savedInstanceState) {
  super.onCreate(savedInstanceState);
  setContentView(R.layout.login);
  pref = PreferenceManager.getDefaultSharedPreferences(this);// 获取SharedPreferences对象
  accountEdit = (EditText) findViewById(R.id.account);
  passwordEdit = (EditText) findViewById(R.id.password);
  rememberPass = (CheckBox) findViewById(R.id.remember_pass);
  login = (Button) findViewById(R.id.laogin); // 分别获取账号输入框，密码输入框，登陆按钮的实例
  boolean isRemember = pref.getBoolean("remember_password", false);// 获取remember_password键对应的值
  if (isRemember) {
   // 将账号和密码都设置到文本框中
   String account = pref.getString("account", "");
   String password = pref.getString("password", "");
   accountEdit.setText(account);
   passwordEdit.setText(password);
   rememberPass.setChecked(true);
  }
  login.setOnClickListener(new OnClickListener() {
   @Override
   public void onClick(View v) {
    String account = accountEdit.getText().toString();
    String password = passwordEdit.getText().toString();
    // 若账号是admin 密码是admin，则登陆成功
    if (account.equals("admin") && password.equals("admin")) {
     editor = pref.edit();
     if (rememberPass.isChecked()) { // 登陆成功后，检查复选框是否被选中
      // 将account和password对应的值都存入到SharedPreferences文件中提交
      editor.putBoolean("remember_password", true);
      editor.putString("account", account);
      editor.putString("password", password);
     } else { // 若没有被选中，将SharedPreferences文件总的数据全部清除掉
      editor.clear();
     }
     editor.commit(); // 提交
     Intent intent = new Intent(LoginActivity.this,
       MainActivity.class);
     startActivity(intent); // 登陆成功，到mainactivity活动界面
     finish();
    } else { // 账号密码不匹配，登陆失败
     Toast.makeText(LoginActivity.this,
       "account or password is invalid",
       Toast.LENGTH_SHORT).show();
    }
   }
  });
 }

}

注释得是不是不能够再详细了！

再次运行之，记住密码，强制下线后，回到登陆界面，账号密码都已经记住啦。

再次注意，这里存储的是明文密码，非常不安全，大家不要学CSDN。至于加密算法，尽情google吧。

LOL