最近在学习java,但是对于数据操作那部分还是不熟悉
因此决定找几个简单的算法写,用php和java分别实现
1.两数相加
两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pHead = new ListNode(0),p = pHead;
int carry = 0;
while(l1!=null||l2!=null||carry !=0){
ListNode tmp= new ListNode(0);
tmp.val += carry;
if(l1!=null){
tmp.val+=l1.val;
l1=l1.next;
}
if(l2!=null){
tmp.val+=l2.val;
l2=l2.next;
}
carry = (int)(tmp.val/10);
tmp.val = tmp.val%10;
p.next = tmp;
p = tmp;
}
if(pHead.next==null)return pHead;
return pHead.next;
}
}
php
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution {
/**
* @param ListNode $l1
* @param ListNode $l2
* @return ListNode
*/
function addTwoNumbers($l1, $l2) {
$pHead = new ListNode(0);
$p = $pHead;
$carry = 0;
while($l1!=null||$l2!=null||$carry !=0){
$tmp= new ListNode(0);
$tmp->val += $carry;
if($l1!=null){
$tmp->val+=$l1->val;
$l1=$l1->next;
}
if($l2!=null){
$tmp->val+=$l2->val;
$l2=$l2->next;
}
$carry = floor($tmp->val/10);
$tmp->val = $tmp->val%10;
$p->next = $tmp;
$p = $tmp;
}
if($pHead->next==null)return $pHead;
return $pHead->next;
}
}
2.罗马数字转整数
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
java
class Solution {
public int romanToInt(String s) {
int rs = 0;
char c,pc;
int tmp=0,tmp1=0;
for (int i=0;i c = s.charAt(i); tmp = getNumber(c); if(i==0){ rs = rs+tmp; }else{ pc = s.charAt(i-1); tmp1 = getNumber(pc); if(tmp<=tmp1){ rs = rs+tmp; }else{ rs = rs+(tmp-tmp1-tmp1); } } } return rs; } public int getNumber(char num){ switch(num){ case 'I': return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; } return 0; } } php class Solution { /** * @param String $s * @return Integer */ function romanToInt($s) { $rs = 0; for ($i=0;$i $c = substr($s,$i,1); $tmp = $this->getNumber($c); if($i==0){ $rs = $rs+$tmp; }else{ $pc = substr($s,$i-1,1); $tmp1 = $this->getNumber($pc); if($tmp<=$tmp1){ $rs = $rs+$tmp; }else{ $rs = $rs+($tmp-$tmp1-$tmp1); } } } return $rs; } function getNumber($num){ switch($num){ case "I": return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; } return 0; } } 3.有效的括号 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1: 输入: "()" 输出: true 示例 2: 输入: "()[]{}" 输出: true 示例 3: 输入: "(]" 输出: false 示例 4: 输入: "([)]" 输出: false 示例 5: 输入: "{[]}" 输出: true java class Solution { public boolean isValid(String s) { char[] charArray = s.toCharArray(); Stack for (Character c : charArray) { switch (c) { case '(': case '[': case '{': stack.push(c); break; case ')': if (stack.isEmpty() || '(' != stack.pop()) {return false; } break; case ']': if (stack.isEmpty() || '[' != stack.pop()) {return false; } break; case '}': if (stack.isEmpty() || '{' != stack.pop()) {return false; } break; } } return stack.isEmpty(); } } php class Solution { /** * @param String $s * @return Boolean */ function isValid($s) { $len = strlen($s); $hao = ['(',')','{','}','[',']']; $result = []; $item = ''; for($i=0;$i<$len;$i++){ $t= substr($s,$i,1); if(in_array($t,$hao)){ switch($t){ case '(': case '[': case '{': array_push($result,$t); break; case ')'; if(count($result)==0||array_pop($result) != '(' ){ return false; } break; case ']'; if(count($result)==0||array_pop($result) != '[' ){ return false; } break; case '}'; if(count($result)==0||array_pop($result) != '{' ){ return false; } break; } } } return count($result) == 0; } } 4.最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 ""。 示例 1: 输入: ["flower","flow","flight"] 输出: "fl" 示例 2: 输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明: 所有输入只包含小写字母 a-z 。 java class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length==1){ return strs[0]; } StringBuilder sb = new StringBuilder(); if(strs.length>1){ for(int i=0;i char c = strs[0].charAt(i); for(int j=1;j if(i>=strs[j].length()||strs[j].charAt(i)!=c){ return sb.toString(); } if(j==strs.length-1||strs[j].charAt(i)!=c){ sb.append(c); } } } } return sb.toString(); } } 测试 public class Main { public static void main(String[] args) { Solution ss = new Solution(); String[] xx = new String[]{"flower","flow","flight"}; String yy = ss.longestCommonPrefix(xx); System.out.println("longestCommonPrefix----"+yy); } } php class Solution { /** * @param String[] $strs * @return String */ function longestCommonPrefix($strs) { $rs = []; if(count($strs)==1){ return $strs[0]; } for($i=0;$i $c = substr($strs[0],$i,1); for($j=1;$j if($i>=strlen($strs[$j])||$strs[$j][$i]!=$c){ return implode("",$rs); break; } if($j==count($strs)-1||$strs[$j][$i]!=$c){ array_push($rs,$c); } } } return implode("",$rs); } } 参考阅读
发表评论