给定一个N×N的二维矩阵表示图像,90度顺时针旋转图像。

给定一个N×N的二维矩阵表示图像,90度顺时针旋转图像。

样例

给出一个矩形[[1,2],[3,4]],90度顺时针旋转后,返回[[3,1],[4,2]]

原理就是:

  • 先上下翻, 以X轴对称
  • 再调换坐标
public class Solution {
    /**
     * @param matrix: a lists of integers
     * @return: nothing
     */
    public void rotate(int[][] matrix) {
        // write your code here

        int l = matrix.length;
        for (int i = 0; i < l / 2; i++) {
            for (int j = i; j < l - 1 - i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[l - 1 - j][i];
                matrix[l - 1 - j][i] = matrix[l - 1 - i][l - 1 - j];
                matrix[l - 1 - i][l - 1 - j] = matrix[j][l - 1 - i];
                matrix[j][l - 1 - i] = tmp;

            }
        }
        
        for (int[] _n : matrix) {
            System.out.print("[");
            for (int x : _n) {
                System.out.print(x + ",");
            }
            System.out.print("]\n");
        }


    }
}

 

 

快排算法的实现与讲解(java/C++)

快排的算法其实不复杂,但是很少时候,偶尔整的自己头晕,所以写一篇博客,以免以后忘记。

假设我们的数组为:{5,2,1,8,9,3,7,0,4,6},一共10个数字,现在需要将这个数组进行排序。首先我们需要找一个基准数,其实就是参照物,得有个东西跟你对比吧?不然怎么可以呈现出你的美?

假设左边为i=0; 右边j = 9;

方法很简单,分别从数组的左右边两段进行“探测”。首先是左边移动,最左边的第一个数字是5,而最右边的数字是6。

6 >= 5 条件成立,接着左边往右边移动一位(j–)

……

4>=5条件不成立,这个时候就换一下位置,4跟5换。现在的数组应该就是这样子:{4,2,1,8,9,3,7,0,5,6}

接着轮到右边探测,左边的数字已经被替换为4,而右边的是5(因为j自减了一次);那么现在条件对比:

5>=4条件成立,右边往左边靠拢(i++)

5>=2条件成立,右边往左边靠拢(i++)

……

5>=8条件不成立,换位置:{4,2,1,5,9,3,7,0,8,6}

到此,第一轮交换结束。接下来j继续向左挪动(再友情提醒,每次必须是j先出发)。他发现了0(比基准数5要小,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下:

{4,2,1,0,9,3,7,5,8,6}

第二次交换结束,“探测”继续。接着轮到i继续向右挪动,他发现了9(比基准数5要大,满足要求)之后又停了下来。交换之后的序列如下:

{4,2,1,0,5,3,7,9,8,6}

….以此类推,哨兵i继续向右移动,悲剧!!!此时i和j撞上了,说明此时“探测”结束。我们将基准数5和3进行交换。交换之后的序列如下:

{4,2,1,0,3,5,7,9,8,6}

到此“探测”真正结束。此时以基准数5为分界点,5左边的数都小于等于5,5右边的数都大于等于5。

回顾一下刚才的过程,其实j的使命就是要找小于基准数(5)的数,而哨兵i的使命就是要找大于基准数(5)的数,直到i和j撞在一起为止为止。

那么现在数据可以区分为两组:

{4,2,1,0,3,        5       ,7,9,8,6}

左边:4  2  1  0  3

右边:7  9  8  6

数组被分为了两组,然后按照直接的方法进行对比,只是开始i=0;j=9,要变为(先从左边开始):

指针位置:i=0; j=4

数组:4  2  1  0  3

还是上一张图吧,比较好理解:

wKiom1MUSRPjUTOIAAC-kWvhNhc591

注:图片是网上找的,数组的排序跟我的不一致,但是看的明白。

最后:

  • 快排的原理很简单;
  • 就是把数组分为两节;
  • 左边的是最小的,而右边的是最大的;
  • 然后再拿左、右边的来继续递归,递归的原理也一样,也是拆分为两节,以此类推。

上代码吧,我写了java跟c的代码:

2.java代码:

public static void main(String[] args) {
    int[] arr = {5,2,1,8,9,3,7,0,4,6};
    sort(arr, 0, arr.length - 1);
    for (int i : arr) {
        System.out.print(i + " ");
    }
}

private static void sort(int[] arr, int l, int r) {
    int i = l;
    int j = r;
    if (l < r) {
        while (l < r) {
            while (l < r && arr[r] >= arr[l]) {
                r--;
            }
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

            while (l < r && arr[l] <= arr[r]) {
                l++;
            }
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

        }
        sort(arr, i, l - 1);//递归左边,此时l=5
        sort(arr, l + 1, j);//递归右边,此时l=5
    }
}

 

2.那么c++的代码会是怎么样呢?

#include "pch.h"
#include <iostream>

using namespace std;

void sortQ(int *arr, int l, int r) {
   int i = l;
   int j = r;
   int tmp;
   if (i < j) {
      while (l < r) {
         while (l < r && arr[r] >= arr[l])
         {
            r--;
         }

         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;

         while (l < r && arr[r] >= arr[l]) {
            l++;
         }
         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;
      }

      sortQ(arr, i, l - 1);//处理左边,此时l=5
      sortQ(arr, l + 1, j);//处理右边,此时l=5
   }

}

int main()
{
    std::cout << "Hello World!\n"; 

   int arr[] = {5,2,1,8,9,3,7,0,4,6};
   int size = sizeof(arr) / sizeof(arr[0]);

   sortQ(arr, 0, size - 1);
   for (int i : arr) {
      cout << i << " ";
   }

}

 

 

 

Java开发XML解析器Document、SAXParser、XMLStreamReader详解

1.Document

接口对象是官方出的,W3C标准,作为HTML、XML实体类加载到内存中,形成文档对象,然后使用循环进行数据解析。

2.SAXParser

SAXParser是一个用于处理XML的事件驱动的“推”模型。它不是W3C标准,但它是一个得到了广泛认可的API,大多数SAXParser解析器在实现的时候都遵循标准。

SAXParser解析器不象DOM那样建立一个整个文档的树型表示,而是使用数据流的方式读取,然后根据读取文档的元素类型进行事件反馈。这些事件将会推给事件处理器,而事件处理器则提供对文档内容的访问数据包装等。

事件处理器有三种基本类型:

用于访问XML DTD内容的DTDHandler;
用于低级访问解析错误的ErrorHandler;
用于访问文档内容的最普遍类型ContentHandler。
3.XMLStreamReader(StAX)

XMLStreamReader也属于数据留解析的一种,读入文件,按线性的方式从文件头一直读到文件尾;和SAXParser一样,使用事件驱动的模型来反馈事件。不同的是,XMLStreamReader不使用SAXParser的推模型,而是使用 “拉”模型进行事件处理。而且XMLStreamReader解析器不使用回调机制,而是根据应用程序的要求返回事件。XMLStreamReader还提供了用户友好的API用于读入和写出。

尽管SAXParser向ContentHandler返回不同类型的事件,但XMLStreamReader却将它的事件返回给应用程序,甚至可以以对象的形式提供事件。

当应用程序要求一个事件时,XMLStreamReader解析器根据需要从XML文档读取并将该事件返回给该应用程序。 XMLStreamReader提供了用于创建XMLStreamReader读写器的工具,所以应用程序可以使用StAX接口而无需参考特定实现的细节。

与Document和SAXParser不同,XMLStreamReader指定了两个解析模型:指针模型,如SAXParser,它简单地返回事件;迭代程序模型,它以对象形式返回事件(这里需要吐槽一下,我个人是比较喜欢SAXParser的handler事件处理的模式,代码方面比较值观),其实XMLStreamReader也可以跟SAXParser一样,但是需要额外的对象创建开销。

FileChannel文件通道

FileChannel

FileChannel 可以通过 RandomAccessFile、FileInputStream、FileOutStream也可以通过FileChannel.open 获取。

其中方法write 和 read 都是通过 ByteBuffer 对象进行操作(读写)。

 

如果使用FileChannel.open打开文件通道时可以提供 OpenOption 来定义行为,如果需要写的话可以使用 write 和 append 模式,在不确定文件是否存在是加入 Create,这样如果不存在会自动创建。

write 和 append 有什么区别?

这两种模式声明的不是 FileChannel 的模式,而是声明那个文件的打开模式,作为 FileChannel 只顾自己position 增加,在 write 模式下文件的 postion 跟 Channel 的 position 是一致的,但是在 append 模式下文件 position 跟 Channel 的完全脱节,两者都是自顾自增加。

说到这里你可能已经想到,如果要实现每次输入内容覆盖之前的话,必须选择 Write 模式,并且每次 channel.write 前都需要将channel的 position 置为零。

文件锁 Lock

FileChannel.lock tryLock 从文档上看一个是同步阻塞、另一个是非阻塞。

tryLock 在同一个JVM中不同线程获取时,先到先得,后到的返回null,但我在windows上测试为抛出异常:OverlappingFileLockException ,据说 Linux 上抛出【java.io.IOException:Permission denied】。

tryLock 和 lock 都提供一个API含有三个参数

lock(long position,
long size,
boolean shared)

看样子貌似可以锁住部分似的,可能跟操作系统有关,反正windows上并不行,抛出异常:java.io.IOException: 另一个程序已锁定文件的一部分,进程无法访问。

共享锁,独占锁概念上跟并发的 WriteReadLock 一样可多读但只一写,写是独占的。

怎么设置?看上面API第三个参数。

lock(long position,
long size,
boolean shared) // 是否共享锁

如何判断获取到的是什么锁?

FileLock.isShared()
实现靠谱的文件锁

主要就是一个循环判断加try.catch

while (true) {
try {
lock = fc.lock();
break;
} catch (OverlappingFileLockException e) {
Thread.sleep(1 * 1000);
}
}

这可以让需要获取锁的代码块阻塞在那里,当然咯,如果想 wait 也是可以的,只是要在 release 的地方加上 notifyAll 了。

内存映射文件

这个可谓 “大杀器”,特别是大文件读写时,效率比普通IO要快N倍。据一位网友测试86M的文件进行读操作,内存映射方式只要78ms,而普通IO需要468ms,差了6倍。可见威力无穷。
为什么这么快?

普通IO是操作系统先读入到内核缓冲器,再转到用户进程私有的内存区,当然JVM进程还作了内核态和用户态的切换;而内存映射方式,是将文件直接映射到内存中的一块区域,当调用读时会抛出缺页异常,OS会读取该页数据,依次往复,因此这里少了依次内核缓冲区到私有内存之间的拷贝,所以快了不少。
内存映射模式:

read_only只读设置 ;

read_write读写都可,并且任何写操作立即反应在文件上,其他共享该文件的内存映射也能立即看到 。

private私有模式,不写时跟read_only 一样,但是写时会克隆一个独立内存区域,不会影响文件。

代码片段:

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Path;
import java.nio.file.Paths;

/**
 * Created by alan on 2018/12/15.
 */
public class FileChannelDemo extends OutPut {

    public static void main(String[] args) {
        String path = "d:/1.txt";
        w(path);
        try {
            Path paths = Paths.get(path);
//            FileChannel channel = FileChannel.open(paths);//HEX{01 02 03 04}
            FileInputStream in = new FileInputStream(path);
            FileChannel channel = in.getChannel();
            MappedByteBuffer buffer = channel.map(FileChannel.MapMode.READ_ONLY, 0, channel.size());

            String str = "";
            for (int i = 0; i < channel.size(); i++) {
                str += buffer.get() + " ";
            }
            out(str);

            buffer.flip();
            channel.close();
            in.close();


        } catch (IOException e) {
            e.printStackTrace();
        }

    }

    public static void w(String path) {
        try {

            FileOutputStream out = new FileOutputStream(path);
            FileChannel channel = out.getChannel();
            ByteBuffer buffer = ByteBuffer.allocate(20);

            buffer.put((byte) 0x1B);
            buffer.put((byte) 0x2B);
            buffer.put((byte) 0x3B);
            buffer.put((byte) 0x4B);
            buffer.put((byte) 0x5B);
            buffer.put((byte) 0xFB);
            buffer.put((byte) 0xEB);

            buffer.flip();

            channel.write(buffer,0);
            channel.close();

            out.flush();
            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}
 
Copyright © 2008-2021 lanxinbase.com Rights Reserved. | 粤ICP备14086738号-3 |