By

已知一个m行n列的矩阵M,它的元素满足一个很特殊的性质，即任一元素M[i][j]都小于它右边与下方的元素(如果存在的话),换言之，M[i][j] < M[i][j + 1]且M[i][j] < M[i + 1][j]。如int[ ][ ] nums = { {1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};

现在有一个值K，编写一个程序，检查矩阵M中是否有K。

对于矩阵M，可以将它划分成两部分区域，一部分是小于等于K的区域，一部分是大于K的区域。沿着两部分区域的边界线查找K即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SearchaMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] > target) {
                j--;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                return true;
            }       
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] nums = { {1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};
        System.out.println(searchMatrix(nums, 17));
    }
}

联系作者

By

已知数组x[ ]储存了一组整数，请写一个程序，找出在数组中连续元素的和中最大的一个。举例而言，如果有数组1，2，-6，3，-2，4，-1，3，2，-4，那么连续的元素和有1 + 2 = 3，1 + 2 + (-6) = -3，2 + (-6) = -4，。。。，但最大的就是3 + (-2) + 4 + (-1) + 3 + 2这一段，值为9。这个题目通常叫做最大连续元素和问题，或者叫做最大连续子数组。

一个自然的办法是使用双重循环，但是性能不好。这个问题要求O(n)解法，需要动点脑筋。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        int result = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0) {
                sum = 0;
            }
            sum += nums[i];
            result = Math.max(result, sum);
        }
        return result;      
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

还有一种是分治的方法，效率慢一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);    
    }
    public static int maxSubArray(int[] nums, int left, int right) {
        if (left > right) {
            return Integer.MIN_VALUE;
        } else if (left == right) {
            return nums[left];
        } else {
            int middle = (right - left) / 2 + left;
            int leftMax = maxSubArray(nums, left, middle);
            int rightMax = maxSubArray(nums, middle + 1, right);
            int sum = 0;
            int maxToLeft = Integer.MIN_VALUE;
            for (int i = middle; i >= left; i--) {
                sum += nums[i];
                maxToLeft = Math.max(maxToLeft, sum);
            }
            sum = 0;
            int maxToRight = Integer.MIN_VALUE;
            for (int i = middle + 1; i <= right; i++) {
                sum += nums[i];
                maxToRight = Math.max(maxToRight, sum);
            }
            int result = maxToLeft + maxToRight;
            result = Math.max(result, leftMax);
            result = Math.max(result, rightMax);
            return result;
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

联系作者

By

假设有一个数组x[ ], 它有n个元素，每一个都大于零，称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序，求出x[ ] 中有多少组相同的前置和与后置和。

说明
如果x[ ] 的元素是3，6，2，1，4，5，2，则x[ ]的前置和有一下7个，即3，9，11，12，16，21，23；后置和则是2，7，11，12，14，20，23；于是11，12，与23这3对就是值相同的前置和与后置和，因为：
11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)
12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)
因为23是整个数组元素的和，因此前置和与后置和一定相同。

可以用变量prefix来表示前置和，用suffix来表示后置和，用i表示前置和累加元素的位置，i从前往后加，用j表示后置和累加元素的位置, j从后往前加。当prefix > suffix时，累加后置和，也就是j向前走；当prefix < suffix时，累加前置和，也就是i往后走；当prefix == suffix时，同时累加前置和与后置和，也就是i往后走，j往前走

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class HeadTail {
    public static int headTail(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        int prefix = 0;
        int suffix = 0;
        int result = 0;
        while (i < nums.length && j >= 0) {
            System.out.println(prefix + " " + suffix + " " + i + " " + j);
            if (prefix == suffix) {        
                prefix += nums[i++];
                suffix += nums[j--];
                result++;
            } else if (prefix > suffix) {
                suffix += nums[j--];
            } else {            
                prefix += nums[i++];
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 1, 4, 5, 2};
        System.out.println(headTail(nums));
    }
}

联系作者

By

已知两个元素从小到大排列的数组x[]与y[],请编写一个程序算出两个数组元素彼此之间差的绝对值最小的一个树，此值称为数组的距离。

说明： 如果x[i]与y[i]是两个元素，那么 |x[i] - y[i]| 就是这两个元素之间的距离，所有这些距离的最小值，称为数组的距离。比如说x[]有1，3，5，7，9， y[]有2，6，8，那么最短距离就是1，因为x[0]与y[0]、 x[1]与y[0]、x[2]与y[1]、x[3]与y[1]、还有x[4]与y[2]的距离都是1。

依然是利用数组已经排好序的特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class MinDist {
    public static int minDist(int[] x, int[] y) {
        int result = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        while (i < x.length && j < y.length) {    
            if (x[i] >= y[j]) {
                result = Math.min(result, x[i] - y[j]);
                j++;
            } else {
                result = Math.min(result, y[j] - x[i]);
                i++;
            }    
        }
        return result;
    }
    public static void main(String[] args) {
        int[] x = {1, 3, 5, 7, 9};
        int[] y = {2, 6, 8};
        System.out.println(minDist(x, y));
    }
}

联系作者

By

已知两个整数数组f[]与g[]，它们的元素都已经从小到大排列好，而且两个数组中的元素都各不相同。例如，f[]中有1,3,4,7,9,而g[]中有3,5,7,8,10。试编写程序算出这两个数组之间有多少组相同的元素。

就上例而言，f[2]和g[1]为3是一组；f[3]与g[2]为7是第二组

依然是利用已经排好序的这个特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class EQCount {
    public static int eqCount(int[] f, int[] g) {
        int i = 0;
        int j = 0;
        int result = 0;
        while (i < f.length && j < g.length) {
            if (f[i] == g[j]) {
                i++;
                j++;
                result++;
            } else if (f[i] > g[j]) {
                j++;
            } else {
                i++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] f = {1, 3, 4, 7, 9};
        int[] g = {3, 5, 7, 8, 10};
        System.out.println(eqCount(f, g));
    }
}

联系作者

By

已知f[]与g[]两个整数数组，元素已经从小到大排列，请写一个程序，算出f[]中比g[]元素大的对数。换句话说，f[0]比g[]中多少个元素大，f[1]比g[]中多少元素大等，这些值的总和就是要求的答案。

例如，如果f[]中有1，3，5，7，9，而g[]中有2，3，4，7，8，比g[0]大的有f[1]~f[4], 比g[1]大的有f[2]~f[4]，比g[2]大的有f[2]~f[4]，比g[3]大的有f[4]，比g[4]大的有f[4]，因此答案是4 + 3 + 3 + 1 + 1 = 12

利用数组已经排好序的这个特性，可以写出高效的程序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class GTCount {
    public static int gtCount(int[] f, int[] g) {
        int i = 0;
        int j = 0;
        int result = 0;
        while (i < f.length && j < g.length) {
            if (f[i] > g[j]) {
                result += f.length - i;
                j++;
            } else {
                i++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] f = {1, 3, 5, 7, 9};
        int[] g = {2, 3, 4, 7, 8};
        System.out.println(gtCount(f, g));
    }
}

联系作者

By

最近又把冼镜光的《C语言名题精选百则–技巧篇》拿出来看看，确实不错。

已知一个已经从小到大排序的数组，这个数组中的一个平台(plateau) 就是连续的一串相同的元素，并且这一串元素不能再延伸。例如，在1，2，2，3，3，3，4，5，5，6中1，2.2，3.3.3，4，5.5，6都是平台。试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。在上面的例子中，3.3.3就是该数组的最长平台。
这个问题曾经困扰过计算机科学家David Gries，他给出的方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Pleateau {
    public static int pleateau(int[] nums) {
        int length = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - length]) {
                length++;
            }
        }
        return length;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6};
        System.out.println(pleateau(nums));
    }
}

自己想到的方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Pleateau {
    public static int pleateau(int[] nums) {
        int length = 1;
        int i = 0;
        while (i + length < nums.length) {
            if (nums[i] == nums[i + length]) {
                length++;
            } else {
                i += length;
                while (i < nums.length && i > 0 &&  nums[i] == nums[i - 1]) {
                    i--;
                }
            }
        }
        return length;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6};
        System.out.println(pleateau(nums));
    }
}

联系作者

By

在上篇中，我们通过在jetty中配置，是update需要进行用户名和密码认证，这篇中我们继续介绍如何在solrj中调用update

*测试添加文档
先尝试使用solrj,编写测试程序

1
2
3
4
String url = "http://localhost:8989/solr"; 
HttpSolrServer server = new HttpSolrServer(url); 
SolrInputDocume doc1 = new SolrInputDocument(); 
server.add(docs);

提示401错误,添加用户名和密码:

1
2
3
4
5
String url = "http://localhost:8989/solr"; 
HttpSolrServer server = new HttpSolrServer(url); 
HttpClientUtil.setBasicAuth((DefaultHttpClient) server.getHttpClient(), "index", "update"); 
SolrInputDocume doc1 = new SolrInputDocument(); 
server.add(docs);

提示 NonRepeatableRequestException, Cannot retry request with a non-repeatable request entity. 想跟踪过去,看看错误出自哪里,没办法调到源代码,于是尝试查询.
测试查询文档
将etc/webdefault.xml中对/update/的限制改成,/select/*,编写查询代码,

1
2
3
4
5
String url = "http://localhost:8989/solr"; 
HttpSolrServer server = new HttpSolrServer(url); 
SolrQuery query = new SolrQuery(); 
String q = "*:*"; 
query.setQuery(q);

提示401错误,添加用户名和密码:

1
2
3
4
5
String url = "http://localhost:8989/solr"; 
HttpSolrServer server = new HttpSolrServer(url); 
SolrQuery query = new SolrQuery(); 
String q = "*:*"; 
query.setQuery(q);

查询成功,

*问题解决
不明白原因,只是猜测post的信息不能反复使用,在setBasicAuth前面有一段说明, “Currently this is not preemtive authentication. So it is not currently possible to do a post request while using this setting.”,意思就是认证过程不是最先进行的,所以现在不能用于post,可是认证过程可以用于get,于是察看get的执行过程,发现它先执行一次,发现要认证,于是再执行一次,而第二次执行时会先执行认证过程. 对于post过程,如果 可以执行同样的过程,那就可以达到目的,关键问题是”Cannot retry request with a non-repeatable request entity”,于是查看solr-4470是如何实现的,看到HttpSolrServer里代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
if (contentStream[0] instanceof RequestWriter.LazyContentStream) {
   post.setEntity(new InputStreamEntity(contentStream[0].getStream(), -1) {
     @Override
     public Header getContentType() {
       return new BasicHeader("Content-Type", contentStream[0].getContentType());
     }

     @Override
     public boolean isRepeatable() {
       return false;
     }

   });
 } else {
   post.setEntity(new InputStreamEntity(contentStream[0].getStream(), -1) {
     @Override
     public Header getContentType() {
       return new BasicHeader("Content-Type", contentStream[0].getContentType());
     }

     @Override
     public boolean isRepeatable() {
       return false;
     }
   });
 }

修改成

1
2
3
4
5
6
7
8
9
10
11
HttpEntity entity = new InputStreamEntity(contentStream[0].getStream(), -1) {
    @Override
    public Header getContentType() {
        return new BasicHeader("Content-Type", contentStream[0].getContentType());
    }
    @Override
    public boolean isRepeatable() {
        return false;
    }  
};
entity = new BufferedHttpEntity(entity);

在生产环境中，可以添加参数控制是否需要entity = new BufferedHttpEntity(entity);和HttpClientUtil.setBasicAuth((DefaultHttpClient) server.getHttpClient(), “index”, “update”);这两句

联系作者

By

有些情况下，想给Solr增加权限控制，这样就不会被随意更新和删除。关于这点，在https://wiki.apache.org/solr/SolrSecurity有详细的描述。觉得最坑人的一点是Solr-4470还没resolved。不管它，先使用Jetty添加权限控制

下载已经编译好的solr-4.8.0,进入example目录
编辑etc/webdefault.xml,添加如下内容:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<security-constraint>
    <web-resource-collection>
      <web-resource-name>Solr authenticated application</web-resource-name>
      <url-pattern>/update/*</url-pattern>
    </web-resource-collection>
    <auth-constraint>
      <role-name>update-role</role-name>
    </auth-constraint>
  </security-constraint>

  <login-config>
    <auth-method>BASIC</auth-method>
    <realm-name>Solr Update</realm-name>
  </login-config>

编辑 etc/jetty.xml, 添加如下内容：

1
2
3
4
5
6
7
8
9
<Call name="addBean">
  <Arg>
    <New class="org.eclipse.jetty.security.HashLoginService">
      <Set name="name">Solr Update</Set>
      <Set name="config"><SystemProperty name="jetty.home" default="."/>/etc/realm.properties</Set>
      <Set name="refreshInterval">0</Set>
    </New>
  </Arg>
</Call>

增加 etc/realm.properties,写入如下内容，也就是用户名，密码以及角色：

1
index: update, update-role

启动solr,到exampledocs目录下执行./post.sh solr.xml,返回401错误，说明未认证。修改post.sh,在调用curl时加上用户名和密码，如下：
curl –user index:update $URL –data-binary @$f -H ‘Content-type:application/xml’

再次执行./post.sh solr.xml,执行成功，到solr后台查看,可以看到添加文件成功,说明认证设置成功

联系作者

By

从Lucene4.0开始，提供了扩展codec功能，这个功能主要是留给想自己定义索引格式的开发者。
在此之前，有必要了解codec主要的作用，codec相关的类主要作用是读写索引。 而通过实现FilterCodec，可以很方便的定义自己的codec。 这个方便主要是可以将许多读写索引部分交给已有的codec实现，而只实现自己需要改进的部分。当然如果这样还不能满足需求 可以重新写一个codec。

写个简单的例子更容易懂，
在Codec.java中，可以看到，读写索引主要实现以下几个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/** Encodes/decodes postings */
 public abstract PostingsFormat postingsFormat();

 /** Encodes/decodes docvalues */
 public abstract DocValuesFormat docValuesFormat();

 /** Encodes/decodes stored fields */
 public abstract StoredFieldsFormat storedFieldsFormat();

 /** Encodes/decodes term vectors */
 public abstract TermVectorsFormat termVectorsFormat();

 /** Encodes/decodes field infos file */
 public abstract FieldInfosFormat fieldInfosFormat();

 /** Encodes/decodes segment info file */
 public abstract SegmentInfoFormat segmentInfoFormat();

 /** Encodes/decodes document normalization values */
 public abstract NormsFormat normsFormat();

 /** Encodes/decodes live docs */
 public abstract LiveDocsFormat liveDocsFormat();

一个纯文本保存索引的codec是SimpleTextCodec,这个codec的主要目的是用来学习

下面定义自己的codec

1
2
3
4
5
6
7
8
9
10
public class HexinCodec extends FilterCodec {
    final private FieldInfosFormat myTermFieldInfoFormat;
    public HexinCodec() {
        super("HexinCodec", new Lucene46Codec());
        myTermFieldInfoFormat = new SimpleTextFieldInfosFormat();
    }
    public FieldInfosFormat fieldInfosFormat() {
        return myTermFieldInfoFormat;
    }
}

最后，还是让上面的例子跑起来，首先下载Lucene4.8.0的源码，之后在codecs/src/java下新建包org.apache.lucene.codecs.hexin,
在这个包下面新建类HexinCodec.java,复制上面的代码。
之后编写测试用的建索引程序Index.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package org.hexin;
import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.codecs.Codec;
import org.apache.lucene.codecs.hexin.HexinCodec;
import org.apache.lucene.codecs.lucene46.Lucene46Codec;
import org.apache.lucene.codecs.simpletext.SimpleTextCodec;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.TextField;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig.OpenMode;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.store.FSDirectory;
import org.apache.lucene.util.Version;

import java.io.File;
import java.io.IOException;
public class Index {
    public static void main(String[] args) throws IOException {
        //Codec codec = new SimpleTextCodec();
        Codec codec = new HexinCodec();
        //Codec codec = new Lucene46Codec();
        String INDEX_DIR = "e:\\index";
        Analyzer analyzer = new StandardAnalyzer(Version.LUCENE_48);
        IndexWriterConfig iwc = new IndexWriterConfig(Version.LUCENE_48, analyzer);
        iwc.setCodec(codec);
        IndexWriter writer = null;
        iwc.setOpenMode(OpenMode.CREATE);
        iwc.setUseCompoundFile(false);
        try {
            writer = new IndexWriter(FSDirectory.open(new File(INDEX_DIR)), iwc);
            Document doc = new Document();
            doc.add(new TextField("title", "who are you, you are a man", Field.Store.YES));
            doc.add(new TextField("content", "A long way to go there. Please drive a car", Field.Store.NO));
            writer.addDocument(doc);
            doc = new Document();
            doc.add(new TextField("title", "are you sure", Field.Store.YES));
            doc.add(new TextField("content", "He is a good man. He is a driver", Field.Store.NO));
            writer.addDocument(doc);
            writer.commit();
            writer.close();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }  
}

编写测试用的搜索例子Search.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package org.hexin;
import java.io.File; 
import java.util.Date;

import org.apache.lucene.codecs.Codec;
import org.apache.lucene.codecs.simpletext.SimpleTextCodec;
import org.apache.lucene.document.Document;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
import org.apache.lucene.index.Term;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.Query;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.search.ScoreDoc;
import org.apache.lucene.search.TopDocs;
import org.apache.lucene.store.FSDirectory;
public class Search {
    private Search() {}
    public static void main(String[] args) throws Exception {

        String index = "e:\\index";
        IndexReader reader = DirectoryReader.open(FSDirectory.open(new File(index)));
        IndexSearcher searcher = new IndexSearcher(reader);
        String queryString = "driver";
        Query query = new TermQuery(new Term("content", queryString));
        System.out.println("Searching for: " + query.toString());
        Date start = new Date();
        TopDocs results = searcher.search(query, null, 100);
        Date end = new Date();
        System.out.println("Time: "+(end.getTime()-start.getTime())+"ms");
        ScoreDoc[] hits = results.scoreDocs;
        int numTotalHits = results.totalHits;
        System.out.println(numTotalHits + " total matching documents");
        for (int i = 0; i < hits.length; i++) {
            String output = "";
            Document doc = searcher.doc(hits[i].doc);
            output += "doc="+hits[i].doc+" score="+hits[i].score;
            String title = doc.get("title");
            if (title != null) {
                output += " " + title;
            }
            System.out.println(output);
        }
        reader.close();
    }
}

在Eclipse中运行Index.java,此时会报错
A SPI class of type org.apache.lucene.codecs.Codec with name ‘Lucene46’ does not exist. You need to add the corresponding
JAR file supporting this SPI to your classpath.The current classpath supports the following names:[]

问过定坤后，知道一个解决的办法是去官网下载已经编译过的Lucene二进制包,将其中的META-INF拷贝到core/src/java目录下，写上下面两行
org.apache.lucene.codecs.simpletext.SimpleTextCodec
org.apache.lucene.codecs.hexin.HexinCodec
此时即可运行通过。查看索引文件，有一个fld结尾的文件，其内容为文本文件,保存着字段值,这个文件就是通过SimpleTextCodec写入的，
而其它文件则是通过Lucene46Codec写入的。

联系作者