面试常问的算法题整理

1、 给定一个字符串，逐个翻转字符串中的每个单词

l1 = "This is a good example".split(" ")
print(l1)

l2 = []
new_str = ""
for i in l1:
l2.append(i)
print(l2)

n = 0
while l2:
if n == 0:
new_str += l2.pop()
else:
new_str += " " + l2.pop()
n += 1
print(new_str)

2、 判断数组中所有的数字是否只出现一次

arr = [1, 2, 3, 1]
d1 = {}
status = True
for i in arr:
if not d1.get(i):
d1[i] = 1
status = True
else:
status = False
break

print(status)

3、 无重复字符的最长子串

public static int lengthOfLongestSubstring(String s) {
if (s.equals(" ")){
return 1;
}
// 滑窗
LinkedList linkedList = new LinkedList();
// 最大互异连续子串大小
int size = 0;
char[] chars = s.toCharArray();
for (int i = 0; i 
if (!linkedList.contains(chars[i])){
linkedList.addLast(chars[i]);
size = linkedList.size() > size ? linkedList.size() : size;
}else {
size = linkedList.size() > size ? linkedList.size() : size;
while (linkedList.removeFirst() != chars[i]){}
linkedList.addLast(chars[i]);
}
}
return size;
}

4、反转链表

/**
* @Author Liruilong
* @Description 链表反转
* @Date 16:58 2019/9/2
* @Param [listNode1]
* @return void
**/
public static void linkInt(ListNode listNode1){
// 链表的反转,
// 思路一: 递归反转法,在反转当前节点之前先反转后续节点,从头节点开始
// 思路二:遍历反转法: 从前往后反转各个节点的指针域指向.
}
// 递归反转
public static ListNode Reverse(ListNode listNode){
if ( listNode == null || listNode.next ==null){
        return  listNode;
    }
    ListNode reNode = Reverse(listNode.next);
    listNode.next.next = listNode;
    listNode.next = null;
    return  reNode;
}
// 遍历反转
public  static  ListNode Reverses(ListNode listNode){
   if (listNode == null){
       return listNode;
   }
   // 上一节点
   ListNode prt = listNode;
   // 当前节点
   ListNode cur = listNode.next;
   // 临时节点
   ListNode temp ;
   while (cur != null){
       temp = cur.next;
       cur.next = prt;// 反转指针域的指向
       prt = cur; // 指针往下移动
       cur = temp;
   }
   listNode.next = null;
   return prt;
}

5、给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++){
            for (int j = i + 1; j <nums.length; j++){
                if (nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }

        }
        return  new int[]{};
    }

6、二叉树的最近公共父亲节点

public class Solution {  
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        //发现目标节点则通过返回值标记该子树发现了某个目标结点  
        if(root == null || root == p || root == q) return root;  
        //查看左子树中是否有目标结点，没有为null  
        TreeNode left = lowestCommonAncestor(root.left, p, q);  
        //查看右子树是否有目标节点，没有为null  
        TreeNode right = lowestCommonAncestor(root.right, p, q);  
        //都不为空，说明做右子树都有目标结点，则公共祖先就是本身  
        if(left!=null&&right!=null) return root;  
        //如果发现了目标节点，则继续向上标记为该目标节点  
        return left == null ? right : left;  
    }  
}

7、写一个函数，找出一个整数数组中，第二大的数

function bubbleSort(arr){

　　var len = arr.length;

　　for(var i=0; i<len; i++){ //总共需要比较的轮数

　　　　for(var j=0; j<len-1-i; j++){  //  每一轮需要进行比较的数字

　　　　　　if( arr[j]<arr[j+1]){    // 相邻元素相比，小的移至到右边

　　　　　　　var temp = arr[j+1];

　　　　　　　arr[j+1] = arr[j];

　　　　　　　arr[j] = temp;

　　　　　　}

　　　　}

　　}

      return arr[1];

}

算法题基本在面试时都会遇到，因为他是对我们代码能力的直观体现，可以这样说，如果在面试时算法题写不出来，甚至连大体思路都讲不出来，那面试想通过就比较难了，所以大家需要好好准备，为了节省大家的时间，我帮大家整理好了（看这里 ），拿下offer就看它了！