趣味算法题-1
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了趣味算法题-1，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8936字，纯文字阅读大概需要13分钟。
内容图文
1.MAX（a，b）
不能用比较符号，if,else,问好,冒号输出二者最大值
public static int max(int a, int b) {
System.out.println((a&(b-a>>31)));
System.out.println((b&~((a-b>>31)+1)));
return (a&(b-a>>31))|(b&~((a-b>>31)+1));
}
2.求N的和的个数（顺序不同也可当成不同序列）
题目是输入一个int n,
输出匹配的括号有多少排列种可能。。
有点抽象举个例子
输入3
可能有如下
((()))
(())()
()(())
public class Solution {
public static void main(String[] args){
int n=10;
cucul(10);
}
private static int cucul(int n) {
if(n==0||n==1) return 1;
int tmp = 0;
for(int i=1;i<=n;i++){
tmp += cucul(n-i);
}
return tmp;
}
}
3.最长回文子序列
1.用二维数组table[][]存放是否是回文字串的标记。
2.若i到j是回文字串，则有s[i]==s[j]&&table[i][j] = table[i+1][j-1].
3.字串长度为1：i=j table[i][j] = 1
4.字串长度为2时：s[i] = s[i+1] table[i][i+1] = 1
时间复杂度为：o(n), 空间复杂度：o(n*2)
public static String LongestPalindrome(String s)
{
int length = s.length();
if(s == null || length == 0)
return null;
int[][] table = new int[length][length];
String maxStr = null;
int maxLen = 0;
for(int i = 0; i < length; i++)
table[i][i] = 1;
for(int i = 0; i < length-1; i++)
if(s.charAt(i) == s.charAt(i+1))
{
table[i][i+1] = 1;
maxStr = s.substring(i, i+2);
}
for(int l = 3; l < length; l++)
for(int i = 0; i <= length - l; i++)
{
int j = i + l -1;
if(s.charAt(i) == s.charAt(j))
{
table[i][j] = table[i+1][j-1];
int len = j - i + 1;
if(table[i][j] == 1 && len > maxLen)
{
maxLen = len;
maxStr = s.substring(i, j+1);
}
}
else
{
table[i][j] = 0;
}
}
return maxStr;
}
4.树的非递归遍历
先序和中序类似,后序比较麻烦，要加一个标记该节点遍历的次数。
private void nonRecurInTraverse(BinaryNode root){
2 LinkedList<BinaryNode> stack = new LinkedList<BinaryNode>();
3 BinaryNode currentNode, tmp;
4 currentNode = root;
5
6 while(currentNode != null || !stack.isEmpty())
7 {
8 //先"走完"左孩子
9 while(currentNode != null)
10 {
11 stack.push(currentNode);
12 currentNode = currentNode.left;
13 }
14 //结点没有左孩子了,出栈,访问结点
15 if(!stack.isEmpty())
16 {
17 tmp = stack.pop();
18 System.out.print(tmp.ele + " ");//visit
19 currentNode = tmp.right;
20 }
21 }
22 }
private void postNonRecurTraverse(BinaryNode root){
2 LinkedList<BinaryNode> stack = new LinkedList<MyBinaryTree.BinaryNode>();
3
4 BinaryNode currentNode, tmp;
5 currentNode = root;
6 while(currentNode != null || !stack.isEmpty())
7 {
8 while(currentNode != null)
9 {
10 stack.push(currentNode);
11 currentNode = currentNode.left;
12 }
13 if(!stack.isEmpty())
14 {
15 tmp = stack.getFirst();
16 //从左子树返回,需要判断它的右子树是否已经访问了
17 if(tmp.isFirst == false)//右子树还未被访问
18 {
19 tmp.isFirst = true;
20 currentNode = tmp.right;
21 }
22 else{//左右子树都已经访问了
23 tmp = stack.pop();
24 System.out.print(tmp.ele + " ");//visit
25 // currentNode = null;
26 }
27 }
28 }//while
29 }
5.两个字符串的编辑距离
1.若其中任意一个字符串长度为零则返回另一个字符串的长度。
2.定义二维数组：dp[m+1][n+1]
3.if s1[i-1] = s2[j-1] dp[i][j] = dp[i-1][j-1]
else dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1
public static int distance(String s1, String s2)
{
if(s1.length() == 0)
return s2.length();
if(s2.length() == 0)
return s1.length();
int len1 = s1.length();
int len2 = s2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i = 0; i <= len1; i++)
for(int j = 0; j <= len2; j++)
{
if(i == 0)
{
dp[i][j] = j;
continue;
}
if(j == 0)
{
dp[i][j] = i;
continue;
}
dp[i][j] = (s1.charAt(i-1) == s2.charAt(j-1) ? dp[i-1][j-1] : Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1);
}
return dp[len1][len2];
}
6.实现atoi转换
1.考虑是空白的时候情况。
2.考虑正负，考虑大于最大整数或小于最小整数。
public static int myAtoi(String str) {
// 合法性判断
if (str.isEmpty()) return 0;
// 正负号标记
int sign = 1;
// 转换值
int base = 0;
// 索引位数
int i = 0;
// 剔除开始空白字符
while (str.charAt(i) == ' ')
i++;
// 判断正负号
if (str.charAt(i) == '-' || str.charAt(i) == '+')
sign = str.charAt(i++) == '-' ? -1 : 1;
// 索引有效数字字符
while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
// that statement is used to test if the num is bigger than INT_MAX after the str[i] is handled, if base > INT_MAX/10,
// then base10+ str[i] -‘0’> base10>INT_MAX, or when base== INT_MAX/10, that means all the places are the same as INT_MAX except the ones place, so str[i]>‘7’ is needed.
// 上面这段是LeetCode国外站对下面代码的解释。
// 简单来说就是
// 如果`base > MAX_VALUE/10`，那么`base*10 + new_value` > `base*10` > `MAX_VALUE`。这个应该很容易理解，这种情况下就会发生溢出。
// 若`base == INT_MAX/10`，而且`new_value = str.charAt(i++) - '0'`大于`7`，也会发生溢出。因为`MAX_VALUE = 2147483647`
if (base > Integer.MAX_VALUE / 10 || (base == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)) {
return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
// 计算转换值
base = 10 * base + (str.charAt(i++) - '0');
}
7.最大乘积子数组
1.记录下最大最小的情况。
public static int maxProductSubarray(int[] arr)
{
if(arr == null || arr.length == 0)
return 0;
int maxData = arr[0];
int minData = arr[0];
int res = arr[0];
for(int i = 1; i < arr.length; i++)
{
int temp = maxData;
maxData = Math.max(Math.max(maxData*arr[i], minData*arr[i]), arr[i]);
minData = Math.min(Math.min(temp*arr[i], minData*arr[i]), arr[i]);
if(res < maxData)
res = maxData;
}
return res;
}
8.最近的公共祖先。
1.就是离两个节点最近的祖先节点。
public static TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q)
{
if(root == p && root == q)
return root;
if((isHasNode(root.left, p) && isHasNode(root.right, q)) || (isHasNode(root.left, q) && isHasNode(root.right, p)))
return root;
if(isHasNode(root.left, p) && isHasNode(root.left, q))
return findLCA(root.left, p, q);
if(isHasNode(root.right, p) && isHasNode(root.right, q))
return findLCA(root.right, p, q);
return null;
}
public static boolean isHasNode(TreeNode root, TreeNode tr)
{
if(root == tr)
return true;
if(root == null)
return false;
return isHasNode(root.left, tr) || isHasNode(root.right, tr);
}
9.堆排序
1.建堆，输出一个后再调整
public static void BuildHeap(int[] arr)
{
for(int i = arr.length/2-1; i >= 0; i--)
maxify(arr, i, arr.length-1);
// for(int i = 0; i < arr.length-1; i++)
// System.out.println(arr[i]);
}
public static void HeapSort(int[] arr)
{
int len = arr.length-1;
for(int i = 0; i <= arr.length-1; i++)
{
int temp = arr[0];
arr[0] = arr[len];
arr[len] = temp;
len--;
System.out.println(temp);
maxify(arr, 0, len);
}
}
public static void maxify(int[] arr, int i , int j)
{
if(i == j)
return;
int l = 2*i + 1;
int r = 2*i + 2;
int largest = i;
if(l <= j && arr[l] > arr[largest])
largest = l;
if(r <= j && arr[r] > arr[largest])
largest = r;
if(largest == i || largest > j)
return;
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
maxify(arr, largest, j);
}
10.给一个字符串，大小写字母和数字和空格，空格不会连续，要求去掉字母和字母或者数字和数字间的空格，所有字母变为小写
public static String filterBlank(String str)
{
if(str == null)
return str;
int count = 0;
for(int i = 0; i < str.length(); i++)
{
if(isTrue(str, i) == true)
count++;
}
char[] s = new char[str.length()-count];
StringBuilder sb = new StringBuilder();
int k = 0;
for(int i = 0; i < str.length(); i++)
{
if(str.charAt(i) >= 'A' && str.charAt(i) <= 'Z')
sb.append((char) ('a'+ (str.charAt(i)-'A')));
else if(isTrue(str, i) == true)
{
continue;
}
else
sb.append(str.charAt(i));
}
return sb.toString();
}
public static boolean isTrue(String str, int i)
{
if(i == 0 || i == str.length() - 1)
return false;
if(str.charAt(i) == ' ')
{
if(str.charAt(i-1) >= '0' && str.charAt(i+1) >= '0' && str.charAt(i-1) <= '9' && str.charAt(i+1) <= '9')
return true;
if((str.charAt(i-1) >= 'a' || str.charAt(i-1) >= 'A') && (str.charAt(i-1) <= 'z' || str.charAt(i-1) <= 'z') && (str.charAt(i+1) >= 'a' || str.charAt(i+1) >= 'A') && (str.charAt(i+1) <= 'z' || str.charAt(i+1) <= 'z'))
return true;
}
return false;
}
11.最长重复子序列
1.找出字符串后缀
2.对后缀进行排序(Arrays.sort())
3.相邻数组肩比较
public static int compare(String s1, String s2)
{
if(s1.length() == 0 || s2.length() == 0)
return 0;
int i = 0;
while(i < s1.length() && i < s2.length() && s1.charAt(i) == s2.charAt(i))
i++;
return i;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "dfsddefsdde";
String[] ss = new String[s.length()];
for(int i = 0; i < s.length(); i++)
ss[i] = s.substring(i);
Arrays.sort(ss);
int maxLen = 0;
int maxi = 0;
for(int i = 1; i < ss.length; i++)
{
int temp = compare(ss[i-1], ss[i]);
if(temp > maxLen)
{
maxLen = temp;
maxi = i;
}
}
System.out.println(ss[maxi].substring(0, maxLen));
}
内容总结
以上是互联网集市为您收集整理的趣味算法题-1全部内容，希望文章能够帮你解决趣味算法题-1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】