2015年8月30日星期日

#LeetCode# Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

 这道题目A的过程很是艰辛，历经数次超时，终于找到原因。先瞅瞅我这超时的代码吧。

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        int length = nums.length;
        if (nums == null)  //或者length == 0
            return null; 
        return BuildBST(nums, 0, length-1);
    }
    
    public TreeNode BuildBST(int[] nums, int start, int end) {
        if (start > end) 
            return null;
        int mid = (start+end)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = BuildBST(nums, 0, mid-1);  //错误的地方，应修改为root.left = BuildBST(nums, start, mid-1);
        root.right = BuildBST(nums, mid+1, end);
        return root;
    }
}

 原理依旧很简单，DFS，递归，只要找清楚mid，start和end，神马都好说。可是，我的问题依旧是Time Limit Exceeded。

 Where is the problem? What the hell should I solve it!

 仔细看代码，BuildBST方法出问题了，就在root.left那一行，参数传递错误，本应该传递start我却传递的是0.

 修改之，root.left = BuildBST(nums, start, mid-1); 再次提交，Accepted.

 再说说之前编码遇到的几个小问题，

 1.判断nums为空，与判断nums.length为0是一个意思；
2.创建树，需要new一个TreeNode不够熟练；
3.定义方法的时候，一定注意参数的类型，像我刚开始就忘了定义start和end的类型了
4.最后返回的是root，就是我们的TreeNode.


发帖者 时间： 没有评论:
标签： , , , ,

2015年8月29日星期六

#LeetCode# Populating Next Right Pointers in Each Node

Given a binary tree
    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
  • You may only use constant extra space.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
         1
       /  \
      2    3
     / \  / \
    4  5  6  7
After calling your function, the tree should look like:
         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL
题目有点长，populate是填入、构成的意思。题目大意是，对每一个节点用指针后继与其右边节点链接起来，如果节点右边没有节点，则指针后继为Null。题目假设给定的树为完全二叉树，给定常数额外空间。
可笑的喔，上来先看图，把题目理解成广度优先搜索挨个把节点值置换为Null，真是可笑。

思路马上就有了，对节点进行链表处理，left.next = right，这样的处理比单双向链表的删除插入还要简单。不过我们还是不能大意，

1.对于，题图中的2、3节点，由于是同一个节点的左右孩子节点，root.left.next = root.right即可

2.对于题目中5、6节点呢？5和6节点不在同一个节点上。我们用root2和root3分别表示2、3节点，root2.left.next = root3.left可以处理。可是，root2和root3该如何表示呢？不要忘了，在上一层，这个时候的3节点已经是2节点的后继节点了，所以我们有root2.right.next = root.next.left。

具体处理的逻辑已经确定，我们下一步需要确定的是条件语句，核心判断节点是否为Null。直接上代码，


/**

 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) 
            return;
        if (root.left != null) {  //父节点非空的情况，如2和3
            root.left.next = root.right;
        }
        if (root.right != null && root.next != null) { //不是兄弟节点的情况，如5和6
            root.right.next = root.next.left;
        }
        
        connect(root.left);
        connect(root.right);
        
    }
}

OK！洗漱滚上床去。

发帖者 时间： 没有评论:
标签： , , , ,

#LeetCode# Same Tree

开学前这阵真是无聊透顶，安卓的项目接近尾声，今天交大校友会的一师兄问我对新项目APP有没有兴趣，回答当然是好呀好呀有呀。今晚，来学习学习LeetCode吧。

经典“相似树”问题，这里注意有节点权值相等。思路很简单，首先判断根节点权值是否相等，然后递归左右子树，直接上代码了。


/**

 * Definition for a binary tree node.

 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q==null) {
            return false;
        }
        if (p.val == q.val) {
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            } else {
                return false;
            }
    }
}

提交了三次才Accepted，说说我遇到的问题，

1. 首先判断树为空的条件，两个空树也是相似树！！两个空树也是相似树！！并且注意是两个树同时为空！！一个为空，另一个不为空就是false；
  我们可以用笨办法，对四种情形挨个条件语句判断（别问我什么是四个..）

2.习惯性的return 0，LeetCode不接受，说是不支持int类型的boolean，只好乖乖改成false和true；

3.我有一个疑问，先判断p.val == q.val然后else，与先判断p.val !=q.val然后else，两种方法的效率是怎样的差别？

4.我还有一个疑问，每次编辑Blog总记不清楚自己用的是小号字还是正常大小的字，莫怪...

 5.再补充一句，这次写的括号有点多...看起来怎么都不自然


LOL！

发帖者 时间： 没有评论:
标签： , , , ,

2015年8月27日星期四

更改Back建行为

安卓的Back键即返回键，顾名思义就是返回的意思。平常使用返回键，可见其在当前的界面与逻辑上一个界面切换，保证了我们的完整使用体验。

问题来了，在上一篇文章《省市县选择位置页面的逻辑》中，默认状态下，我们按下返回键就会一下子回到了桌面，这可大事不妙。我们想要的是返回逻辑上一层选择列表，县列表->市列表->省列表，这可如何是好呢。

方法来了。

public void onBackPressed() {
if (currentLevel == LEVEL_COUNTY) {
queryCities();
} else if (currentLevel == LEVEL_CITY) {
queryProvinces();
} else {
finish();
}

}


这里我们重定义onBackPressed()方法来覆盖默认返回键的功能。通过判断当前的creerntLevel来决定返回的是哪个选择列表，如当前为县列表（LEVEL_COUNTY），就返回城市查询列表（queryCities()）。是不是很机智呢，不得不感谢currentLevel了！

LOL！
发帖者 时间： 没有评论:
标签： , ,

省市县选择位置页面的逻辑

现在的APP，涉及到位置查询的，直接就是输入某个城市，甚至某个区就可以直达。如果有些API不支持这样的一键搜索直达，只支持按梯度的检索怎么办呢？比如，我想查找昆山市，只支持  江苏->苏州->昆山 这样的查找逻辑呢？

学习嘛，有时候笨笨的方法还是不得不学。

做一个天气预报APP的时候，就是这么个一步一步从 省->市->县 来检索位置的，看看它的逻辑是怎么实现的吧。废话不多说，先上代码！


public class ChooseAreaActivity extends Activity {

public static final int LEVEL_PROVINCE = 0;
public static final int LEVEL_CITY = 1;
public static final int LEVEL_COUNTY = 2;

private ProgressDialog progressDialog;
private TextView titleText;
private ListView listView;
private ArrayAdapter<String> adapter;
private WeatherDB weatherDB;
private List<String> dataList = new ArrayList<String>();
private List<Province> provinceList;

private List<City> cityList;

private List<County> countyList;

private Province selectedProvince;

private City selectedCity;

private County selestedCounty;

private int currentLevel;

@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
requestWindowFeature(Window.FEATURE_NO_TITLE);
setContentView(R.layout.choose_area);
listView = (ListView) findViewById(R.id.list_view);
titleText = (TextView) findViewById(R.id.title_text);
adapter = new ArrayAdapter<String>(this,
android.R.layout.simple_list_item_1, dataList);
listView.setAdapter(adapter);
weatherDB = WeatherDB.getInstance(this);
listView.setOnItemClickListener(new OnItemClickListener() {
@Override
public void onItemClick(AdapterView<?> arg0, View view, int index,
long arg3) {
if (currentLevel == LEVEL_PROVINCE) {
selectedProvince = provinceList.get(index);
queryCities();
} else if (currentLevel == LEVEL_CITY) {
selectedCity = cityList.get(index);
queryCounties();
}

}
});
queryProvinces(); // 加载省级数据
}

/**
* 查询全国所有的省，优先从数据库查询，如果没有查询到再去服务器上查询
*/
private void queryProvinces() {
provinceList = weatherDB.loadProvinces();// 从数据库中读取省级数据
if (provinceList.size() > 0) { // 数据库中读到，将数据显示到街面上
dataList.clear();
for (Province province : provinceList) {
dataList.add(province.getProvinceName());
}
adapter.notifyDataSetChanged();
listView.setSelection(0);
titleText.setText("中国");
currentLevel = LEVEL_PROVINCE;
} else { // 数据库中未读到，调用queryFromServer从服务器查询数据
queryFromServer(null, "province");
}
}

/**
* 查询选中省内的城市，优先从数据库中查询，如果没有查询到再去服务器上查询
*/
private void queryCities() {
cityList = weatherDB.loadCities(selectedProvince.getId());
if (cityList.size() > 0) {
dataList.clear();
for (City city : cityList) {
dataList.add(city.getCityName());
}
adapter.notifyDataSetChanged();
listView.setSelection(0);
titleText.setText(selectedProvince.getProvinceName());
currentLevel = LEVEL_CITY;
} else {
queryFromServer(selectedProvince.getProvinceCode(), "city");
}
}

/**
* 查询选中市内所有的县，优先从数据库查询，如果没有查询到再去服务器上查询
*/
private void queryCounties() {
countyList = weatherDB.loadCounties(selectedCity.getId());
if (countyList.size() > 0) {
dataList.clear();
for (County county : countyList) {
dataList.add(county.getCountyName());
}
adapter.notifyDataSetChanged();
listView.setSelection(0);
titleText.setText(selectedCity.getCityName());
currentLevel = LEVEL_COUNTY;
} else {
queryFromServer(selectedCity.getCityCode(), "county");
}
}

private void queryFromServer(final String code, final String type) {
String address;
if (!TextUtils.isEmpty(code)) {
address = "http://www.weather.com.cn/data/list3/city" + code
+ ".xml";
} else {
address = "http://www.weather.com.cn/data/list3/city.xml";
}
showProgressDialog();
// 向服务器发送请求，相应的数据回调到onFinish()方法中
HttpUtil.sendHttpRequest(address, new HttpCallbackListener() {
@Override
public void onFinish(String response) {
boolean result = false;
if ("province".equals(type)) {
result = Utility.handleProvincesResponse(weatherDB,
response);// 解析和处理服务器返回的数据
} else if ("city".equals(type)) {
result = Utility.handleCititesResponse(weatherDB, response,
selectedProvince.getId());
} else if ("county".equals(type)) {
result = Utility.handleCountiesResponse(weatherDB,
response, selectedCity.getId());
}
if (result) {
// 通过runOnUiThread()方法回到主线程处理逻辑，子线程切换到主线程(异步消息处理机制)
runOnUiThread(new Runnable() {
@Override 
public void run() {
closeProgressDialog();
if ("province".equals(type)) {
queryProvinces(); // 再次调用queryProvinces()方法，由于牵涉UI操作，故必须在主线程中调用
} else if ("city".equals(type)) {
queryCities();
} else if ("county".equals(type)) {
queryCounties();
}
}
});
}
}

@Override
public void onError(Exception e) {
// 通过runOnUiThread方法回到主线程处理逻辑
runOnUiThread(new Runnable() {
@Override
public void run() {
closeProgressDialog();
Toast.makeText(ChooseAreaActivity.this, "加载失败",
Toast.LENGTH_LONG).show();
}
});
}
});
}

/**
* 显示进度对话框
*/
private void showProgressDialog() {
if (progressDialog == null) {
progressDialog = new ProgressDialog(this);
progressDialog.setMessage("正在加载...");
progressDialog.setCanceledOnTouchOutside(false);
}
progressDialog.show();
}

/**
* 关闭进度对话框
*/
private void closeProgressDialog() {
if (progressDialog != null) {
progressDialog.dismiss();
}
}

@Override
public void onBackPressed() {
if (currentLevel == LEVEL_COUNTY) {
queryCities();
} else if (currentLevel == LEVEL_CITY) {
queryProvinces();
} else {
finish();
}

}


}


打开应用，这就是我们的首Activity，选择区域位置，然后才好从服务器处理具体的天气预报信息。

1. onCreate()方法中，各种初始化如获取控件示例，初始化ArrayAdapter等（不是本篇文章的重点）后，最后调用queryProvinces()方法，开始加载省级数据。

2. queryProvinces()方法中，weatherDB.loadProvinces()从数据库中读取省级数据，通过provinceList.size() 判断是否存在。若provinceList.size() >0，即读取到数据，将其显示在界面上，更新currentLEVEL为LEVEL_PROVINCE；否则，调用queryFromServer()方法，传入两个参数，分别是code(此时为null)和String type(此处为“province”)

3. queryFromServer()方法，首先根据传入的code拼装好查询地址，然后调用HttpUtil.sendHttpRequest向服务器发送请求，响应的数据会回调到onFinish()中
  
  3.1 onFinish()方法中，条件语句匹配type，当前我们的type为“province”，Utility.handleProvincesResponse解析和处理服务器返回的数据，存储在result中

 3.2 进入if(result)，通过runOnUiThread()方法回到主线程处理逻辑，子线程切换到主线程(异步消息处理机制)，此时的type仍为“province”，故会再次调用queryProvinces()方法，此时数据库中已经存在了数据，所以此时数据会直接显示在界面上，即省份数据。

4.  当我们选择了某一个具体的省份时，会进入ListView的onItemClick()方法中，此时会根据当前的currentLevel来判断进入哪个query，如，当前currentLevel为LEVEL_PROVINCE，就进入了queryCities()方法中，从此，进入下一次的查询逻辑。这里我们需要注意的时，每次传递的参数在变化。

我的文字叙述应该是比较详尽了，有一个UML图的话会更直观，不过很抱歉，现在就是没有，所以耐心地看代码看注释吧。

LOL! 跑步去了


发帖者 时间： 没有评论:
标签： , ,

2015年8月24日星期一

R.layout.XXX无法正常调用

半个月前的项目，写好了XXX布局，这次重新找出来继续完善onCreate部分时，R.layout.XXX却怎么也调用不成功。卡壳半天，做了一发饭回来，一一排除。

 XXX布局，名字没错，layout位置没错，重新检查一遍，布局写得很好，没有BUG；

 再看Activity部分，只是用Eclipse的自动补全勾勒出了onCreate，onPause等方法，正一一待我去完成；

 import部分呢？这里是import了android.R，是不是它的问题呢？先删掉，重新Ctrl+Shift+O，蹦出载入选项，还有另一个是com.包名.app.R，选择之。保存，报错消息不见了，我的问题解决了。

 总之，检查import是一个常见的排除Bug的利器。

 LOL! 吃饭去了
发帖者 时间： 没有评论:
标签： , ,

2015年8月2日星期日

再说Android网络编程——优化

之前有写到HttpURLConnection和HttpClient的用法，知道了如何发起HTTP请求，此乃基本功。随着应用开发学习的深入，面临着这个么一个问题，应用程序不止一个地方会遇上网络功能，而每次都重新编写网络编程部分代码，是一个费力又愚蠢的做法。

 所以，我们需要把通用的网络操作提取到一个公共类中，并提供一个静态方法，使用时只需简单调用即可。上代码！

 public class HttpUtil {
public static String sendHttpRequest(String address) {
HttpURLConnection connection = null;
try {
URL url = new URL(address);
connection = (HttpURLConnection) url.openConnection();
connection.setRequestMethod("GET");
connection.setConnectTimeout(8000);
connection.setReadTimeout(8000);
connection.setDoInput(true);
connection.setDoOutput(true);
InputStream in = connection.getInputStream();
BufferedReader reader = new BufferedReader(
new InputStreamReader(in));
StringBuilder response = new StringBuilder();
String line;
while ((line = reader.readLine()) != null) {
response.append(line);
}
return response.toString();
} catch (Exception e) {
e.printStackTrace();
return e.getMessage();
} finally {
if (connection != null) {
connection.disconnect();
}
}
}

}

 当需要发起一条HTTP请求时，可以这样写，

 String address = "http://www.baidu.com"
String response = HttpUtil.sendHttpRequest(address);

 我们获取到服务器的响应后就可以对其进行解析和处理了。但我们需要注意的是，网络请求通常都属于耗时操作，而senHttpRequest()方法内部并没有开启线程，这样可能导致调用sendHttpRequest()方法时使得主线程被阻塞。

 倘若我们想在sendHttpRequest()内部开启一个子线程来发起HTTP请求，那么所有的耗时操作逻辑都在子线程内完成，sendHttpReques()方法会在服务器还来得及反应的时候就执行结束了，自然无法返回相应的数据，描述的应该还算比较清楚了吧。所以该怎么解决这个难题呢？

 Java的回调机制!

 首先，定义一个名为HttpCallbackListener的接口，

 public interface HttpCallbackListener {

 void onFinish(String response);

 void onError(Exception e);

}

 onFinish()方法表示当服务器成功相应请求的时候调用，参数response代表服务器返回的数据。onError()方法则表示出现错误时调用，参数e记录错误信息。

 修改前边HttpUtil的代码，

 public class HttpUtil {

 public static void sendHttpRequest(final String address,
final HttpCallbackListener listener) {
new Thread(new Runnable() {
@Override
public void run() {
HttpURLConnection connection = null;
try {
URL url = new URL(address);
connection = (HttpURLConnection) url.openConnection();
connection.setRequestMethod("GET");
connection.setConnectTimeout(8000);
connection.setReadTimeout(8000);
connection.setDoInput(true);
connection.setDoOutput(true);
InputStream in = connection.getInputStream();
BufferedReader reader = new BufferedReader(
new InputStreamReader(in));
StringBuilder response = new StringBuilder();
String line;
while ((line = reader.readLine()) != null) {
response.append(line);
}
if (listener != null) {
// 回调onFinish()方法
listener.onFinish(response.toString());
}
} catch (Exception e) {
if (listener != null) {
// 回调onError()方法
listener.onError(e);
}
} finally {
if (connection != null) {
connection.disconnect();
}
}
}
}).start();
}

}

 这里给sendHttpRequest()方法添加了一个HttpCallbackListener的参数，并在方法内开启了一个子线程，然后在子线程内执行具体的网络操作。注意这里的子线程是无法通过return来返回数据，所以把服务器响应的数据传入HttpCallbackListener的onFinish()方法中，异常错误则传入onError()方法中。

 成功达成目的，快来看看怎么使用HttpUtil吧，

 HttpUtil.sendHttpRequest(address, new HttpCallbackListener() {
@Override
public void onFinish(String response) {
// 在这里根据返回内容执行具体的逻辑
}
@Override
public void onError(Exception e) {
// 在这里对异常情况进行处理
}

});

 一定注意在使用的时候要把HttpCallbackListener的实例传入！

 LOL !


发帖者 时间： 没有评论:
标签： , ,

Java接口复习回顾

接口可以看成是特殊的抽象类。即只包含抽象方法和常量的抽象类。可以通过interface关键字来定义接口。看如下代码：
interface Runner {
public static int DEFAULT_SPEED = 100;
public void run(); 
} 
注意，run()方法，此处可以省略public abstract。因其默认就是public abstract的。

实现接口
与继承不同，一个类可以实现多个接口，实现的接口直接用逗号分隔。当然，该类需要实现这些接口中定义的所有方法；
一个类可以通过implements关键字”实现”接口。一个类实现了某个接口后必须实现该接口中定义的所有方法。看下面的代码，类实现了接口并实现了方法：
class AmericanCurl implements Runner , … {
public void run() {
System.out.println("run..."); 
}
} 
另外需要说明的一点，接口可以作为一种类型声明变量，一个接口类型的变量可以引用实现了该接口的类的对象；通过该变量可以调用该接口中定义的方法（具体的实现类提供了方法的实现）。代码如下所示：
Runner runner = new AmericanCurl(); 

此句代码为，一个接口类型变量，引用了子类的对象。调用时，调用的是子类对象的具体的实现。

接口的继承
接口间可以存在继承关系，一个接口可以通过extends关键字继承另外一个接口。子接口继承了父接口中定义的所有方法。代码如下所示：
interface Runner { 
public void run();
}
interface Hunter extends Runner { 
public void hunt();
}
class AmericanCurl implements Hunter { 
public void run() {… … …} 
public void hunt() {… … …} 
} 
说明：AmericanCurl实现了Hunter，必须实现Hunter接口中的hunt方法以及其父接口Runner中的run方法。

接口和抽象类的区别
一个类只能继承一个抽象类，但可以实现多个接口。

抽象类中可以包含抽象方法和非抽象方法，而接口中的所有方法均为抽象的。
子类继承抽象类必须实现抽象类中所有抽象方法，否则子类也必须是抽象类。而子类实现接口则必须实现接口中的所有抽象方法。
发帖者 时间： 没有评论:
标签：
订阅： 博文 (Atom)