RSS
SITEMAP
Articles
-
基于Arrays.binarySearch解决最长递增子序列
1. Arrays.binarySearch的简单介绍 Arrays.binarySearch构造函数的简单介绍 1.1 binarySearch(Object[] arr, Object key) binarySearch(Object[] arr, Object key) arr:要检索的数组 key:要搜索的值 如果key在数组中，则返回索引值的索引；否则返回-1或者”-“(插入点)。插入点是索引键将要插入数组的哪一点，即第一个大于该键的元素的索引。 1.1.1 技巧 [1] 搜索值不是数组元素，且在数组范围内，从1开始计数，得“ - 插入点索引值”； [2] 搜索值是数组元素，从0开始计数，得搜索值的索引值； [3] 搜索值不是数组元素，且大于数组内元素，索引值为 – (length + 1); [4] 搜索值不是数组元素，且小于数组内元素，索引值为 – 1。 1.1.2 代码 int arrays [] =new int[]{1,3,4,5,8,9}; Arrays.sort(arr); int a = Arrays.binarySearch(arrays,6); int b = Arrays.binarySearch(arrays,4); int c = Arrays.binarySearch(arrays,0); int d = Arrays.binarySearch(arrays,10); System.out.println(“a = “+a +”,b = “ +b +”,c = “ + c +”,d = “+d); -
字符串
最经典的就是寻找最长回文子串的问题 解题思想：回文子串的详细思路 在上面的链接中，对该问题做了很详细的思路讲解 下面自己实现采用 Manacher 算法，被中国程序员戏称为“马拉车”算法。它专门用于解决“最长回文子串”问题，时间复杂度为O(N) 。 public int getLongestPalindrome(String A, int n) { // 做字符串的预处理 String str = changeStr(A,'#'); // 定义左跳跃的指针和右跳跃的指针以及最长回文串的返回值 int left=0,right=0,max=0; for(int i = 1;i<str.length();i++) { //判断每一步扩散的步数 right = i + 1; left = i - 1; int count = 0; while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) { count++; left--; right++; } max = max > count ? -
对数组中寄偶数据的处理
类型一：给定一个整形数组，将数组中的数据按奇数排列在前，偶数排列在后 解题思路：定义两个指针，从前后开始遍历数组，遇到前后奇偶位置不匹配的，将其交换位置 public void changeArr(int[] arr) { if (arr == null || arr.length == 0) { return; } int left = 0, right = arr.length - 1; while (left < right) { while ((arr[left] & 1) == 1 && left < right) { left++; } while ((arr[right] & 1) == 0 && left < right) { right--; } if (left < right) { arr[left] ^= arr[right]; arr[right] ^= arr[left]; arr[left] ^= arr[right]; } } } 类型二：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 -
数组
总结与数组有关的算法题： 数组的概念：占据一块连续的内存，并按照顺序存储数组。 算法题： 在一个二维数组中，每一行都按照从左右到右顺序排序，每一列从上到下都按照顺序排序。给定一个数，若存在于数组中则返回true public static Boolean checkNum(int[][] arr,int target){ int row = 0; int column = arr[0].length-1; while (row<arr.length && column >=0){ if (arr[row][column]==target){ return true; } if (arr[row][column]>target){ column--; }else { row++; } } return false; } 1.判断一个数是奇数还是偶数的方法 使用除2取余的方式 如 4%2 判断余数是否为0，是则为偶数，不是则为奇数 将判断的数与1做按位与运算，结果为1则为奇数，为0则为偶数 2.交换两个数字的位置 使用第三变量 如 int tmp = a; a = b;b = tmp; 使用异或运算 如 a ^= b; b ^= a; a ^= b;这样既可将两个数字交换位置 -
最长子序列问题解决思路
对于最长子序列以及最长子串的问题可以看这一下这位博主的博客，介绍比较详细。 最长子串及最长子序列的问题讲解 题目描述如下图所示； 根据动态规划的思想，将问题划分为多个子问题，寻找辅助数组dp 分析关键步骤 这里将辅助数组设为int[][] dp = new int[s1.length+1][s2.length+1];这里对于二维数组来说，多了一行一列； 在辅助数组中填入数据时，保证数组中的值永远是s1与s2响对应的最大值，这里用了原值填充，在代码中填充的字符对于的ASII码；如下图所示 dp数组中填充的值如下图所示 在dp数组想要找到最大子序列，即可以从对角线开始找，因为一个矩阵中最长的直线在对角线； 设计初始程序如下 public String LCS (String s1, String s2) { // write code here if(s1==null || s1.length()==0 || s2==null || s2.length()==0)return "-1"; int s1L = s1.length(); int s2L = s2.length(); int[][] dp = new int[s1L+1][s2L+1]; StringBuilder str = new StringBuilder(); //初始化二维表的元素, for(int i=0;i<s1L+1;i++){ for(int j = 0;j<s2L+1;j++){ //保证二维表的第一个元素为空，或者是0； if (i==0 || j==0){ dp[i][j]=0; continue; } if(s1.
