编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[]
的形式给出。
不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1:
输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for (int i : nums1) {
set1.add(i);
}
for (int i : nums2) {
set2.add(i);
}
Set<Integer> ans = new HashSet<Integer>();
if (set1.size() >= set2.size()) {
for (int i : set2) {
if (set1.contains(i)) {
ans.add(i);
}
}
}
else {
for (int i : set1) {
if (set2.contains(i)) {
ans.add(i);
}
}
}
int index = 0;
int[] finalAns = new int[ans.size()];
for (int i : ans) {
finalAns[index++] = i;
}
return finalAns;
}
}
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int p1 = 0;
int p2 = 0;
int p = 0;
int[] ans = new int[Math.min(nums1.length, nums2.length)];
while (p1 < nums1.length && p2 < nums2.length) {
if (nums1[p1] == nums2[p2]) {
ans[p] = nums1[p1];
p++;
p1++;
p2++;
}
else if (nums1[p1] < nums2[p2]) {
p1++;
}
else if(nums1[p1] > nums2[p2]) {
p2++;
}
}
return Arrays.copyOfRange(ans, 0, p);
}
}
给定一个 正整数 num
,编写一个函数,如果 num
是一个完全平方数,则返回 true
,否则返回 false
。
进阶:不要 使用任何内置的库函数,如 sqrt
。
示例 1:
输入:num = 16
输出:true
class Solution {
public boolean isPerfectSquare(int num) {
if (num == 1) {
return true;
}
long left = 0;
long right = num /2;
long mid;
long mul;
while (left <= right) {
mid = left + (right - left) / 2;
mul = mid * mid;
if (num == mul) {
return true;
}
else if (mul < num) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return false;
}
}
给定一个二叉树的根节点 root
,返回它的 中序 遍历。
输入:root = [1,null,2,3]
输出:[1,3,2]
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<Integer>();
inorder(root, ans);
return ans;
}
public void inorder(TreeNode root, List<Integer> ans) {
if (root == null) {
return;
}
inorder(root.left, ans);
ans.add(root.val);
inorder(root.right, ans);
}
}
一般会考这个
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk = new LinkedList<>();
while (root != null || !stk.isEmpty()) {
while (root != null) {
stk.push(root);
root = root.left;
}
root = stk.pop();
ans.add(root.val);
root = root.right;
}
return ans;
}
}